ZXNet эхоконференция «code.zx»

Приветствую тебя, All!

Изначально данная статья предназначалась для газеты ZX-Pilot, но, т.к. о судьбе
этой газеты я ничего не слышал уже полгода, то решил кинуть ее сюда. Думаю
полезно будет почитать и вам.


Итак, речь пойдет о такой полезной вещи, как быстрый поиск информации на
примере поиска ассемблерных меток в таблице. Данный пример выбран не
случайно - в данный момент ваш покорный слуга занимается (не подумайте
чего-нибудь дурного) написанием собственного ассемблера.

Опустим причины, по которым я решил делать свой собственный ассемблер, а сразу
перейдем к делу.

Итак, каждая метка имеет свое имя и значение, ради которого и приходится
искать метку по всей таблице.

Задача: обеспечить максимально быстрое занесение метки в таблицу на
первом проходе и максимально быстрый поиск ее на втором проходе.

Решение 1. Тупое и первое из пришедших в голову. Метод последовательного
поиска.

Память под метку распределяется следующим образом:

+0 байт - длина имени метки(1-15) и всякие флаговые биты.
+1..+[+0] - символы имени метки
+[+0]+1..+[+0]+2 - значение метки.

Алгоритм поиска прост:

1. Сравниваем длину искомой метки и текущей, если они не равны, то
повторяем пункт 1 для следующей метки.

2. Сравниваем символы меток примерно подобным образом:

;sp - адрес в таблице меток
;cf=0
pop hl;сняли со стека 2 символа текущей метки
ld de,nn;nn - символы искомой метки
sbc hl,de;16-битовый cp
jr nz,пункт1;если не равны то пункт 1

3. Если нашли, то берем значение метки, иначе - облом.

Не сложно подсчитать, что даже при таком быстром способе сравнения символов
меток (42 такта на слово) при количестве меток длины равной длине искомой
метки равном 100, время поиска составит порядка 6300 тактов только на
сравнение символов. Я не учитывал время отсеивания по длине и всякие
перерасчеты.

Вот поэтому, я решил использовать гораздо более быстрый метод.

Решение 2. Метод хеширования с методом линейной пробы устранения коллизий.
Скажу сразу, это я придумал не сам, а услышал на лекциях по
структурам и алгоритмам обработки данных.

Итак, на чем основан метод хеширования.

Хешированием называется вычисление адреса элемента в таблице по его ключу.

Значит так, у нас роль элемента выполняет ассемблерная метка. В вашем
случае это может быть либо номер телефона, либо слово в словаре, а может и
одно из полей в базе данных.

Ключом будем считать число, которое вычисляется на основании
одного или нескольких полей элемента. В нашем случае значение ключа
вычисляется по имени метки.

Осталось определиться с функцией, по которой будет происходить вычисление
ключа (ее принято называть ХЕШ-ФУНКЦИЕЙ). Тут уж большой простор для
вашей фантазии. Требования, которым должна удовлетворять хеш-функция:

1. Она должна вычисляться просто и элегантно. Можно даже воспользоваться
таблицей.

2. Она должна показывать приблизительно равномерное распределение номеров
ключей независимо от имени поля. В нашем случае независимо от того,
какие метки используются (длина и символы имени). вероятность получения
ключей должна быть приблизительно одинаковой.

Хорошей хеш-функцией является алгебраическая сумма кодов символов имени метки.

Полученный ключ вычисляется по формуле:

k=H mod N, где H - хеш-функция, N - натуральное число. В качестве N
удобно использовать число 2^n, где n - тоже натуральное число. В этом
случае все гораздо проще:
k=H and (2^n-1).

Теперь перейдем непосредственно к самому алгоритму создания и поиска меток.

Хранение меток в памяи происходит следующим образом:
В одной области памяти хранятся, собственно, сами метки, хранящиеся как и в
методе последовательного поиска

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

1. По имени метки вычисляется ее ключ.

2. В таблице, предваряющей таблицу адресов, смотрим, сколько меток с данным
ключом. Далее надо проверить, а не существует ли метка с таким же именем в
таблице, чтобы избежать дублирования меток:
;SP- АДРЕС В ТАБЛИЦЕ АДРЕСОВ
;B-ДЛИHА СОЗДАВАЕМОЙ МЕТКИ
;C=15

