Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт мар 28, 2024 13:41

...
Google Search
Forth-FAQ Spy Grafic

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 39 ]  На страницу Пред.  1, 2, 3  След.
Автор Сообщение
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Вт июн 20, 2017 22:28 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1287
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Ещё один вариант того, как словарь скажет у меня нет такого слова
Пусть у словаря будет поле mask-names размером 8 байт (64 бита).
Каждый бит этого поля будет указывать на присутствие слова (-ов) которое начинается с символа '!' ( 33 в кодах после пробела ) и последующих.
В крайних случаях ускорит поиск ( переход в след. словарь или сразу к словам кодогенерации )
Недостатки: 64 бит может не хватить. И тут возможны варианты разной степени адекватности. К примеру, архивация этого поля :)

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Вт июн 20, 2017 22:54 
Не в сети

Зарегистрирован: Пт янв 06, 2017 14:57
Сообщения: 365
Благодарил (а): 17 раз.
Поблагодарили: 1 раз.
Какие-то странные мысли уже пошли, не находишь? :)


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Вт июн 20, 2017 23:08 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1287
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Что странного в битовых полях?

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Чт июн 22, 2017 11:50 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1287
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
В продолжение битовости поиска ( поле 64 бит )
Словарь может иметь 3 списка вместо одного
1 для слов подпадающих под 1-ю часть битового поля
2 для слов подпадающих под 2-ю часть битового поля
3 для слов, которые нельзя впихнуть в битовое поле ( всё что с символа больше чем BL 1+ 64 + )

Недостатки: данное "дерево" получится крайне несбалансированным 2-я ветка будет самой большой

Ещё варианты по битовой маске:
Пусть каждое слово хранит битовую маску предыдущих слов.
Словарь сможет быстрее выяснить, что слов которые начинается с опр.символа уже нет с у него нет и закончить поиск.
Недостатки: придется делать 3 списка (см.выше), а в словах третьей ветви в поле маски будет всегда все биты

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Чт июн 22, 2017 16:18 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Victor__v писал(а):
В продолжение битовости поиска ( поле 64 бит )
Словарь может иметь 3 списка вместо одного

Вы выбрали плохой метод хэширования списка.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Чт июн 22, 2017 17:23 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1287
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
mOleg писал(а):
Victor__v писал(а):
В продолжение битовости поиска ( поле 64 бит )
Словарь может иметь 3 списка вместо одного

Вы выбрали плохой метод хэширования списка.


читаем дальше

Цитата:
Недостатки: данное "дерево" получится крайне несбалансированным 2-я ветка будет самой большой

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Чт июн 22, 2017 22:00 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Victor__v писал(а):
читаем дальше

вы бы статью про хеширование таки почитали бы.
при 16 тредах(цепочках) на 256 именах при более-менее неплохой хеш функции будет 10-20 имен, чего вполне достаточно.
напомню, что 16 тред - это 16 адресных ссылок, что вполне экономично на любой архитектуре.

в форке хеш-функия такая:
Код:
\ определить хеш код строки √
CODE HASH ( asc # --> byte )
          dpop addr
          MOV cntr , tos
         JCXZ @@2
    @@1:  ROR tos-byte , # 5
          XOR tos-byte , -1 [addr] [cntr]
          DEC cntr
         JNZ @@1
    @@2:  AND tos , # 0xFF
        exit
     END-CODE

результат при проходе по текстовому файлу dpans94us.txt выглядит так:
Цитата:
FORTH(0)>samples/hash.fts
hTest(0)>s" dpans94us.txt" m-voc
47 52 48 47 31 42 51 38 33 50 33 46 40 49 43 50 44 53 47 38 45 48 53 49 40 42 33 43 38 42 46 54 55 54 39 35 37 32 54 53
41 55 39 41 45 42 49 42 52 50 46 49 54 63 58 39 36 54 49 53 45 49 59 51 45 39 49 29 39 38 45 48 49 44 40 39 54 45 21 46
50 49 45 46 41 42 39 42 58 41 43 38 43 37 39 32 45 40 29 30 36 47 39 44 41 38 28 40 41 34 40 35 42 46 41 46 42 44 28 41
44 39 43 43 46 35 36 34 40 44 54 38 34 40 45 33 37 35 45 46 42 35 39 45 32 38 51 46 43 45 41 35 41 49 42 49 38 30 40 35
40 44 42 42 43 54 45 42 35 41 40 41 47 37 45 43 50 41 48 45 50 48 47 41 42 58 39 41 52 44 50 40 44 40 41 45 46 29 50 49
41 38 50 48 39 32 49 55 45 39 61 43 44 27 42 33 43 39 40 36 52 39 40 51 38 43 44 52 38 27 32 30 33 38 36 49 44 33 40 43
45 37 46 46 50 38 44 42 51 41 36 56 55 39 37 42
total: 10966 ideal: 42 min: 21 max: 63 repletion: 795 ~ 7 %


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

в данном случае 256 тред, но и уникальных имен более 10000

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Чт июн 22, 2017 23:14 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1287
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Цитата:
вы бы статью про хеширование таки почитали бы

Таки читал.
В моей системе ( которая пишется :) ) хеширование используется для создания уникального идентификатора слова. Всё равно быстрее чем сравнивать строки посимвольно.
Битовый набор слов создан для быстрой проверки наличия слова в словаре - если нет уходим сразу из словаря.
Конечно, OVER C@ Bute>bit maskFA @ AND может быть хеш-функцией, но ей она является лишь умозрительно, а не фактически.

