Сортировка массива по "Расстоянию Левенштейна" с максимальной производительностью на JavaScript

Ваш код реализации алгоритма Левенштейна кажется довольно неплохим! Вот несколько замечаний и предложений по оптимизации, которые могли бы помочь улучшить производительность и читаемость вашего кода:

1. Инициализация матрицы: Вместо создания двумерного массива (d) с помощью вложенных массивов, можно использовать одномерный массив и обрабатывать индексы аккуратно. Это может сэкономить память и повысить скорость доступа.

2. Упрощение условий: В строке, где проверяется максимальное значение дистанции, можно упростить логику проверки, если позволяют другие условия программы.

3. Устранение повторных вычислений: Можно попробовать улучшить код, чтобы избежать не нужных вычислений (например, замены символов и их стоимости). Это может быть сделано с помощью выделения повторяющихся значений в переменные.

Ниже приведён переработанный вариант вашего кода с минимальными изменениями и комментариями:

var levDist = function(s, t) {
    var n = s.length, m = t.length;
    
    if (n === 0) return m;
    if (m === 0) return n;

    // Используем одномерный массив для хранения промежуточных значений
    var d = new Array(m + 1);
    for (var j = 0; j <= m; j++) d[j] = j;

    for (var i = 1; i <= n; i++) {
        var prev = d[0]; 
        d[0] = i;

        for (var j = 1; j <= m; j++) {
            var temp = d[j]; // Сохраняем значение до изменения
            var cost = (s.charAt(i - 1) == t.charAt(j - 1)) ? 0 : 1;
            d[j] = Math.min(d[j - 1] + 1, Math.min(d[j] + 1, prev + cost));
            prev = temp; // Присваиваем значение для следующей итерации
        }
    }

    return d[m];
}

Этот вариант должен работать быстрее и занимать меньше памяти, особенно для длинных строк. Попробуйте протестировать и посмотреть, улучшилась ли производительность вашего проверщика спеллинга!

Ваше решение выглядит очень хорошо! Этот код реализует алгоритм Левенштейна для вычисления расстояния между двумя строками, что позволяет оценить, насколько они похожи.

Вот краткое объяснение вашего кода:

1. Вы используете замыкание для создания функции levenshtein, которая инициализирует массив row2 и возвращает внутреннюю функцию.
2. Внутренняя функция принимает две строки s1 и s2 в качестве параметров.
3. Если строки одинаковые, то расстояние равно 0. Если одна из строк пустая, то расстояние равно длине другой строки.
4. Вы инициализируете массив row, который будет использоваться для хранения промежуточных результатов.
5. Весь алгоритм основывается на циклах, которые итерируют по символам строк, сравнивая их и обновляя значения в массиве row для вычисления стоимости вставки, удаления и замены.

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

Если вам нужно больше оптимизаций, вы можете изучить применение более сложных стратегий, таких как использование одномерной матрицы или сравнение нескольких символов одновременно.

Спасибо за ваше решение и ссылку на jsPerf — это отлично помогает другим лучше понять производительность алгоритма!

Обновлено: http://jsperf.com/levenshtein-distance/5

Новое обновление полностью перекрывает все предыдущие бенчмарки. Я специально искал производительность в Chromium/Firefox, так как не имею тестовой среды для IE8/9/10, но оптимизации, которые были внесены, должны применяться ко многим другим браузерам.

Расстояние Левенштейна

Матрица для вычисления расстояния Левенштейна может быть переиспользована многократно. Это был очевидный объект для оптимизации (но будьте осторожны, теперь это накладывает ограничение на длину строки, если только вы не будете динамически изменять размер матрицы).

Единственная возможность для оптимизации, которую не преследовали в Revision 5 jsPerf, — это мемоизация. В зависимости от вашего использования расстояния Левенштейна это может помочь значительно, но было упущено из-за специфической природы реализации.

// Кешируем матрицу. Обратите внимание, что эта реализация ограничена
// строками длиной 64 символа или меньше. Это можно изменить для динамического обновления
// или использовать большее значение.
var matrix = [];
for (var i = 0; i < 64; i++) {
    matrix[i] = [i];
    matrix[i].length = 64;
}
for (var i = 0; i < 64; i++) {
    matrix[0][i] = i;
}

// Функциональная реализация расстояния Левенштейна.
String.levenshteinDistance = function(__this, that, limit) {
    var thisLength = __this.length, thatLength = that.length;

    if (Math.abs(thisLength - thatLength) > (limit || 32)) return limit || 32;
    if (thisLength === 0) return thatLength;
    if (thatLength === 0) return thisLength;

    // Вычисляем матрицу.
    var this_i, that_j, cost, min, t;
    for (i = 1; i <= thisLength; ++i) {
        this_i = __this[i-1];

        for (j = 1; j <= thatLength; ++j) {
            // Проверяем текущий жёсткий ld
            if (i === j && matrix[i][j] > 4) return thisLength;

            that_j = that[j-1];
            cost = (this_i === that_j) ? 0 : 1;  // Если символы совпадают, никаких дополнительных операций.
            // Вычисляем минимум (гораздо быстрее, чем Math.min(...)).
            min    = matrix[i - 1][j    ] + 1;                      // Удаление.
            if ((t = matrix[i    ][j - 1] + 1) < min) min = t;     // Вставка.
            if ((t = matrix[i - 1][j - 1] + cost) < min) min = t;  // Замена.

            matrix[i][j] = min; // Обновляем матрицу.
        }
    }

    return matrix[thisLength][thatLength];
};

Расстояние Дамерау-Левенштейна

jsperf.com/damerau-levenshtein-distance

Расстояние Дамерау-Левенштейна — это небольшое изменение расстояния Левенштейна для учета перестановок. Оптимизировать здесь практически нечего.

// Перестановка Дамерау.
if (i > 1 && j > 1 && this_i === that[j-2] && __this[i-2] === that_j
&& (t = matrix[i-2][j-2]+cost) < matrix[i][j]) matrix[i][j] = t;

Алгоритм сортировки

Вторая часть этого ответа — выбрать подходящую функцию сортировки. Я скоро загружу оптимизированные функции сортировки на http://jsperf.com/sort.

Очевидный способ сделать это — сопоставить каждую строку с парой (расстояние, строка), затем отсортировать этот список и, наконец, снова убрать расстояния. Таким образом, вы обеспечите, что расстояние по Левенштейну вычисляется только один раз. Возможно, стоит сначала объединить дубликаты.

Я определенно рекомендую использовать более эффективный метод Левенштейна, как указано в ответе @James Westgate.

Тем не менее, манипуляции с DOM часто требуют значительных затрат. Вы можете улучшить использование jQuery.

Ваши циклы достаточно малы в приведенном выше примере, но гораздо более эффективно будет объединить сгенерированный HTML для каждого oneResult в одну строку и выполнить один append в конце цикла.

Ваши селекторы работают медленно. Использование $('.oneResult') будет искать все элементы в DOM и проверять их className в старых версиях IE. Рассмотрите возможность использования такого подхода, как atRes.find('.oneResult'), чтобы сузить область поиска.

Когда дело касается добавления обработчиков click, лучше всего избегать установки обработчиков на каждый keyup. Вы можете использовать делегирование событий, установив один обработчик на atRest для всех результатов в том же блоке, где вы устанавливаете обработчик keyup:

atRest.on('click', '.oneResult', function() {
  window.location.href = 'http://hashtag.ly/' + $(this).html();
});

Для получения дополнительной информации обратитесь к документации: http://api.jquery.com/on/.