solidity如何实现抽取池
April 29th, 2022

背景

开发智能合约的时候,可能会遇到从固定池子中随机抽取不重复item的需求。

问题分析

solidity有以下限制

  • map
    • 不能获取length
    • 不能遍历keyset
    • key不能是自定义类型
  • array
    • 只有原生数组array
    • 基于array实现功能丰富的list,update性能较差,gas费高
    • 只能从顶部push或pop(能remove指定下标的value,但其实只是置空,不会移除该项)

思路

先用array充当这个池子,假设池子中共有十个元素

第一次抽到了下标为3的元素(randomValue % 10 = 3)

共10个元素,抽走了一个,应该剩余9个,但array不能移除指定下标元素,只能移除最后一个元素,那么我们假设刚才抽到的不是3,而是最后一个元素9,但同时要保证返回的是3对应的value。那么我们交换下标3、9对应的元素:

这样的话,下次抽奖公式就变成了:randomValue % 9 了,问题解决了

方案分析

这种方案简单,但有个问题:每次抽到时,都需要交换两个下标的值,造成额外的写入,gas费翻倍

升级版

假设还是先抽到3

这里不与9交换了,而是做个标识,3已被抽,若下次再抽到3,请拿9的值

也就是3指向9(3 → 9)

下次的抽奖公式依然为:randomValue % 9

假设第二次还是抽到了3

3 → 8

同时记录

  • totalCount:池子总数
  • alreadyMintCount:已铸造数

那么被指向的下标targetPointIndex算法为:

uint targetPointIndex = totalCount - alreadyMintCount - 1;
if (pool[targetPointIndex].pointIndex > 0) { // 若目标也已经下发,则指向目标的目标
    targetPointIndex = pool[targetPointIndex].pointIndex;
}

其中pool为“池子”数组,池子数组中存储元素结构体如下:

struct Item {
    bool    status; /** alreday mint mark, true: yes */
    uint16  pointIndex;
}

方案分析2

如果item比较简单,仅仅是数字的话,可以节省struct Item的定义,使用mapping(uint => uint)取代更简洁,而且mapping不需要初始化,可以用于动态增加池子的场景。

升级版2

我写了个demo,供大家参考

Subscribe to sen
Receive the latest updates directly to your inbox.
Verification
This entry has been permanently stored onchain and signed by its creator.
More from sen

Skeleton

Skeleton

Skeleton