Автор |
Сообщение |
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Цитата: стоит ли овчинка выделки? То ж об этом думаю. Цитата: Имхо, выгоднее просто активнее работать со словарями - чаще убирая из поиска ненужное. Никто и не предлагает замусоривать контекст, чтобы по времени выходило так же если б мы писали культурно
[quote]стоит ли овчинка выделки?[/quote] То ж об этом думаю.
[quote]Имхо, выгоднее просто активнее работать со словарями - чаще убирая из поиска ненужное.[/quote] Никто и не предлагает замусоривать контекст, чтобы по времени выходило так же если б мы писали культурно :(
|
|
|
|
Добавлено: Ср июн 28, 2017 20:32 |
|
|
|
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Victor__v писал(а): Просто неохота придумывать интерфейс под это и менять интерпретатор. Уже есть такое. Ничего придумывать не надо, и интерпретатор только проще вышел не изменив сути и свойств. Victor__v писал(а): Тем и быстрее будет выявляться что слово "нетипично" в данном словаре. и перейти либо к другому словарю, либо к механизму кодогенерации. то есть хочется вообще не искать в словаре, если ничего не ожидается похожего? Ну, боюсь тут будет немного толку - слов у нас удобных меньше, чем возможное количество определений. Имхо, выгоднее просто активнее работать со словарями - чаще убирая из поиска ненужное. Однако, основной вопрос остается - сколько времени работы программы занимает поиск в словаре? - стоит ли овчинка выделки?
[quote="Victor__v"] Просто неохота придумывать интерфейс под это и менять интерпретатор.[/quote] Уже есть такое. Ничего придумывать не надо, и интерпретатор только проще вышел не изменив сути и свойств.
[quote="Victor__v"]Тем и быстрее будет выявляться что слово "нетипично" в данном словаре. и перейти либо к другому словарю, либо к механизму кодогенерации.[/quote] то есть хочется вообще не искать в словаре, если ничего не ожидается похожего? Ну, боюсь тут будет немного толку - слов у нас удобных меньше, чем возможное количество определений. Имхо, выгоднее просто активнее работать со словарями - чаще убирая из поиска ненужное.
Однако, основной вопрос остается - сколько времени работы программы занимает поиск в словаре? - стоит ли овчинка выделки?
|
|
|
|
Добавлено: Ср июн 28, 2017 19:32 |
|
|
|
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Собственный вариант поиска у каждого словаря это здорово. Просто неохота придумывать интерфейс под это и менять интерпретатор. Хотя, кому как Цитата: основная масса имен имеет длину в пределах 3-12 символов. Тем и быстрее будет выявляться что слово "нетипично" в данном словаре. и перейти либо к другому словарю, либо к механизму кодогенерации. к примеру фрагмент 0/(3#R0-)R0(3^) вообще не типичен.
Собственный вариант поиска у каждого словаря это здорово. Просто неохота придумывать интерфейс под это и менять интерпретатор. Хотя, кому как [quote]основная масса имен имеет длину в пределах 3-12 символов.[/quote] Тем и быстрее будет выявляться что слово "нетипично" в данном словаре. и перейти либо к другому словарю, либо к механизму кодогенерации. к примеру фрагмент 0/(3#R0-)R0(3^) вообще не типичен.
|
|
|
|
Добавлено: Ср июн 28, 2017 16:27 |
|
|
|
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Victor__v писал(а): Ещё как вариант отказ по размеру слова в словаре. уже разбиралось - не выгодно, т.к. основная масса имен имеет длину в пределах 3-12 символов. Вообще, имхо, поиск у каждого словаря должен быть собственный: где-то можно искать просто по цепочке, где-то надо ускорять, где-то надо вообще распознавать запрос.
[quote="Victor__v"] Ещё как вариант отказ по размеру слова в словаре.[/quote] уже разбиралось - не выгодно, т.к. основная масса имен имеет длину в пределах 3-12 символов. Вообще, имхо, поиск у каждого словаря должен быть собственный: где-то можно искать просто по цепочке, где-то надо ускорять, где-то надо вообще распознавать запрос.
|
|
|
|
Добавлено: Ср июн 28, 2017 13:18 |
|
|
|
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Ещё как вариант отказ по размеру слова в словаре. Как и пред.случае. Пусть будет поле длинною 32 бита. Каждый бит которого обозначает длину имеющихся слов в словаре. 1 - 1 символ 10 - 2 символа 11 - 1 и 2 символа и т.д. Если есть слова такой длины ищем, нет сворачиваем поиск. Длина больше 32-х символов? Что сказать? Попробуем найти.
Ещё как вариант отказ по размеру слова в словаре. Как и пред.случае. Пусть будет поле длинною 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
Тогда уж лучше ввести слова >VOC и VOC>
[quote]хуже всего тормозят поиск литералы[/quote] По этой причине и ввёл в свой форт отказ по битовой маске. Часть чисел отрубает сразу. В моём случае все кроме 0 1 2 т.к есть слова 1+ 2+ 2/ 2* Да и зачем вспоминать? [code] 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
[/code]
|
|
|
|
Добавлено: Пн июн 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 дважды. Это самый простой пример, могут быть более заковыристые случаи.
[quote="Victor__v"]То есть взяли специфическое слово и его наверх словаря. С таким подходом вопрос спорный. Пересобрать список не проблема. Надо всего лишь хранить предыдущий LFA, дабы пересобрать. Но не факт, что вытащенное слово будет иметь высокую частотность в исходниках. Тут ещё от стиля фортера и задачи зависит.[/quote] безусловно. но выигрыш дает. Кстати, хуже всего тормозят поиск литералы (числа), по хорошему (в моем случае) словарь распознающий числа должен находиться на самом верху контекста.
[quote="Victor__v"]Вот этого вообще не понимаю. Как это надо так умудриться напрограммировать, чтобы в контексте повторялся несколько раз один и тот же словарь? Это ж плохой стиль.[/quote] нет, так бывает удобно.
Вопрос сколько у вас словарей в контексте обычно 8) дубляж иногда сложно избежать, если, скажем, в контексте более 10 словарей находится.
[quote="Victor__v"]Можете привести пример, где повтор словарей в контекстах был жизненно необходим?[/quote] не то, чтобы необходим жизненно, но бывает удобно, или, скорее неудобно упорядочивать словари в контексте. Самый простой вариант, дубляж верхнего словаря:
пример: [code]FORTH(0)>ORDER
Context: FORTH NUMBERS ROOT Current: FORTH Ok FORTH(0)>ALSO Ok FORTH(0)>ORDER
Context: FORTH FORTH NUMBERS ROOT Current: FORTH[/code]
дальше я по идее должен указать имя еще одного словаря, скажем, он находится в 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
кстати, попробовал в качестве хеш-фукции использовать CRC8 (принцип тот же по сути) вышло чуть лучше, чем мой исходный вариант(но дольше): [code] это исходный 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[/code]
[code] это с 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[/code]
|
|
|
|
Добавлено: Пн июн 26, 2017 12:39 |
|
|
|
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Цитата: да, в том и смысл: нашли - вытащили в начало То есть взяли специфическое слово и его наверх словаря. С таким подходом вопрос спорный. Пересобрать список не проблема. Надо всего лишь хранить предыдущий LFA, дабы пересобрать. Но не факт, что вытащенное слово будет иметь высокую частотность в исходниках. Тут ещё от стиля фортера и задачи зависит. Цитата: Была еще идея перед поиском выкидывать из контекста дубли Вот этого вообще не понимаю. Как это надо так умудриться напрограммировать, чтобы в контексте повторялся несколько раз один и тот же словарь? Это ж плохой стиль. Можете привести пример, где повтор словарей в контекстах был жизненно необходим?
[quote]да, в том и смысл: нашли - вытащили в начало[/quote] То есть взяли специфическое слово и его наверх словаря. С таким подходом вопрос спорный. Пересобрать список не проблема. Надо всего лишь хранить предыдущий LFA, дабы пересобрать. Но не факт, что вытащенное слово будет иметь высокую частотность в исходниках. Тут ещё от стиля фортера и задачи зависит.
[quote]Была еще идея перед поиском выкидывать из контекста дубли[/quote] Вот этого вообще не понимаю. Как это надо так умудриться напрограммировать, чтобы в контексте повторялся несколько раз один и тот же словарь? Это ж плохой стиль. Можете привести пример, где повтор словарей в контекстах был жизненно необходим?
|
|
|
|
Добавлено: Пн июн 26, 2017 12:39 |
|
|
|
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Victor__v писал(а): Угу, здесь тоже предлагалось. Но как делать это постоянно? да, в том и смысл: нашли - вытащили в начало. Затраты дополнительные не очень велики, а выигрыш вроде как есть. Victor__v писал(а): Поле статистики ввести что-ль для слов.статьи? Или есть ещё варианты? мне понравился подход, реализованный в SMAL32, там одна хеш-таблица на все словари (кажется на 256 элементов) во время поиска имя ищется по сути сразу во всех словарях, после нахождения проверяется в контексте ли оно. В форке я поступил не так, собственно, там я отдал это дело на откуп каждому словарю. Хеширование используется в статических словарях, и выигрыш в скорости таки заметный. Была еще идея перед поиском выкидывать из контекста дубли, собственно после каждой операции с контекстом надо по хорошему строить теневой контекст без дублей, но руки пока не дошли до этого. Однако, хочу сказать, что ускорение поиска не очень важная и не самая ценная для меня вещь. В конце концов я могу разбить(и делаю это) имена на множество словарей и управляя контекстом сильно сокращать просматриваемые списки. Victor__v писал(а): Лучше делать это время от времени вариант создать врем.словарь из которого парсится какой-то файл с форт-исходниками. И слова с наибольшей частотой ищутся в текущих контекстах. И цепочка слов меняется. Оформляем в виде скрипта и запускаем время от времени ну, тут всегда есть поиск компромисса между сложностью реализации, объемом кода и выигрышем. Пока что именно хеширование выглядит с этой точки зрения оптимальным: сложность реализации практически никакая, проигрыш по занимаемой памяти очень невелик, к тому же(кажется в СПФе это сделано) можно подготавливать хеш список после добавления словаря в контекст, но это требует использования динамической памяти. Victor__v писал(а): Можно, к примеру хешировать входную строку и в зависимости от типа хеша ( положительное/отрицательное) выбирать нить блин, ну так же и делается, имя скармливается (кстати не обязательно все, можно и первые 4 символа) хеш-функции, она возвращает номер цепочки, и дальше либо добавляется в словарь либо ищется в нем. Обычно количество цепочек кратно степени двойки - так проще считать хеш.
[quote="Victor__v"]Угу, здесь тоже предлагалось. Но как делать это постоянно?[/quote] да, в том и смысл: нашли - вытащили в начало. Затраты дополнительные не очень велики, а выигрыш вроде как есть.
[quote="Victor__v"]Поле статистики ввести что-ль для слов.статьи? Или есть ещё варианты?[/quote] мне понравился подход, реализованный в SMAL32, там одна хеш-таблица на все словари (кажется на 256 элементов) во время поиска имя ищется по сути сразу во всех словарях, после нахождения проверяется в контексте ли оно.
В форке я поступил не так, собственно, там я отдал это дело на откуп каждому словарю. Хеширование используется в статических словарях, и выигрыш в скорости таки заметный. Была еще идея перед поиском выкидывать из контекста дубли, собственно после каждой операции с контекстом надо по хорошему строить теневой контекст без дублей, но руки пока не дошли до этого.
Однако, хочу сказать, что ускорение поиска не очень важная и не самая ценная для меня вещь. В конце концов я могу разбить(и делаю это) имена на множество словарей и управляя контекстом сильно сокращать просматриваемые списки.
[quote="Victor__v"]Лучше делать это время от времени вариант создать врем.словарь из которого парсится какой-то файл с форт-исходниками. И слова с наибольшей частотой ищутся в текущих контекстах. И цепочка слов меняется. Оформляем в виде скрипта и запускаем время от времени[/quote] ну, тут всегда есть поиск компромисса между сложностью реализации, объемом кода и выигрышем. Пока что именно хеширование выглядит с этой точки зрения оптимальным: сложность реализации практически никакая, проигрыш по занимаемой памяти очень невелик, к тому же(кажется в СПФе это сделано) можно подготавливать хеш список после добавления словаря в контекст, но это требует использования динамической памяти.
[quote="Victor__v"]Можно, к примеру хешировать входную строку и в зависимости от типа хеша ( положительное/отрицательное) выбирать нить[/quote] блин, ну так же и делается, имя скармливается (кстати не обязательно все, можно и первые 4 символа) хеш-функции, она возвращает номер цепочки, и дальше либо добавляется в словарь либо ищется в нем. Обычно количество цепочек кратно степени двойки - так проще считать хеш.
|
|
|
|
Добавлено: Пн июн 26, 2017 12:22 |
|
|
|
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Цитата: Кстати, были варианты ускорения поиска за счет постоянного перетаскивания искомых имен в начало цепочки Угу, здесь тоже предлагалось. Но как делать это постоянно?Поле статистики ввести что-ль для слов.статьи? Или есть ещё варианты? Лучше делать это время от времени вариант создать врем.словарь из которого парсится какой-то файл с форт-исходниками. И слова с наибольшей частотой ищутся в текущих контекстах. И цепочка слов меняется. Оформляем в виде скрипта и запускаем время от времени Цитата: так, в том то и дело, что разбиение списка имен на несколько цепочек(тред) сильно укорачивает просматриваемый список. Это понятно, что легче перебрать 1 из 4 списоков по 10-эл-тов чем 1 список в котором 40. Можно, к примеру хешировать входную строку и в зависимости от типа хеша ( положительное/отрицательное) выбирать нить Кстати, интересно посмотреть будет на форт-систему, где реализовано большинство идет в ЭТОЙ ТЕМЕ. на больших словарях, спору нет, ускорение будет, но на мелких ( слов ~100 ) будет замедление
[quote]Кстати, были варианты ускорения поиска за счет постоянного перетаскивания искомых имен в начало цепочки[/quote] Угу, здесь тоже предлагалось. [b]Но как делать это постоянно?[/b] Поле статистики ввести что-ль для слов.статьи? Или есть ещё варианты? Лучше делать это время от времени вариант создать врем.словарь из которого парсится какой-то файл с форт-исходниками. И слова с наибольшей частотой ищутся в текущих контекстах. И цепочка слов меняется. Оформляем в виде скрипта и запускаем время от времени
[quote]так, в том то и дело, что разбиение списка имен на несколько цепочек(тред) сильно укорачивает просматриваемый список.[/quote] Это понятно, что легче перебрать 1 из 4 списоков по 10-эл-тов чем 1 список в котором 40. Можно, к примеру хешировать входную строку и в зависимости от типа хеша ( положительное/отрицательное) выбирать нить Кстати, интересно посмотреть будет на форт-систему, где реализовано большинство идет в ЭТОЙ ТЕМЕ. на больших словарях, спору нет, ускорение будет, но на мелких ( слов ~100 ) будет замедление
|
|
|
|
Добавлено: Вс июн 25, 2017 00:00 |
|
|
|
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Victor__v писал(а): Цитата: сомневаюсь - надо доказать Ну-ну. в смысле не код показать, а замерить время поиска для разных решений. Victor__v писал(а): Единственная затрата это хеширование строки на входе. Если в словаре мало слов ( ~30 ) то возможно COMPARE будет быстрей. Всё ж у сравнения хешей затрат на 1-ну итерацию будет меньше. так, в том то и дело, что разбиение списка имен на несколько цепочек(тред) сильно укорачивает просматриваемый список. Кстати, были варианты ускорения поиска за счет постоянного перетаскивания искомых имен в начало цепочки... В смысле, чем чаще встречается имя в тексте, тем ближе к началу списка оно находится.
[quote="Victor__v"]Цитата: сомневаюсь - надо доказать Ну-ну.[/quote] в смысле не код показать, а замерить время поиска для разных решений. [quote="Victor__v"]Единственная затрата это хеширование строки на входе. Если в словаре мало слов ( ~30 ) то возможно COMPARE будет быстрей. Всё ж у сравнения хешей затрат на 1-ну итерацию будет меньше.[/quote] так, в том то и дело, что разбиение списка имен на несколько цепочек(тред) сильно укорачивает просматриваемый список.
Кстати, были варианты ускорения поиска за счет постоянного перетаскивания искомых имен в начало цепочки... В смысле, чем чаще встречается имя в тексте, тем ближе к началу списка оно находится.
|
|
|
|
Добавлено: Сб июн 24, 2017 22:35 |
|
|
|
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Цитата: а что делать с одинаковыми именами? А что с ними надо делать? Какое будет определено позднее, такое и будет выдано. Цитата: сомневаюсь - надо доказать Ну-ну. Код: L>HashFA @ OVER = IF .... L>NFA @ COUNT 2OVER COMPARE 0= IF
Единственная затрата это хеширование строки на входе. Если в словаре мало слов ( ~30 ) то возможно COMPARE будет быстрей. Всё ж у сравнения хешей затрат на 1-ну итерацию будет меньше. Цитата: в уме много чего дает неплохой выигрыш Опять же реализовать бит.маску в словаре очень просто. Для пущего быстродействия можно хоть на асме написать . Затрата только в начале поиска, в итерации не участвует. Словарь делает одно из трёх: а) у меня есть такое слово, счас найду б) у меня нет такого слова, и не просите в) Это? Не знаю. Счас поищу.
[quote]а что делать с одинаковыми именами?[/quote] А что с ними надо делать? Какое будет определено позднее, такое и будет выдано.
[quote]сомневаюсь - надо доказать[/quote] Ну-ну. [code] L>HashFA @ OVER = IF .... L>NFA @ COUNT 2OVER COMPARE 0= IF
[/code]
Единственная затрата это хеширование строки на входе. Если в словаре мало слов ( ~30 ) то возможно COMPARE будет быстрей. Всё ж у сравнения хешей затрат на 1-ну итерацию будет меньше.
[quote]в уме много чего дает неплохой выигрыш[/quote] Опять же реализовать бит.маску в словаре очень просто. Для пущего быстродействия можно хоть на асме написать :) . Затрата только в начале поиска, в итерации не участвует. Словарь делает одно из трёх: а) у меня есть такое слово, счас найду б) у меня нет такого слова, и не просите в) Это? Не знаю. Счас поищу.
|
|
|
|
Добавлено: Сб июн 24, 2017 11:19 |
|
|
|
|
|
Заголовок сообщения: |
Re: Ускорение поиска в словарях |
|
|
Victor__v писал(а): В моей системе ( которая пишется :) ) хеширование используется для создания уникального идентификатора слова. а что делать с одинаковыми именами? Вообще, уникальным в словарной статье будет только LFA, поэтому в форке я и сделал его базой, относительно которой можно найти все остальные части определения. Victor__v писал(а): Всё равно быстрее чем сравнивать строки посимвольно. сомневаюсь - надо доказать. Victor__v писал(а): А битовая маска при компиляции в уме даёт неплохой выигрыш. в уме много чего дает неплохой выигрыш... Только не подумайте, что я против поиска оптимального решения ;)
[quote="Victor__v"]В моей системе ( которая пишется :) ) хеширование используется для создания уникального идентификатора слова. [/quote] а что делать с одинаковыми именами? Вообще, уникальным в словарной статье будет только LFA, поэтому в форке я и сделал его базой, относительно которой можно найти все остальные части определения.
[quote="Victor__v"]Всё равно быстрее чем сравнивать строки посимвольно.[/quote] сомневаюсь - надо доказать. [quote="Victor__v"] А битовая маска при компиляции в уме даёт неплохой выигрыш.[/quote] в уме много чего дает неплохой выигрыш...
Только не подумайте, что я против поиска оптимального решения ;)
|
|
|
|
Добавлено: Пт июн 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 бита, то бит от символа А будет равен биту от символа ! , поэтому приходится использовать две ячейки для более корректной организации. Продолжать не стал т.к. использование малых букв, русских букв и псевдографики очень маловероятно.
[quote="_KROL"][quote]Какие-то странные мысли уже пошли, не находишь?[/quote] Прости, теперь я вроде тебя понял. Ты пытаешься делить таблицу сканкодов на части. Это в принципе можно делать и для слов. Например: 16-бит: FEDCBA98|76543210 0 - 00 - 0F 1 - 10 - 1F ... 32-бита: ...|FEDCBA98|76543210 0 - 00 - 07 1 - 08 - 0F ... Т.е. я могу внести доп. ячейку для ускорения поиска(но это действительно не хеш функция). Спасибо за идею![/quote]
Можно скачать исходники моего форта и посмотреть там. Папки \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 бита, то бит от символа [b]А[/b] будет равен биту от символа [b]![/b] , поэтому приходится использовать две ячейки для более корректной организации. Продолжать не стал т.к. использование малых букв, русских букв и псевдографики очень маловероятно.
|
|
|
|
Добавлено: Пт июн 23, 2017 07:27 |
|
|
|
|