Парсер Хабра: LINQ на JavaScript для самых маленьких

суббота, 15 августа 2020 г.

LINQ на JavaScript для самых маленьких

Шел очередной день самоизоляции, и я делал один из тех проектов для себя, которые мы забрасываем через пару дней после того как начали. Ну вы знаете, тот проект, который сделает вас знаменитым, позволит вам выучить новый ЯП, новый фреймворк и все такое. В общем, это был самый обычный день, самой обычной пандемии. Ничего не предвещало беды, пока одна библиотека, которой я пользовался для работы с массивами не выпала со stack overflow… И вот тут-то все и запузырилось.

В общем-то я прекрасно понимаю, что можно было использовать что-то готовое, но так не интересно.

Почему LINQ?

Вкратце для тех, кто не в курсе:

LINQ (Language-Integrated Query) представляет простой и удобный язык запросов к источнику данных. В качестве источника данных может выступать объект, реализующий интерфейс IEnumerable (например, стандартные коллекции, массивы), набор данных DataSet, документ XML.

И LINQ позволяет делать вот так:

string[] teams = { "Бавария", "Боруссия", "Реал Мадрид", "Манчестер Сити", "ПСЖ", "Барселона" };

var selectedTeams = teams.Where(t=>t.ToUpper().StartsWith("Б")).OrderBy(t => t);

Из особых преимуществ хотелось бы отметить:

Lazy-computation
Оптимизацию запросов
Удобная система методов расширения

Не знаю, как вы, но лично для меня это послужило вескими аргументами, для того, чтобы приступить к работе.

Приступая к работе

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

Поэтому поставим для себя некоторые требования, помимо того, что указано в преимуществах LINQ:

Код должен быть легко-расширяемым
Код должен быть быстрым

Для оценки скорости возьмем Benchmark.js. А за эталон мы возьмем Lodash, потому что он написан серьезными большими мальчиками, а значит годится в качестве некоторой точки отсчета.

Если вам интересны исходники, то вот репозиторий, а если хочется просто поиграться с тем, что получилось, то вот npm-пакет.

В этой статье я расскажу как сделать несколько методов, потому что, если я буду описывать весь код, то эту портянку никто не будет читать.

Разберем мы:

Where
Sort
Min

Эти методы я, в общем-то, взял не с потолка:

Where мы рассмотрим как метод, который легко поддается оптимизации и его можно использовать для ленивых вычислений.
Sort как метод, который требует чтобы выражение до него было вычислено.
Min как пример агрегатной операции.

Приступим

Начнем с некоторых умозаключений:

Мы хотим иметь методы расширения
Методы расширения будут возвращать нам новые данные

На мой взгляд это очень похоже на паттерн Декоратор.

Если кратко, то схема классов должна быть такой:

То есть, есть родительский класс, умеющий возвращать дочерние классы, которые умеют делать по кусочку нужного функционала.

export class Collection<T> implements ICollection<T> {
    protected inner: Collection<T>;
    private _computed: T[] | null = null; // Здесь мы с вами будем хранить уже посчитанный результат выражения, после того как коллекция "материализовалась"

    public where(condition: FilterCondition<T>): ICollection<T> {
        return new FilteringCollection<T>(this, condition);
    }

    public sort(condition?: CompareCondition<T> | undefined): ICollection<T> {
        return new SortingCollection<T>(this, {
            compare: condition
        })
    }

    public min(predicate?: CompareCondition<T> | undefined): T {
        return new MinAggregator(this, predicate).aggregate();
    }

    public toArray(): T[] {
        return this.computed;
    }

    public [Symbol.iterator](): IterableIterator<T> {
        return this.getIterator();
    }

    public getIterator(): IterableIterator<T> {
        return this.computed[Symbol.iterator](); // По задумке, коллекция материализуется еще и в цикле for - of
    }

