Array union and intersection

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

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

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

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

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

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

( Read more... )