5

我在内存中有一个已经排序的大小 (N) 集，并且想将其转储到 redis 中，如果先插入头部或尾部，是否可以在 O(N) 中完成？或者没关系，插入会 O(log(N!)) ~ O(N log(N))

有关更多详细信息，redis 排序集是使用哈希图和跳过列表（用于排序）实现的。

编辑：这个问题一直没有答案，或者至少答案对我来说有点模棱两可：Redis：当插入的元素位于开头或结尾时，ZADD 是否比 O(logN) 好？

4

2 回答 2

3

以下是我的“经验”方法的结果，表明订购可能会有一点好处:)

(.venv)foo@bar:~/so_bounty$ python main.py
ascending order
5.57414388657
descending order
5.72963309288
random order
6.75937390327
0 score
5.79048109055
于 2015-02-18T03:43:31.477 回答
1

在对另一种经验方法中使用的方法产生怀疑之后，我进行了自己的插入基准测试（所有集合在时间插入之前初始化，对于随机插入测试，元组列表在开始计时之前被打乱），结果如下：

对于具有 2k、20k 和 200k 成员的有序集：

  • 领先：196.29s | 1146.43s | 9897.29s
  • 尾先：170.14s | 993.43s | 9722.14s
  • 兰特插入：146.00s | 1014.57s | 9968.57s

所有这些都具有足够的可变性（标准开发者分别为 7.8 | 54.5 | 324.5），因此差异不足以得出结论。好像没关系……:(

于 2015-02-18T12:33:59.667 回答