Array union and intersection

[ermouth]

После того, как в разделе Ноутбуки на formoza29.ru появилось больше 200 позиций – это просто новый магазин открылся – стало ясно, что алгоритмы фильтра надо переписывать.

Вот такой примерно выбор (клик на картинку – перейти на этот выбор) рендерился почти 5 секунд.

Я стал тестить – и получилось, что время жрут встроенные в SugarJS алгоритмы объединения и пересечения массивов. Я поискал другие реализации – и все небыстрые, потому что без индексирования.

Ровно в одно очень простое соображение у меня получилось их ускорить со сложности в O(n^2) до O(n log n). То-есть, по русски, для выборок в два массива по примерно 100 элементов – в 50 примерно раз выигрыш по скорости.

Чисто в интерфейсном плане это отсутствие лагов даже на медленных железяках. 50 крат скорости в одно соображение – это много. Оно стоит того, чтобы рассказать – на Javascript я такого ни в одной библиотеке не встречал.

Дальше будет интересно только околокомпьютерным монстрам.

В самом яваскрипте операций слияния и пересечения массивов нет. В обычных яваскриптовых библиотеках слияние делается циклом в цикле, либо циклом операций indexOf() – что аналогично по скорости. Это как раз сложность O(n^2).

Вообще, если строить B-trees по значениям исходных массивов, слияние массивов станет операцией сложности O(n log n). Вопрос, как построить B-tree, а потом ходить по нему быстро именно на Javascript. Он очень хреново подходит для таких задач из-за отсутствия указателей и нестрогой типизации. Медленно очень получается и адово прожорливо в плане памяти.

А ответ то на поверхности.

В самом деле, любая js-машина и так юзает B-trees для выборки в хэш-массивах по ключу. Также как и для поиска по RegExp, например.

Поэтому мы сначала преобразуем входной массив значений в хэш-массив ключей, вот так:

["a", "b", "c", "a", "cd"] => {"a":1, "b":1, "c":1, "cd":1}

Дальше всё тривиально. Для пересечения мы проверяем наличие в получившемся массиве ключа со значением проверяемого элемента. Для объединения просто пишем два раза в один hash-array.

Вуаля. Код для интерсекта выглядит нопремер так:

function fastIntersect(a,b) {

     //returns intersection of two flat arrays.
     //slow for little arrays, fast for big, very fast for huge

     var o = {}; var r = [];
     for (var i=0; i<a.length; i++) o[a[i]]=1;
     for (var i=0; i<b.length; i++) if (o[b[i]]) o[b[i]]=2;
     for (var i in o) {
         if (o[i]==2){
             var i0 = i;
             if (!isNaN(i)) i0=Number(i);
             r.push(i0);
         }
     }
     return r;

}



Думаю, что быстрее способа на яваскрипте просто нет. Есличо, код не идеален.

Comments

[ermouth.livejournal.com]

да, тэги у меня и так гасятся с задержкой 300мс после отрисовки, этот лаг визуально заметен, если приглядеться.

у меня стояла планка в 3 секунды по первоначальной загрузке, в большинстве случаев мы укладываемся в 2,5. Если у тебя 5 -- подозреваю что дело просто в физической удалённости. хотя оптимизировать там можно ещё многое и выигрыша вдвое вполне можно достичь. мы это будем делать, когда у нас стабилизируется функционал -- до этого примерно месяц ещё.

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

я был уверен (видимо, давно читал когда-то и в памяти отложилось), что применяются именно ассоциативные массивы, а не хэш-таблицы, чтобы вставка тоже была гарантировано не хуже O(log n), а не O(n) как в худшем случае при использовании хэш-таблиц.

спасибо за комментарий -- я сподобился проверить )