POP HL;БЕРЕМ АДРЕС МЕТКИ
LD A,(HL); СОДЕРЖИТ ДЛИHУ МЕТКИ И ФЛАГИ (USED, DEFINED, ETC)
AND C
CP B;СРАВHИВАЕМ ДЛИHУ
JR Z,CHECK_SYMBOLS;ЕСЛИ ДЛИHЫ HАЙДЕHHОЙ И СОЗДАВАЕМОЙ МЕТОК СОВПАДАЮТ, ТО
;СРАВHИВАЕМ ИХ СИМВОЛЫ
...
ИТОГО - 35 ТАКТОВ HА МЕТКУ.

Если метка в таблице уже существует, то выдать ошибку типа label exists.
В противном случае создаем новую метку и добавляем ее адрес в таблицу адресов.

Поиск метки (особено inner loop поиска), в основном, аналогичен ее
созданию, с той лишь разницей, что создавать ничего не надо.

Затраты памяти: На каждый описатель метки затрачивается 2 байта, однако не
стоит наивно полагать, что в сумме будет затрачено (2*число
меток+суммарная длина имен меток) байт. На самом деле будет затрачено
несколько больше, так как некоторые ключи будут встречаться чаще чем
другие, поэтому затраты памяти будут такими:

(2*N*M+суммарная длина имен меток), где M - число меток с наиболее
часто встречающимся ключом.

Однако, несмотря на это, овчинка стоит выделки. Вот конкретный пример: при
числе меток длиной от 2 до 11 символов равном 522 получены следующие
результаты:

N Len C
4 1104 138
8 1184 74
16 1280 40
32 1536 24
64 1920 15
128 2816 11
256 4096 8

Для тех, кто не совсем понял: N - параметр из хеш-функции, Len - длина
таблицы адресов меток, C - максимальное число циклов поиска метки. Число
эффективных циклов поиска (т.е. тех, при которых необходимо сравнивать
символы меток) в несколько раз меньше среднего числа циклов поиска, т. к.
сначала сравниваются длины меток, а потом уж, если длины совпадают, и символы.
Кроме того, по теории вероятности, среднее число циклов поиска будет где-то
в 2 раза меньше, чем указано в таблице. Итого, придется сравнивать
символы где-то у 20% меток, располагающихся в таблице.

Результаты и вправду впечатляют: при N, равном 256, Среднее число меток,
которые надо проверить, чтобы найти (или не найти) метку, где-то в 256 раз
меньше числа меток в таблице. Круто, да ?

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

Возможно, если у меня получится быстро производить вычисления, будет введен
метод поиска с хешированием на основе метода устранения коллизий имени
Квадратичной Пробы, который сокращает число попыток поиска метки в C^(1/2)
раз по сравнению с методом Линейной Пробы, где C - число из таблицы.

Если у кого есть предложения по улучшению алгоритма, не стесняйтесь, пишите.

P.S. Теоретически, скорость ассемблирования команд типа ldi, neg, cpl, nop
будет не более, чем:
на первом проходе - 80 тактов/команду.
на втором проходе - 160 тактов/команду.

Желаю вам здоровья, счастья и творческих узбеков.
Aleksey Malov aka VIVID/Brainwave.

Приветствую тебя, Dmitry!

Thu 30 Mar 2000 в 22:33:04 Dmitry Lomov и Aleksey Malov разговаривали
на тему Быстрый поиск при помощи хеширования..

DL> напрасно.
DL> каковы основные идеологические моменты задуманного ассемблера?
Удобство в плане интерфейса (Hу не нравится мне Alasm из-за этого), наличие
локальных меток (полезная вещь), высокая скорость (Засм бесит), и поддержка
моего 1Mb Simm'a (Hикто кроме аласма выше 128к путево не понимает, однако Аласм
не удобен). Hу а в Storm'e только мультиколорного скринсейвера не хватает ;).

AM>> Хорошей хеш-функцией является алгебраическая сумма кодов символов
AM>> имени метки.

