Просмотр полной версии : Исключить повторы из массива
Вот думаю, как лучше организовать такое:
Есть массив 8 байт, в нём могут быть значения от 1 до 255, в любой последовательности. Требуется в цикле считать данные из массива без повторов. Результат каждого уникального числа массива в регистр А и флаг для перехода EXX:CALL Z,xxxx:EXX
Кол-во переходов равно кол-ву уникальных чисел массива.
Например в массиве: 1,1,2,3,3,3,6,8.
Результат: 1,2,3,6,8
Andrew771
12.08.2013, 12:38
А чё-то в примере не любая последовательность, а возрастающая. Так что, пока не понятно с заданием, чего надо.
А чё-то в примере не любая последовательность, а возрастающая. Так что, пока не понятно с заданием, чего надо.
Это я для примера:
вот так: 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 ----------
Идея алгорима наверное такая:
Первый байт у нас уникальный, читаем делаем переход.
Читаем второй байт, сравниваем с первым. нет совпадений? переход.
Читаем третьий байт, сравнимаем с первым и вторым. нет совпадений, переход.
итд..
При совпадении переход к следующему байту массива.
null_device
12.08.2013, 12:56
drbars, Вариантов несколько:
1 (быстрый, но требующий больше памяти). Завести два массива, размерность которого определяется максимально возможным числом. Далее, организуем цикл: извлекаем из первого массива (со "случайными" числами) первый элемент и значение из второго массива, "номер" которого является величина числа из первого массива. Если "флаг" наличия во втором массиве не установлен, устанавливаем его и переходим к следующему элементу первого массива. В противном случае "сдвигаем" все значения первого массива вниз на одну ячейку и уменьшаем "верхнее" значение счетчика цикла. После чего, повторяем проверку той же ячейки еще раз.
2 (медленный, не требующий второго массива). Организуем цикл. Извлекаем значение ячейки массива соответствующее параметру цикла. Сравниваем его со всеми числами от первой ячейки до текущей. Если они равны, смещаем элементы массива "вниз" на одну ячейку. Уменшаем верхний предел цикла. Повторяем сравнение.
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
Быстрый алгоритм можно опитимизировать по памяти, вместо 256 байт таблички, можно 32мя обойтись, кажому числу по биту, пробегаемся ставим биты, потом набигаем на битовый массив и из него получаем результат, а что бы не париться с сдвигами можно сделать самомодифицирующийся код, который инструкцию bit будет патчить
Быстрый алгоритм можно опитимизировать по памяти, вместо 256 байт таблички, можно 32мя обойтись, кажому числу по биту, пробегаемся ставим биты, потом набигаем на битовый массив и из него получаем результат, а что бы не париться с сдвигами можно сделать самомодифицирующийся код, который инструкцию bit будет патчить
Интересная идея :) Интересно, насколько оно быстрее будет.
Причем по скорости можно тож немного оптимизировать если байт с битами который надо смотреть на текущей итерации =0 то сразу в счетчик байта результат +8 делать и переходить к следующему байту, из 32байт максимум 8 байт будет обработано (при исходном массиве 8 чисел)
главное чтобы ваши оптимизации не были больше 256 байт... 8 чисел можно и отсортировать быстренько, а потом просто проверять, равен текущий предыдущему или нет.
патчить команды на ходу хорошо только в демах или интрах. а так это зло.
патчить погорячился, rrca + jr c шустрее будет даже
главное чтобы ваши оптимизации не были больше 256 байт... 8 чисел можно и отсортировать быстренько, а потом просто проверять, равен текущий предыдущему или нет.
патчить команды на ходу хорошо только в демах или интрах. а так это зло.
У меня это в реалтайме всё будет работать, поэтому скорость важна.
Сортировать мне не нужно, т.к. пересечений нет... нет смысла думать о порядке. Значений всего 255.
С битовым способом можно всё по OR быстро сложить, дубли объединятся.
На этапе обработки массива тока быстро вычислить нужно будет.
Примеры? :)
а запись в табличку через set bit, (IX+offs) все таки быстрее будет патчем, в bit младшие 3 бита найденного числа, в offs старшие 5 бит, шустрее будет
а запись в табличку через set bit, (IX+offs) все таки быстрее будет патчем, в bit младшие 3 бита найденного числа, в offs старшие 5 бит, шустрее будет
LD A,#08
LD IX,ARRAY
LD B,A
AND %00000111
RLCA
RLCA
RLCA
OR #C6
LD (PATCH+3),A
LD A,B
AND %11111000
RRCA
RRCA
RRCA
LD (PATCH+2),A
PATCH SET 0,(IX+0)
---------- Post added at 17:44 ---------- Previous post was at 17:32 ----------
Что-то не уверен в быстроте, два деления делать 8 раз!
drbars, а чего вообще то нужно сделать?
уточни условия
просто убрать последовательные повторения или надо убрать любые повторения?
Что-то не уверен в быстроте
тут 2 момента, алгоритм состоит еще из чтения, и этот кусок примерно раза в два шустрее сделать можно
drbars, а чего вообще то нужно сделать?
уточни условия
просто убрать последовательные повторения или надо убрать любые повторения?
любые повторения:) пример я выше сделал, но тормозной)
любые повторения:) пример я выше сделал, но тормозной)
не сильно тормозной
;на входе данные в массиве 1
;на выходе - HL массив; BC длинна
ld bc,1
ld de,array1
ld a,(de)
inc de
exx
ld hl,array2
ld (hl),a
ld bc,1
exx
loop0
push bc
ld a,(de)
ld hl,array1
cpir
pop bc
jr z,loop1
exx
ld (hl),a
inc bc
exx
loop1
inc de
inc bc
ld a,c
cp 8
jr nz,loop0
exx
ret
array1 db 1,2,1,3,1,4,1,5
array2 db 0,0,0,0,0,0,0,0
не сильно тормозной
Фишка в том, что процедура вызываемая из цикла запарывает все регистры :) даже альтернативные :)
Можно использовать SP и IX,IY
ну или вот если стек не хочешь дергать
;на выходе
;HL- массив
;ВС- длинна массива
ld de,array1
ld bc,1
ld a,(de)
inc de
exx
ld hl,array2
ld bc,1
ld (hl),a
exx
loop0
ld b,c
ld a,(de)
ld hl,array1
loop2
cp (hl)
inc hl
jr z,loop1
djnz loop2
exx
ld (hl),a
inc bc
exx
loop1
inc de
inc c
ld a,c
cp 8
jr nz,loop0
exx
ret
array1 db 1,2,1,3,1,4,1,5
array2 db 0,0,0,0,0,0,0,0
---------- Post added at 16:23 ---------- Previous post was at 16:23 ----------
из какого цикла?
вопрос, а в каком соотношении чтения/записи
и насколько важно быстродействие записи ?
а то сделать вставку со сдвигом ??
где находится тот цикл который надо вызывать?
вопрос, а в каком соотношении чтения/записи
и насколько важно быстродействие записи ?
а то сделать вставку со сдвигом ??
Я вообще склоняюсь к тому, что чем меньше чтений и записи, тем лучше.
---------- Post added at 19:29 ---------- Previous post was at 19:28 ----------
где находится тот цикл который надо вызывать?
Цикл подразумевается под переходом по RESULT. Я думаю счётчики быстрее всего через половинки индксных регистров делать, всегда так быстрее.
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
Я вообще склоняюсь к тому, что чем меньше чтений и записи, тем лучше.[COLOR="Silver"]
я про другое,
допустим что чтений 10000 а записей всего 100, тогда всю эту хренотень запихиваем ближе к записи, а при чтении вообще про это не задумывемся.
я про другое,
допустим что чтений 10000 а записей всего 100, тогда всю эту хренотень запихиваем ближе к записи, а при чтении вообще про это не задумывемся.
Исходный массив маленький... 9 или 12 байт всего за фрейм надо обработать.
Andrew771
12.08.2013, 16:50
просто убрать последовательные повторения
вот она разгадка. Сравниваем два последовательных байта, если равны, то ldir на -1 до конца списка.
---------- Post added at 16:50 ---------- Previous post was at 16:49 ----------
комбинация cpir и ldir :)
вот она разгадка. Сравниваем два последовательных байта, если равны, то ldir на -1 до конца списка.
---------- Post added at 16:50 ---------- Previous post was at 16:49 ----------
комбинация cpir и ldir :)
Повторения могут быть не последовательные! :)
---------- Post added at 21:23 ---------- Previous post was at 20:11 ----------
Продолжаю эксперименты:
CNT1 LD IY,ARRAY
LD IX,#0901
LOOP LD A,(IY+1)
OR A
JR Z,NO_CHK
LD HL,ARRAY
CNT2 LD B,#00
LD C,LX
CPIR
CALL NZ,RESULT
NO_CHK INC IY
INC LX
DEC HX
JP NZ,LOOP
JR $
RESULT OUT (#FE),A
RET
ARRAY DB 1,2,3,1,0,3,4,5,6
Замечания?
П/П RESULT использует все регистры, в т.ч. альтернативные, всё кроме SP,IX,IY.
research
12.08.2013, 18:39
сортИровать пузырьком. повторы тут и всплывут
так сохранять надо регистры :) и не парить мосх
ld de,array1
ld c,1
ld a,(de)
inc de
loop0
ld b,c
ld a,(de)
ld hl,array1
loop2
cp (hl)
inc hl
jr z,loop1
djnz loop2
push de,bc
call result
pop bc,de
loop1
inc de
inc c
ld a,c
cp 8
jr nz,loop0
ret
array1 db 1,2,1,3,1,4,1,5
---------- Post added at 17:48 ---------- Previous post was at 17:44 ----------
кстати это чо такое будет?
так сохранять надо регистры :) и не парить мосх
кстати это чо такое будет?
Я стараюсь не использовать стековые команды PUSH/POP, если есть возможность всё через регистры пустить. Получается быстрее. :) ну и CPIR это же, а что это за команда?))))))
Процедура отрисовывает найденый тайл поверх спрайта 1 раз. Нашла 4 тайла в области координат спрайта, нарисовала 4. :)
Barmaley_m
12.08.2013, 19:12
Если уж сортировать - то не пузырьком, а более эффективным методом.
Еще есть варианты - хранить исходные числа в таком контейнере, который автоматически сортируется по мере добавления в него элементов. Например, в двоичном дереве (http://ru.wikipedia.org/wiki/%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%BE%D0%B5_% D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE). Ну и битовая карта, предложенная выше, тоже хороша.
Не, сортировка это из другой оперы) тут просто дубли.
Не, сортировка это из другой оперы) тут просто дубли.
сортировка оч помогает выявлять дубли. мне по большому счету пофиг, но я все равно не вкурил, что надо. то надо быстро, то жалко памяти... определиться бы...
сортировка оч помогает выявлять дубли. мне по большому счету пофиг, но я все равно не вкурил, что надо. то надо быстро, то жалко памяти... определиться бы...
Я сделал через CPIR как и хотел вначале, в общем-то скорости хватило... просто думал, над более быстрым алгоритмом с массивом... но в моём контексте это оказалось лишним :) Пример применимости алгоритма в ролике здесь (http://zx.pk.ru/showpost.php?p=620822&postcount=923). Анализируется атрибутная карта тайлов, если спрайт героя в области каких-то атрибутов тайла, то собственно рисуем этот тайл поверх спрайта 1 раз за прерывание. 4 разных атрибута в области сканирования - рисуем 4 тайла по разу каждый. итд..
Powered by vBulletin® Version 4.2.5 Copyright © 2026 vBulletin Solutions, Inc. All rights reserved. Перевод: zCarot