5 ms·

Also known as an order-statistic tree. Good for obscure leetcode problems, though I've never needed to implement one in my whole career. [1] https://en.wikiped

Also known as an order-statistic tree. Good for obscure leetcode problems, though I've never needed to implement one in my whole career. [1] https://en.wikipedia.org/wiki/Order_statistic_tree https://en.wikipedia.org/wiki/Order_statistic_tree

erikrozendaal 2y ago
Funnily enough this is (was?) used by the Scala collection library's TreeSet/TreeMap, for fast performance of the `take` and `drop` operations. This is a red-black tree though, not a B-Tree. Commit https://github.com/scala/scala/pull/82/commits/b7e671446892c232afdfb5e36ceeab135ece649b https://github.com/scala/scala/pull/82/commits/b7e671446892c... of PR https://github.com/scala/scala/pull/82 https://github.com/scala/scala/pull/82
throw_pm23 2y ago
Hard to evaluate your comment without knowing in what field your career is.
josephg 2y ago
I’ve done a few implementations of this data structure recently. It’s an essential part of making a high performance CRDT for collaborative text editing. I haven’t found any decent 3rd party order statistic tree online that I can use for CRDTs for 2 reasons: 1. I want my tree to be internally run-length encoded. Ie, each item in my tree represent an adjacent runs of inserted characters in the document. In my tests, this seems to make the data structure about 20x smaller. But it adds complexity - we also need to be able to later split those runs if we discover an insert in the middle of any run. 2. I also need random access. Items have a unique ID, and I need to be able to find any item by looking up its ID. The IDs are just auto incremented integers to make the run length encoding work. You end up with a pretty custom set of data structures, but the result is a system which performs fabulously well in practice. The fastest implementation I know of of this stuff is the Cola crdt library, which is written in 100% safe rust.
- yencabulator 2y ago
  FYI "run-length encoded" means compressing repetitions. "123 repeats of the character 'x'" would be RLE. You seem to be talking about keeping a tree-of-strings instead of tree-of-characters, to decrease the overhead. https://en.wikipedia.org/wiki/Run-length_encoding https://en.wikipedia.org/wiki/Run-length_encoding
  - o11c 2y ago
    It's almost like a RangeMap, of which there are at least 3 notable variations: * The basic RangeMap, where a range of adjacent keys all map to the same value * The computed RangeMap, where a range of adjacent keys all map to adjacent values (common for e.g. case-conversion of Unicode, can also come up for IP addresses) * The DenseMap, where a range of adjacent keys map to arbitrary values, but use an array for memory optimization. The first two actually can be made to work for string-like keys. The last is only possible for integer-like keys; use a carefully chosen trie design for string-like keys.
  - josephg 2y ago
    It’s not “123 repeats of the character x”, and it’s not a tree of characters either. The sibling comment is right. The data is crdt metadata. If you type a series of characters, each character has some fields. In my case, this is an id (autoincrementing integer), and origin-left and origin-right (the id of the items immediately to the left and right when the character was typed). If a user types a continuous run of 100 characters, we don’t need to actually store all 100 IDs - since they’re just, say, the numbers 1000-1100 in order. The origin-right for all items will be the same. And we don’t need to store the origin-left for each one. The first item in the run has an unguessable left origin (say, 600). But the rest will have an origin-left equal to the id of the previous item. Ie, 1000, 1001, 1002, and so on up to 1099. Naively you’d need 300 integers to store the metadata for 100 contiguous items. But if you’re clever, a run of 100 items only needs to store a start id, length (or end id), the origin-left of the first item in the run and the common origin-right for all the items in the run. That’s just 4 integers, which I store in a single fixed sized entry in the btree. Because of how humans actually type, this compression makes a big difference in practice. In code, I have a pair of rust traits for Splitable and Mergable which define functions like len(), can_append(), append(), truncate(), split() and so on. Then I have a generic order statistic tree implementation which stores Splitable & Mergable items. Run-length encoding is the best term I’ve seen for this kind of packing. It’s definitely not a tree of strings - the document text itself is stored in a completely separate data structure. (In my case, a skip list). (Credit for the run length encoding goes to Kevin Jahns, author of Yjs.)
chipdart 2y ago
> Good for obscure leetcode problems (...) God, I hate how pointless leetcode has become, and how it's used in interviews. Smug assholes using obscure data structures and algorithms trivia that no one ever used at all in any professional setting, and which the interviewer only learned about because he spent a week searching for a coding problem, to decide whether you are competent at putting a button on a window.
- josephg 2y ago
  > that no one ever used at all in any professional setting, (…), to decide whether you are competent at putting a button on a window. Some software jobs involve more than putting a button on a window.
  - crest 2y ago
    Maybe they should keep interviewing for jobs that require nothing more complex, important, or dangerous than that.
- kccqzy 2y ago
  It's also about your communication skills and ability to use existing knowledge even when it isn't the most suitable. A while ago in an interview I was asked a problem for which the correct solution is in fact an order statistic tree, but not knowing that, I solved the problem using more standard data structures with worse complexity, and pointed out their limitation. I still passed that interview.
- deciplex 2y ago
  I mean, fwiw sometimes "obscure data structures" really do cleanly, efficiently, and performatively solve a problem that would have been a nightmare to address with simpler, more well known structures. That said, for most of us, it's rare enough to be memorable - but it does happen. I think you're right that requiring such knowledge off the top of one's head and in the context of a one-hour interview is almost always unreasonable, though. What I'd really want to know is how well a person can do the research to arrive at performant solutions involving, as you say, obscure data structures. In an interview context though, I think you basically just have to ask them - would be nice if you could get a sense of it through doing, though.
