4 ms·

Trello gives each card a `pos` attribute, which is simply a double (64-bit float). When the first card in a list is created, it is given a `pos` of 16384. Whe

Trello gives each card a `pos` attribute, which is simply a double (64-bit float). When the first card in a list is created, it is given a `pos` of 16384. When a card is added to the end of a list it is given <pos of last card> + 16384. If added to the beginning, it is given <pos of first card> / 2. If inserted between two cards, it is simply the average of the two neighbors. Finally, if two cards end up with values too close together (just some magic number - .0001 apart or something) then those cards and some nearby are all re-numbered. This means that most of the time you only have to update a single card. In degenerate movement cases, you might update up to an entire list, but that can only happen every so many moves (~20 or so, but depends on exact values) even in the worst case.

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?
mhw 11y ago
An approach that would be familiar to anyone who has programmed in vintage BASIC with line numbers!
e12e 11y ago
While interesting, I wonder if this makes any sense in terms of performance vs simply using a linked-list (or some kind of built-in equivalent, maybe backed by a binary tree, or something)? How many cards are you going to have in a given stack anyway? All you need is a list of card-ids (integers?) -- It's not like this has to run on a micro-controller...
- throwupper247 11y ago
  I'm not sure if those are the meassures that guide the decision: Searching in linked lists is suboptimal (was it O(n)?), as is their cache performance. Sure, with small lists, that doesn;t matter, but how small is small enough?
welanes 11y ago
Incredible. I'm actually scrolling HN during a break from 3 hours of trying to optimize a solution to this problem. Came up with something like this but wanted to avoid ever having to update the entire list. A combo of Rubaxa Sortable's 'onEnd' option and Vue to render card properties in HTML attributes make it easy.

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?

mhw 11y ago

An approach that would be familiar to anyone who has programmed in vintage BASIC with line numbers!

e12e 11y ago

While interesting, I wonder if this makes any sense in terms of performance vs simply using a linked-list (or some kind of built-in equivalent, maybe backed by a binary tree, or something)? How many cards are you going to have in a given stack anyway? All you need is a list of card-ids (integers?) -- It's not like this has to run on a micro-controller...

throwupper247 11y ago
I'm not sure if those are the meassures that guide the decision: Searching in linked lists is suboptimal (was it O(n)?), as is their cache performance. Sure, with small lists, that doesn;t matter, but how small is small enough?

welanes 11y ago

Incredible. I'm actually scrolling HN during a break from 3 hours of trying to optimize a solution to this problem. Came up with something like this but wanted to avoid ever having to update the entire list. A combo of Rubaxa Sortable's 'onEnd' option and Vue to render card properties in HTML attributes make it easy.