Префиксное дерево trie низкоуровневая структура данных в PHP

--- Добавлено ---
это профиль поиска 1 слова человек в готовом словаре.
--- Добавлено ---
Из долгого в порядке убывания, не считая времени открытия и загрузки словаря:
node_get_children() - получение маски узла по его id, функция включает в себя расчет номера элемента в массиве где записана нужная часть словаря. тут используется деление и floor().
Потом идет substr() для чтения строки маски. Дальше unpack_48() - распаковывает 48 битную строку функцией для 64 битной, дополняя недостающие байты нулями.
split_rus() - делит русское слово по буквам. Работает быстрее, чем preg_split().

Из элементарных функций самые затратные в порядке убывания:
unpack()
floor()
str_pad()
substr()
bin2hex()
--- Добавлено ---
Вот что нашел вчера.
https://github.com/php-ds

 

https://github.com/php-ds

Dj

это fread() только для сжатых gzip файлов.

 

Без gz 150мб.

Отказаться от всего это - хорошая идея. Только как? Чем заменить floor(a/b) еще можно придумать. Но как обойтись без str_pad()? Там сейчас есть 2 ключевые функции, в которых str_pad() задействован. unpack_24() и unpack_48(). В обоих случаях принцип работы такой. Поскольку pack() unpack() понимает только 8, 16, 32, 64 и битные числа, то для распаковки числа 24 битной длины используется формат 32 битной. str_pad() тут заполняет недостающие байты нулями.
Было бы здорово заменить. Все что мне попадалось для pack unpack 24 и 48 битных строк тоже было со str_pad(), но еще сложнее.


bin2hex() используется в функции split_rus(), русские буквы бывают в utf8 2-мя байтами записаны, а бывают тремя, Вот там функция строку по 2 байта делит, и каждый кусочек с таблицей hex значений русских букв сравнивает, если не находит, то пытается 3 байта поискать.

В сущности bin2hex() для наглядности сделано:

Код (Text):

1. $hex = bin2hex(substr($word, 0, 2));

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

 

На коротких строчках substr() довольно быстро работает. Попытаюсь все таки сделать переменную длину узла, может не будет сильно тупить, а объём сократится в разы. Сейчас 75тыс. слов в секунду, если около 50 будет - успех.

 

Как так сделать?

Так и сделаю.

На примере буквы 'а'

Код (Text):

1.  
2. $str = 'а';
3. $hex = chr(0xd0).chr(0xb0);
4. $bin = chr(0b11010000).chr(0b10110000);
5.  
6. print "str:$str hex:$hex bin:$bin \n";

--- Добавлено ---
Все таки придется делать тесты. По полчаса ковыряюсь с такой ерундой, что даже обидно. Начал запиливать тесты.

 

Все таки придется делать тесты. По полчаса ковыряюсь с

Все преобразования были лишними. Исправил, спасибо.

Ты сказал, что можно как-то обойтись без str_pad(). Как это можно сделать?

 

Выжал чуть больше попугаев из unpack.
Число длиной 6 байт.

4.1861s на 1 млн. операций

Код (Text):

1.  
2. function unpack_mod(string $str)
3. {
4.     return hexdec(strrev(unpack('h*', $str)[1]));
5. }

4.2747s на 1 млн. операций

Код (Text):

1.  
2. function unpack_48(string $str)
3. {
4.     return unpack('P', str_pad($str, 8, "\0"))[1];
5. }

Прирост скорости 2.07%

Можно ли еще быстрее?
--- Добавлено ---

Я что-то такое пробовал уже. Тогда не получилось.
--- Добавлено ---
Термин даже есть у этой процедуры. https://en.wikipedia.org/wiki/Sign_extension

 

Термин даже есть у этой проценд

Саму сдвижку и переключение битов я сделал вроде бы правильно, т.е. побитовыми операциями можно более короткое число сделать более длинным в двоичном представлении. Само двоичное число сделать не проблема. Проблема в том, чтобы как-то распаковать строку длиной 6 байт. Именно там относительно долгий str_pad() используется.

Вот у меня такая упакованная строка 4Vx�, что с ней сделать, чтобы ее взял как родную 64 битную unpack?

 

Занимательная фигня.

Спойлер

Код (Text):

