typescript - Filtrering av Immutable.js List: filter vs skipUntil vs findIndex/takeLast

Jag behöver filtrera en Immutable.js-lista som redan är sorterad. För att jämföra tre olika tillvägagångssätt utförde jag följande benchmark-test (baserat på Benny):

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()
)

Detta var resultaten på min maskin:

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

Självklart förväntade jag mig att det enkla filter-sättet skulle vara det långsammaste med O(n), men jag är lite förbryllad över att findIndex/takeLast är mycket snabbare än skipUntil - kan någon förklara, tack?

UPPDATERING: Detta ser ut att vara en regress i v4.0.0-rc.12 jämfört med v3.8.2, jag rapporterade ett problem

Svar #1

I immutabla är den dyraste/långsammaste operationen när det måste skapa något nytt.

findIndex returnerar endast ett enskilt element. Det behöver inte skapa eller ändra något.

takeLast använder internt slice, som använder sekvenser för att skapa en del-lista istället för att själv fylla en ny lista.

filter returnerar en ny samling med alla matchande element. Att skapa en sådan lista är kostsamt.

skipUntil kallar internt skipWhile(not(predicate)), vilket verkar fungera på ett sätt som liknar filtrering.

Returnerar en ny samling av samma typ som inkluderar poster från och med när predikatet först returnerar sant.

Du kan få snabbare resultat från skipUntil när du skapar en Seq av listan först, eftersom det är ett lat omslag och låter dig göra vissa operationer utan att fullt ut realisera hela samlingen.

Dokumentationen är faktiskt ganska bra, jag rekommenderar att titta på den regelbundet. Immutable har en hel del fallgropar där man kan slösa prestanda, så jag tenderar att slå upp funktioner i dokumentationen varannan dag.