Solidity 优化 - 如何维护排序列表

本文我们探索和讨论在以太坊独特的 EVM 成本模型下编写高效的 Solidity 代码的数据结构和实现技术。读者应该已经对 Solidity 中的编码以及 EVM 的总体工作方式所有了解。
在上一篇文章[6]中，我们讨论了(可以在每个元素上迭代的数据结构)如何在列表中添加元素或从列表中删除元素。这篇文章将扩展我们的数据结构，以维护链上已排序的链表。像上一篇文章一样，我们将通过展示每个函数的实现来进行解释。如果你准备好了，那就开始吧！
场景范例
像上一篇文章[7]一样，我们依旧要创建一个“学校”智能合约，但是这次我们只保留了学生地址列表。我们需要根据他们的分数来维持他们的排序，老师可以在学生中增加或减去他们的分数，并且可以保证学生列表仍然可以随时按分数保持顺序。最后一个要求是我们可以列出排名前 k 的学生，以奖励表现良好的学生。
函数需求
让我们考虑一下满足所有要求所需的函数，需要实现 5 个函数。
· 将新学生添加到具有分数排序的列表中
· 提高学生分数
· 降低学生分数
· 从名单中删除学生
· 获取前 K 名学生名单
实现

但是，在开始实现每个函数之前，我们需要设置基础数据结构(数组，映射等)，我们使用上一篇文章中的可迭代映射[8]。创建映射以存储分数并为每个函数编写接口，框架代码如下所示：

注意：GUARD 是列表的头。
添加带有分数的新学生 addStudent
让我们从第一个函数 addStudent 开始。与普通的可迭代映射有所不同的是，我们需要在正确的索引处插入新项目，而不是在列表的前面添加以维持我们的排序。

为了使代码易于阅读，我们创建了 2 个辅助函数来查找和验证新值的索引。
_verifyIndex 函数用于验证该值在左右地址之间。如果左边的值 ≥ 新值 > 右边的值将返回 true(如果我们保持降序，并且如果值等于，则新值应该在旧值的后面)

_findIndex 帮助函数，用于查找新值应该插入在哪一个地址后面。从 GUARD 遍历列表，通过使用_verifyIndex检查来找到有效的索引。此代码确保我们可以肯定地找到有效的索引

addStudent 在有效索引地址后插入新项目，更新分数并增加 listSize。

从列表中删除学生：removeStudent
removeStudent 的实现与上一篇文章相同，因为如果 a≥b≥c，然后 a≥c，在列表删除 b 之后仍是排序。

辅助函数_isPrevStudent和_findPrevStudent

与上一篇文章相同的 removeStudent 不过需要清除 scores映射。

更新学生分数：increaseScore 和 reduceScore
increaseScore和reduceScore可以使用相同的逻辑来实现，即将旧值更新为新值。主要思想是我们将旧项目临时删除，然后将其添加到新(或相同)索引中，该索引应具有新值，因此我们可以重复使用添加/删除函数。

注意：我们会检查条件，以确定新值是否适合相同的索引，这样我们不需要删除项目并将其添加到相同的值(这只是优化操作，可以节省 1000 gas )
如果我们具有updateScore函数，则可以用一行代码来实现increaseScore和reduceScore函数。

获取前 k 名学生名单：getTop
这个函数没有什么花哨的，只是从 GUARD 循环开始，将地址存储到数组并返回该数组。容易吧？

