4 ms·

You can get much farther by storing a fraction. Still, a midpoint is not the most effective point to chose. One solution I've explored is in the form of fractio

by strmpnk 11y ago

You can get much farther by storing a fraction. Still, a midpoint is not the most effective point to chose. One solution I've explored is in the form of fractions generated by the Stern-Brocot tree. The continued fraction representation is easy to work with and can easily be turned into other representations. With that, you could pick ideal points between bounds very cheaply: (1/4, 1/2) → 1/3 (4/3, 5/2) → 2/1 (5/4, 7/5) → 4/3 In languages with large integers, it's quite easy to store two numbers. In a language like JavaScript, 53 bits of the mantissa in a double floating point number give 70+ moves [1] before you'd have to worry about losing precision, and if that were a deal breaker, a continued fraction is very cheap to store instead. If people are interested, I'd be happy to share some implementations I've got in a number of languages including Erlang and JavaScript (I'm rewriting these from a prior version I did which used a slightly less optimal path representation). [1] These are worst case. Most interactions could survive 1000+ resorts in practice. I've yet to see any of the components outgrow the 53bit mantissa of a double in JavaScript. The worse case grows with the Fibonacci sequence which is easy to see once you learn more about the Stern-Brocot tree structure. Even when they do grow large though, it's easy to switch to the continued fraction representation which solves this problem. EDIT: Here is a short list of indices from a production database where it's easy to see why fractions are far superior to floating point indices: https://gist.github.com/strmpnk/d4afe4bb5bb69b46631b https://gist.github.com/strmpnk/d4afe4bb5bb69b46631b

papa_bear 11y ago
I'd really love to see a JavaScript implementations of this if you're willing to share
- strmpnk 11y ago
  I'll wrap up a new version of the library that's independent of what I have it hooked up to and upload it to npm and hex.pm respectively. When I first wrote it, I started with midpoints but it doesn't take long to see that it gets messy to optimize. I eventually stumbled on the b-tree representation of all positive rational numbers (Stern-Brocot) and the optimization became obvious.
vbezhenar 11y ago
Thank you very much. That problem was bothering me for quite a long time, but I couldn't figure out correct term for googling. Another solution I made myself is just to use string as a key. If you need to insert something between "a" and "b", it'll become "an". If you need to insert something between "an" and "am", it'll become "ann", etc. It uses 26 letters but probably should use 64 different characters. This way you'll manipulate strings, they could be easily sorted and you'll figure out next string quite fast. But they could grow long, so entire recalculation should be done from time to time.
- strmpnk 11y ago
  Yes. This is very similar if you consider the path on the b-tree with the alphabet L, R. It doesn't follow traditional lexical sorting though since RRL (5/2) comes before RR (3/1). This is handy though. Consider having something at index 'a'. Now find something that comes right before it. You can't if you use traditional alphabetical ordering.
- deleted 11y ago
  [deleted]
bsznjyewgd 11y ago
I'm dense. Why is it less effective to choose the midpoint fraction and more effective to choose with the Stern-Brocot tree? Is it just the growth/storage or are there other issues too?
- strmpnk 11y ago
  Growth is one, the average term will be smaller. The real reason to pick this is that the tree is a b-tree so you can pick terms above and bellow, so you can end up with simpler terms, not just more complex ones.
  - strmpnk 11y ago
    Not sure why this got down voted. It's easy to see that points can be selected between two others that are parents in some cases. With mid-points, it usually mixes a fractional part like taking a midpoint 1/2 and then moving the upper bound so the next card is 2 and then moving something between 0.5 and 2. This ends up being a messier fraction. Adding logic to pick 1 instead of 1.25 seems easy but there are a lot of edge cases and ends up creating something that is at least as complex as this simple binary tree that generates all positive rational numbers.
