Optimize sorted list

[fulldecent]

This new API is more efficient assuming update is run more often than ranking.

1. Update: 1 SSTORE, N SLOAD
2. Ranking: 2N SLOAD

---

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

// todo: getDataSize 必须不要回答0（现在可以回答0）

library TopN {
    // stores the top N scores, order is undefined, except that any zero scores are at the end
    struct List {
        uint256 maxLength;
        mapping(uint256 => bytes32) public keys;
        mapping(uint256 => uint256) public values;
    }

    error InvalidKey(bytes32 key);

    error ValueTooSmall(uint256 value);

    error MaxLengthCannotShrink();

    /// @notice 获取一个值
    /// @param  self      TopN数据结构
    /// @param  maxLength 最大长度， 必须不小于当前最大长度
    function setMaxLength(List storage self, uint256 maxLength) public {
        if (maxLength < self.maxLength) {
            revert MaxLengthCannotShrink();
        }
        self.maxLength = maxLength;
    }

    /// @notice 更新一个值
    /// @param  self  TopN数据结构
    /// @param  key   键，必须部位0
    /// @param  value 值，必须大于当前这个key的值
    function updateValue(List storage self, bytes32 key, uint256 value) public {
        if (key == bytes32(0)) {
            revert InvalidKey(key);
        }
        if (value == 0) {
            revert ValueTooSmall(value);
        }

        // 找最小的值，如果比最小的值还小，就不用更新了
        uint256 replaceAt = 0;
        uint256 replaceValue = 0;
        bool found = false;
        for (uint256 i = 0; i < self.maxLength; i++) {
            uint256 v = self.values[i];
            if (v == 0) {
                // insert
                self.keys[i] = key;
                self.values[i] = value;
                return;
            }
            if (self.keys[i] == key) {
                if (value <= v) {
                    revert InvalidValue(value);
                }
                self.values[i] = value;
                return;
            }
            if (value > v && (v < replaceValue || !found)) {
                replaceValue = v;
                replaceAt = i;
                found = true;
            }
        }
        if (found) {
            self.keys[replaceAt] = key;
            self.values[replaceAt] = value;
        }
    }

    // todo: 如果不同的key有相同的value，他们每一个ranking一样。这个好吗？

    /// @notice 考虑一个key的排名
    /// @param  self  TopN数据结构
    /// @param  key   键，必须部位0
    /// @return 最大为1，第二大为2。。。。。。，如果不存在，返回0
    function getRanking(List storage self, bytes32 key) public view returns (uint256) {
        // 找key和value
        uint256 keyValue = 0;
        for (uint256 i = 0; i < self.maxLength; i++) {
            if (self.keys[i] == key) {
                keyValue = self.values[i];
                break;
            }
            if (self.keys[i] == bytes32(0)) {
                return 0;
            }
        }
        if (keyValue == 0) {
            return 0;
        }

        // 找比这个值大的值
        uint256 ranking = 1;
        for (uint256 i = 0; i < self.maxLength; i++) {
            if (self.values[i] > keyValue) {
                ranking += 1;
            }
            if (self.values[i] == 0) {
                break;
            }
        }
        return ranking;
    }
}

[weiqiushi]

Thanks for the Issue! I'm a new bee for Solidity(only about 1 ~ 2 months), so I prefer to use C-like algorithms to solve problems. I'm very inspired by your idea!

However, according to the documentation (doc/erc/ideas.md), items with the same score in the sorted list MUST return different rankings, which is related to the reward algorithm at reward cycle end. Therefore, if getRanking() returns the same rankings for the same values, which would cause an incorrect rewards.

I'll continue to refer to your thoughts on optimizing sorted lists.

Thanks again for your Issue!

[fulldecent]

This approach here also supports giving the lower ranking if there is a tie.

So 20, 20, 20, 30 would produce ranking of 3, 3, 3, 4.

In Solidity I have not seen projects that sort data on on-chain because it is so expensive. Let's benchmark it well and decide the acceptable gas. It may be necessary to pick a different game mechanism if the gas costs are prohibitive.

[weiqiushi]

According to the gas cost reported by npm package hardhat-gas-reporter, if we insert 40 items which has random hash and score(0-1000) to 32 length list ,it costs:	Contract	Method	Min	Max	Avg	# calls
TestList	addScore	27415	231323	147442	83
TestList	setMaxLen	29674	46774	38224	4

when insert into a 16 length list, it costs:	Contract	Method	Min	Max	Avg	# calls
TestList	addScore	27415	155292	124574	83
TestList	setMaxLen	29674	46774	38224	4

I`m not familiar with gas limit but I think it may be acceptable?

[fulldecent]

Are those typical usage scenarios? We expecting 40 participants and each one only sets the score once?

Or will there be many participants and each one is updating the score frequently?