Теперь покрытие тестами 100% кода, осталось уменьшить словарь до приличных размеров и можно наконец попробовать его использовать в в морфологическом анализаторе.
ок давай дальше коверкать прогони бенчи, скажи, где самое медленное место скрипта --- Добавлено --- public function &trie(int $id) а что значит амперсанд пере функцией? --- Добавлено --- это что делает? PHP: /** * @param int $size * @return string */ public function str_pad_null(int $size = 0) { return str_repeat("\0", $size); }
Ампенданс перед функцией означает, что функция возвращает ссылку, а не значение. Этот метод trie() своего рода роутер, он возвращает конкретный блок в котором искомый узел лежит. Функция str_pad_null() работает при инициализации пустого словаря. Т.е. когда не готовый словарь есть, а новый создаётся. Она делает узлы первого алфавита, там проверок нигде нет, поэтому первые 46 узлов создаются сразу пустыми. Можно и убрать, но это очень редкая функция, работает 1 раз при инициализации словаря.
эта балалайка встречается в двух местах в твоём алгоритме PHP: $this->node_make(); функция имеет кучу параметров, а вызывается всего в двух местах и только без параметров. подумай. --- Добавлено --- хм, ок. я всегда при ретурне ставлю амперсанд. пофик. --- Добавлено --- подумай
PHP: /** * @param int $i * @return bool|string */ public function pack_24(int $i) { return substr(pack('V', $i), 0, 3); } добавь описание функции. а то я бы по описанию понял, что она сама по себе делает и возможно присоветовал бы что-то для оптимизации а так я не понимаю что она делает и не хочу думать --- Добавлено --- вывод? --- Добавлено --- тоже опиши плс, а то я не понимаю
154 байта на узел - перебор явный, надо переделать. У меня словарь сейчас на ~380 тыс. Слов с размером 150мб, если эти же слова просто в txt списком сделать можно в 15 уложиться. --- Добавлено --- Все функции pack unpack для упаковки числа в бинарную строку и распаковки, соответственно. Число в названии означает для какой битности эта функция. Pack_24 пакует в 24 бита 3 байта. Pack_48 в 48 бит, 6 байт и т.д. там не все задействованы сейчас. Используется только 6 байт и 3 байта. --- Добавлено --- Т.е. сейчас по затратности самая тяжелая функция unpack_48, а следом unpack_24, первая распаковывает битовую маску узла, а вторая ссылку на следующий узел. Они и так после отказа от substr(unpack()), стали на 10% быстрее. Кажется, что их быстрее уже не сделаешь.
Надо бы придумать функцию, которая не просто сможет поднятые биты считать, такая уже довольно быстрая функция есть. Нужна такая, которая сможет считать биты до определенного. Т.е. например у нас есть 48 бит "11111111 11111111 11111111 11111111 11111111 11111110" и все подняты кроме первого. Вот надо как-то придумать быструю функцию, которая сможет посчитать поднятые биты с 1 по 8. Если сейчас оптимизировать для уменьшения размера узла, то эта функция будет необходима для определения адреса ссылки в узле. Вот к примеру у нас есть слово "гдр" в словаре, смотрим 4 узел, который у буквы г, там поднят 5 бит от буквы д, теперь надо адрес узла получить. В существующей схеме, мы просто перемещается на 5 * 3 байта вперед и читаем адрес. Если же сделать сделать размер узла переменным, то количество ссылок будет зависеть от кол-ва поднятых бит, поэтому нужно будет постоянно считать число поднятых бит до определенного. Самое простое у меня уже есть, я сейчас так и попробую сделать: Код (Text): function bit_count($mask, $length = null){ return substr_count(decbin($mask), '1', 0, $length); }
1. с этого дня давай договоримся, что все операции с битами происходят как операции с битами без конвертации в строки. 2. для подсчета числа битов в числе можно пойти как минимум двумя путями: сдвигом и через &. Через & в php будет проще всего, скорость должна быть весьма большой. Алгоритм такой: берёшь маску по твоему примеру это 111111110...0, т.е. маска это такое ЧИСЛО, А НЕ СТРОКА которая имеет поднятые нужные биты заранее. делаешь операцию & исходного и маски. Результат получит только те единички, где и там и там были единички. Т.е. маска позволяет указать те биты, которые нас интересуют, а & вернёт только те биты, которые на этих местах подняты. считаешь число битов в результате предыдущей операции. Как считать? https://stackoverflow.com/questions/16848931/how-to-fastest-count-the-number-of-set-bits-in-php https://stackoverflow.com/questions/5357932/count-the-number-of-set-bits-in-an-integer но я считаю, что можно подууумать и сделать допустим для всех комбинаций 00000000-11111111 просто массив (это всего 256 элементов) который по ord() байта или прямо по ключу-байту (тут надо проверить, не будет ли коллизий) будет тупо сразу иметь число. =) Т.е. заранее посчитать число битов во всех байтах с 0 по 256 и хардкодить это в массив во веки веков. Это должно быть быстрее всего. нужно только найти способ через маску и смещение получить нужный кусок из многобитной последовательности. это тоже несложно - нужно просто сдвинуть оригинал на нужно число бит вправо плюс натравить маску, начинающуюся с нулей, а заканчивающуюся нужным числом битов, которые нужно прочесть. полученное число/байт сразу в массив или в функцию подсчета битов из примеров выше и получаешь результат почти мгновенно и никаких перегонов в строку
Не все понял. Сейчас ломаю голову вот с чем: Сейчас место расходуется очень неэкономно. Все работает, работает достаточно быстро, но словарь надо загрузить в память сначала, а большой объем долго загружается. Даже если весь словарь русских слов загрузить, а это 3.02 млн. слов, то использование места все равно очень расточительное. Весь словарь занимает 650мб, т.е. лучше чем 150мб на 0.4млн. слов. В общем надо-то что-то придумать. Предположим, что нужно добавить ссылку в узел, который сейчас занимает 6 байт маска +3 байта 1 ссылка. Нужно или сдвинуть все узлы после него, тогда там ссылки поплывут, или вытащить этот узел, дописать его в конец (по сути создать новый узел). У узла есть только 1 родитель, соответственно нужно будет изменить 1 ссылку. Но что делать с местом, которое освободилось, после того как узел переехал?
т.е. ты просто заигнорил всё, что я написал только потому, что не понял и даже решил не пытаться и не спрашивать? =) это очень демотивирует. я думаю ускорение загрузки можно делать потом, благо для этого есть всякие APCu и прочие фишки. давай ты просто сначала избавишься от строк --- Добавлено --- это вопрос такой... сложный. смотря на что ты затачиваешь свой алгоритм. если тебе важна скорость чтения с дерева, то можно "денормализовать" кучу вещей и пересчитывать их при вставке. если тебе важна скорость изменения дерева, то тогда никаких развёрнутых путей и проход по дереву всегда будет долгим, зато модификации не будут требовать пересчета других узлов, а только одного изменяемого.
Сори, просто не успел переварить все что там написано. 1. Отказаться от строк. Что тут можно сказать? Согласен. 2. По поводу способа считать поднятые биты. Вот такой, довольно быстрый счетчик уже есть. Код (Text): function bit_count(int $bmask) { $cnt = 0; while ($bmask != 0) { $cnt++; $bmask &= $bmask - 1; } return $cnt; } Тут я понял, но смутно. Надо попробовать. Тут я не понял.
Вот сделал по этой методе. Код (Text): function bit_count(int $bmask, $length = null) { if($length !== null){ $bmask &= pow(2,$length) -1; } $cnt = 0; while ($bmask != 0) { $cnt++; $bmask &= $bmask - 1; } return $cnt; } --- Добавлено --- Вообще важно и скорость добавления и скорость чтения. Но они выполняются отдельно, т.е. когда добавляешь не обязательно, чтобы компактно было, главное чтобы быстро добавлялось. Хрен с ним, пусть он будет денормализованный. Но для чтения надо суперкомпактно сделать, чтобы быстро загружалось и искало.
я выкладывал ссылки на быстрые алгоритмы без перебора по битику и без степеней не знаю, почему они были проигнорированы
Спойлер: начало вчерашней мысли Все ломаю голову над оптимизи Что-то не понял идею. Что двигать влево? Если единицу двигать влево - будут нули с конца отрастать, а мне нужны там единицы тоже. --- Добавлено --- Вовсе нет. Я просмотрел те ссылки на стеке, которые ты дал. Просто там я не разглядел подходящего способа. Этот метод, который ты "по битику" назвал тоже там упомянут. Это кстати классный способ, он впервые был опубликован Питером Вегнером в 1960. Стэнфордские задроты сделали подборку известных способов подсчета битов на Си. Из тех, что мне удалось оттуда переписать на PHP, я взял этот метод Вегнера. https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive
возведение в степень двойки может заменяться на сдвиг если тебе надо добить единицами, то после сдвига просто | на маску с нужным числом единиц в нужных местах --- Добавлено --- там были только способы подсчета бит в байтах. и всё. никаких других тем там не обсуждались. т.е. там все способы подходящие тебе. только ты не вчитался. там и твой способ есть, просто он медленный.
Сейчас еще раз посмотрю. Пока вот что получилось. Код (Text): function bit_count_pow(int $bmask, $length = null) { if($length !== null){ $bmask &= pow(2,$length) -1; } $cnt = 0; while ($bmask != 0) { $cnt++; $bmask &= $bmask - 1; } return $cnt; } function bit_count_shift(int $bmask, $length = null) { if($length !== null){ $shift = 0; for( $i = 0; $i < $length; ++$i){ $shift += 1 << $i; } $bmask &= $shift; } $cnt = 0; while ($bmask != 0) { $cnt++; $bmask &= $bmask - 1; } return $cnt; } function bit_count_string($mask, $length = null){ return substr_count(decbin($mask), '1', $length); } А это результаты бенча на миллион повторений. Код (Text): [bit_count_pow] 2.3559739589691 [bit_count_string] 2.4681520462036 [bit_count_shift] 2.3832979202271 --- Добавлено --- Языковой барьер мешает Усилием воли заставляю себя понять смысл их тарабарской писанины.
Я там 2 годных метода разглядел: Параллельный метод Метод Вернера (aka Кернигана) Первый как раз из тех, что мне в прошлый раз не удалось повторить при переписывании с Си. Недостаток первого метода в том, что он до 32бит, если его протянуть на 48 или 64 - не факт, что он быстрее будет. Я сейчас на маленьких числах тестил, когда хочу посчитать до 25 бита к примеру, метод Кернигана побеждает. Там у оксфордцев ещё некий комбинированный метод описан я его так и не смог разобрать. Может ты сможешь, если на их мове лучше размовляешь.