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, может поправят у себя. у них то интерсект вообще жопа.

[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. Можно построить структурку посложней и делать операции сублинейно :)
Понятно, что изначальный фильтр будет линейный, если у тебя данные не проиндексированы, но если проиндексированы, сублинейно можно делать всё целиком. И если бы это было нельзя, в поисковой индустрии было бы всё очень печально :)

[morfizm.livejournal.com]

Из практических соображений, конкретно в твоём случае (исходные данные - просто массив, без индекса, всё на JavaScript, и, вот, штук пять фильтров), я бы сделал следующее:

Отсортировал бы фильтры в порядке от наиболее restrictive к наименее (можно hard-coded последовательность, а можно копить статистику). Допустим, "марка" отсеивает больше всего - значит, "марка" - первый фильтр.

Прошёлся бы по исходному массиву, и всё, что попадает под фильтр, занёс бы (индексы) в массив найденного. Потом шёл бы по этому массиву, брал бы индексы, по ним заглядывал бы в изначальный массив, и тестировал бы второй фильтр, генерируя новый массив индексов. И т.п. С каждым проходом массивы всё меньше и меньше, поэтому вместо, скажем, 5 полных проходов, у тебя будет суммарно - ну, там, скажем, 2. Алгоритм всё ещё линейный, но мы пробуем уменьшить константу перед N.

[ermouth.livejournal.com]

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

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

твоя схема не учитывает то, что тэги в одном ряду сначала надо сложить (union массивов), а уже потом получившиеся построчно массивы надо intersect.

то, что осталось, мы показываем.

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

По поводу O(log n). Выбор -- да, но нам ещё индекс надо построить и он у меня не кэшируется, то есть строится каждый раз. Поэтому O(n log n).

[morfizm.livejournal.com]

Ну если тебе хочется "гасить" тэги, которые дают пустое множество - то да, надо прогонять по всем, но (!) это вполне можно сделать потом, в бэкграунде, а поисковый результат выдавать быстрее, as you type.

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

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

[ermouth.livejournal.com]

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

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

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

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

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