6 ms·

I'm trying to work out how apps like this and trello calculate and store card poisition with as little overhead as possible. It seems obvious that every time y

by dwarner 11y ago

I'm trying to work out how apps like this and trello calculate and store card poisition with as little overhead as possible. It seems obvious that every time you move a card to a column, you recalculate the order of every card, however that has overhead because you have to send the new order of every card to the server. Is there a more efficient way to solve this problem? It seems to me it would be more efficient to assign a position value for only the card you are moving relative to those before and after it. I'm sure trello has solved this

totallymike 11y ago
You might be able to watch the network tab in the chrome developer tools to see what they send back and forth. Trello also has an api that may prove illustrative.
tortilla 11y ago
Take a look at this Rails gem, https://github.com/mixonic/ranked-model/ https://github.com/mixonic/ranked-model/ It's a bit more efficient than traditional ordering... From the readme: ranked-model is also optimized to write to the database as little as possible: ranks are stored as a number between -8388607 and 8388607 (the MEDIUMINT range in MySQL)
thedufer 11y ago
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.

by dwarner 11y ago

totallymike 11y ago

You might be able to watch the network tab in the chrome developer tools to see what they send back and forth. Trello also has an api that may prove illustrative.

tortilla 11y ago

Take a look at this Rails gem, https://github.com/mixonic/ranked-model/ https://github.com/mixonic/ranked-model/ It's a bit more efficient than traditional ordering... From the readme: ranked-model is also optimized to write to the database as little as possible: ranks are stored as a number between -8388607 and 8388607 (the MEDIUMINT range in MySQL)

thedufer 11y ago

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.