    private get computed(): T[] { // Ленивые вычисления: материализуем коллекцию только при вызове геттера
        if (this._computed == null) {
            const result = this.materialize();

            Object.freeze(result);

            this._computed = result;
        }
        return this._computed
    }

    protected materialize(): T[] { // Метод материализации коллекции
        return this.inner.toArray();
    }
}

"В чем здесь декоратор?" — спросите вы, а я вам отвечу: ~~"Учите матчасть"~~.

Допустим есть выражение:

const collection = new Collection([6, 5, 4, 3, 2, 1]);

const result = collection.where(item => item % 2).sort(); // [1, 3, 5]

Разберем его по шагам, пусть:

        const collection = new Collection([6, 5, 4, 3, 2, 1]);
/* 1) */const filtered = collection.where(item => item % 2);
/* 2) */const sorted = filtered.sort();

1) Мы вызываем метод where у класса Collection, мы передаем ему ссылку на текущую коллекцию и записываем ее в поле inner.
2) Мы вызываем метод sort у класса FilteringCollection, мы передаем ему ссылку на текущую коллекцию и записываем ее в поле inner.

Затем, когда мы будем материализовывать выражение, все вычисления произойдут в таком же порядке:

1) Вызовется materialize у FilteringCollection и вернется массив [5, 3, 1].
2) Вызовется materialize у SortingCollection и вернется массив [1, 3, 5].

Where

Реализация фильтрующего декоратора

export class FilteringCollection<T> extends Collection<T> {
    public constructor(iterable: Collection<T> | T[], private condition: FilterCondition<T>) {
        super(iterable);
    }

    public where(condition: FilterCondition<T>): ICollection<T> { // Перегрузка метода where
        const that = this;

        const result = new FilteringCollection<T>(this.inner, item => condition(item) && that.condition(item));

        return result;
    }

    protected materialize(): T[] { // перегрузка метода материализации
        return this.inner.toArray().filter(this.condition);
    }
}

Пояснение

В классе хранится ссылка на внутреннюю коллекцию и выражение для фильтрации. Все.
Это все что нам нужно, для того чтобы реализовать метод расширения where(). Красиво выглядит, неправда ли?

Отдельно хотелось бы отметить, что данная реализация оптимизирует проход по цепочке из where:

То есть

_(cats).where(cat => cat.age < 3).where(cat => cat.age > 1).toArray()

будет преобразовано в

_(cats).where(cat => cat.age < 3 && (function(item){
    return item.age > 1;
}(cat))).toArray()

происходит эта оптимизация вот тут:

public where(condition: FilterCondition<T>): ICollection<T> { // Перегрузка метода where
        const result = new FilteringCollection<T>(this.inner, item => condition(item) && this.condition(item)); // <-- тут

        return result;
    }

Мы просто отдаем в новый декоратор исходную коллекцию и подменяем выражение "сращенным".

В методе materialize у нас просто используется метод массива filter. Я выбрал его как самый простой и эффективный вариант для фильтрации. Все другое, что я пробовал проигрывало в производительности.

Поговорим о производительности

----------------------------------------------------
Filter for 1000000:

Where x 104 ops/sec ±14.73% (61 runs sampled)
Lodash filter x 609 ops/sec ±0.67% (88 runs sampled)
Native filter x 537 ops/sec ±1.69% (85 runs sampled)

Double where x 102 ops/sec ±11.51% (64 runs sampled)
Double lodash filter x 368 ops/sec ±1.00% (88 runs sampled)
Double native filter x 336 ops/sec ±1.08% (84 runs sampled)

10 where x 66.60 ops/sec ±9.15% (59 runs sampled)
10 lodash filter x 99.44 ops/sec ±1.20% (73 runs sampled)
10 native filter x 81.80 ops/sec ±1.33% (70 runs sampled)
----------------------------------------------------
Filter for 1000:

Where x 24,296 ops/sec ±0.90% (88 runs sampled)
Lodash filter x 60,927 ops/sec ±0.90% (89 runs sampled)
Native filter x 204,522 ops/sec ±6.76% (87 runs sampled)

