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

[dennyrolling.livejournal.com]

If you can imagine something, there is someone already doing it...

http://www.falsepositives.com/index.php/2009/12/01/javascript-function-to-get-the-intersect-of-2-arrays/

я бы не говорил что "просто нет". может и есть :)

[ermouth.livejournal.com]

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

как ты понимаешь, этот пример мне не попался, хотя видно, что чувак рассуждал также, как и я -- даже переменные одинаково называются )

видно, что чувак -- также, как и я -- прифигел от скорости. и да, написано это было 3 года назад, а в Underscore.js как оно было медленное, так до сих пор и есть.

я твитнул shugarjs, может поправят у себя. у них то интерсект вообще жопа.