Важная информация

User Tag List

Страница 1 из 4 1234 ПоследняяПоследняя
Показано с 1 по 10 из 33

Тема: Исключить повторы из массива

  1. #1
    Veteran Аватар для drbars
    Регистрация
    01.03.2005
    Адрес
    Новосибирск
    Сообщений
    1,529
    Благодарностей: 654
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию Исключить повторы из массива

    Вот думаю, как лучше организовать такое:

    Есть массив 8 байт, в нём могут быть значения от 1 до 255, в любой последовательности. Требуется в цикле считать данные из массива без повторов. Результат каждого уникального числа массива в регистр А и флаг для перехода EXX:CALL Z,xxxx:EXX
    Кол-во переходов равно кол-ву уникальных чисел массива.

    Например в массиве: 1,1,2,3,3,3,6,8.
    Результат: 1,2,3,6,8
    Последний раз редактировалось drbars; 12.08.2013 в 10:38.
    ZX Spectrum +2 / DataGear / DivIDE 2k14
    ZX Evolution rev.C
    ZX Spectrum NEXT

  2. #1
    С любовью к вам, Yandex.Direct
    Размещение рекламы на форуме способствует его дальнейшему развитию

  3. #2
    Veteran
    Регистрация
    29.12.2010
    Адрес
    Москва
    Сообщений
    1,497
    Благодарностей: 668
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    А чё-то в примере не любая последовательность, а возрастающая. Так что, пока не понятно с заданием, чего надо.
    Формально всё правильно, а по существу - издевательство (В.И.Ленин)

  4. #3
    Veteran Аватар для drbars
    Регистрация
    01.03.2005
    Адрес
    Новосибирск
    Сообщений
    1,529
    Благодарностей: 654
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от Andrew771 Посмотреть сообщение
    А чё-то в примере не любая последовательность, а возрастающая. Так что, пока не понятно с заданием, чего надо.
    Это я для примера:

    вот так: 3,10,1,1,10,7,15,15
    результат: 3,10,1,7,15

    повторы могут идти не подряд.

    пока вижу тут команду CPIR

    ---------- Post added at 15:51 ---------- Previous post was at 15:41 ----------

    Идея алгорима наверное такая:

    Первый байт у нас уникальный, читаем делаем переход.
    Читаем второй байт, сравниваем с первым. нет совпадений? переход.
    Читаем третьий байт, сравнимаем с первым и вторым. нет совпадений, переход.
    итд..

    При совпадении переход к следующему байту массива.
    Последний раз редактировалось drbars; 12.08.2013 в 10:47.
    ZX Spectrum +2 / DataGear / DivIDE 2k14
    ZX Evolution rev.C
    ZX Spectrum NEXT

  5. #4
    Guru Аватар для null_device
    Регистрация
    26.09.2009
    Адрес
    г. Красноярск
    Сообщений
    2,679
    Благодарностей: 2035
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    drbars, Вариантов несколько:
    1 (быстрый, но требующий больше памяти). Завести два массива, размерность которого определяется максимально возможным числом. Далее, организуем цикл: извлекаем из первого массива (со "случайными" числами) первый элемент и значение из второго массива, "номер" которого является величина числа из первого массива. Если "флаг" наличия во втором массиве не установлен, устанавливаем его и переходим к следующему элементу первого массива. В противном случае "сдвигаем" все значения первого массива вниз на одну ячейку и уменьшаем "верхнее" значение счетчика цикла. После чего, повторяем проверку той же ячейки еще раз.

    2 (медленный, не требующий второго массива). Организуем цикл. Извлекаем значение ячейки массива соответствующее параметру цикла. Сравниваем его со всеми числами от первой ячейки до текущей. Если они равны, смещаем элементы массива "вниз" на одну ячейку. Уменшаем верхний предел цикла. Повторяем сравнение.
    Когда есть, но не знаеш где - это все равно, что нету.

  6. #5
    Veteran Аватар для drbars
    Регистрация
    01.03.2005
    Адрес
    Новосибирск
    Сообщений
    1,529
    Благодарностей: 654
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от null_device Посмотреть сообщение
    drbars, Вариантов несколько:
    1 (быстрый, но требующий больше памяти). Завести два массива, размерность которого определяется максимально возможным числом. Далее, организуем цикл: извлекаем из первого массива (со "случайными" числами) первый элемент и значение из второго массива, "номер" которого является величина числа из первого массива. Если "флаг" наличия во втором массиве не установлен, устанавливаем его и переходим к следующему элементу первого массива. В противном случае "сдвигаем" все значения первого массива вниз на одну ячейку и уменьшаем "верхнее" значение счетчика цикла. После чего, повторяем проверку той же ячейки еще раз.

    2 (медленный, не требующий второго массива). Организуем цикл. Извлекаем значение ячейки массива соответствующее параметру цикла. Сравниваем его со всеми числами от первой ячейки до текущей. Если они равны, смещаем элементы массива "вниз" на одну ячейку. Уменшаем верхний предел цикла. Повторяем сравнение.
    Первый вариант быстрее, но требует памяти 256 байт. Во втором случае чуть медленее будет. Кстати если попадается ноль, сразу переход на следующий байт массива без проверки.

    Но задачка в том, как изящно сделать этот второй вариант чтобы не дёргать стек.

    ---------- Post added at 16:28 ---------- Previous post was at 15:59 ----------

    Может так? Как бы оптимизировать?)

    Код:
    ARRAY	DB 1,3,9,7,5,9,4,3
    
    TEST:	DI
    	LD SP,#BFFF
    
    	LD B,#08
    	LD A,#01
    	LD (CNT2+1),A
    	LD DE,ARRAY+1
    LOOP	LD A,(DE)
    	EXX
    	LD HL,ARRAY
    CNT2	LD BC,01
    	CPIR
    	EXX
    	CALL NZ,RESULT
    	INC DE	
    	LD HL,CNT2+1
    	INC (HL)
    	DJNZ LOOP
    
    	JR $
    
    RESULT	OUT (#FE),A
    	RET
    Последний раз редактировалось drbars; 12.08.2013 в 11:48.
    ZX Spectrum +2 / DataGear / DivIDE 2k14
    ZX Evolution rev.C
    ZX Spectrum NEXT

  7. #6
    ZEK
    Гость

    По умолчанию

    Быстрый алгоритм можно опитимизировать по памяти, вместо 256 байт таблички, можно 32мя обойтись, кажому числу по биту, пробегаемся ставим биты, потом набигаем на битовый массив и из него получаем результат, а что бы не париться с сдвигами можно сделать самомодифицирующийся код, который инструкцию bit будет патчить
    Последний раз редактировалось ZEK; 12.08.2013 в 11:39.

  8. #7
    Veteran Аватар для drbars
    Регистрация
    01.03.2005
    Адрес
    Новосибирск
    Сообщений
    1,529
    Благодарностей: 654
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    Цитата Сообщение от ZEK Посмотреть сообщение
    Быстрый алгоритм можно опитимизировать по памяти, вместо 256 байт таблички, можно 32мя обойтись, кажому числу по биту, пробегаемся ставим биты, потом набигаем на битовый массив и из него получаем результат, а что бы не париться с сдвигами можно сделать самомодифицирующийся код, который инструкцию bit будет патчить
    Интересная идея Интересно, насколько оно быстрее будет.
    Последний раз редактировалось drbars; 12.08.2013 в 11:47.
    ZX Spectrum +2 / DataGear / DivIDE 2k14
    ZX Evolution rev.C
    ZX Spectrum NEXT

  9. #8
    ZEK
    Гость

    По умолчанию

    Причем по скорости можно тож немного оптимизировать если байт с битами который надо смотреть на текущей итерации =0 то сразу в счетчик байта результат +8 делать и переходить к следующему байту, из 32байт максимум 8 байт будет обработано (при исходном массиве 8 чисел)
    Последний раз редактировалось ZEK; 12.08.2013 в 11:49.

  10. #9
    Guru
    Регистрация
    25.01.2005
    Адрес
    Miass, Chelyabinsk region
    Сообщений
    4,083
    Благодарностей: 924
    Mentioned
    0 Post(s)
    Tagged
    0 Thread(s)

    По умолчанию

    главное чтобы ваши оптимизации не были больше 256 байт... 8 чисел можно и отсортировать быстренько, а потом просто проверять, равен текущий предыдущему или нет.

    патчить команды на ходу хорошо только в демах или интрах. а так это зло.

  11. #10
    ZEK
    Гость

    По умолчанию

    патчить погорячился, rrca + jr c шустрее будет даже

Страница 1 из 4 1234 ПоследняяПоследняя

Информация о теме

Пользователи, просматривающие эту тему

Эту тему просматривают: 1 (пользователей: 0 , гостей: 1)

Похожие темы

  1. Ответов: 454
    Последнее: 04.01.2017, 00:50

Ваши права

  • Вы не можете создавать новые темы
  • Вы не можете отвечать в темах
  • Вы не можете прикреплять вложения
  • Вы не можете редактировать свои сообщения
  •