What's the best way to return top X values in a mapping?

Question

Let's say I have

mapping(address => uint) balances;

and there are over 25.000 in this.
What would be the best way to filter out top 10 values?

Example:
balances[0x0] = 100.000;
balances[0x1] = 90.000;
balances[0x2] = 85.151;
balances[0x3] = 72.444;

For me it does not matter if it's in the contract or through javascript, I just need a good way to return the top X (for example top 10) values of the array without need to go through 25k values. Is that possible?

Answer 1

Yes, create a 2nd mapping that will contains the top 10 values and on each buy/sell operations, iterate trough this mapping to check if balance is greater than any top 10 addresses.

With this solution, you just need to iterate over all entries one time to prefill.

Answer 2

It's possible but I wouldn't suggest you to cycle the entire collection to get the top 10 elements, that gonna be too expensive. Would be better if you actually save the top X elements during the elaboration.

Assume that you will have a method that gonna save the balance into your mapping

mapping(address => uint) balanceOf;

function pay() public payable {
    require(msg.value > 0);
    balanceOf[msg.sender] = msg.value;
}

you might change it adding the algorithm to actually calculate the top X elements just after you added the new one into your mapping

So your method gonna be something like

function pay2() public payable {
    require(msg.value > 0);
    balanceOf[msg.sender] = msg.value;
    elaborateTopX(msg.sender, msg.value);
}

function elaborateTopX(address addr, uint currentValue) private {
    uint i = 0;
    /** get the index of the current max element **/
    for(i; i < topBalances.length; i++) {
        if(topBalances[i].balance < currentValue) {
            break;
        }
    }
    /** shift the array of position (getting rid of the last element) **/
    for(uint j = topBalances.length - 1; j > i; j--) {
        topBalances[j].balance = topBalances[j - 1].balance;
        topBalances[j].addr = topBalances[j - 1].addr;
    }
    /** update the new max element **/
    topBalances[i].balance = currentValue;
    topBalances[i].addr = addr;
}

where topBalances is an array defined in this way:

struct TopBalance {
    uint balance;
    address addr;
}
TopBalance[10] public topBalances;