How do you pick a data structure for fast merge-plus-render in a big list?

programming web dev
1

What’s up everyone? I’m working on a UI that ingests batches of items from an API and merges them into an existing list while keeping the list stable for rendering, and my current approach feels like it’s trending toward O(n log n) + extra churn when updates are frequent.

// existing: [{id, updatedAt, ...}] sorted desc by updatedAt
// incoming: same shape, may contain new + updates
function merge(existing, incoming) {
  const byId = new Map(existing.map(x => [x.id, x]));
  for (const x of incoming) {
    const prev = byId.get(x.id);
    byId.set(x.id, prev ? { ...prev, ...x } : x);
  }
  return Array.from(byId.values()).sort((a, b) => b.updatedAt - a.updatedAt);
}

If I care about long-term complexity and fewer reorders (to avoid wasted renders), is it better to keep a Map + a separate heap/tree/index for ordering, or just accept the full re-sort each batch and optimize elsewhere?

1 Like
2

You don’t need a heap/tree for this unless you’re doing tiny batches at a crazy rate; in JS a full sort is usually “fine, ” and the churn you’re feeling is more about identity than Big-O. One small tweak that cuts reorders a lot: when updatedAt ties (or is coarse), add a stable tie-breaker so items don’t randomly reshuffle between batches. I usually do updatedAt desc, then id asc (or keep a seq from first-seen). That makes React/Vue diffing way calmer even if you still sort every time. I’m not sure what your list size / batch size is, but if you’re talking like 5k items and 20-item batches, I’d try “merge + sort with tie-breaker + virtualization” before building a whole secondary index you’ll have to keep consistent forever.

3

your current version is fine for correctness, but i wouldn’t keep re-sorting the whole array every batch unless the list is tiny.

i’d do Map by id for the actual item data, and keep a separate ordered list of ids for render. then only move the rows whose updatedAt changed. that keeps React from acting like the whole screen got rerolled.

one thing i’ve seen in QA: the incremental version feels great when updates are small and frequent, but it gets kinda gross once a batch touches a big chunk of the list. at that point the extra splice bookkeeping starts eating the win, and a plain sort with virtualization is usually less annoying.

also, indexOf in your draft is the sneaky part that’ll hurt. if you go this route, you probably want an id -> position map too, or you’ll just move the O(n) pain somewhere else.

1 Like