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

...
Google Search
Forth-FAQ Spy Grafic

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




Ответить
Имя пользователя:
Заголовок:
Текст сообщения:
Введите текст вашего сообщения. Длина сообщения в символах не более: 60000

Размер шрифта:
Цвет шрифта
Настройки:
BBCode ВКЛЮЧЕН
[img] ВЫКЛЮЧЕН
[flash] ВЫКЛЮЧЕН
[url] ВКЛЮЧЕН
Смайлики ВЫКЛЮЧЕНЫ
Отключить в этом сообщении BBCode
Не преобразовывать адреса URL в ссылки
Вопрос
Теперь гостю придется вводить здесь пароль. Не от своей учетной записи, а ПАРОЛЬ ДЛЯ ГОСТЯ, получить который можно после регистрации на форуме через ЛС.:
Этот вопрос предназначен для выявления и предотвращения автоматических регистраций.
   

Обзор темы - Ускорение поиска в словарях
Автор Сообщение
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Цитата:
стоит ли овчинка выделки?

То ж об этом думаю.

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

Никто и не предлагает замусоривать контекст, чтобы по времени выходило так же если б мы писали культурно :(
Сообщение Добавлено: Ср июн 28, 2017 20:32
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Victor__v писал(а):
Просто неохота придумывать интерфейс под это и менять интерпретатор.

Уже есть такое. Ничего придумывать не надо, и интерпретатор только проще вышел не изменив сути и свойств.

Victor__v писал(а):
Тем и быстрее будет выявляться что слово "нетипично" в данном словаре. и перейти либо к другому словарю, либо к механизму кодогенерации.

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

Однако, основной вопрос остается - сколько времени работы программы занимает поиск в словаре? - стоит ли овчинка выделки?
Сообщение Добавлено: Ср июн 28, 2017 19:32
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Собственный вариант поиска у каждого словаря это здорово. Просто неохота придумывать интерфейс под это и менять интерпретатор. Хотя, кому как
Цитата:
основная масса имен имеет длину в пределах 3-12 символов.

Тем и быстрее будет выявляться что слово "нетипично" в данном словаре. и перейти либо к другому словарю, либо к механизму кодогенерации.
к примеру фрагмент 0/(3#R0-)R0(3^) вообще не типичен.
Сообщение Добавлено: Ср июн 28, 2017 16:27
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Victor__v писал(а):
Ещё как вариант отказ по размеру слова в словаре.

уже разбиралось - не выгодно, т.к. основная масса имен имеет длину в пределах 3-12 символов.
Вообще, имхо, поиск у каждого словаря должен быть собственный: где-то можно искать просто по цепочке, где-то надо ускорять, где-то надо вообще распознавать запрос.
Сообщение Добавлено: Ср июн 28, 2017 13:18
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Ещё как вариант отказ по размеру слова в словаре.
Как и пред.случае. Пусть будет поле длинною 32 бита. Каждый бит которого обозначает длину имеющихся слов в словаре.
1 - 1 символ
10 - 2 символа
11 - 1 и 2 символа
и т.д.
Если есть слова такой длины ищем, нет сворачиваем поиск. Длина больше 32-х символов? Что сказать? Попробуем найти.
Сообщение Добавлено: Ср июн 28, 2017 11:26
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Тогда уж лучше ввести слова >VOC и VOC>

Цитата:
хуже всего тормозят поиск литералы

По этой причине и ввёл в свой форт отказ по битовой маске. Часть чисел отрубает сразу.
В моём случае все кроме 0 1 2 т.к есть слова 1+ 2+ 2/ 2*
Да и зачем вспоминать?
Код:
SRC2\START.F
Ok
N-WORDS
GetProcAddress      LoadLibraryA      OPEN_EXISTING      FILE_EXECUTE      R/W   W/O   R/O   Stdcall:   (stdcall)   API-CALL   init-API   NOTFOUND-GENEGATE      [']   '   SFIND   SFIND-IN-VOC      OK(std)   ORDER   WORDS   TYPE(std)   ."   S"   EMIT   .   CR   LT   OK   TYPE   FILE-EXIST   CLOSE-FILE   OPEN-FILE-SHARE      OPEN-FILE   WRITE-FILE   READ-FILE   TEMP-WORDLIST      TEMP-WL-SIZE      VOCABULARY   USER-CREATE      USER-VALUE   USER   EXIT   ;   :   DOES>   CREATE   VECT   VARIABLE   VALUE   CONSTANT   HEADER   FREE   ALLOCATE   [CHAR]   CHAR   PARSE   PARSE-NAME   ParseWord   SkipUpTo   SkipWord   OnNotDelimiter      SkipDelimiters      OnDelimiter      GetChar   IsDelimiter      PeekChar   CharAddr   EndOfChunk   ->parse-data      parse-data->      ParseBuff_t      >IN   ParseBuff   ParseBuff.simb      INIT-STACK&USER      ALIGN-NOP   ALIGN   ALIGN-TO   ALIGN-SIZE   ]   [   TO-comp,   params-COMPILE,      CALL-in-addr?      INLINE-COMPILE,      INLINE(ret)      INLINE(pop)      COMPILE,   RET,   LIT,   USER-ALLOT   USER-OFFS   EVENT-WORD   INLINE   IMMEDIATE   SHEADER   SHEADER(std)      NAME-head   Name-head(lit,)      mask-in-voc?      mask-names-update      L>maskFA   L>notfoundFA      L>hereFA   L>LLFA   L>NFA   L>countFA   L>FFA   L>HFA   L>CFA   UNTIL   REPEAT   WHILE   AGAIN   BEGIN   THEN   ELSE   IF   STACK?   COMP?   THROW   CATCH   S,   ALLOT   C,   W,   ,   HERE   DP   DP[cdf]   !   W!   C!   @   W@   C@   FILL   COMPARE   ASCIIZ>   MOVE->R   MOVE    SEARCH   0=   <>   =   <   >   OR   AND   INVERT   NEGATE   RSHIFT   LSHIFT   ABS   /MOD   MOD   /   *   -   +   HASH   HASH(LY)   STR>NUM   sign-n   usign   }num   num>s{   GET-ORDER   DEFINITIONS      PREVIOUS   ALSO   F2@   F2>   >F2   F@   F>   >F   RP@   RP!   NR>   N>R   RDROP   2R>   2R@   2>R   R>   R@   >R   SP@   SP!   PICK   ROT   2OVER   OVER   NIP   2DROP   DROP   2SWAP   SWAP   2DUP   DUP   VOC-CODE   USER-SIZE   DATA-STACK-SIZE      H-STDOUT   H-STDIN   DEPTH   LAST-LFA   CONTEXT-SPACE      VOC0   S0   R0   CONTEXT   CURRENT   STATE   BASE   HANDLER   EXECUTE   NOOP   CELL   TRUE   FALSE   'TAB'   BL   >param   CELLS   CELL-   CELL+   2*   2/   2-   2+   1-   1+   0!   1+!   SLIT-CODE   CREATE-CODE      VECT-CODE   CONST-CODE   VALUE-CODE   VARIABLE-CODE      USER-CREATE-CODE      USER-VALUE-CODE      USER-CODE   
words: 244
Ok
ENDLOG


Сообщение Добавлено: Пн июн 26, 2017 13:03
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Victor__v писал(а):
То есть взяли специфическое слово и его наверх словаря. С таким подходом вопрос спорный. Пересобрать список не проблема. Надо всего лишь хранить предыдущий LFA, дабы пересобрать. Но не факт, что вытащенное слово будет иметь высокую частотность в исходниках. Тут ещё от стиля фортера и задачи зависит.

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

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

нет, так бывает удобно.

Вопрос сколько у вас словарей в контексте обычно 8) дубляж иногда сложно избежать, если, скажем, в контексте более 10 словарей находится.

Victor__v писал(а):
Можете привести пример, где повтор словарей в контекстах был жизненно необходим?

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

пример:
Код:
FORTH(0)>ORDER

Context: FORTH NUMBERS ROOT
Current: FORTH
Ok
FORTH(0)>ALSO
Ok
FORTH(0)>ORDER

Context: FORTH FORTH NUMBERS ROOT
Current: FORTH


дальше я по идее должен указать имя еще одного словаря, скажем, он находится в ROOT - значит искаться будет в словаре FORTH дважды. Это самый простой пример, могут быть более заковыристые случаи.
Сообщение Добавлено: Пн июн 26, 2017 12:48
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
кстати, попробовал в качестве хеш-фукции использовать CRC8 (принцип тот же по сути) вышло чуть лучше, чем мой исходный вариант(но дольше):
Код:
это исходный
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 %
Take up ticks: 898356626


Код:
это с CRC8
40  37  45  44  41  53  40  42  32  36  55  37  40  45  49  44  45  37  45  51  49  43  44  37  39  35  55  44  42  48  51  40  38  38  37  52  47  32  44  34
41  33  41  55  32  46  42  47  44  40  43  36  40  44  35  42  38  40  46  34  34  34  40  50  44  39  43  43  40  56  35  50  48  49  60  43  48  37  46  39
52  30  44  41  56  38  35  38  39  44  46  38  35  40  40  45  38  41  32  35  49  39  40  53  32  36  36  36  47  34  42  48  59  41  52  34  37  48  37  37
43  40  46  53  39  35  50  35  39  43  32  46  45  50  46  44  37  47  45  44  35  42  45  26  40  44  36  46  36  58  28  45  47  50  40  42  42  40  40  50
55  42  54  47  46  47  46  47  50  39  43  34  39  49  48  47  40  51  51  49  46  51  45  44  43  49  45  44  36  29  51  41  40  35  50  47  43  43  47  37
30  53  49  47  37  31  56  48  38  48  34  54  47  44  48  40  36  38  45  55  23  40  46  54  38  50  44  56  55  31  46  36  49  40  34  43  44  47  38  51
43  32  56  39  48  39  50  50  34  47  42  41  43  37  48  45
total: 10966  ideal: 42  min: 23  max: 60  repletion: 805  ~ 7 %
Take up ticks: 1226470632
Сообщение Добавлено: Пн июн 26, 2017 12:39
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Цитата:
да, в том и смысл: нашли - вытащили в начало

То есть взяли специфическое слово и его наверх словаря. С таким подходом вопрос спорный. Пересобрать список не проблема. Надо всего лишь хранить предыдущий LFA, дабы пересобрать. Но не факт, что вытащенное слово будет иметь высокую частотность в исходниках. Тут ещё от стиля фортера и задачи зависит.

Цитата:
Была еще идея перед поиском выкидывать из контекста дубли

Вот этого вообще не понимаю. Как это надо так умудриться напрограммировать, чтобы в контексте повторялся несколько раз один и тот же словарь? Это ж плохой стиль.
Можете привести пример, где повтор словарей в контекстах был жизненно необходим?
Сообщение Добавлено: Пн июн 26, 2017 12:39
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Victor__v писал(а):
Угу, здесь тоже предлагалось.
Но как делать это постоянно?

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

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

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

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

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

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

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

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

блин, ну так же и делается, имя скармливается (кстати не обязательно все, можно и первые 4 символа) хеш-функции, она возвращает номер цепочки, и дальше либо добавляется в словарь либо ищется в нем. Обычно количество цепочек кратно степени двойки - так проще считать хеш.
Сообщение Добавлено: Пн июн 26, 2017 12:22
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Цитата:
Кстати, были варианты ускорения поиска за счет постоянного перетаскивания искомых имен в начало цепочки

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

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

Это понятно, что легче перебрать 1 из 4 списоков по 10-эл-тов чем 1 список в котором 40.
Можно, к примеру хешировать входную строку и в зависимости от типа хеша ( положительное/отрицательное) выбирать нить
Кстати,
интересно посмотреть будет на форт-систему, где реализовано большинство идет в ЭТОЙ ТЕМЕ.
на больших словарях, спору нет, ускорение будет, но на мелких ( слов ~100 ) будет замедление
Сообщение Добавлено: Вс июн 25, 2017 00:00
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Victor__v писал(а):
Цитата:
сомневаюсь - надо доказать
Ну-ну.

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

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

Кстати, были варианты ускорения поиска за счет постоянного перетаскивания искомых имен в начало цепочки... В смысле, чем чаще встречается имя в тексте, тем ближе к началу списка оно находится.
Сообщение Добавлено: Сб июн 24, 2017 22:35
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Цитата:
а что делать с одинаковыми именами?

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

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

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



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

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

Опять же реализовать бит.маску в словаре очень просто. Для пущего быстродействия можно хоть на асме написать :) . Затрата только в начале поиска, в итерации не участвует.
Словарь делает одно из трёх:
а) у меня есть такое слово, счас найду
б) у меня нет такого слова, и не просите
в) Это? Не знаю. Счас поищу.
Сообщение Добавлено: Сб июн 24, 2017 11:19
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
Victor__v писал(а):
В моей системе ( которая пишется :) ) хеширование используется для создания уникального идентификатора слова.

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


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

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

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

Только не подумайте, что я против поиска оптимального решения ;)
Сообщение Добавлено: Пт июн 23, 2017 11:42
  Заголовок сообщения:  Re: Ускорение поиска в словарях  Ответить с цитатой
_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 бита, то бит от символа А будет равен биту от символа ! , поэтому приходится использовать две ячейки для более корректной организации. Продолжать не стал т.к. использование малых букв, русских букв и псевдографики очень маловероятно.
Сообщение Добавлено: Пт июн 23, 2017 07:27

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


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