将已排序的集合插入到REDIS中最有效的方法

Question

我有一个大小为N的已排序集合在内存中，我想将其转储到Redis中，如果从头或尾部插入，是否可以在O(N)时间内完成？还是无论如何插入，插入都将是O(log(N!)) ~ O(N log(N))。（参考链接） 进一步说，Redis排序集使用哈希映射和跳表（用于排序）实现。

编辑：这个问题一直没有得到回答，至少对我来说答案有点含糊不清：Redis:当插入元素在开头或结尾时，ZADD是否比O(logN)更好？

- Daren

---

在我看来，这并不重要。 - Itamar Haber

我不熟悉跳表，但对于其他有序数据结构（如树），如果按特定顺序插入，则确实可以获得log(N)的时间复杂度...从维基百科关于跳表的文章中看来，似乎也可以达到O(N)，但REDIS的实现是否相同？ - Daren

有趣的问题...我会尝试进行基准测试，看看能否找到任何实证差异。另一个选择是阅读源代码：https://github.com/antirez/redis :) - Itamar Haber

我试着读源代码，但20分钟后就绝望了...抱歉。我没有考虑过基准测试。 - Daren

现在有赏金了，我真的很有动力 :P - Itamar Haber

Answer 1

以下是我使用"经验主义"方法得出的结果，这表明有序性可能会带来轻微的好处 :)

(.venv)foo@bar:~/so_bounty$ python main.py
ascending order
5.57414388657
descending order
5.72963309288
random order
6.75937390327
0 score
5.79048109055

- Itamar Haber

---

你能详细说明一下你模拟中使用的方法吗？迭代次数、数据集大小等。谢谢！ - Daren

代码链接在答案中 (https://gist.github.com/itamarhaber/6c9f3dd75ec5e25d8044) - 我在笔记本电脑上的虚拟机中使用了大小为 10,000 的集合，并针对每个排序进行了 100 次迭代 - 结果可能因人而异 :) - Itamar Haber

尝试在Java中复制实验，但是使用不同的数据集大小（1k、10k和100k）并没有得出确定性的结果。这不能是任何愚蠢的错误，例如在Python中获取随机数需要更长的计算时间，因此随机数据集构建速度较慢。 - Daren

可能会有很多愚蠢的错误——我过去和现在每天都犯这些错误；但我相信通过在插入之前准备好集合，我避免了这些错误。 - Itamar Haber

好的，既然没有人查看源代码来获得答案，那么你就获得了悬赏。享受吧。 - Daren

Answer 2

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

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

- 头部插入：196.29秒|1146.43秒|9897.29秒 - 尾部插入：170.14秒|993.43秒|9722.14秒 - 随机插入：146.00秒|1014.57秒|9968.57秒

所有结果的可变性足够大（分别为7.8、54.5、324.5的标准偏差），因此差异并不足以得出结论。看来这并不重要... :(

- Daren

---

没有什么比拿起锤子敲打石头更好的了 :) - Itamar Haber

是啊...我本来希望现在已经找到了一个线索... :S 我不比你更信任自己。所以我还是有疑虑的。问题在于有太多的噪音，REDIS 太快了，而网络接口太慢了。 - Daren

REDIS太快了<3！ - Itamar Haber

是的，这就是为什么我们也使用它 :p - Daren