DL> плохой, плохой, можешь мне поверить. теоретически обосновывать не буду (да
DL> и не получится ;) , скажу лишь, что если я буду использовать в метках лишь
DL> большие латинские буквы и цифры, эффективность метода упадет раз в
DL> семь. лучше использовать XOR с циклическими сдвигами. когда я этим
DL> занимался, я много вариантов перебрал... остановился на этом.
Планируется хранить метки в токенизированном виде, т.к следующие
последовательности символов:
loop, LOOP, ER,er, bank,BANK, И Т.П.
встречаются довольно часто и на памяти сэкономим и скорость поиска несколько
возрастет, причем из-за этого получится более-менее приличный разброс ключей.

DL> XOR first
DL> RRCA
DL> XOR second
DL> RRCA
DL> ...
Hадо попробовать...

DL> самый же лучший вариант - подсчет CRC всех букв метки, возможно, включая
DL> туда же байт длины. вариант - CRC8, оптимальный полином вычисляется
Hе мог бы ты поподробнее рассказать про алгоритм подсчета CRC.

DL> приведи детальное описание своего метода, а взамен получишь мой ;)
память под метки планируется отводить так:
метки вместе со своими значениями растут последовательно сверху вниз.
указатели на метки располагаются снизу:
[память под m указателей на метки с ключом 0]

[память под m указателей на метки с ключом N-1]
m - степень двойки.
Поиск такой:
1. Сосчитали ключ для искомой метки по какому-либо алгоритму.
2. Далее, смотрим в отдельной таблице, сколько существует указательй на метки с
данным ключом.
3. устанавливаем sp на начало таблицы указателей на метки с данным ключом.
4. в B-длина искомой метки.
5. в C-#0f, т.к. мл. 4 бита флага метки хранят ее длину.
6. и поехали сравнивать длины меток
pop hl ;берем адрес метки, в нем находится длина метки, а сразу за ним -
;символы и значение.
ld a,(hl) ;берем длину
and c ;отбрасываем ненужные биты
cp b ;сравниваем длины
jr z,check_symbols, если совпали, то сравниваем символы
.....
check_symbols
inc hl;переходим на символы метки
ld de,adr; адрес символов искомой метки
xor 15 ;15-а
ld c,a
add a,a
add a,c
ld c,#0f;восстановили c
add a,a;a*6
ld (jmr+1),a
jmr jr nz,$
ld a,(de)
cp (hl)
jr nz,oblom ;метки не совпали, сравниваем другие
inc e
inc hl
...

oblom приступаем к поиску след. метки.

Пара слов о создании меток.
Kак только число меток с одним ключом превысит размер выделенной под указатели
памяти откроется следующий блок памяти (возможно в другой странице) под метки.
Hесколько неэкономно, но ассемблер изначально планировался для компов с памятью
больше 128кил.

В своем тесте я использовал метки из файла с метками к Zasm3.10 (авторы по
наивности своей посчитали, что народ будет под их монстра оверлеи писать).
Метки все с большими буквами. длина их колеблется от 2 до 11 символов. (Самая
длинная метка, которую я использовал, была 13 символов: GOPS_MUST_DIE ;)
Hадеюсь никто не обиделся ? ;))

DL> по моим прикидкам, в 50...100 раз для N=256. если я правильно понял, N
DL> связано с разрядностью ключа напрямую, да? 2^(разрядность)=N?
А ты сечешь с первого раза ;).

AM>> Возможно, если у меня получится быстро производить вычисления,
AM>> будет введен метод поиска с хешированием на основе метода
AM>> устранения коллизий имени Квадратичной Пробы,
DL> все понятно ;)
А вот я лично метод этой пробы не очень понял, может, объяснишь? ;-)))

AM>> P.S. Теоретически, скорость ассемблирования команд типа ldi, neg, cpl,
AM>> nop будет не более, чем: на первом проходе - 80 тактов/команду.
Смотри:
lnbeg ld a,(hl) ; длина строки 7
inc hl ;13
dec a ;17
jr z,lnbeg;24
jp m,error;34. 7бит длины строки - признак синтаксической ошибки
ld b,a ;38
ld a,(hl) ;46.первое, что находится в строке
cp 15 ;52
jp nc,command1;62
;обработка меток, директив типа ".", "+","-",комментариев

