Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

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

news.ycombinator.com

Post reply on HN
Print view View original

321–330 of 772 posts

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

#321

Post by xxs »

dundarious wrote: post #119
vlmutolo wrote: post #108

Earlier quoted context omitted.

That Cloudflare article is a little frustrating. > While we could think of more sophisticated data structures like Cuckoo filter, maybe we can be simpler Yes, standard Bloom filters fail for large filter sizes and/or very small false-positive rates. But we've known this for decades, and tons of other probabilistic filters have come out since then to address the problem. Cuckoo filters in particular are incredible. Wa…

A linear probing hash table is simpler. That’s the trade off they were going for at that time. I don’t think that’s the most efficient solution given the hardware they were using, and I don’t think the blog author would either, but it’s certainly easier to write such a hash table — and it’s well written, but still mostly interview level stuff. To me the blog post is not about cuckoo or bloom filters or hash tables at…

Cuckoo is terrible from constant const point of view, linear probe is where is it at, indeed.

>"mov" is the biggest cycle-eater of them all.

The R part in 'RAM' is so wrong nowadays.

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

#322

Post by paskozdilar »

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()
            defer c.mut.RUnlock()
            ret = c.ret
        }
        return ret
    }
The way to use it is to write a non-concurrent nullary get() function, then pass it to the Multiplex() function in as many goroutines as needed:

    get := func() DataType { ... }
    muxer := Muxer[DataType]{}
    
    // in other goroutines
    value := muxer.Multiplex(get)
The value will be shared across all goroutines, so we get minimum latency with minimum copying.

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

#323

Post by xxs »

FullyFunctional wrote: post #286

My absolute favorite, Cuckoo hashing, has been mentioned already, but so far (239 comment in) nobody has mention this approach (called?) to store an array A[] of N-bit numbers, most of which are zero or small: use N set of numbers S[N], such that for each A[I] you store I in S[J] where J are the bit positions where A[I] have a set bit. In other words, S[J] are the indices of elements from A that has a set bit in posi…

In practice Cuckoo sucks, b/c the reading from an unknown index in an array is not a const cost operation. It has an upper bound of course, but its average cost is quite different, depending if you are to hit L1, or L2... or just go for the a cache miss.

"Cache misses" is what dominates performance nowadays.

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

#324

Post by nly »

manuelabeledo wrote: post #313

Concurrent tries with non-blocking snapshots [0] Say that you have a dataset that needs to be ordered, easily searchable, but is also updated quite frequently. Fast accesses are a pain if you decide to use traditional read-write locks. Ctries are entirely lock-free, thus there is no waiting for your read operations when an update is happening, i.e. you run lookups on snapshots while updates happen. They are also a lo…

Sounds like if you want a version of this that doesn't leak memory you need a garbage collected language?

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

#325

Post by WithinReason »

filoeleven wrote: post #198

HAMT: Hash Array Mapped Trie. This data structure makes efficient immutable data possible. You can update a list of a million items, and keep a reference to the original list, by changing 3 or 4 references and some bytes. This should replace copy-on-write for scripting languages. I really want to see it in a JS spec soon. There are libraries that can do it, but they add translation penalties and extra steps. I’d comp…

Isn't this slow because of pointer chasing in the trie?

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

#326

Post by sgtnoodle »

jacamera wrote: post #16
sgtnoodle wrote: post #2

Monotonic stacks are neat. I made up a data structure once, consisting of a pyramid of deques. It lets you efficiently compute any associative function over a streaming window of data.

I recently learned about monotonic stacks thanks to this LeetCode problem: https://leetcode.com/problems/sum-of-total-strength-of-wizar... I feel like they're quite possibly the most deceptively simple data structure I've yet to encounter. That is to say that for me at least there was/is a wide gulf between simply understanding what the data structure is (doesn't get much simpler than a stack!) and when/how to actual…

Do folk genuinely get asked problems like that in technical interviews these days? I can't think of any plausible reason why anyone would want to do a calculation as contrived as that. I love the required modulo value too.

I assume the trick is to somehow leverage the distributive property of multiplication to refactor the data to no longer require as much iteration? Is there supposed to be a linear time solution?

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

#327

Post by WatchDog »

filoeleven wrote: post #198

HAMT: Hash Array Mapped Trie. This data structure makes efficient immutable data possible. You can update a list of a million items, and keep a reference to the original list, by changing 3 or 4 references and some bytes. This should replace copy-on-write for scripting languages. I really want to see it in a JS spec soon. There are libraries that can do it, but they add translation penalties and extra steps. I’d comp…

I imagine careless use of such a structure would be an easy way to create a memory leak. Is it possible to create persistent collections in js, that will free data no longer directly referenced?

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

#328

Post by slazaro »

I don't know whether it already exists or if it has a name, but internally I call it Virtual List.

- Reasoning: It's used in cases where you'd ideally use an array because you want contiguous memory (because you'll usually iterate through them in order), but you don't know beforehand how many elements you'll insert. But you can't use a resizeable version like std::vector, because it invalidates any pointers to the elements you've already allocated, and you need to store those pointers.

- Implementation: As a black box, it's used like a list: you index elements with an integer, and you can append to the end. But internally it uses different lists. Like a std::vector, it starts with an allocated size, and when it needs a bigger size, it allocates newer blocks that are "added" to the end, but doesn't move the already allocated elements.

- Downsides: Data is not all contiguous, at some point there are jumps between elements that should be close together. For performance when iterating, it's negligible since those cache misses happen "rarely" (depends on the block size, bigger block size means better cache performance but more potential wasted allocated memory), and most of the time you're iterating from start to end. But this means that you can't use this structure with algorithms that use "pointer + size", since internally it doesn't work like that. And since internally you can't shrink the lists and invalidate pointers, there's no way to delete elements, but in my case it's not a problem since I'd reuse indices afterwards with an added structure.

- Applications: I used it when coding games, when you have a big list of entities/components but you don't know how many beforehand. You access them by index, you might store pointers to elements, and most of the time you'll iterate through the whole list (when updating, drawing, etc.).

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

#330

Post by idontwantthis »

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…

It’s also the clearest and least buggy way to iterate over the results. Map over Await Promise.all(map).
Post reply on HN