Попытка реализовать "дерево" из 3-х ветвей при компиляции в уме уже показала нецелесообразность. О чём сам же и написал выше. Однако, вариант соединить механизм отказа по битовой маске с поиском по ветвям всё ж имеет подозрения на оптимальность.

Так, добавим несколько ветвей. 32 бита - под ветвь 1, 8 бит под ветвь 2, 8 бит под ветвь 3 16 бит под ветвь 4, вообще не подпадающие в 5 ветвь. 5 CELLS 8 + ---> 28 байт . Да уж словари с каждым разом всё "жирнее"

Пока не берусь использовать таблицы. А битовая маска при компиляции в уме даёт неплохой выигрыш.

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Чт июн 22, 2017 23:45 
Не в сети

Зарегистрирован: Пт янв 06, 2017 14:57
Сообщения: 365
Благодарил (а): 17 раз.
Поблагодарили: 1 раз.
Цитата:
Какие-то странные мысли уже пошли, не находишь?

Прости, теперь я вроде тебя понял. Ты пытаешься делить таблицу сканкодов на части. Это в принципе можно делать и для слов.
Например:
16-бит: FEDCBA98|76543210
0 - 00 - 0F
1 - 10 - 1F
...
32-бита: ...|FEDCBA98|76543210
0 - 00 - 07
1 - 08 - 0F
...
Т.е. я могу внести доп. ячейку для ускорения поиска(но это действительно не хеш функция). Спасибо за идею!


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Пт июн 23, 2017 07:27 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1287
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
_KROL писал(а):
Цитата:
Какие-то странные мысли уже пошли, не находишь?

Прости, теперь я вроде тебя понял. Ты пытаешься делить таблицу сканкодов на части. Это в принципе можно делать и для слов.
Например:
16-бит: FEDCBA98|76543210
0 - 00 - 0F
1 - 10 - 1F
...
32-бита: ...|FEDCBA98|76543210
0 - 00 - 07
1 - 08 - 0F
...
Т.е. я могу внести доп. ячейку для ускорения поиска(но это действительно не хеш функция). Спасибо за идею!


Можно скачать исходники моего форта и посмотреть там.
Папки \forth\mid\voc-search.f и \forth\top\comp-word.f

Касательно идеи.
Преобразовать коды символов в биты очень просто
вот примеры:
2 BASE !
1 CHAR ! BL 1+ - LSHIFT .
1 CHAR # BL 1+ - LSHIFT .
1 CHAR # 0 1+ - LSHIFT .
1 CHAR * BL 1+ - LSHIFT .

Всё упирается в размер поля. У меня кстати порядок следования смешанный
т.к. в спф размер ячейки 32 бита, то бит от символа А будет равен биту от символа ! , поэтому приходится использовать две ячейки для более корректной организации. Продолжать не стал т.к. использование малых букв, русских букв и псевдографики очень маловероятно.

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Пт июн 23, 2017 11:42 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Victor__v писал(а):
В моей системе ( которая пишется :) ) хеширование используется для создания уникального идентификатора слова.

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


Victor__v писал(а):
Всё равно быстрее чем сравнивать строки посимвольно.

сомневаюсь - надо доказать.
Victor__v писал(а):
А битовая маска при компиляции в уме даёт неплохой выигрыш.

в уме много чего дает неплохой выигрыш...

Только не подумайте, что я против поиска оптимального решения ;)

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Сб июн 24, 2017 11:19 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1287
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Цитата:
а что делать с одинаковыми именами?