thedufer 11y ago
So, the problem with your approach is that Trello has an open API. This means that they don't control the clients, and also that the API needs to be reasonably easy to understand. "Sort by this attribute" for displaying and "pick literally any floating point number that sorts it into the right position" for moving cards is much easier to get across than what you're describing.
- strmpnk 11y ago
  Sure, you'd need a library but the problem with integral sorting is that operations must be totally ordered. This starts showing limits under stress of heavy collaboration. There is more than one way to solve this but most solutions either have unstable merges or involve the same point on a number line concept. The above might seem odd but is much more reliable than midpoints and not hard to implement. The representation of the index can use multiple formats, one of the easiest is just a pair of numbers in a fraction. The problem with floating point numbers is that you'lol lose precision faster than you might expect. See my gist for an example of 40 fractions from a production database where there is no double precision floating point number between them.
  - thedufer 11y ago
    Like I said, Trello re-numbers when things get to close together, so you never see something like that. Obviously there are trade-offs, but very occasional re-numbering vs. a ton more complexity seems like an easy decision. "you'd need a library" is not a solution when you have API consumers in dozens of languages.
    - strmpnk 11y ago
      If you can sort fractions and call a function to get something between two points, then that's the entirety of the complexity. The "library" is about a hundred lines in JS and less in Erlang. The logic, which I have written in the past to do conditional reindexing has a worse interface and ends up with about the same LOC burden. Seriously, I've done both of these and the complexity is about the same. One route just ends up with a much better separation of concerns where the other has surprising edge cases which I see hit far more often than I would have imagined.

by strmpnk 11y ago

papa_bear 11y ago

I'd really love to see a JavaScript implementations of this if you're willing to share

strmpnk 11y ago
I'll wrap up a new version of the library that's independent of what I have it hooked up to and upload it to npm and hex.pm respectively. When I first wrote it, I started with midpoints but it doesn't take long to see that it gets messy to optimize. I eventually stumbled on the b-tree representation of all positive rational numbers (Stern-Brocot) and the optimization became obvious.

vbezhenar 11y ago

Thank you very much. That problem was bothering me for quite a long time, but I couldn't figure out correct term for googling. Another solution I made myself is just to use string as a key. If you need to insert something between "a" and "b", it'll become "an". If you need to insert something between "an" and "am", it'll become "ann", etc. It uses 26 letters but probably should use 64 different characters. This way you'll manipulate strings, they could be easily sorted and you'll figure out next string quite fast. But they could grow long, so entire recalculation should be done from time to time.

strmpnk 11y ago
Yes. This is very similar if you consider the path on the b-tree with the alphabet L, R. It doesn't follow traditional lexical sorting though since RRL (5/2) comes before RR (3/1). This is handy though. Consider having something at index 'a'. Now find something that comes right before it. You can't if you use traditional alphabetical ordering.
deleted 11y ago
[deleted]

bsznjyewgd 11y ago

I'm dense. Why is it less effective to choose the midpoint fraction and more effective to choose with the Stern-Brocot tree? Is it just the growth/storage or are there other issues too?

strmpnk 11y ago
Growth is one, the average term will be smaller. The real reason to pick this is that the tree is a b-tree so you can pick terms above and bellow, so you can end up with simpler terms, not just more complex ones.
- strmpnk 11y ago
  Not sure why this got down voted. It's easy to see that points can be selected between two others that are parents in some cases. With mid-points, it usually mixes a fractional part like taking a midpoint 1/2 and then moving the upper bound so the next card is 2 and then moving something between 0.5 and 2. This ends up being a messier fraction. Adding logic to pick 1 instead of 1.25 seems easy but there are a lot of edge cases and ends up creating something that is at least as complex as this simple binary tree that generates all positive rational numbers.

thedufer 11y ago

So, the problem with your approach is that Trello has an open API. This means that they don't control the clients, and also that the API needs to be reasonably easy to understand. "Sort by this attribute" for displaying and "pick literally any floating point number that sorts it into the right position" for moving cards is much easier to get across than what you're describing.

strmpnk 11y ago
Sure, you'd need a library but the problem with integral sorting is that operations must be totally ordered. This starts showing limits under stress of heavy collaboration. There is more than one way to solve this but most solutions either have unstable merges or involve the same point on a number line concept. The above might seem odd but is much more reliable than midpoints and not hard to implement. The representation of the index can use multiple formats, one of the easiest is just a pair of numbers in a fraction. The problem with floating point numbers is that you'lol lose precision faster than you might expect. See my gist for an example of 40 fractions from a production database where there is no double precision floating point number between them.
- thedufer 11y ago
  Like I said, Trello re-numbers when things get to close together, so you never see something like that. Obviously there are trade-offs, but very occasional re-numbering vs. a ton more complexity seems like an easy decision. "you'd need a library" is not a solution when you have API consumers in dozens of languages.
  - strmpnk 11y ago
    If you can sort fractions and call a function to get something between two points, then that's the entirety of the complexity. The "library" is about a hundred lines in JS and less in Erlang. The logic, which I have written in the past to do conditional reindexing has a worse interface and ends up with about the same LOC burden. Seriously, I've done both of these and the complexity is about the same. One route just ends up with a much better separation of concerns where the other has surprising edge cases which I see hit far more often than I would have imagined.