Вид для печати
Вот думаю, как лучше организовать такое:
Есть массив 8 байт, в нём могут быть значения от 1 до 255, в любой последовательности. Требуется в цикле считать данные из массива без повторов. Результат каждого уникального числа массива в регистр А и флаг для перехода EXX:CALL Z,xxxx:EXX
Кол-во переходов равно кол-ву уникальных чисел массива.
Например в массиве: 1,1,2,3,3,3,6,8.
Результат: 1,2,3,6,8
А чё-то в примере не любая последовательность, а возрастающая. Так что, пока не понятно с заданием, чего надо.
Это я для примера:Цитата:
Сообщение от 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, Вариантов несколько:
1 (быстрый, но требующий больше памяти). Завести два массива, размерность которого определяется максимально возможным числом. Далее, организуем цикл: извлекаем из первого массива (со "случайными" числами) первый элемент и значение из второго массива, "номер" которого является величина числа из первого массива. Если "флаг" наличия во втором массиве не установлен, устанавливаем его и переходим к следующему элементу первого массива. В противном случае "сдвигаем" все значения первого массива вниз на одну ячейку и уменьшаем "верхнее" значение счетчика цикла. После чего, повторяем проверку той же ячейки еще раз.
2 (медленный, не требующий второго массива). Организуем цикл. Извлекаем значение ячейки массива соответствующее параметру цикла. Сравниваем его со всеми числами от первой ячейки до текущей. Если они равны, смещаем элементы массива "вниз" на одну ячейку. Уменшаем верхний предел цикла. Повторяем сравнение.
Первый вариант быстрее, но требует памяти 256 байт. Во втором случае чуть медленее будет. Кстати если попадается ноль, сразу переход на следующий байт массива без проверки.Цитата:
Сообщение от null_device
Но задачка в том, как изящно сделать этот второй вариант :) чтобы не дёргать стек.
---------- 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 будет патчить
Интересная идея :) Интересно, насколько оно быстрее будет.Цитата:
Сообщение от ZEK
Причем по скорости можно тож немного оптимизировать если байт с битами который надо смотреть на текущей итерации =0 то сразу в счетчик байта результат +8 делать и переходить к следующему байту, из 32байт максимум 8 байт будет обработано (при исходном массиве 8 чисел)
главное чтобы ваши оптимизации не были больше 256 байт... 8 чисел можно и отсортировать быстренько, а потом просто проверять, равен текущий предыдущему или нет.
патчить команды на ходу хорошо только в демах или интрах. а так это зло.
патчить погорячился, rrca + jr c шустрее будет даже
У меня это в реалтайме всё будет работать, поэтому скорость важна.Цитата:
Сообщение от psb
Сортировать мне не нужно, т.к. пересечений нет... нет смысла думать о порядке. Значений всего 255.
С битовым способом можно всё по OR быстро сложить, дубли объединятся.
На этапе обработки массива тока быстро вычислить нужно будет.
Примеры? :)
а запись в табличку через set bit, (IX+offs) все таки быстрее будет патчем, в bit младшие 3 бита найденного числа, в offs старшие 5 бит, шустрее будет
Цитата:
Сообщение от ZEK
Код: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
любые повторения:) пример я выше сделал, но тормозной)Цитата:
Сообщение от jerri
не сильно тормознойЦитата:
Сообщение от 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
Фишка в том, что процедура вызываемая из цикла запарывает все регистры :) даже альтернативные :)Цитата:
Сообщение от jerri
Можно использовать 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 ----------
из какого цикла?
вопрос, а в каком соотношении чтения/записи
и насколько важно быстродействие записи ?
а то сделать вставку со сдвигом ??
где находится тот цикл который надо вызывать?
Я вообще склоняюсь к тому, что чем меньше чтений и записи, тем лучше.Цитата:
Сообщение от esl
---------- Post added at 19:29 ---------- Previous post was at 19:28 ----------
Цикл подразумевается под переходом по RESULT. Я думаю счётчики быстрее всего через половинки индксных регистров делать, всегда так быстрее.Цитата:
Сообщение от jerri
Код: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
допустим что чтений 10000 а записей всего 100, тогда всю эту хренотень запихиваем ближе к записи, а при чтении вообще про это не задумывемся.
Исходный массив маленький... 9 или 12 байт всего за фрейм надо обработать.Цитата:
Сообщение от esl
вот она разгадка. Сравниваем два последовательных байта, если равны, то ldir на -1 до конца списка.Цитата:
Сообщение от jerri
---------- Post added at 16:50 ---------- Previous post was at 16:49 ----------
комбинация cpir и ldir :)
Повторения могут быть не последовательные! :)Цитата:
Сообщение от Andrew771
---------- 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.
сортИровать пузырьком. повторы тут и всплывут
так сохранять надо регистры :) и не парить мосх
Код: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 это же, а что это за команда?))))))Цитата:
Сообщение от jerri
Процедура отрисовывает найденый тайл поверх спрайта 1 раз. Нашла 4 тайла в области координат спрайта, нарисовала 4. :)
Если уж сортировать - то не пузырьком, а более эффективным методом.
Еще есть варианты - хранить исходные числа в таком контейнере, который автоматически сортируется по мере добавления в него элементов. Например, в двоичном дереве. Ну и битовая карта, предложенная выше, тоже хороша.
Не, сортировка это из другой оперы) тут просто дубли.
сортировка оч помогает выявлять дубли. мне по большому счету пофиг, но я все равно не вкурил, что надо. то надо быстро, то жалко памяти... определиться бы...Цитата:
Сообщение от drbars
Я сделал через CPIR как и хотел вначале, в общем-то скорости хватило... просто думал, над более быстрым алгоритмом с массивом... но в моём контексте это оказалось лишним :) Пример применимости алгоритма в ролике здесь. Анализируется атрибутная карта тайлов, если спрайт героя в области каких-то атрибутов тайла, то собственно рисуем этот тайл поверх спрайта 1 раз за прерывание. 4 разных атрибута в области сканирования - рисуем 4 тайла по разу каждый. итд..Цитата:
Сообщение от psb