分享 · 2020-01-06 0

Substrate Runtime 中的堆排序

8-1578402169
9-1578402170
8-1578402171
0-1578402171
10-1578402172
9-1578402172
3-1578402173
9-1578402173
5-1578402174
4-1578402174
4-1578402175
9-1578402175
0-1578402176
6-1578402176
2-1578402177
9-1578402177
3-1578402177
2-1578402178
7-1578402179
substrate
原文：https://mp.weixin.qq.com/s/jqkjXIAN8rZcBWqlPL0gSw

周洋，某区块链项目核心开发者，拥有多年的汽车电子嵌入式开发及区块链开发经验，擅长 C++，Go，Rust 语言。1月5日，周洋分享了「Substrate Runtime 中的堆排序」。以下为分享的关键内容。
1.给加密猫

添加一个 lifetime 属性

 
在第一期课程的挑战赛中，我们小组为加密猫添加了 lifetime 属性。lifetime 可以理解为小猫的寿命，如果一只猫存在的时间达到了生命周期，它对应的 token 会被系统自动删除掉，这只猫也消失了。
 
要求链上自动化完成上述过程，所以每次 import block 都要检查哪些猫的 lifetime 超时需要被删除。由于所有猫被存在一个数组结构中，找出 lifetime 超时的猫是典型的寻找 Top K 问题。
 
如果实现不当，可能会引入 O(n) 的时间复杂度，进而有可能发生对链的恶意攻击。这时使用堆排序可以将时间复杂度降低为O(mlogn)。
 
今天分享主要关注 heap 的实现，不会有加密猫 lifetime feature 实现细节。

 

2. 堆排序介绍

 
 堆需要以下2个条件：
1. 堆是一个完全二叉树；
2. 堆中每一个节点的值都必须大于等于（或小于等于）其子树中每个节点的值。
 
堆排序有几个非常重要的应用：优先级队列、求 Top K 和 求中位数。
 
对于每个节点的值都大于等于子树中每个节点值的堆，我们叫作“大顶堆”。对于每个节点的值都小于等于子树中每个节点值的堆，我们叫作“小顶堆”。
 
rust 标准库里面提供了 binary heap 的实现，但是现在我们还不能在 Substrate Runtime 环境下直接使用它。
 
那么我们在 Substrate Runtime 环境中实现一个泛型的堆结构，并且利用 Substrate 默认的 storage value 作为堆的存储来解决 Top K 问题。
 

3.要实现一个堆，

我们先要知道如何存储一个堆

 
用数组来存储完全二叉树是个不错的选择。因为我们不需要存储左右子节点的指针，单纯地通过数组的下标，就可以找到一个节点的左右子节点和父节点，非常节省存储空间。
 
先来看一下这个堆结构代码的样子：
        Subdev 分享 | Substrate Runtime 中的堆排序       
这里 T 代表堆中元素类型。C 代表 Compare trait，可供自定义排序方式（决定是大顶堆还是小顶堆）。S 代表存储类型，这个数组利用了 Substrate 提供的 StorageValue<Vec<T>, Query=Vec<T>> 类型。
 
我画了一个用数组存储堆的例子:
   Subdev 分享 | Substrate Runtime 中的堆排序
从图中我们可以看到，数组中下标为 i 的节点的左子节点，就是下标为 i∗2+1 的节点，右子节点就是下标为 i∗2+2 的节点。
 
 寻找左子节点，右子节点对应的代码：
        Subdev 分享 | Substrate Runtime 中的堆排序       
 寻找父节点对应代码：
        Subdev 分享 | Substrate Runtime 中的堆排序 

4. 下面看一看堆的基本操作

 
 向堆中 push 一个元素：
往堆中插入一个元素后，我们需要进行调整，让其重新满足堆的特性，这个过程叫作堆化（heapify）。
 
       Subdev 分享 | Substrate Runtime 中的堆排序
堆化非常简单，就是顺着节点所在的路径，向上或者向下，对比，然后交换。我这里画了一张堆化的过程分解图。
 
我们可以让新插入的节点与父节点对比大小。如果不满足子节点小于等于父节点的大小关系，我们就互换两个节点。一直重复这个过程，直到父子节点之间满足刚说的那种大小关系。
    Subdev 分享 | Substrate Runtime 中的堆排序       
 对应的代码：
       Subdev 分享 | Substrate Runtime 中的堆排序       
通过简单的递归实现向上交换。
        Subdev 分享 | Substrate Runtime 中的堆排序              Subdev 分享 | Substrate Runtime 中的堆排序       
 pop 堆顶元素：
 
       Subdev 分享 | Substrate Runtime 中的堆排序        
 对应代码：
       Subdev 分享 | Substrate Runtime 中的堆排序              Subdev 分享 | Substrate Runtime 中的堆排序              Subdev 分享 | Substrate Runtime 中的堆排序       
 单元测试如何使用的这个堆结构：
        Subdev 分享 | Substrate Runtime 中的堆排序              Subdev 分享 | Substrate Runtime 中的堆排序              Subdev 分享 | Substrate Runtime 中的堆排序              Subdev 分享 | Substrate Runtime 中的堆排序        
以上代码可以参考这里
https://github.com/yz89/substrate-heap/blob/master/runtime/src/heap.rs 
有完整的实现及单元测试。
 
总结一下。我们实现了一个泛型的堆结构，用户可以自定义元素类型及排序方式（大顶堆，小顶堆）。使用了Substrate 内置的 StorageValue 作为堆的存储，这样为 Substrate Runtime 提供了通用的堆排序实现。

shooter

ጿ ኈ ቼ ዽ ጿ

You may also like...

Leave a Reply