Forth и другие саморасширяющиеся системы программирования Locations of visitors to this page
Текущее время: Чт ноя 15, 2018 06:36

...
Google Search
Forth-FAQ Spy Grafic

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




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

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 649
Благодарил (а): 0 раз.
Поблагодарили: 6 раз.
Поиск в словарях можно ускорить разными способами.
1) Наличие поля для хранения хеша от имени слова.
Недостатки: возможность коллизии если слов больше миллиарда ( 32бит) :)
Затрата на хеширование во время поиска слова.
1.1) Хешируем по условию.
Если длина слова меньше 5 байт, то можно в поле для хеша хранить имя слова в виде числа.
Недостатки: возможность увеличения кол-ва коллизий.
1.2) Тот же вариант что и 1.1 но уже для проверки используем поле NFA

2) Поля у словаря, в которых содержатся длина самого короткого и длинного определений.
Возможно существенное ускорение поиска.

3) Собираем статистику по словам. И часто используемые продвигаем в начало списка.

Ещё варианты?

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


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

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 4954
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 18 раз.
Поблагодарили: 56 раз.
Victor__v писал(а):
Ещё варианты?

разбиение программы на много мелких лексиконов 8) т.е. словарей.
бинарное дерево
но, привычно хеширование, а насчет коллизий, так на них плевали всегда, таки советую почитать: хеширование в форте

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


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

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 649
Благодарил (а): 0 раз.
Поблагодарили: 6 раз.
Насчёт бинарного дерева не понял.
Это вообще как может выглядеть?
Первое что идёт на ум - пересобрать список слов по какому-то признаку ( какому? ) И отталкиваться уже от него.

mOleg писал(а):
привычно хеширование, а насчет коллизий, так на них плевали всегда

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

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


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

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

см. бинарный поиск.
Victor__v писал(а):
Первое что идёт на ум - пересобрать список слов по какому-то признаку ( какому? )

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

и? я не ссылался. Вообще, эти самые коллизии из пальца высосаны в отношении поиска.
Ты просто укорачиваешь цепочку в которой ищешь.
длины хэша в один бит достаточно, чтобы ускорить поиск в словаре почти в два раза 8)

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


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

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 649
Благодарил (а): 0 раз.
Поблагодарили: 6 раз.
mOleg писал(а):
Victor__v писал(а):
Насчёт бинарного дерева не понял

см. бинарный поиск.
Victor__v писал(а):
Первое что идёт на ум - пересобрать список слов по какому-то признаку ( какому? )

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

и? я не ссылался. Вообще, эти самые коллизии из пальца высосаны в отношении поиска.
Ты просто укорачиваешь цепочку в которой ищешь.
длины хэша в один бит достаточно, чтобы ускорить поиск в словаре почти в два раза 8)


А, теперь понял.
1) пусть у каждого словаря будет массив где хранятся хеши от имени функций и их LFA. и уже производить бинарный поиск в массиве.
Недостатки: при каждом новом определении придётся сортировать по новой. Где расположить массив? Самый оптимальный вариант в хипе. Но опять же проблема возникнет если в конечной программе используется поиск по словарям. Это решаемо, конечно, но писать менеджер памяти для бинарного поиска в словарях....

Какой ещё возможен вариант? Более элегантный и не поедающий за раз ресурсы, на которые многим пофиг?

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


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

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

8) только я имел ввиду другое
Victor__v писал(а):
пусть у каждого словаря будет массив где хранятся хеши от имени функций и их LFA. и уже производить бинарный поиск в массиве

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

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

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


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

Зарегистрирован: Ср фев 23, 2011 20:42
Сообщения: 521
Откуда: Карелия
Благодарил (а): 3 раз.
Поблагодарили: 22 раз.
Victor__v писал(а):
1) пусть у каждого словаря будет массив где хранятся хеши от имени функций и их LFA.
Пусть у каждого имени в словаре будут кроме указателя LFA еще два указателя (как две ветки у дерева, левая и правая) - один в сторону меньших имен, другой в сторону больших. В результате словарь будет двоичным деревом, причем еще и отсортированным. Остается только продумать функцию вставки нового элемента в это дерево так, чтобы оно выходило максимально сбалансированным. Думаю так - если в словарь вставляется слово такое, что оно больше того на которую указывает левая ветка от вершины и меньше того на которое указывает правая, то надо прикинуть что ближе к среднему арифметическому левой и правой веток - старая вершина или новое слово. Если ближе новое, то нужно его сделать вершиной. И вот так вот действовать на любом разветвлении дерева. Что-то типа того.
Ну а уж поиск по этому дереву очевиден и максимально быстр. Быстрее не бывает.
mOleg писал(а):
И, да, никаких динамических памятей 8)
Вот именно так. Никаких дополнительных памятей-шмамятей, никаких лишних массивов-шмассивов и боже упаси какие-то хеши-шмеши. Два дополнительных указателя у каждого элемента и все.


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

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 649
Благодарил (а): 0 раз.
Поблагодарили: 6 раз.
Ещё один вариант дополнительные поля в словаре и словах по движению от слова с минимальным именем к максимальному и наоборот.
И при поиске слова рассчитывается как ближе получится добраться. От минимума или от максимума?
И потом скачем от выбранного указателя minLFA или maxLFA.
Недостатки: Перетряхивать 2 списка при определении слова. Слабый эффект, если имёна по длине не сбалансированы. Мелких 8 больших 100.

