script (⏱,💰)

script (⏱,💰)

NG#3 - 字典

racing riverboats start

没有完成入门任务的参考安装入门

Racing Riverboats 是 Cairo 数据结构与算法任务 Think Cairo 的第三个任务,主要是使用字典查询数组中重复值的问题,共有两个小题。

列表中重复值的索引#

第一题「寻找鳄鱼」,本质上是在 array 中找到重复项,标记出 index 存到另一个 array 中。

array 中需要对比的子元素是个 struct,由 u32, u32, felt252 组成。起始数据是一个Array<Obstacle>

#[derive(Drop)]
struct Obstacle {
    length: u32,
    width: u32,
    description: Array<felt252>
}

直接思路是用 Felt252Dict,循环 Obstacle 并 pop 出来放到 Felt252Dict 中,类似 solidity 中的mapping(index => struct),如果 get 有值,就记录 index,没有就 insert。

写出第一版代码后发现由于 Obstacle 子元素Array<felt252>不能 Copy,所以felt252Dict.get(index) -> Obstacle是不合法的。所以得换个思路。

如果不使用字典,采取 2 个循环套嵌,对比 Obstacle 把重复的都加到一个临时列表里,然后再找出 index,结果测试时 out of gas 了,实际花了 320 万,目标 180 万,需要优化。

分析测试用例的 gas limit ,2 个 Obstacle 直接对比一次的 gas 成本在 26100,测试用例里有 13 个 Obstacle,计算 1800000 gas 只能对比 69 次以下,而上面的算法全部遍历需要对比 78 次(1+2...+12)。所以需要减少对比的次数。

然后我采取了核心库dict 的测试用例 方法,用 Felt252Dict 存 index,如果拿到了就跳过,可以减少一些不必要的对比。但最终还是会超 gas,减少对比的次数已经无法再优化。所以需要单次对比的成本,具体来说是优化 Obstacle.description 的比较。

卡了一段时间没有思路后,找到 NG 的导师私聊,他给了思路先把 Obstacle 进行 hash 后可以复杂度 O (n) 一次达成目标。

那该如何把 struct 转为 hash 呢?一开始我把 Obstacle 的 #[derive(Drop)]改成了#[derive(Drop,Serde)],用以下代码获取 hash:

let mut raw_data = Default::default();
obs.serialize(ref raw_data);
let hash = poseidon_hash_span(raw_data.span());

后来发现无法通过线上测试,因为 Obstacle 不能修改。

如果不修改 Obstacle,可以把 struct 中的所有属性手动打包再来 hash。

成功 hash 后,只需要往 dict 里 insert (index, hash) 和 get(index) 就能得到重复索引了。代码就能顺利通过测试。

中间还有很多 u_size 和 felt252 的互换,需要用intounwarp,你可以查文档解决。

这儿的另一个坑是,如果 index 是 0 且值也是 0,dict.get(0)dict.get(不存在索引)都返回 0,判断就会错误,无法通过后一题的相关测试。

这需要用 use nullable::{NullableTrait, match_nullable, FromNullableResult}; 库来解决,这部分建议看nullable 的源码学习。

总结一下,第一题的知识点有:

  • 如何 hash 一个 struct,
  • u_size 和 felt 的互相转换,
  • Felt252Dict 的 new, get 和 insert
  • nullable 的使用

循环中的条件语句返回 Option#

这题是返回最少需要跳几步能大于数组(河流),步长不能超过 3。如果第一格和最后一格是鳄鱼,返回 None。

思路:通过循环套嵌,每次跳跃判断 3,2,1,能跳就跳,步数 +=1;如果都不能跳,直接返回 Option::None,多次跳跃达成目标。

这题实现比较简单,拿到第一题得到的 index array 后,用 2 个 loop 解决。主要是测试会遇到 out of gas 的问题,也就是说判断空河流和判断起点终点是鳄鱼,都需提前判断以节省 gas。

建议对比测试用例,活用 print,看看每步跳到哪儿了。

有的坑第一题中已经说过,如果提前写好就不用再改。

最后提交 verify 后还有个小 bug 无法通过测试,需注意判断 loop 中断的条件是 river.len 还是 river.len-1。

这题涉及很多 loop 中返回值,cairo 中没有 return,容易出错,需要多修改。

还会练习到很多 Option 相关的的操作。

总结#

由于 cairo 的内存是不变的,并不能覆盖 slot,就需要一些技巧来达到 dict 的效果。熟悉相关操作对后续开发会很有帮助。

racing riverboats

加载中...
此文章数据所有权由区块链加密技术和智能合约保障仅归创作者所有。