Storing and sorting large numbers of objects

Move
1

Is there a recommended way for storing and sorting a large number of objects (or even just hundreds)? It seems like you could use dynamic object field tabless with a u64 as the key that provides the order of the objects (e.g. the first object is at key 1, second object at key 2, etc), but sorting by removing the object from the table and adding it back in at a different key is expensive. At the same time just storing the data in a local vector gets expensive as well. Based on my experience so far the vector seems to be the best option, but wondering if some sort of linked list implementation using dynamic object fields might work (seems like it would get expensive trying to find the correct place in the sorted list to insert).

13 Likes
2

Replaying this convo from elsewhere:

My specific context is a leaderboard. I want to be able to insert a game summary struct into the leaderboard at the appropriate location (depending on the score of the game) and be able to iterate over the leaderboard to display the results in order. So I need to be able to order it based on the score and iterate over it in sorted order (or at least retrieve each item in sorted order). Does that answer your question?

Got it. Here are some thoughts.

  • One approach is to not do the ordering on-chain at all–e.g., you can keep the Score objects either in a vector or in dynamic fields, emit an event each time you add a new Score, and (in the UI code) tail the relevant event stream + use insertion sort to keep your scoreboard up-to-date. This will almost certainly be the cheapest from a gas cost perspective, and should work well if there are only 100s of scores.
  • Another approach is to maintain an ordered vector scores: vector, derive a dynamic field from each score, and place the relevant score object(s) there. If the Score objects are big and there are only 100s, I think this is a reasonable approach–otherwise, putting them directly in the vector might be easier/cheaper
  • Finally, you could do a dynamic fields-powered binary search tree ordered by score. We should probably have a library like this.
11 Likes