Это, так сказать, облегчённый вариант 8) написанного выше

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


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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 6435
Благодарил (а): 14 раз.
Поблагодарили: 101 раз.
Замечательная по своей эффективности пустая затея :) Можно подумать, основная претензия к Форту заключается в том, что он слишком медленно обрабатывает тексты. Но если на этот факт закрыть глаза, то можно потратить кучу времени на обсуждение списков, хэшей и прочих улучшений. Вроде бы дело движется, потому что обсуждение активное... а Форта что-то больше не становится.


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

Зарегистрирован: Чт май 04, 2006 00:53
Сообщения: 4954
Откуда: был Крым, теперь Новосибирск
Благодарил (а): 18 раз.
Поблагодарили: 56 раз.
Ethereal писал(а):
Пусть у каждого имени в словаре будут кроме указателя LFA еще два указателя (как две ветки у дерева, левая и правая)

только нужно еще придумать, что делать с переопределением имен.

Ethereal писал(а):
Два дополнительных указателя у каждого элемента и все.

и более сложное в реализации бинарное уравновешенное дерево.

Кстати, хеш-списки таки на большом количестве имен будут компактнее, т.к. адресная ссылка на предыдущее слово одна + размер хеш-таблицы + меньший объем кода, необходимого для реализации поиска по списку.
так вот, на хеш-списке в 256 элементов выигрыш в объеме служебной части словаря получится уже на 257 определении 8)

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


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

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 649
Благодарил (а): 0 раз.
Поблагодарили: 6 раз.
Hishnik писал(а):
Замечательная по своей эффективности пустая затея :) Можно подумать, основная претензия к Форту заключается в том, что он слишком медленно обрабатывает тексты. Но если на этот факт закрыть глаза, то можно потратить кучу времени на обсуждение списков, хэшей и прочих улучшений. Вроде бы дело движется, потому что обсуждение активное... а Форта что-то больше не становится.


Код:

REQUIRE MOVr-im-r ~ER\ASM\MINI-ASM.F


HEADER LY
   ECX EAX MOVr-r
   ESI 0 [EBP] MOVr-im-r
   EAX EAX XORr-r
   EDX 1664525 MOVr-im
   EBX EBX XORr-r
   Mark1
      EAX EDX IMULr-r
      0x8A C, 0x1E C, \ BL [ESI] MOVr-r
      EAX EBX ADDr-r
      EAX 1013904223 ADDr-im
      ESI INC
      ECX DEC
      Mark1 JNE SHORT >Jcc
   EBP CELL LEA+-
   RET



Ну как?Форта стало больше? :D

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


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

Зарегистрирован: Чт янв 07, 2016 19:14
Сообщения: 649
Благодарил (а): 0 раз.
Поблагодарили: 6 раз.
Код:

: LY
  0 SWAP 0 DO
   1664525 * OVER I + C@ + 1013904223 +
   LOOP NIP
;



А сейчас? :)

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


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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 6435
Благодарил (а): 14 раз.
Поблагодарили: 101 раз.
Victor__v писал(а):
Ну как?Форта стало больше?

Ассемблер вижу. Еще вижу персональное желание приписать процессу кодирования Глубокий Смысл, чтобы не так скучно было. Через определенное время все это забудется.


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

Зарегистрирован: Пн ноя 05, 2007 13:54
Сообщения: 136
Благодарил (а): 0 раз.
Поблагодарили: 11 раз.
Я догадываюсь, что Хищник больше пишет для read-only-читателей форума, а не для нескольких активистов, которые опять что-то самозабвенно и вопреки всему "шуруют" :)

Вот и я оставлю следующую цитату для тех самых молчаливых читателей.

Код:
Compilers construct symbol tables. They are built up while processing declarations, and
they are searched during the processing of statements. In languages that allow nested
scopes, every scope is represented by its own table.

Traditionally these tables are binary trees in order to allow fast searching. Having also
quietly followed this long-standing tradition, the author dared to doubt the benefit of trees
when implementing the Oberon compiler. As soon as doubts occur, one is quickly
convinced that tree structures are not worth while for local scopes. In the majority of
cases, procedures contain a dozen or even fewer local variables. The use of a linked
linear list is then both simpler and more effective.

In programs 30 and 40 years ago, most variables were declared globally. So perhaps a
tree structure was justified for the global scope. In the meantime, however, skeptizism
against the value of global variables had been on the rise. Modern programs do not
feature many globals, and hence also in this place a tree structured table is hardly
recommendable.

Modern programming systems are compositions of many modules, each of which
probably contains some globals (mostly procedures), but not hundreds. The many globals
of early programs have become distributed over many modules and are referenced not by
a single identifier, but by a name combination M.x defining the initial search path.
The use of sophisticated data structures for symbol tables had evidently been a poor idea.
Once we had even considered balanced trees!


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

Зарегистрирован: Вт май 02, 2006 22:48
Сообщения: 6435
Благодарил (а): 14 раз.
Поблагодарили: 101 раз.
Я даже еще и усугублю! :D Не является ли чрезмерная тяга к "модным" программным технологиям признаком зависимости от навязываемых устаревших концепций?


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

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


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

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


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

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