Skip to content

Latest commit

 

History

History
271 lines (229 loc) · 11.2 KB

15.algorithm.md

File metadata and controls

271 lines (229 loc) · 11.2 KB

15.算法

此算法参考我之前写的JS 教程算法,然后做改动。

在 Solidity 内主要是经济模型的算法，在其他语言内的各种排序算法，在合约内使用场景并不是很常见，之所以在这里罗列，是一起熟悉下思路，算法是很基础的逻辑训练途径，下面仅以插入排序喝冒泡排序作为例子。快速排序和数组去重作为扩展练习

1️⃣ 插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

操作步骤：首先选取数组的第一项即 ary[0]，我们可以认为这个数是已经安排好序的，再取 ary[1]项插入到已经排好序的元素中，此时只有 ary[0]，我们比较 ary[0]和 ary[1]；大于 ary[0]就放在后面，小于就插到 ary[0] 前面；要插入的元素依次为 ary[1]至 ary[ary.leng-1]项；插入到排序好的数组中的时候，插入每一项都需要从后面往前面遍历已经排序好的元素；

如果排序好的元素比插入的元素大，则把该元素往后挪一位，直到已经排序的元素小于等于要插入的元素（或者已经遍历完已经排好序的数组项），则把要插入的元素放在该位置+1 的索引位置中（反向排的时候，需要放在数组的第 0 个位置），对每个插入的元素都执行上面的操作，最终数组就是排序好的；

错误版本

把原来 JS 算法 里写的代码拷贝进来修改后，竟然错了。

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

// [11,2,31,45,6,78,37,33,21] => [2, 6, 11, 21, 31, 33, 37, 45, 78]
contract Demo {
    function insertSort(uint256[] memory ary)
        public
        pure
        returns (uint256[] memory)
    {
        uint256 temp; //定义一个临时变量，保存要插入的值；
        uint256 len = ary.length;
        for (uint256 i = 1; i < len; i++) {
            if (ary[i] < ary[i - 1]) {
                temp = ary[i]; //需要插入的值；
                uint256 pIndex = i - 1; //需要插入值的前一个索引；
                while (temp < ary[pIndex] && pIndex >= 0) {
                    ary[pIndex + 1] = ary[pIndex]; //相当于ary[i]=ary[i-1];
                    ary[pIndex] = temp; //相当于ary[i-1]=temp;完成一波交换；
                    pIndex--; //准备下一波交换；
                }
            }
        }
        return ary;
    }
}

报错信息如下：出现了 overflow了。

{
	"error": "Failed to decode output: Error: overflow (fault=\"overflow\", operation=\"toNumber\", value=\"35408467139433450592217433187231851964531694900788300625387963629091585785856\", code=NUMERIC_FAULT, version=bignumber/5.5.0)"
}

这个代表超出了 uint256的范围了，uint256 的范围是 0 至115792089237316195423570985008687907853269984665640564039457584007913129639935，肯定不是运算超出最大值了，只能是计算时候超出最小值了；基本可以锁定 pIndex--; 这一句导致的错误，运行到 0-- 等于 -1 ，导致出错了。

修复如下

原理: 只需要让 pIndex-- 最小运行到 1-- 就可以解决溢出问题了。

  • 而让pIndex最小值等 1，则需要 pIndex >= 1
  • 其他一次修改即可
// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;

// [11,2,31,45,6,78,37,33,21] => [2, 6, 11, 21, 31, 33, 37, 45, 78]
contract Demo {
    function insertSort(uint256[] memory ary)
        public
        pure
        returns (uint256[] memory)
    {
        uint256 temp; //定义一个临时变量，保存要插入的值；
        uint256 len = ary.length;
        for (uint256 i = 1; i < len; i++) {
            if (ary[i] < ary[i - 1]) {
                temp = ary[i]; //需要插入的值；
                // 原代码
                // uint256 pIndex = i - 1; //需要插入值的前一个索引；
                // while (temp < ary[pIndex] && pIndex >= 0) {

                // 新代码
                uint256 pIndex = i;
                while (temp < ary[pIndex - 1] && pIndex >= 1) {
                    // 原代码
                    // ary[pIndex + 1] = ary[pIndex]; //相当于ary[i]=ary[i-1];
                    // ary[pIndex] = temp; //相当于ary[i-1]=temp;完成一波交换；

                    // 新代码
                    ary[pIndex] = ary[pIndex - 1]; //相当于ary[i]=ary[i-1];
                    ary[pIndex - 1] = temp; //相当于ary[i-1]=temp;完成一波交换；
                    pIndex--; //准备下一波交换；
                }
            }
        }
        return ary;
    }
}

但是这个版本的代码还是有问题的，因为我们代码中的 temp < ary[pIndex - 1] && pIndex >= 1 这里的 temp < ary[pIndex - 1] 在 pIndex--;后 pIndex 为 0，而此时 ary[pIndex - 1] 又出现错误了。

再次修复如下

这时候我们需要使用短路规则，把条件位置换一下，因为我们要求 pIndex >= 1,当 pIndex 为 0 时候就不需要继续运行了。

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