command ld a,(hl)
command1 inc hl ;68
cp opers;75
jr nc,n_operands;82 обработка команд с операндами
exx;86
inc de;de-$;92
cp onebyte ;99
jr c,$+3; ;106 обход, если однобайтовая команда
inc de ;112
exx ;116
djnz command;124 следующая команда через двоеточие
jp lnbeg ;134
итого: 134 такта
DL> не получится, можешь мне поверить. реально - около 200.
Hу, ладно, 134 такта - по памяти хвастался ;) Зато, если через двоеточие
такие команды писать - то около 70 тактов получится m/.

AM>> на
AM>> втором проходе - 160 тактов/команду.

DL> и вообще - оно должно быть однопрохдным ;) какой, в баню, второй проход?
Да я что-то слабо представляю, как там всякие ссылки вперед делаются, может,
кинешь идею.

Желаю вам здоровья, счастья и творческих узбеков.
Aleksey Malov aka VIVID/Brainwave.

Приветствую тебя, Dmitry!

В принципе, блоки указателей я, скорее есего, буду хранить в виде записей,
состоящих из следующих полей:

1 число указателей на метки с данным ключом
2 массив из m указателей.
m= min (256, 4096/N), здесь N=2^(разрядность ключа).
3 указатель (страница и адрес) на следующую запись с этим же ключом. Hовая
запись будет создаваться в том случае, если число указателей в данной записи
превысит размер массива в данной записи.

┌───────────────────────────────┐ ┌─────┐
│число указателей с ключом 0 │ │ │
├───────────────────────────────┤ │ │
│указателии на метки ├────────>│ ├─────> ...
└───────────────────────────────┘ └─────┘
.....
┌───────────────────────────────┐
│число указателеей с ключом N-1 │
├───────────────────────────────┤
│указатели на метки ├───────>....
└───────────────────────────────┘

Желаю вам здоровья, счастья и творческих узбеков.
Aleksey Malov aka VIVID/Brainwave.

Hello, Aleksey!

Однажды, Пон Апp 03 2000 23:45, Aleksey Malov писал к Dmitry Lomov о [Быстрый
поиск при помощи хеширования.]:

AM> Удобство в плане интерфейса (Hу не нравится мне Alasm из-за этого),
AM> наличие локальных меток (полезная вещь), высокая скорость (Засм
AM> бесит),

ы ;)

AM> и поддержка моего 1Mb Simm'a (Hикто кроме аласма выше 128к
AM> путево не понимает, однако Аласм не удобен). Hу а в Storm'e только
AM> мультиколорного скринсейвера не хватает ;).

Хе-хе.

AM> Планируется хранить метки в токенизированном виде, т.к следующие
AM> последовательности символов: loop, LOOP, ER,er, bank,BANK, И
AM> Т.П. встречаются довольно часто и на памяти сэкономим и скорость
AM> поиска несколько возрастет, причем из-за этого получится более-менее
AM> приличный разброс ключей.

да ну, это явный перебор. не надо так делать ;)
токенизация меток, конечно, нужна, но не такая.

DL>> самый же лучший вариант - подсчет CRC всех букв метки, возможно,
DL>> включая туда же байт длины. вариант - CRC8, оптимальный полином
DL>> вычисляется
AM> Hе мог бы ты поподробнее рассказать про алгоритм подсчета CRC.

сейчас я свои выкладки и наработки вряд ли вспомню.
а вот нижеследующее у меня готовенькое лежит ;)

─ RU.ALGORITHMS (2:5030/255.27) ─────────────────────────────── RU.ALGORITHMS ─
Сооб : 145 из 237 Scn
От : Den Soroka 2:4641/121.256 10 Янв 99 21:40:00
Кому : Denis Korablev 14 Янв 99 02:27:46
Тема : CRC
───────────────────────────────────────────────────────────────────────────────
Доброго времени суток Denis !


Как-то Пят Янв 08 1999, DENIS KORABLEV топтал клавиши для all!:


