Content
@
https://warpcast.com/~/channel/solidity
0 reply
0 recast
0 reaction
Noah Bragg 🔥
@nbragg
Solidity devs: How possible is it to store a large array to hold a leaderboard onchain? It would need to be updated as it changes and shifted around. My gut reaction as that this would be too expensive to make happen. Is on a layer2 at least. Or are there any better solutions?
7 replies
0 recast
10 reactions
flick the dev 🎩📦
@flick
it all you need is to go from score to rank and rank to score (but not, for example, rank to player) then sparse trees and a little magic could possibly work https://github.com/0xFlicker/ranker/blob/main/src%2Franker%2Franker.ts
1 reply
0 recast
0 reaction
Noah Bragg 🔥
@nbragg
this sin't onchain though is it?
1 reply
0 recast
1 reaction
flick the dev 🎩📦
@flick
no, it's just an efficient ranking algorithm I have used in web2
1 reply
0 recast
0 reaction
Noah Bragg 🔥
@nbragg
Gotcha. Thanks!
1 reply
0 recast
1 reaction
flick the dev 🎩📦
@flick
it has an update and read somewhere below O(n) the data structure is a map of int arrays that define a tree structure. the tree has addressable deterministic nodes that can be looked up in the map. each node has an array that contains all scores under it and the leaf nodes will be the number of players with a distinct score so starting from the tip, if you want to find a rank n for a score m then you can slice the tree at that score and the top of the tree will have total number of scores for each bucket. eventually you probably will get to bucket you need to slice, so that's when you go down the tree to find which array you can slice to find the exact rank this also means that if you can accept a looser rank, you can even exit this algorithm early to get an approximation of rank updates are a little bit more complicated because you both need to increment and decrement numbers in the tree, but this algorithm supported hundreds of updates per second through a singleton in web2
0 reply
0 recast
0 reaction