hawk_ 2y ago
I have had to implement it but still I wouldn't use it directly for an interview.
- kragen 2y ago
  what were you using it for

erikrozendaal 2y ago

Funnily enough this is (was?) used by the Scala collection library's TreeSet/TreeMap, for fast performance of the `take` and `drop` operations. This is a red-black tree though, not a B-Tree. Commit https://github.com/scala/scala/pull/82/commits/b7e671446892c232afdfb5e36ceeab135ece649b https://github.com/scala/scala/pull/82/commits/b7e671446892c... of PR https://github.com/scala/scala/pull/82 https://github.com/scala/scala/pull/82

throw_pm23 2y ago

Hard to evaluate your comment without knowing in what field your career is.

josephg 2y ago

I’ve done a few implementations of this data structure recently. It’s an essential part of making a high performance CRDT for collaborative text editing. I haven’t found any decent 3rd party order statistic tree online that I can use for CRDTs for 2 reasons: 1. I want my tree to be internally run-length encoded. Ie, each item in my tree represent an adjacent runs of inserted characters in the document. In my tests, this seems to make the data structure about 20x smaller. But it adds complexity - we also need to be able to later split those runs if we discover an insert in the middle of any run. 2. I also need random access. Items have a unique ID, and I need to be able to find any item by looking up its ID. The IDs are just auto incremented integers to make the run length encoding work. You end up with a pretty custom set of data structures, but the result is a system which performs fabulously well in practice. The fastest implementation I know of of this stuff is the Cola crdt library, which is written in 100% safe rust.

yencabulator 2y ago
FYI "run-length encoded" means compressing repetitions. "123 repeats of the character 'x'" would be RLE. You seem to be talking about keeping a tree-of-strings instead of tree-of-characters, to decrease the overhead. https://en.wikipedia.org/wiki/Run-length_encoding https://en.wikipedia.org/wiki/Run-length_encoding
- o11c 2y ago
  It's almost like a RangeMap, of which there are at least 3 notable variations: * The basic RangeMap, where a range of adjacent keys all map to the same value * The computed RangeMap, where a range of adjacent keys all map to adjacent values (common for e.g. case-conversion of Unicode, can also come up for IP addresses) * The DenseMap, where a range of adjacent keys map to arbitrary values, but use an array for memory optimization. The first two actually can be made to work for string-like keys. The last is only possible for integer-like keys; use a carefully chosen trie design for string-like keys.
- josephg 2y ago
  It’s not “123 repeats of the character x”, and it’s not a tree of characters either. The sibling comment is right. The data is crdt metadata. If you type a series of characters, each character has some fields. In my case, this is an id (autoincrementing integer), and origin-left and origin-right (the id of the items immediately to the left and right when the character was typed). If a user types a continuous run of 100 characters, we don’t need to actually store all 100 IDs - since they’re just, say, the numbers 1000-1100 in order. The origin-right for all items will be the same. And we don’t need to store the origin-left for each one. The first item in the run has an unguessable left origin (say, 600). But the rest will have an origin-left equal to the id of the previous item. Ie, 1000, 1001, 1002, and so on up to 1099. Naively you’d need 300 integers to store the metadata for 100 contiguous items. But if you’re clever, a run of 100 items only needs to store a start id, length (or end id), the origin-left of the first item in the run and the common origin-right for all the items in the run. That’s just 4 integers, which I store in a single fixed sized entry in the btree. Because of how humans actually type, this compression makes a big difference in practice. In code, I have a pair of rust traits for Splitable and Mergable which define functions like len(), can_append(), append(), truncate(), split() and so on. Then I have a generic order statistic tree implementation which stores Splitable & Mergable items. Run-length encoding is the best term I’ve seen for this kind of packing. It’s definitely not a tree of strings - the document text itself is stored in a completely separate data structure. (In my case, a skip list). (Credit for the run length encoding goes to Kevin Jahns, author of Yjs.)

chipdart 2y ago

> Good for obscure leetcode problems (...) God, I hate how pointless leetcode has become, and how it's used in interviews. Smug assholes using obscure data structures and algorithms trivia that no one ever used at all in any professional setting, and which the interviewer only learned about because he spent a week searching for a coding problem, to decide whether you are competent at putting a button on a window.

josephg 2y ago
> that no one ever used at all in any professional setting, (…), to decide whether you are competent at putting a button on a window. Some software jobs involve more than putting a button on a window.
- crest 2y ago
  Maybe they should keep interviewing for jobs that require nothing more complex, important, or dangerous than that.
kccqzy 2y ago
It's also about your communication skills and ability to use existing knowledge even when it isn't the most suitable. A while ago in an interview I was asked a problem for which the correct solution is in fact an order statistic tree, but not knowing that, I solved the problem using more standard data structures with worse complexity, and pointed out their limitation. I still passed that interview.
deciplex 2y ago
I mean, fwiw sometimes "obscure data structures" really do cleanly, efficiently, and performatively solve a problem that would have been a nightmare to address with simpler, more well known structures. That said, for most of us, it's rare enough to be memorable - but it does happen. I think you're right that requiring such knowledge off the top of one's head and in the context of a one-hour interview is almost always unreasonable, though. What I'd really want to know is how well a person can do the research to arrive at performant solutions involving, as you say, obscure data structures. In an interview context though, I think you basically just have to ask them - would be nice if you could get a sense of it through doing, though.

hawk_ 2y ago

I have had to implement it but still I wouldn't use it directly for an interview.

kragen 2y ago
what were you using it for