5

サイズ (N) のメモリに既に並べ替えられたセットがあり、それを redis にダンプしたいのですが、head または tail を最初に挿入した場合、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

別の経験的アプローチで採用されている方法論に疑問を抱いた後、私は独自の挿入ベンチマークを実施しました (すべてのセットはタイミング挿入の前に初期化され、ランダム挿入テストでは、タイミングを開始する前にタプルのリストがシャッフルされます)、次の結果が得られました。

2,000、20,000、および 200,000 メンバーの順序付きセットの場合:

  • 頭から: 196.29 秒 | 1146.43秒 | 9897.29秒
  • テールファースト: 170.14s | 993.43秒 | 9722.14秒
  • ランド挿入: 146.00s | 1014.57秒 | 9968.57秒

すべてに十分なばらつきがあるため (それぞれ 7.8 | 54.5 | 324.5 の標準開発者)、その差は結論を出すのに十分なほど重要ではありません。それは問題ではないようです... :(

于 2015-02-18T12:33:59.667 に答える