专栏首页深入浅出区块链技术Solidity 优化 - 如何维护排序列表

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

  • 译者:Tiny 熊[1]
  • 译文出自:登链翻译计划[2]

本系列文章有:

  1. Solidity 优化 - 控制 gas 成本[3]
  2. Solidity 优化 - 编写 O(1) 复杂度的可迭代映射[4]
  3. Solidity 优化 - 维护排序列表[5]

本文我们探索和讨论在以太坊独特的 EVM 成本模型下编写高效的 Solidity 代码的数据结构和实现技术。读者应该已经对 Solidity 中的编码以及 EVM 的总体工作方式所有了解。

在上一篇文章[6]中,我们讨论了(可以在每个元素上迭代的数据结构)如何在列表中添加元素或从列表中删除元素。这篇文章将扩展我们的数据结构,以维护链上已排序的链表。像上一篇文章一样,我们将通过展示每个函数的实现来进行解释。如果你准备好了,那就开始吧!

场景范例

像上一篇文章[7]一样,我们依旧要创建一个“学校”智能合约,但是这次我们只保留了学生地址列表。我们需要根据他们的分数来维持他们的排序,老师可以在学生中增加或减去他们的分数,并且可以保证学生列表仍然可以随时按分数保持顺序。最后一个要求是我们可以列出排名前 k 的学生,以奖励表现良好的学生。

函数需求

让我们考虑一下满足所有要求所需的函数,需要实现 5 个函数。

  1. 将新学生添加到具有分数排序的列表中
  2. 提高学生分数
  3. 降低学生分数
  4. 从名单中删除学生
  5. 获取前 K 名学生名单

实现

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

注意:GUARD 是列表的头。

添加带有分数的新学生 addStudent

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

显示如何将Dave插入维护的排序列表中

为了使代码易于阅读,我们创建了 2 个辅助函数来查找和验证新值的索引。

_verifyIndex 函数用于验证该值在左右地址之间。如果 左边的值新值 > 右边的值将返回 true(如果我们保持降序,并且如果值等于,则新值应该在旧值的后面)

验证索引

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

查找索引

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

addStudent

从列表中删除学生:removeStudent

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

链表删除Bob

辅助函数_isPrevStudent_findPrevStudent

检查前一个学生并找到前一个学生

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

删除学生函数

更新学生分数:increaseScorereduceScore

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

显示如何更新鲍勃的分数

更新分数

注意:我们会检查条件,以确定新值是否适合相同的索引,这样我们不需要删除项目并将其添加到相同的值(这只是优化操作,可以节省 1000 gas )

如果我们具有updateScore函数,则可以用一行代码来实现increaseScorereduceScore函数。

增加分数并减少分数函数

获取前 k 名学生名单:getTop

这个函数没有什么花哨的,只是从 GUARD 循环开始,将地址存储到数组并返回该数组。容易吧?

获取前k名学生函数

代码已发布此处[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;
  }


  function _verifyIndex(address prevStudent, uint256 newValue, address nextStudent)
    internal
    view
    returns(bool)
  {
    return (prevStudent == GUARD || scores[prevStudent] >= newValue) &&
           (nextStudent == GUARD || newValue > scores[nextStudent]);
  }

  function _findIndex(uint256 newValue) internal view returns(address) {
    address candidateAddress = GUARD;
    while(true) {
      if(_verifyIndex(candidateAddress, newValue, _nextStudents[candidateAddress]))
        return candidateAddress;
      candidateAddress = _nextStudents[candidateAddress];
    }
  }

  function _isPrevStudent(address student, address prevStudent) internal view returns(bool) {
    return _nextStudents[prevStudent] == student;
  }

  function _findPrevStudent(address student) internal view returns(address) {
    address currentAddress = GUARD;
    while(_nextStudents[currentAddress] != GUARD) {
      if(_isPrevStudent(student, currentAddress))
        return currentAddress;
      currentAddress = _nextStudents[currentAddress];
    }
    return address(0);
  }
}

优化查找索引

与上一篇文章一样,按链查找索引会消耗与列表长度成比例的 gas 。我们可以通过发送前一个地址到函数来优化这些函数(对于更新分数操作,我们需要发送 2 个地址以供删除和添加使用),并通过我们的 2 个内部函数验证这些地址是否有效。这就是为什么我们分开验证条件并查找地址函数的原因。让我们来看看每个函数!

addStudent

优化addStudent

