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

451–460 of 772 posts

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

#451

Post by funcDropShadow »

chriswarbo wrote: post #233
mastermedo wrote: post #209

Earlier quoted context omitted.

I don’t understand why wouldn’t you just use a list and an index. You can always access list[index+1] or list[index-1] or list[0] or list[list.length-1]. What is the benefit here?

Firstly, accessing an arbitrary list index is O(N), whilst a Zipper can access its focus in O(1) (shifting the focus is O(1) for both Zippers and list+index) Secondly, using an index forces us to do bounds checks, keep track of the length (or re-calculate it at O(N) cost), etc. whereas a Zipper is "correct by construction"; i.e. every value of type (List[A], A, List[A]) makes sense as a zipper; whereas many values of…

And they can be generalized to work on any kind of trees instead of just lists.

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

#452

Post by fulafel »

fulafel wrote: post #298

This post: http://www.frankmcsherry.org/graph/scalability/cost/2015/01/... "Scalability! But at what COST?" In it Frank McSherry uses a handful of data structure tricks to make graph algorithms like connectivity and PageRank run progressively faster on his laptop, beating distributed cluster implementations. It's actually a version of their HotOS paper with Isard and Murray. Admittedly it's the opposite of obscure, b…

Addenum.

Link to paper: https://www.usenix.org/system/files/conference/hotos15/hotos...

COST acronym: "Configuration that Outperforms a Single Thread"

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

#453

Post by mathgenius »

chriswarbo wrote: post #233
mastermedo wrote: post #209

Earlier quoted context omitted.

I don’t understand why wouldn’t you just use a list and an index. You can always access list[index+1] or list[index-1] or list[0] or list[list.length-1]. What is the benefit here?

Firstly, accessing an arbitrary list index is O(N), whilst a Zipper can access its focus in O(1) (shifting the focus is O(1) for both Zippers and list+index) Secondly, using an index forces us to do bounds checks, keep track of the length (or re-calculate it at O(N) cost), etc. whereas a Zipper is "correct by construction"; i.e. every value of type (List[A], A, List[A]) makes sense as a zipper; whereas many values of…

> accessing an arbitrary list index is O(N)

I think you mean linked-list here. Parent is talking about "arrays".

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

#454

Post by mathgenius »

mastermedo wrote: post #209
chriswarbo wrote: post #181

The Zipper acts like a linked-list with a cursor, or "focused element"; it's implemented as a pair of lists in opposite orders; or, equivalently but more symmetric, as triple of (List[A], A, List[A]) Say we have a zipper containing [0, 1, 2, 3, 4, 5], and we're focusing on the 3. In code this will look like: ([2, 1, 0], 3, [4, 5]) Where [a, b, c] denotes a singly-linked list, with O(1) head (returning a) and tail (re…

I don’t understand why wouldn’t you just use a list and an index. You can always access list[index+1] or list[index-1] or list[0] or list[list.length-1]. What is the benefit here?

This zipper stuff is for immutable data structures.. For us normal folk that just use & abuse array's we don't need zippers. :-). Just kidding. I am dieing to find a use for zippers tho, i'm not a functional programmer.

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

#455

Post by earthnail »

Vantage-point trees. Great structure for nearest neighbour searches.

Bonus tip: When you have a fast distance function (like a hamming distance) and write your tree from scratch in C (which almost automatically means you'll optimise it for your use case), they can become absurdly fast - much faster than the general-purpose nearest neighbour libraries I'm aware of.

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

#456

Post by RF_Savage »

Low Density Parity Codes (LDPC) (1).

So good forward error correction that up toa few years ago it was all under patents.

Gold Codes (2) are also very cool in CDMA systems.

[1] https://en.m.wikipedia.org/wiki/Low-density_parity-check_cod...

[2] https://en.m.wikipedia.org/wiki/Gold_code

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

#457

Post by pflanze »

wingspan wrote: post #443
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…

I love this approach and have used it many times in JavaScript. I often end up adding an additional map in front with the resolved values to check first, because awaiting or then'ing a Promise always means you will wait until the next microtask for the value, instead of getting it immediately. With a framework like React, this means you'll have a flash of missing content even when it is already cached.

Replacing the promise with the result in the map (using a sum type as the map value type) might be more efficient than maintaining two maps?

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

#458

Post by djmips »

kcbanner wrote: post #182

"This is the story of a clever trick that's been around for at least 35 years, in which array values can be left uninitialized and then read during normal operations, yet the code behaves correctly no matter what garbage is sitting in the array. Like the best programming tricks, this one is the right tool for the job in certain situations. The sleaziness of uninitialized data access is offset by performance improveme…

I've used this type of data structure in the past for things like managing sprite DMA on old consoles. It's very friendly to old systems with simple memory access patterns.

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

#459

Post by almog »

The Hierarchical Timing Wheels is an efficient data structure/algorithm for managing timers (event scheduling) when: 1. The timers variance is large. 2. Timers are likely to be cancelled. 3. A fixed (configurable) precision is configurable.

This talk provides a nice overview of different timing wheels implementations including hierarchial and hashed timing wheels.

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

#460

Post by thegeomaster »

vvanders wrote: post #42
jiggawatts wrote: post #25

Cache-Oblivious Data Structures: https://cs.au.dk/~gerth/MassiveData02/notes/demaine.pdf A vaguely related notion is that naive analysis of big-O complexity in typical CS texts ignores over the increasing latency/cost of data access as the data size grows. This can't be ignored, no matter how much we would like to hand-wave it away, because physics gets in the way. A way to think about it is that a CPU core is like a…

Realtime collision detection[1] has a fantastic chapter in this with some really good practical examples if I remember right. Great book, I used to refer to it as 3D "data structures" book which is very much in theme with this thread. [1] https://www.amazon.com/Real-Time-Collision-Detection-Interac...

It's a stellar book. I work on a commercial realtime physics engine, the "orange book" is practically required reading here.
Post reply on HN