Операции с массивами и множествами: что вам нужно знать
28 февраля 2023 г.Недавно я взял на себя задачу переписать несколько репозиториев JavaScript с открытым исходным кодом, которые я поддерживаю, чтобы воспользоваться последними оптимизациями в движке JavaScript v8.
Некоторые из этих оптимизаций включали использование встроенных классов, таких как Map и Set, вместо массивов. Когда я впервые реализовал библиотеки, либо Map и Set либо были недоступны, либо не давали реального преимущества в производительности по сравнению с Array.
Другие оптимизации включали изменение порядка итераций массива или типов циклов. На уровне микрооптимизации иногда цикл назад выполняется быстрее, чем вперед, и while может быть быстрее, чем for.
Работая с операциями над массивами, я обнаружил фундаментальный сдвиг парадигмы, обеспечивающий повышение производительности в 1, 2 или даже порядков.
Смена парадигмы
Для многих операций с наборами конечные элементы набора могут быть известны до того, как будет собран полный набор. Например, при запросе объединения каждый элемент в каждой коллекции (наборах или массивах) будет в конечном результате как минимум и не более одного раза.
Итак, почему бы не вернуть все элементы в первой коллекции в быстрой последовательности, а затем элементы в последующих коллекциях один за другим, пока они еще не возвращены?
Этот тип кода обычно можно реализовать с помощью функции-генератора, но, что удивительно, ни одна из других библиотек с открытым исходным кодом, с которыми я сравнивал производительность своего кода, за исключением декартова произведения, не использовала их эффективно.
Многие библиотеки просто сосредоточились на более коротком коде, используя рекурсивную карту и уменьшая функции с оператором расширения. В других библиотеках генераторы использовались настолько наивно, что практически не давали прироста производительности.
Неспособность быстро вернуть начальное значение из операции над набором во время работы конвейера анализа данных может замедлить или исключить способность конвейера выдавать какие-либо окончательные результаты из-за прямых или косвенных тайм-аутов, вызванных невозможностью использования параллелизма ниже по течению от набора. операция.
Кроме того, использование рекурсивных функций или отказ от использования генерации по запросу может привести к сбоям из-за потребления памяти при вычислении промежуточных значений.
Хорошо написанные генераторы решат некоторые проблемы с памятью и производительностью, однако совместно использовать их алгоритмы с кодом, не являющимся генератором, непросто.
Это вызывает раздувание кода, когда вызывающая программа гарантирует негенеративные подходы, поскольку необходимо поддерживать два набора кода. Это также означает больше модульного тестирования, чтобы получить надлежащее покрытие и больше шансов на ошибку.
Однако есть еще один альтернативный настраиваемый протокол итерации для JavaScript<. /strong> и Python, которые реализуют генеративный подход без общих генераторов. .
Используя общий шаблон, их можно написать так, чтобы логика разделялась между генеративным и негенеративным подходами.
Написание общего пользовательского итерируемого объекта
Ниже показана функция объединения в JavaScript:
function union(...args) {
const nOthers = args.length - 1,
memory = new Set();
let j = 0;
for(let i=0;i<=nOthers;i++) {
const array = args[i],
len = array.length;
while(j<len) {
const elem = array[j++];
if(!memory.has(elem)) {
memory.add(elem);
}
}
j=0;
}
return [...memory];
}
Чтобы подготовиться к созданию Iterable, нам нужно зафиксировать в замыкании все переменные, которые могут меняться каждый раз, когда мы запрашиваем следующий элемент, и обусловить их, когда мы итерируем. Итак, мы создаем функцию unionizer, которая возвращает функцию union.
const unionizor = (iterating) => {
let i, j, nOthers, args, memory;
return function union() {
if(!args) { // initilaize variables the first time union is called
args = [...arguments];
nOthers = args.length - 1;
memory = new Set();
i = 0;
j = 0;
}
for(;i<=nOthers;i++) {
const array = args[i],
len = array.length;
while(j<len) {
const elem = array[j++];
if(!memory.has(elem)) {
memory.add(elem);
if(iterating) { // conditionaly yield result if iterating
return {value:elem}
}
}
}
j=0;
}
args = null; // set args back to null so iterating can restart
return iterating ? {done:true} : [...memory];
}
}
const union = unionizer();
При вызове без аргумента unionizer возвращает функцию, которая ведет себя точно так же, как наша первая реализация. Он имеет только два дополнительных логических теста для итерации, поэтому он будет почти неотличим с точки зрения производительности и увеличит размер всего на несколько байтов.
Функция будет ЧРЕЗВЫЧАЙНО быстрой для первого массива в arguments, потому что ничего не будет в переменной memory. Поскольку Set используется для памяти, он будет ОЧЕНЬ быстрым для последующих массивов, хотя он немного замедлится, когда пересечение, т. е. memory, станет очень большим. р>
Затем должен быть реализован фактический Iterable:
function iterableUnion(...args) {
const union = unionizer(true);
let started;
return {
next() {
return union(...args);
},
[Symbol.iterator]() {
return this;
}
}
}
Вызывая unionizer(true) из iterableUnion, функцию, которая возвращает объекты-значения или {done:true}, а не просто собирает все результаты создается.
Итак, теперь есть две функции, union и iterableUnion, основанные на одном и том же фундаментальном коде. Меньше поддержки и почти идентично по производительности исходному коду или генератору соответственно!
Для тех, кто заинтересован, вот прямая реализация генератора объединения:
function* union(...args) {
const nOthers = args.length - 1,
memory = new Set();
let j = 0;
for(let i=0;i<nOthers;i++) {
let array = args[i];
if(!Array.isArray(array)) args[i] = array = [...array];
const len = array.length;
while(j<len) {
const elem = array[j++];
if(!memory.has(elem)) {
memory.add(elem);
yield elem;
}
}
j=0;
}
}
Те же принципы можно применить к difference, intersection, симметричномуIntersection и CartesianProduct.
Хотя существует еще больше возможностей для оптимизации CartesianProduct, выходящих за рамки этой статьи, см. http ://phrogz.net/lazy-cartesian-product.
Чтобы применить эти принципы в других случаях, мы можем сохранить небольшую базу кода, реализуя функцию, которая создает Iterable:
function createIterable(setFunction) {
return function(...args) {
const f= setFunction(true);
let started;
return {
next() {
return f(...args);
},
[Symbol.iterator]() {
return this;
}
}
}
}
Итак, теперь определение iterableUnion будет выглядеть так:
const iterableUnion = createIterable(unionizor);
Используя несколько массивов, содержащих более 10 000 элементов в каждом, в качестве тестовых данных, вот преимущества производительности по сравнению с наивными подходами, которые я вижу для доступа к первому элементу в результате с использованием JavaScript:
* разница в 1,5-2 раза * пересечение, 1,5 до 2x * симметричная разница, от 2,5 до 3x * союз от 2,5 до 3 порядков * Декартово произведение, 3+ порядка
Производительность генераторов и Iterables обычно находится в пределах погрешности друг друга, но Iterables требует меньше кода для поддержки.
Я надеюсь, что вы нашли эту статью полезной для оптимизации конвейера данных. Библиотека array-set-ops использует описанные выше принципы, а также более тонкие оптимизации и предоставляет согласованный API для работы с наборами Array и Set, а также добавляет все стандартные функции, такие как map, reduce, slice и т. д. в Set и CartesianProduct.
Изображение предоставлено: Dall-E High Speed Programmer
Также опубликовано здесь
Оригинал