2

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?

1
  • Unless you index this in the contract itself, there's really no graceful way to get the top X balances without looping through all iterations.
    – ReyHaynes
    Mar 28, 2018 at 13:49

2 Answers 2

3

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.

0
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;
1
  • This can lead to duplicate entries of the same address. Any suggestions how to prevent that? I considered first removing it from the topBalances (by setting its balance to zero), but then you can end up with a "gap" in your topBalances
    – Marc
    Oct 18, 2021 at 16:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.