Double where x 20,281 ops/sec ±0.86% (90 runs sampled)
Double lodash filter x 37,553 ops/sec ±0.97% (90 runs sampled)
Double native filter x 115,652 ops/sec ±6.12% (91 runs sampled)

10 where x 9,559 ops/sec ±1.09% (87 runs sampled)
10 lodash filter x 8,850 ops/sec ±0.80% (87 runs sampled)
10 native filter x 22,507 ops/sec ±9.22% (84 runs sampled)
----------------------------------------------------
Filter for 10:

Where x 1,788,009 ops/sec ±0.81% (87 runs sampled)
Lodash filter x 720,558 ops/sec ±0.80% (84 runs sampled)
Native filter x 14,917,151 ops/sec ±0.61% (85 runs sampled)

Double where x 1,257,163 ops/sec ±0.52% (95 runs sampled)
Double lodash filter x 456,365 ops/sec ±0.74% (76 runs sampled)
Double native filter x 8,262,940 ops/sec ±0.64% (90 runs sampled)

10 where x 489,733 ops/sec ±0.67% (94 runs sampled)
10 lodash filter x 135,275 ops/sec ±0.61% (94 runs sampled)
10 native filter x 1,350,316 ops/sec ±0.94% (90 runs sampled)
----------------------------------------------------

Коротко для ленивых: Наши побеждают, но только на коротких дистанциях.
Кстати такой расклад еще и с select (его реализацию вы можете увидеть в исходниках).

Sort

Реализация сортирующего декоратора

export class SortingCollection<T, V = T> extends Collection<T> implements ISortingCollection<T> {
    private sortSettings: SortSettings<T, V>[];

    public constructor(iterable: Collection<T>, ...sortSettings: SortSettings<T, V>[]) {
        super(iterable);
        this.sortSettings = _(sortSettings)
        .where(item => !!item.compare || !!item.mapping) // Получаем правила маппинга полей и сортировку по ним
        .toArray();
    }

    protected materialize(): T[] {
        const comparer = new Comparer(this.sortSettings, this.defaultCompare);

        return  Array.from(this.inner.toArray()).sort(this.sortSettings.length ? (first, second) => comparer.compare(first, second) : undefined);
    }

    private defaultCompare(first: V, second: V): number {
        if(first < second) {
            return -1
        } else if (second < first) {
            return 1
        } else {
            return 0;
        }
    }
}

Пояснение

В классе хранится ссылка на внутреннюю коллекцию и настройки сортировки. Переопределен метод материализации. За сравнение объектов отвечает специальный класс Comparer.

Отдельно бы хотелось отметить тот факт что Lodash, так же как и js изменяет исходный массив при сортировке.

Поговорим о производительности

----------------------------------------------------
Sort for 1000000:

Sort x 0.80 ops/sec ±3.59% (6 runs sampled)
Lodash sort x 0.97 ops/sec ±27.98% (7 runs sampled)
Native sort x 1.05 ops/sec ±14.71% (7 runs sampled)

SortBy x 0.19 ops/sec ±10.31% (5 runs sampled)
Lodash SortBy x 0.37 ops/sec ±7.21% (5 runs sampled)
Sort after map x 0.47 ops/sec ±8.67% (6 runs sampled)
----------------------------------------------------
Sort for 1000:

Sort x 1,121 ops/sec ±0.77% (85 runs sampled)
Lodash sort x 1,267 ops/sec ±0.77% (89 runs sampled)
Native sort x 1,274 ops/sec ±0.88% (86 runs sampled)

SortBy x 488 ops/sec ±1.45% (80 runs sampled)
Lodash SortBy x 549 ops/sec ±9.60% (70 runs sampled)
Sort after map x 954 ops/sec ±1.50% (83 runs sampled)
----------------------------------------------------
Sort for 10:

Sort x 171,700 ops/sec ±1.38% (85 runs sampled)
Lodash sort x 196,364 ops/sec ±2.01% (80 runs sampled)
Native sort x 250,820 ops/sec ±0.96% (85 runs sampled)

