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

[morfizm.livejournal.com]

1. Я точно не знаю, как в конкретном JavaScript'е для конкретного browser'а это реализовано, но так, в принципе, lookup по хештаблице/dictionary это обычно O(1). Ну, т.е. бывают реализации и за O(logN), но это медленно. Другими словами, ты построил линейный алгоритм.

2. Можно тоже линейно, но ещё быстрее - если по каждому твоему поисковому фильтру сделать битвектор, вроде [0, 0, 1, 1, 1, 0, 1] если 0-й, 1-й и 5-й не выбраны, а 2-й, 3-й, 4-й и 6-й выбраны.

Далее, тривиально линейный intersect: бежим по двум битвекторам и умножаем попарно (ну, или AND'им, один х-.)

3. Можно построить структурку посложней и делать операции сублинейно :)
Понятно, что изначальный фильтр будет линейный, если у тебя данные не проиндексированы, но если проиндексированы, сублинейно можно делать всё целиком. И если бы это было нельзя, в поисковой индустрии было бы всё очень печально :)