有很多 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;
  }


  function _verifyIndex(address prevStudent, uint256 newValue, address nextStudent)
    internal
    view
    returns(bool)
  {
    return (prevStudent == GUARD || scores[prevStudent] >= newValue) &&
           (nextStudent == GUARD || newValue > scores[nextStudent]);
  }

  function _isPrevStudent(address student, address prevStudent) internal view returns(bool) {
    return _nextStudents[prevStudent] == student;
  }
}

结论

在本文中,我们探索了排序列表的实现,该列表是从可迭代映射扩展而来的数据结构,用于维护链上排序的列表,可以在列表中添加,删除和更新值。我们还实现了此数据结构的优化版本,以节省寻找有效索引的麻烦。


本翻译由 Cell Network[12] 赞助支持。

来源:https://medium.com/bandprotocol/solidity-102-3-maintaining-sorted-list-1edd0a228d83


参考资料

[1]

Tiny 熊: https://learnblockchain.cn/people/15

[2]

登链翻译计划: https://github.com/lbc-team/Pioneer

[3]

Solidity 优化 - 控制 gas 成本: https://learnblockchain.cn/article/1639

[4]

Solidity 优化 - 编写 O(1) 复杂度的可迭代映射: https://learnblockchain.cn/article/1632

[5]

Solidity 优化 - 维护排序列表: https://learnblockchain.cn/article/1638

[6]

上一篇文章: https://learnblockchain.cn/article/1632

[7]

上一篇文章: https://learnblockchain.cn/article/1632

[8]

可迭代映射: https://learnblockchain.cn/article/1632

[9]

此处: https://gist.github.com/taobun/198cb6b2d620f687cacf665a791375cc

[10]

require: https://learnblockchain.cn/docs/solidity/control-structures.html#assert-require-revert

[11]

此处: https://gist.github.com/taobun/2e409e4d11659408508fe893c5cf2fc1

[12]

Cell Network: https://www.cellnetwork.io/?utm_souce=learnblockchain

本文分享自微信公众号 - 深入浅出区块链技术(blockchaincore),作者:Tiny熊

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-10-30

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 剖析非同质化代币ERC721-全面解析ERC721标准

    什么是ERC-721?现在我们看到的各种加密猫猫狗狗都是基于ERC-721创造出来的,每只都是一个独一无二的ERC-721代币,不过ERC-721在区块链世界远...

    Tiny熊
  • 在Substrate链上跑Solidity ERC20智能合约

    本实践案例中,我们首先会搭建和启动一条substrate链,再通过MetaMask这款著名的以太坊钱包浏览器插件,通过自定义RPC的方式,接入我们搭建好的sub...

    Tiny熊
  • Solidity 0.6.11 更新

    Solidity v0.6.11[1] 为 NatSpec 注释添加了继承性,改进了调试数据输出,并修复了为非外部函数打开calldata的一些小问题。

    Tiny熊
  • Python获取本机所有网卡的MAC地址

    在拙作《Python可以这样学》(清华大学出版社,2017.2)第297页介绍了一种获取本机网卡MAC地址的方法,不过代码显得稍微有点啰嗦,并且只能获得一块网卡...

    Python小屋屋主
  • Tapestry 教程(六)使用BeanEditForm来创建用户表单

    在前面一章,我们看到了Tapestry如何处理简单地链接,甚至于处理能在URL中传递信息的链接。在本章,我们将会看到Tapestry如何以不同的方式做同样的事情...

    LeoXu
  • Python 命令行参数解析库argparse

    在工作业务中,有些函数的调用要尽量傻瓜,能够让其他人能够方便地调用,毕竟甲方是爸爸。

    zhangqibot
  • TPU中的指令并行和数据并行

    TPU V1定义了一套自己的指令集,虽然在介绍处理器时,往往会先谈指令集架构,但此处却把它放到了最后,这主要基于两个原因;其一在于个人的对处理器不太了...

    sea-wind
  • “大”事务引起的锁等待分析案例

    生产环境数据库在某一刻突然发现大量活跃连接,而且大部分状态是updating。问题出现在周六上午,持续了大概三、四分钟,得益于我们自己的快照程序,拿到了当时现场...

    wubx
  • Redis源码解析——Zipmap

            本文介绍的是Redis中Zipmap的原理和实现。(转载请指明出于breaksoftware的csdn博客)

    方亮
  • 20万赚200万,48岁创业者是这样吊打小鲜肉的!

    说起吴思进这个名字,想必知道的人并不多,但如果说起他一手建立的33复杂美,干过区块链的都会情不自禁地竖起大拇指。

    区块链大本营

扫码关注云+社区

领取腾讯云代金券