SortBy x 114,064 ops/sec ±0.90% (86 runs sampled)
Lodash SortBy x 86,370 ops/sec ±17.93% (67 runs sampled)
Sort after map x 221,034 ops/sec ±1.31% (87 runs sampled)
----------------------------------------------------

Все так же для ленивых:
± одинаково.

Min

Реализация агрератора поиска минимального элемента

export class MinAggregator<T> extends ReduceAggregator<T> {
    public constructor(collection: ICollection<T>, condition?: CompareCondition<T>) {
        super(collection, condition ? (first, second) => this.compare(first, second, condition) : (a, b) => a < b ? a : b)
    }

    private compare(first: T, second: T, func: CompareCondition<T>): T {
        return func(first, second) < 0 ? first : second;
    }
}

export class ReduceAggregator<T> extends Aggregator<T> {
    public constructor(private collection: ICollection<T>, protected predicate: ReduceCondition<T>){
        super();
    }

    public aggregate(): T {
        return this.collection.toArray().reduce((first, second) => this.predicate(first, second))
    }
}

Не ожидали? А декоратора не будет.

Вместо него у нас будет агрегатор.

Пояснение

Не уверен что оно вообще нужно, мы просто делаем свертку.

Поговорим о производительности

----------------------------------------------------
Aggregate for 1000000:
Min x 43.69 ops/sec ±28.48% (65 runs sampled)
Lodash Min x 117 ops/sec ±0.58% (73 runs sampled)
----------------------------------------------------
Aggregate for 1000:
Min x 61,220 ops/sec ±5.10% (87 runs sampled)
Lodash Min x 111,452 ops/sec ±0.72% (90 runs sampled)
----------------------------------------------------
Aggregate for 10:
Min x 3,502,264 ops/sec ±1.36% (86 runs sampled)
Lodash Min x 4,181,189 ops/sec ±1.48% (86 runs sampled)
----------------------------------------------------
Aggregate By for 1000000 disp 50:
Min By x 23.81 ops/sec ±2.02% (42 runs sampled)
Lodash Min By x 42.66 ops/sec ±2.46% (55 runs sampled)
----------------------------------------------------
Aggregate By for 1000 disp 50:
Min By x 43,064 ops/sec ±0.71% (86 runs sampled)
Lodash Min By x 60,212 ops/sec ±0.89% (87 runs sampled)
----------------------------------------------------
Aggregate By for 100 disp 50:
Min By x 351,098 ops/sec ±1.03% (81 runs sampled)
Lodash Min By x 382,302 ops/sec ±1.39% (76 runs sampled)
----------------------------------------------------

Lodash победил.

Итоги

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

Если кто знает как понизить стоимость итерации при фильтрации и маппинге, а именно вот тут:
this.inner.toArray().filter(this.condition);
то буду раз узнать ответ!

Открыт к критике, хочу сделать код лучше.

Всем спасибо за внимание.

→ Репозиторий
→ Npm-пакет

Let's block ads! (Why?)

Парсер Хабра

...

суббота, 15 августа 2020 г.

LINQ на JavaScript для самых маленьких

Почему LINQ?

Приступая к работе

Приступим

Where

Реализация фильтрующего декоратора

Пояснение

Sort

Реализация сортирующего декоратора

Пояснение

Min

Реализация агрератора поиска минимального элемента

Пояснение

Итоги

Комментариев нет:

Отправить комментарий

...

суббота, 15 августа 2020 г.

LINQ на JavaScript для самых маленьких

Почему LINQ?

Приступая к работе

Приступим

Where

Реализация фильтрующего декоратора

Пояснение

Sort

Реализация сортирующего декоратора

Пояснение

Min

Реализация агрератора поиска минимального элемента

Пояснение

Итоги

Комментариев нет:

Отправить комментарий

суббота, 15 августа 2020 г.