Алгоритм нахождения высоких баллов в Солидности / Эфириуме

Question

С точки зрения минимизации затрат на газ (или любого другого соответствующего эталонного теста), как лучше всего использовать Solidity для сортировки массива значений и определения наивысших баллов?Если это имеет значение, все цифры находятся в довольно узком диапазоне

Answer 1

Подход

Мирга - лучший путь, если вы хотите сохранить несколько лучших результатов.Очевидно, что если вам нужно отсортировать все элементы, такой подход не будет наиболее эффективным, особенно если массив становится длиннее.

В общем, вам следует избегать сортировки в блокчейне.Это будет очень дорого, и вы можете столкнуться с нехваткой газа из-за увеличения размера массива.Если вы ДОЛЖНЫ сортировать по цепочке, вы, вероятно, захотите использовать heapsort .

Answer 2

Я не знаю, есть ли лучший способ или нет, но я обычно отслеживаю самые высокие числа, когда вы добавляете новый элемент в массив

function refreshTopXOrdered(uint value) private {
    uint i = 0;
    /** get the index of the current max element **/
    for(i; i < topElementsOrdered.length; i++) {
        if(topElementsOrdered[i] < value) {
            break;
        }
    }
    /** shift the array of one position (getting rid of the last element) **/
    for(uint j = topElementsOrdered.length - 1; j > i; j--) {
        topElementsOrdered[j] = topElementsOrdered[j - 1];
    }
    /** update the new max element **/
    topElementsOrdered[i] =  value;
}

, где topElementsOrdered - это просто массив спредопределенный размер:

uint[3] public topElementsOrdered; //can be any size

. Он будет отслеживать изменения, пока вы добавляете свои элементы, и сохраняете верхние элементы в порядке (в порядке убывания).

Предположим, чтобы вызывать его таким образом

uint[] elements;

function add(uint value) public {
    elements.push(value);
    refreshTopXOrdered(value);
}