Ask HN: What are some cool but obscure data structures you know about?

Post by jjgreen » Fri, Jul 22, 2022, 9:24 AM UTC

allanrbo wrote: post #371

Frugal streaming. For estimating a median or percentile in a stream, using constant memory. It's very simple: if the current value is higher than our estimate, then increase our estimate by one. Else decrease by one. It will converge over long enough time. This is called the Frugal-1U algorithm. The Frugal-2U is a slightly more advanced version that modifies the step size along the way, plus other optimizations, to c…

Post by simonlindholm » Fri, Jul 22, 2022, 9:25 AM UTC

hexomancer wrote: post #289

jtolmar wrote: post #171

The union-find data structure / algorithm is useful and a lot of fun. The goal is a data structure where you can perform operations like "a and b are in the same set", "b and c are in the same set" and then get answers to questions like "are a and c in the same set?" (yes, in this example.) The implementation starts out pretty obvious - a tree where every element either points at itself or some thing it was merged wi…

I have always wanted to really understand this data structure. Sure, I can follow the analysis with the potential functions and all, but I never really understood how Tarjan came up with the functions in the first place. Does anybody have a resource which intuitively explains the analysis?

Post by twic » Fri, Jul 22, 2022, 9:26 AM UTC

compressedgas wrote: post #364

Dwedit wrote: post #232

Here's one I don't know if I've ever seen documented anywhere. If anyone knows a proper name for this one, let me know! Imagine it's for a text editor, and you want to map Line Numbers to Byte Positions. But then you want to insert a byte somewhere, and you need to add 1 to all your Byte Position values. Instead of actually keeping a big array of Byte Position values, you have a hierarchical array. The convention is…

Ted Nelson named them Enfilades. Guy Steele called them Monoid Cached Trees.

Post by samatman » Fri, Jul 22, 2022, 9:30 AM UTC

skrebbel wrote: post #297

Not a very deep CS-y one, but still one of my favourite data structures: Promise Maps. It only works in languages where promises/futures/tasks are a first-class citizen. Eg JavaScript. When caching the result of an expensive computation or a network call, don't actually cache the result, but cache the promise that awaits the result. Ie don't make a Map but a Map > This way, if a new, uncached key gets requested twice…

    setmetatable({}, {__index = function(tab, key)
          local co = coroutine.running()
          uv.read(fd, function(err, result)
               tab[key] = result
               return coroutine.resume(result)
            end)
          return coroutine.yield()
      end })

Post by paskozdilar » Fri, Jul 22, 2022, 9:33 AM UTC

sph wrote: post #339

paskozdilar wrote: post #322

I've had a situation where I needed to stream blocks of data from a remote computer in soft-realtime, but still needed to share the same data with many different consumers. The code was simple, but effective (Go): import "sync" type Muxer[T any] struct { ret T mut sync.RWMutex } func (c *Muxer[T]) Multiplex(fn func() T) (ret T) { if c.mut.TryLock() { defer c.mut.Unlock() ret = fn() c.ret = ret } else { c.mut.RLock()…

I don't get it. It seems overengineered to me, but I can't formulate my reasoning well enough. Why isn't the original value that you're returning protected by a RWLock, and all goroutines will just need to acquire a read lock, instead of using a write lock for what is basically a getter function? Yeah, I don't get it.