代码已发布此处[9] , 代码如下：
pragma solidity 0.5.9;
contract School{
mapping(address => uint256) public scores;
mapping(address => address) _nextStudents;
uint256 public listSize;
address constant GUARD = address(1);
constructor() public {
_nextStudents[GUARD] = GUARD;
}
function addStudent(address student, uint256 score) public {
require(_nextStudents[student] == address(0));
address index = _findIndex(score);
scores[student] = score;
_nextStudents[student] = _nextStudents[index];
_nextStudents[index] = student;
listSize++;
}
function increaseScore(address student, uint256 score) public {
updateScore(student, scores[student] + score);
}
function reduceScore(address student, uint256 score) public {
updateScore(student, scores[student] – score);
}
function updateScore(address student, uint256 newScore) public {
require(_nextStudents[student] != address(0));
address prevStudent = _findPrevStudent(student);
address nextStudent = _nextStudents[student];
if(_verifyIndex(prevStudent, newScore, nextStudent)){
scores[student] = newScore;
} else {
removeStudent(student);
addStudent(student, newScore);
}
}
function removeStudent(address student) public {
require(_nextStudents[student] != address(0));
address prevStudent = _findPrevStudent(student);
_nextStudents[prevStudent] = _nextStudents[student];
_nextStudents[student] = address(0);
scores[student] = 0;
listSize–;
}
function getTop(uint256 k) public view returns(address[] memory) {
require(k <= listSize);
address[] memory studentLists = new address[](k “] memory studentLists = new address[“);
address currentAddress = _nextStudents[GUARD];
for(uint256 i = 0; i < k; ++i) {
studentLists[i] = currentAddress;
currentAddress = _nextStudents[currentAddress];
}
return studentLists;
}

有很多 require[10]！我们添加 2 个 require，第一个是检查 candidateStudent 是否存在，第二个是验证新值必须在该 candidateStudent 之后。
removeStudent
只需通过_isPrevStudent进行验证以删除元素。

updateScore

我们添加验证条件，以防万一在同一索引处进行更新。第一个条件就像移除元素，第二个条件检查新值是否在旧索引上有效。
完整的优化代码已发布此处[11]，代码如下：
pragma solidity 0.5.9;
contract OptimizedSchool{
mapping(address => uint256) public scores;
mapping(address => address) _nextStudents;
uint256 public listSize;
address constant GUARD = address(1);
constructor() public {
_nextStudents[GUARD] = GUARD;
}
function addStudent(address student, uint256 score, address candidateStudent) public {
require(_nextStudents[student] == address(0));
require(_nextStudents[candidateStudent] != address(0));
require(_verifyIndex(candidateStudent, score, _nextStudents[candidateStudent]));
scores[student] = score;
_nextStudents[student] = _nextStudents[candidateStudent];
_nextStudents[candidateStudent] = student;
listSize++;
}
function increaseScore(
address student,
uint256 score,
address oldCandidateStudent,
address newCandidateStudent
) public {
updateScore(student, scores[student] + score, oldCandidateStudent, newCandidateStudent);
}
function reduceScore(
address student,
uint256 score,
address oldCandidateStudent,
address newCandidateStudent
) public {
updateScore(student, scores[student] – score, oldCandidateStudent, newCandidateStudent);
}
function updateScore(
address student,
uint256 newScore,
address oldCandidateStudent,
address newCandidateStudent
) public {
require(_nextStudents[student] != address(0));
require(_nextStudents[oldCandidateStudent] != address(0));
require(_nextStudents[newCandidateStudent] != address(0));
if(oldCandidateStudent == newCandidateStudent)
{
require(_isPrevStudent(student, oldCandidateStudent));
require(_verifyIndex(newCandidateStudent, newScore, _nextStudents[student]));
scores[student] = newScore;
} else {
removeStudent(student, oldCandidateStudent);
addStudent(student, newScore, newCandidateStudent);
}
}
function removeStudent(address student, address candidateStudent) public {
require(_nextStudents[student] != address(0));
require(_isPrevStudent(student, candidateStudent));
_nextStudents[candidateStudent] = _nextStudents[student];
_nextStudents[student] = address(0);
scores[student] = 0;
listSize–;
}
function getTop(uint256 k) public view returns(address[] memory) {
require(k <= listSize);
address[] memory studentLists = new address[](k “] memory studentLists = new address[“);
address currentAddress = _nextStudents[GUARD];
for(uint256 i = 0; i < k; ++i) {
studentLists[i] = currentAddress;
currentAddress = _nextStudents[currentAddress];
}
return studentLists;
}