Immutable Trie: найди то, не знаю что, но быстро, и не мусори

[DistortNeo]

Как разминка для мозгов — нормально.

Но в реальности такое никто делать не будет, потому что код сложный, логика работы неочевидная, правки потребуют построения нового дерева, да и эффективность сомнительна. Количество одинарных сравнений символа — странная метрика, так как проход по дереву, индексация требуют гораздо больше ресурсов, особенно в случае использования JS. Сравнение двух подстрок длиной в 50 символов, возможно, будет даже быстрее, чем извлечение из них 3 символов и сравнение только этих символов.

Так что я бы сделал более наивную реализацию: тупо разбивал строку по пробелам на неделимые слова и строил дерево, сравнивая только слова.

[Kilor]

такое никто делать не будет, потому что код сложный, логика работы неочевидная, правки потребуют построения нового дерева, да и эффективность сомнительна

Я просто покажу разницу в работе GC относительно предыдущей «наивной» реализации со .slice и рекурсией — она стоит и усложнения кода:



Или вот CPU-нагрузка — уменьшилась в среднем примерно на 10% (14.37 -> 13.02), существенно меньше стало «биение»:

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

Разбиение на слова порождает новый объект массива, а этого как раз и не хочется при поиске.

[DistortNeo]

Я из этого графика не понимаю проблемы. По оси Y Mns — это мега-нано-секунды, или миллисекунды, если переводить на человеческий язык. Но за какой период собирается эта статистика?

[Kilor]

Это вот эти показатели работы GC:
medium.com/@andrejsabrickis/monitor-node-application-garbage-collection-8e92980bb855
Можно особо даже не всматриваться в значения, достаточно профиля графика: больше — хуже/дольше.

[mayorovp]

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

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

function find(str, off) {
    switch (str.charCodeAt(off+2)) {
        case 100:
            switch (str.charCodeAt(off+6)) {
                case 79:
                    if (str.startsWith("Index Only Scan Backward", off))
                        return "Index Only Scan Backward";
                    if (str.startsWith("Index Only Scan", off))
                        return "Index Only Scan";
                break;
                case 83:
                    if (str.startsWith("Index Scan Backward", off))
                        return "Index Scan";
                    if (str.startsWith("Index Scan", off))
                        return "Index Scan";
                break;
            }
        break;
        case 115:
            if (str.startsWith("Insert", off))
                return "Insert";
        break;
    }
}

[Kilor]

почему структура данных в итоге названа trie

Потому что полностью подходит под определение: «Префиксное дерево — структура данных, позволяющая хранить ассоциативный массив, ключами которого являются строки. Представляет собой корневое дерево, каждое ребро которого помечено каким-то символом так, что для любого узла все рёбра, соединяющие этот узел с его сыновьями, помечены разными символами.»

почему бы не нагенерить из такого дерева код заранее?

Когда-то очень давно, еще в школе, мы тоже писали на Pascal программу-генератор QuickSort'а IF'ами, но это из серии материалов для другого хаба. :)
Впрочем, не исключаю, что и до этого дойдем когда-нибудь.

[mayorovp]

Вот только trie — это не абстрактная структура данных, а конкретная. Не любое дерево, подходящее под это определение, является trie.

[Kilor]

Структурно, это как раз сжатое префиксное дерево. А уж как именно я его сжимаю, определение не описывает.

[mayorovp]

Ну нет. В сжатом префиксном дереве в каждом узле хранится некоторая подстрока, по котором можно построить текущий префикс если идти из корня. А у вас строки только в листах хранятся.

Кстати, формат именно сжатого бора для задач подобных вашей как раз нежелателен, поскольку ограничивает возможности оптимизации. Например, для следующего гипотетического случая — "aaa, aab, aac, ddd, eee" сжатый бор обязан выделить общий префикс "aa", в то время как оптимальным решением будет начинать проверку сразу с третьего символа не выделяя никаких префиксов.

[Kilor]

Собственно, именно так и отработает алгоритм — сначала выделит длину общего префикса 'aa', начнет проверку с 3-го символа, а потом перепроверит, является ли найденное префиксом.