Hacker News Reader

Comment by dwarner | Hacker News Reader

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

View on HN

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.

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

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

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.

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.

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.

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?

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.

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.

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.

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.

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.

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.

The complexity sounds fairly similar, but my point is that there's a world of difference between server-side complexity (implement once) and client side (implement 3 dozen or so times).

Fair enough. Getting a usable API that works reliably here is tricky though. I've often fallen back to a sort of indirection like "move this card right after that one" ... this only works if you can calculate that right away since that card can be moved by some other agent.

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

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...

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?

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.

Take a look at this Rails gem, 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)

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.

Reply on news.ycombinator.com