А что с ними надо делать? Какое будет определено позднее, такое и будет выдано.

Цитата:
сомневаюсь - надо доказать

Ну-ну.
Код:
L>HashFA @ OVER = IF
....
L>NFA @ COUNT 2OVER COMPARE 0= IF



Единственная затрата это хеширование строки на входе. Если в словаре мало слов ( ~30 ) то возможно COMPARE будет быстрей.
Всё ж у сравнения хешей затрат на 1-ну итерацию будет меньше.

Цитата:
в уме много чего дает неплохой выигрыш

Опять же реализовать бит.маску в словаре очень просто. Для пущего быстродействия можно хоть на асме написать :) . Затрата только в начале поиска, в итерации не участвует.
Словарь делает одно из трёх:
а) у меня есть такое слово, счас найду
б) у меня нет такого слова, и не просите
в) Это? Не знаю. Счас поищу.

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Сб июн 24, 2017 22:35 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Victor__v писал(а):
Цитата:
сомневаюсь - надо доказать
Ну-ну.

в смысле не код показать, а замерить время поиска для разных решений.
Victor__v писал(а):
Единственная затрата это хеширование строки на входе. Если в словаре мало слов ( ~30 ) то возможно COMPARE будет быстрей.
Всё ж у сравнения хешей затрат на 1-ну итерацию будет меньше.

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

Кстати, были варианты ускорения поиска за счет постоянного перетаскивания искомых имен в начало цепочки... В смысле, чем чаще встречается имя в тексте, тем ближе к началу списка оно находится.

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Вс июн 25, 2017 00:00 
Не в сети

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 1287
Благодарил (а): 3 раз.
Поблагодарили: 18 раз.
Цитата:
Кстати, были варианты ускорения поиска за счет постоянного перетаскивания искомых имен в начало цепочки

Угу, здесь тоже предлагалось.
Но как делать это постоянно?
Поле статистики ввести что-ль для слов.статьи? Или есть ещё варианты?
Лучше делать это время от времени
вариант создать врем.словарь из которого парсится какой-то файл с форт-исходниками. И слова с наибольшей частотой ищутся в текущих контекстах. И цепочка слов меняется. Оформляем в виде скрипта и запускаем время от времени

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

Это понятно, что легче перебрать 1 из 4 списоков по 10-эл-тов чем 1 список в котором 40.
Можно, к примеру хешировать входную строку и в зависимости от типа хеша ( положительное/отрицательное) выбирать нить
Кстати,
интересно посмотреть будет на форт-систему, где реализовано большинство идет в ЭТОЙ ТЕМЕ.
на больших словарях, спору нет, ускорение будет, но на мелких ( слов ~100 ) будет замедление

_________________
Цель: сделать 64-битную Нову под Винду


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
 Заголовок сообщения: Re: Ускорение поиска в словарях
СообщениеДобавлено: Пн июн 26, 2017 12:22 
Не в сети
Moderator
Moderator
Аватара пользователя

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 5062
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 23 раз.
Поблагодарили: 63 раз.
Victor__v писал(а):
Угу, здесь тоже предлагалось.
Но как делать это постоянно?

да, в том и смысл: нашли - вытащили в начало. Затраты дополнительные не очень велики, а выигрыш вроде как есть.

Victor__v писал(а):
Поле статистики ввести что-ль для слов.статьи? Или есть ещё варианты?

мне понравился подход, реализованный в SMAL32, там одна хеш-таблица на все словари (кажется на 256 элементов)
во время поиска имя ищется по сути сразу во всех словарях, после нахождения проверяется в контексте ли оно.

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

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

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

ну, тут всегда есть поиск компромисса между сложностью реализации, объемом кода и выигрышем. Пока что именно хеширование выглядит с этой точки зрения оптимальным: сложность реализации практически никакая, проигрыш по занимаемой памяти очень невелик, к тому же(кажется в СПФе это сделано) можно подготавливать хеш список после добавления словаря в контекст, но это требует использования динамической памяти.

Victor__v писал(а):
Можно, к примеру хешировать входную строку и в зависимости от типа хеша ( положительное/отрицательное) выбирать нить

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

_________________
Мне бы только мой крошечный вклад внести,
За короткую жизнь сплести
Хотя бы ниточку шёлка.
fleur


Вернуться к началу
 Профиль Отправить личное сообщение  
Ответить с цитатой  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 39 ]  На страницу Пред.  1, 2, 3  След.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 13


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

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
phpBB сборка от FladeX // Русская поддержка phpBB