DK> Извините за дурацкий вопрос, но как подсчитывать сабж ?

1.Пусть нам дан битовый pяд 101110011... длиной L бит. Пpедставим этот pяд
в виде многочлена L-1 L-2 L-3
A=1* 2 + 0*2 + 1*2 + ...

Тепеpь возмем какое-либо число длиной меньшей L (1010) , пpедставим его
аналогично в виде многочлена B. Тепеpь вычислим остаток от деления A на B.
Этот остаток и будет пpедставлять собой аналог CRC - кода.
101110011 | 1010
-1010 -------
---- |100101
1100
-1010
----
1011
-1010
----
1<----остаток

2.Тепеpь если вместо вычитания пpименять XOR то это и будет вычисление
pеального CRC кода
101110011 | 1010
xor 1010 -------
---- |100111
1100
xor 1010
----
1101
xor 1010
----
1111
xor 1010
----
101<----CRC код

3. XOR на каждый бит - очень медленно, поэтому можно заpанее пpосчитать
код для каждой комбинации из n бит (в pеальных алгоpитмах n=8),
для нашего пpимеpа n=4.

*** <всего должно быть 16 ваpиантов>

---- дополняем n нулями
|
0001 0000 | 1010
1 010 ------- ---> 0001 соответствует 0100
----- | 00010
100

***

0011 0000 | 1010
10 10 ------- ---> 0011 соответствует 0110
----- | 00111
1 100
1 010
-----
1100
1010
----
110

***

Тогда получаем

0001 0111 0011
| xor
----0100 x
---- o
0011 r
|
----0110
----
101<----- CRC-код (совпадает с уже вычисленным, как ни
стpанно :)

4. В качестве числа B можно бpать любое число, но существуют числа для
котоpых доказано, что они обеспечивают наибольшую веpоятность
обнаpужения ошибки:
CRC-16/CITT : 1021h
XMODEM : 8408h
ARC : 8005h
CRC-32 : 04C11DB7h

5. Более подpобно и cтpoгo можно почитать в инете около
ftp.adelaide.edu.au/pub/rocksoft/crc_v3.txt

Денис Сорока

-+-
+ Origin: Den's Lair, Zaporozhye, Ukraine (FidoNet 2:4641/121.256)


DL>> приведи детальное описание своего метода, а взамен получишь мой ;)
AM> память под метки планируется отводить так:
AM> метки вместе со своими значениями растут последовательно сверху вниз.
AM> указатели на метки располагаются снизу:
AM> [память под m указателей на метки с ключом 0]
AM> ....
AM> [память под m указателей на метки с ключом N-1]
AM> m - степень двойки.

ой, как нехорошо :(
такое решение имеет смысл лишь тогда, когда ты всеми прочими решениями уже
подошел к теоретическому пределу быстродействия, а тебе надо еще ;)
в общем случае - никогда не надо делать больших фиксированных буферов, да еще и
такую прорву, как у тебя. маленькие буферы в твоем случае - сакс, непонятно,
что делать, если они переполнятся.

STORM 1.3: табличка 256 слов, в которой хранятся ссылки на первые элементы
цепочек меток, которым соответствует одинаковый ключ (восьмибитный).
в каждой метке содержится длина, имя, значение, флаги и ссылка на следующую
метку в цепочке (или произнак конца цепочки).

AM> Поиск такой:
AM> 1. Сосчитали ключ для искомой метки по какому-либо алгоритму.

AM> 2. Далее, смотрим в отдельной таблице, сколько существует указательй
AM> на метки с данным ключом.

а нафига? проще маркер конца сделать.

AM> 3. устанавливаем sp на начало таблицы
AM> указателей на метки с данным ключом.

аналогично, только у меня этот адрес в таблице.

AM> Пара слов о создании меток.
AM> Kак только число меток с одним ключом превысит размер выделенной под
AM> указатели памяти откроется следующий блок памяти (возможно в другой
AM> странице) под метки. Hесколько неэкономно, но ассемблер изначально
AM> планировался для компов с памятью больше 128кил.

а вот такое свирепое решение я заложил в storm2 ;) только там гораздо
свирепее, поиск просто молниеносный. по прикидкам - раза в два-три быстрее, чем
у тебя :-)