1.  
2. function unpack_mod(string $str)
3. {
4.     return hexdec(strrev(unpack('h*', $str)[1]));
5. }
6.  
7. function unpack_48_mod2(string $str)
8. {
9.     $ar = unpack("C*", $str);
10.     return ($ar[6] << 48) + ($ar[5] << 36) + ($ar[4] << 24) + ($ar[3] << 16) + ($ar[2] << 8) + ($ar[1]);
11. }
12.  
13. function unpack_24_mod2(string $str)
14. {
15.     $ar = unpack("C*", $str);
16.     return ($ar[3] << 16) + ($ar[2] << 8) + ($ar[1]);
17. }
18.  
19. function unpack_48(string $str)
20. {
21.     return unpack('P', str_pad($str, 8, "\0"))[1];
22. }
23.  
24. function pack_48(int $i)
25. {
26.     return substr(pack('P', $i), 0, 6);
27. }
28.  
29. function pack_24(int $i)
30. {
31.     return substr(pack('V', $i), 0, 3);
32. }
33. function unpack_24(string $str)
34. {
35.     return unpack('V', str_pad($str, 4, "\0"))[1];
36. }

Вот результаты тестов:

Код (Text):

1.  
2. Array
3. (
4.     [times] => 100000
5.     [int3] => Array
6.         (
7.             [int3] => 15599999
8.             [str3] =>  ▒
9.             [pack_24_hex] => 7f09ee
10.             [unpack_24] => 15599999
11.             [unpack_mod] => 15599999
12.             [unpack_24_mod2] => 15599999
13.         )
14.  
15.     [int6] => Array
16.         (
17.             [int6] => 1234567890
18.             [str6] => ▒▒I
19.             [pack_48_hex] => d20296490000
20.             [unpack_48] => 1234567890
21.             [unpack_mod] => 1234567890
22.             [unpack_48_mod2] => 1234567890
23.         )
24.  
25. )
26. Array
27. (
28.     [int6] => Array
29.         (
30.             [unpack_48] => 0.41487097740173
31.             [unpack_mod] => 0.4118549823761
32.             [unpack_48_mod2] => 0.48053193092346
33.         )
34.  
35.     [int3] => Array
36.         (
37.             [unpack_24] => 0.24093008041382
38.             [unpack_mod] => 0.241858959198
39.             [unpack_24_mod2] => 0.25665903091431
40.         )
41.  
42. )

Первый массив со входными данными, второй массив с результатами тестов.

Видимо вызов unpack самый дорогой тут, потому что в первых 2 функциях он вызывается как бы однократно для большого числа, а в последней функции - по числу байт.

 

Я не понял как надо сделать. Т.е. хочешь сказать, что надо двигать прямо строку?
--- Добавлено ---

Там же строка на входе перед анпэком.
--- Добавлено ---

Код (Text):

1.  
2. <?php
3. $s = pack('C', 244);
4. Print $s[0] << 0;

Так не работает, просит число, чтобы двигать.

 

Получилось быстрее.

Код (Text):

1.  
2.     [int6] => Array
3.         (
4.             [unpack_48] => 0.45364308357239
5.             [unpack_mod] => 0.43855810165405
6.             [unpack_48_mod2] => 0.46687388420105
7.             [unpack_48_mod3] => 0.40635180473328
8.         )

на 7.3% быстрее самого быстрого способа.

 

Выходит unpack, вообще нет смысла использовать.

Сделал по аналогии вместо pack.

Код (Text):

1.  
2. function pack_24_mod(int $i)
3. {
4.     return chr($i & 0xFF) . chr(($i >> 8) & 0xFF) . chr(($i >> 16) & 0xFF);
5. }
6.  
7. function pack_24(int $i)
8. {
9.     return substr(pack('V', $i), 0, 3);
10. }

Код (Text):

1.  
2.             [pack_24] => 0.21841502189636
3.             [pack_24_mod] => 0.22249889373779

--- Добавлено ---

Сейчас допишу для остальных функций. Пока сделал для всех элементарных функций тесты.
--- Добавлено ---

strpad() получается больше не нужен, он был как раз в unpack, это единственное его место.

 

Делать тесты оказалось сложнее, чем делать то, что они проверяют. В процессе написания тестов пришлось даже рефакторить код, чтобы пройти тесты. Но зато теперь покрытие тестами 92% и в ходе их написания было выявлено кажется 2 ошибки.

Надо все таки попробовать хотя бы раз сделать сначала тест, а потом код.