typescript - Filtrování Immutable.js List: filter vs skipUntil vs findIndex/takeLast

Potřebuji filtrovat seznam Immutable.js, který je již seřazený. Abych porovnal tři různé přístupy, provedl jsem následující benchmark test (na základě Bennyho):

import b from 'benny'
import { Range } from 'immutable'

const elementCount = 100000
const list = Range(0, elementCount).toList()
const predicate = (e: number): boolean => e > elementCount / 2

b.suite(
  'Filter sorted Immutable.js List',

  b.add('via filter', () => {
    list.filter(predicate)
  }),

  b.add('via skipUntil', () => {
    list.skipUntil(predicate)
  }),

  b.add('via findIndex/takeLast', () => {
    list.takeLast(list.size - list.findIndex(predicate))
  }),

  b.cycle(),
  b.complete()
)

Toto byly výsledky na mém počítači:

via filter:
    104 ops/s, ±1.54%   | slowest, 77.09% slower

via skipUntil:
    104 ops/s, ±1.65%   | 77.09% slower

via findIndex/takeLast:
    454 ops/s, ±1.17%   | fastest

Očividně jsem očekával, že obyčejný přístup pomocí filter bude nejpomalejší s O(n), ale jsem trochu zmatený, že findIndex/takeLast je mnohem rychlejší než skipUntil - mohl by mi to někdo prosím vysvětlit?

AKTUALIZACE: Toto vypadá jako regres v verzi v4.0.0-rc.12 ve srovnání s v3.8.2, nahlásil jsem problém

Odpověď č. 1

U neměnného je nejdražší/nejpomalejší operací, když musí vytvořit něco nového.

findIndex vrací pouze jeden prvek. Nemusí nic vytvářet ani měnit.

takeLast interně používá slice, který k vytvoření podseznamu používá sekvence, místo aby sám naplnil nový seznam.

filter vrací novou kolekci se všemi odpovídajícími prvky. Vytvoření takového seznamu je nákladné.

skipUntil interně volá skipWhile(not(predicate)), což se zdá fungovat podobně jako filtrování.

Vrací novou kolekci stejného typu, která zahrnuje položky začínající od okamžiku, kdy predikát poprvé vrátí hodnotu true.

Můžete dosáhnout rychlejších výsledků s skipUntil, pokud nejdříve vytvoříte Seq z listu, protože je to líný wrapper a umožňuje vám provádět některé operace, aniž byste plně realizovali celou kolekci.

Dokumentace je vlastně docela dobrá, doporučuji se na ni pravidelně dívat. Immutable má docela dost úskalí, kde můžete ztratit výkon, takže mám tendenci si funkce v dokumentaci prohlížet každý druhý den.