// [11,2,31,45,6,78,37,33,21] => [2, 6, 11, 21, 31, 33, 37, 45, 78]
contract Demo {
    // 47897 gas
    function insertSort(uint256[] memory ary)
        public
        pure
        returns (uint256[] memory)
    {
        uint256 temp; //定义一个临时变量，保存要插入的值；
        uint256 len = ary.length;
        for (uint256 i = 1; i < len; i++) {
            if (ary[i] < ary[i - 1]) {
                temp = ary[i]; //需要插入的值；
                uint256 pIndex = i;
                while (pIndex >= 1 && temp < ary[pIndex - 1]) {
                    ary[pIndex] = ary[pIndex - 1]; //相当于ary[i]=ary[i-1];
                    ary[pIndex - 1] = temp; //相当于ary[i-1]=temp;完成一波交换；
                    pIndex--; //准备下一波交换；
                }
            }
        }
        return ary;
    }
}

这下终于执行成功了。 查看调用成功的 gas，花费了 47897 gas；

然后我们再次开始怎么优化这些 gas。

优化后的最终版本

然后我们再看看怎么优化，

  • if (ary[i] < ary[i - 1]) 与 temp < ary[pIndex - 1] 重复判断了
  • 输入变量的位置 memory，可以改为 calldata
  • i++ 可以改为 ++;
  • pIndex--; 可以改为 --pIndex;
  • 内部声明的所有变量，都可以提到循环外

最终的版本: gas 消耗从最开始的 47897 gas 优化成了 41125 gas

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

// [11,2,31,45,6,78,37,33,21]
//           => [2, 6, 11, 21, 31, 33, 37, 45, 78]
// 47897 gas
// ...
// 41125 gas
contract Demo {
    // 47897 gas
    function insertSort(uint256[] calldata ary)
        public
        pure
        returns (uint256[] memory)
    {
        uint256[] memory tempArr = ary;
        uint256 temp; //定义一个临时变量，保存要插入的值；
        uint256 len = tempArr.length;
        uint256 pIndex; // 上一个值
        for (uint256 i = 1; i < len; ++i) {
            temp = tempArr[i]; //需要插入的值；
            pIndex = i;
            while (pIndex >= 1 && temp < tempArr[pIndex - 1]) {
                tempArr[pIndex] = tempArr[pIndex - 1]; //相当于ary[i]=ary[i-1];
                --pIndex; //准备下一波交换；
            }
            tempArr[pIndex] = temp; //相当于ary[i-1]=temp; 因为上面 pIndex-- 了
        }
        return tempArr;
    }
}

2️⃣ 冒泡排序

冒泡排序（Bubble Sort）也是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 算法步骤：

  • 1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  • 2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  • 3）针对所有的元素重复以上的步骤，除了最后一个。
  • 4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
contract Demo2 {
    function sortAry(uint256[] calldata ary)
        public
        pure
        returns (uint256[] memory)
    {
        uint256[] memory tempArr = ary;
        uint256 len = tempArr.length; //获取数组的长度；有aryLen个数在排序；
        uint256 temp; //临时变量，交换数据中用的
        bool flag = false; //设置标志位，初始化为false
        for (uint256 i = 0; i < len - 1; ++i) {
            //外层循环n-1次；
            for (uint256 j = 0; j < len - 1 - i; ++j) {
                //每次循环完，都能从剩下的数组中找出个最大的数组放在 len-1-i 的位置；
                if (tempArr[j] > tempArr[j + 1]) {
                    temp = tempArr[j];
                    tempArr[j] = tempArr[j + 1];
                    tempArr[j + 1] = temp;
                    flag = true; //如果交换好了，做个标记，避免无效的循环；
                }
            }
            if (!!flag) {
                //只要交换了位置，flag的值就重新设置为false了；
                flag = false;
            } else {
                //如果没有交换，说明数组已经排好序了，可以结束循环了；
                break;
            }
        }
        return tempArr;
    }
}

🆗 实战应用

快速排序和数组去重作为扩展练习，自己可以动手实现。

  • 实现快速排序
  • 实现数组去重

#️⃣ 问答题

  • 插入排序的写法 
      function insertSort(uint256[] calldata ary)
  public
  pure
  returns (uint256[] memory)
  {
      uint256[] memory tempArr = ary;
      uint256 temp; //定义一个临时变量，保存要插入的值；
      uint256 len = tempArr.length;
      uint256 pIndex; // 上一个值
      for (uint256 i = 1; i < len; ++i) {
          temp = tempArr[i]; //需要插入的值；
          pIndex = i;
          while (pIndex >= 1 && temp < tempArr[pIndex - 1]) {
              tempArr[pIndex] = tempArr[pIndex - 1]; //相当于ary[i]=ary[i-1];
              --pIndex; //准备下一波交换；
          }
          tempArr[pIndex] = temp; //相当于ary[i-1]=temp; 因为上面 pIndex-- 了
      }
      return tempArr;
  }
    • if (ary[i] < ary[i - 1]) 与 temp < ary[pIndex - 1] 重复判断了
    • 输入变量的位置 memory，可以改为 calldata
    • i++ 可以改为 ++;
    • pIndex--; 可以改为 --pIndex;
    • 内部声明的所有变量，都可以提到循环外