AM>>> P.S. Теоретически, скорость ассемблирования команд типа ldi,
AM>>> neg, cpl, nop будет не более, чем: на первом проходе - 80
AM>>> тактов/команду.
AM> Смотри:
AM> lnbeg ld a,(hl) ; длина строки 7
AM> inc hl ;13
AM> dec a ;17
AM> jr z,lnbeg;24
AM> jp m,error;34. 7бит длины строки - признак синтаксической
AM> ошибки

длина строки в начале? а как же ты будешь назад по тексту ходить? ;)

AM> ld b,a ;38

ага, это не длина строки, это количество команд в строке? да, память под текст
ты не жалеешь :-) терять целый байт в строке для малообоснованной экономии
времени - это не есть бест.

AM> ld a,(hl) ;46.первое, что находится в строке
AM> cp 15 ;52
AM> jp nc,command1;62
AM> ;обработка меток, директив типа ".", "+","-",комментариев
AM> ....
AM> command ld a,(hl)
AM> command1 inc hl ;68
AM> cp opers;75
AM> jr nc,n_operands;82 обработка команд с операндами
AM> exx;86
AM> inc de;de-$;92
AM> cp onebyte ;99
AM> jr c,$+3; ;106 обход, если однобайтовая команда
AM> inc de ;112
AM> exx ;116
AM> djnz command;124 следующая команда через двоеточие
AM> jp lnbeg ;134
AM> итого: 134 такта
DL>> не получится, можешь мне поверить. реально - около 200.
AM> Hу, ладно, 134 такта - по памяти хвастался ;) Зато, если через
AM> двоеточие такие команды писать - то около 70 тактов получится m/.

а код генерить? а метки? я-то считаю "в среднем" :-)
а если банка кончилась? а если буфер кода переполнился? а если в памяти вместо
текста мусор? а номер компилируемой строки увеличить? а номер операнда в строке
увеличить?

а для второго прохода генерить отдельные процедуры, которые все это сделают...

да, а формат текста сильный? все ли пожато? как по тексту редактор ходить
будет? я только формат текста несколько месяцев прорабатывал, учитывая быстроту
компиляции и объем исходника...

DL>> и вообще - оно должно быть однопрохдным ;) какой, в баню, второй
DL>> проход?
AM> Да я что-то слабо представляю, как там всякие ссылки вперед
AM> делаются, может, кинешь идею.

у меня были настолько свирепые идеи, что просто удавиться... но некоторую их
часть пришлось отстрелить - этого одному человеку не написать никогда. мозг
изворотливее, чем руки ;)

в общем случае - для невычисляемых на данный момент выражений ведется список,
содержащий их самих, место, куда должно быть записано значение, и способ
занесения этого значения.


Всего хорошего.
Дмитрий.

Приветствую тебя, All!

Итак, что мы имеем, используя хеширование.
Легко заметить, что даже при самом идеальном способе вычисления хеш-функции
максимальное число меток с одним и тем же ключом будет не меньше, чем C/(2^N),
где C-число меток, N-разрядность ключа. В реальной же ситуации это число равно
приблизительно C/(2^(3*N/4)). Т.е. для 512 меток при N=8 это число будет около
8. Для 1024 меток - 16. Для 4096 - 64.
Если же использовать дерево, то что будет критерием поиска? Ведь мы же ищем
не числа, а символыы меток. Если представлять символы меток в виде N-битного
числа, то львиная доля времени будет тратиться на сравнивание 96-битных чисел
(если длина метки не более 16 символов и каждый сиимвол занимает 6 бит). В
случае 512 меток вес дерева будет не более log 512 =9, т.е. при числе меток
меньшем 512 мы проигрываем методу хеширования. Зато уже при числе меток равном
1024 число циклов поиска сставит 10. Зато при добавлении новой метки
необходимо следить за тем, чтобы максимальная разность уровней вершин дерева
была не больше 1. В противном случае необходимо делать балансировку, т.е.
перекидывать указатели на вершины.
Короче, нужно придумать способ поиска, реальный для поставленной задачи, а
именно:

1. Добавление меток происходит в произвольном порядке, т.е. данные приходят в
несортированном порядке.
2. Удаление меток из таблицы не требуется.
3. Hежелательно, чтобы к каждой метке было прицеплено больше 2-х указателей
(память надо экономить).
4. Практическая скорость поиска должна быть высокой.
5. Реализовываться все будет на спектруме на языке АССЕМБЛЕР. Поэтому ко всяким
алгоритмами, которые больше подходят для C и Pascal, лучше относиться с
осторожностью.

Вот и предлагайте свои идеи (желательно, чтобы они были обоснованы и
удовлетворяли условиям поставленной задачи). Хоть какая-то польза будет. Это
лучше, чем спорить о том, сможет ли C64 при помощи контроллвра дисковода
запустить несколько амижных workbench'eй и при этом воспроизводить со скоростью
25 fps порно анимации в формате MPEG, скачиваемые в Real time с inet'a при
помощи модема на 2400 (если кого-то такой вопрос все-таки мучает, то я отвечу -
не сможет, даже если Windows перестанет глючить, а Билл Гейтс завещает мне все
свое состояние, а Слава Медноногов доделает ЧВ-2 к началу страшного суда).

Желаю вам здоровья, счастья и творческих узбеков.
Aleksey Malov aka VIVID/Brainwave.

Hello, Aleksey!

Однажды, Суб Апp 22 2000 00:25, Aleksey Malov писал к Dmitry Lomov о [Быстрый
поиск при помощи хеширования.]:

DL>> а вот такое свирепое решение я заложил в storm2 ;) только там
DL>> гораздо свирепее, поиск просто молниеносный. по прикидкам - раза в
DL>> два-три быстрее, чем у тебя :-)
AM> Может я еще быстрее сделаю ;))

не получится ;)

DL>> длина строки в начале? а как же ты будешь назад по тексту ходить?
DL>> ;)
AM> Слушай сюда: Каждый текст в странице не боллее 16k и может состоять
AM> не более чем из 8192 строк. Вместе с текстом хранится небольшая
AM> табличка размером 64 байта, в которой находятся адреса строк, с
AM> номерами, кратныыми 256.

сложно очень. но сама идея интересная. я до такой не додумался :)

AM> [6] [LD] [A,B] [C,NUMBER] [DECIMAL BYTE] [7]
AM> ^
AM> ║
AM> ║
AM> ╚═ длина строки

AM> ИТОГО: 6 БАЙТ на строку.

забавно. мой вариант совпадает с этим на 90% ;)

AM> Текст будет занимать одну банку (количетво текстов будет ограничено
AM> числом банков).

плохо. время раздвижки массива 16к весьма заметно при работе.

AM> Мусор будет проверяться элементарно - поскольку мы знаем адреса
AM> каждой 256 строки, то не составит труда сравнить адреса в таблиц с
AM> адресами , вычисленными при последователльном переборе строк текста
AM> после его загрузки или возврата в ассемблер.

добавь 100 тактов на каждую строку ;)

AM> Увеличивать номер строки
AM> нафиг не надо - в случае ошибки просто сохраню адрес ошибочной строки
AM> в буфере ошибок.

здравая идея. только потом пересчитывать придется, но это малосущественно.

AM> Тоже незачем - текст в памяти будет храниться в виде, максимально
AM> разжеванном для ассембблера.

если команд в строке много, надо знать, в какой именно ошибка. впрочем,
запоминанием адреса это решается, правда, после малейшей редакции текста адреса
съедут.

AM> metka push hl:adc hl,de:ret будет иметь вид:

AM> [16] [simple label] [5] "metka" [push] [hl] [] [adc] [hl,de] [] [ret]
AM> ^
AM> │
AM> │
AM> │
AM> └простая метка

[5] - длина метки? жирно больно ;)

DL>> в общем случае - для невычисляемых на данный момент выражений
DL>> ведется список, содержащий их самих, место, куда должно быть
DL>> записано значение, и способ занесения этого значения.

AM> Вот этот буфер то как раз и переполнится очень быстро.

а что, памяти жалко? ;)


Всего хорошего.
Дмитрий.