データベース テストでは、クエリを生成する必要があります。複雑さを軽減するために、「挿入」クエリと「選択」クエリのみがあり、最大 2^64 の int のみを格納するとします。データベース内のエントリは、メイン キーとクラスター キーの 2 つのレベルでクラスター化されます。各メイン キーは、最大 2^64 の一意のクラスター キーを持つことができ、最大 2^64 の一意のデータ項目を持つこともできます。
挿入クエリごとに、2 つのチャンス値が与えられます。
- 新しいメインキーを作成するかどうか
- 既存のアイテムの新しいクラスター キーを作成するかどうか。
また、擬似乱数ジェネレーターと、既に生成されたアイテムの数があります。この数は、新しいアイテムを作成するときにランダム ジェネレーターをシードするためにも使用されます。私がそれをしようとしている方法については、コードを参照してください。
from random import Random
def generate_seeds(main_chance, cluster_chance, max_generated):
generator = Random()
new = main_chance > generator.random()
# increase the counter if a new item is generated
max_generated += new
# We chose "insert", so a new item needs to be generated
if new:
main_key = max_generated
# seed the generator with that main_key
generator.seed(main_key)
# now determine if a whole new item will be generated
# or an old key gets new additional items
# Save the main seed. In case we just add an item
# the main seed will be an old one and the main
# seed will only be used for the new items.
cluster_key = main_key
add_item = cluster_chance > generator.random()
# check if a completely new item will be generated
if (not add_item) and new:
return main_key, main_key, max_generated
# We need an old main key that created a new item, so iterate
# over the old keys until we find one that did. If no key was
# ever used to create a completely new item, fall back to
# seed zero, which always generates a completely new item.
if add_item:
# if the cluster_chance is big we might iterate very often :(
for main_key in generator.sample(xrange(main_key), main_key):
generator.seed(main_key)
if cluster_chance < generator.random() or \
cluster_key == 0:
break
else:
# special case: no items have been generated yet
main_key = 0
return main_key, cluster_key, max_generated
else:
# The choice was "select", regenerate an old item
choice = generator.randint(0, max_generated)
return generate_seeds(1, cluster_chance, choice)
問題: add_item の後の for ループで非常に多くの「再帰的」呼び出しが行われる可能性がありcluster_chanceます。
これをより良い方法で解決する方法はありますか?
編集:今まで思いついた唯一のアイデアは、int のリストを作成することです。リスト[n]は次のとおりです。
- n、メイン キー = クラスタ キーで完全に新しいアイテムを生成するために n が使用された場合
- n に対して新しいクラスターが生成された場合、n 未満のメイン キー k があるため、メイン キー = k、クラスター キー = n
問題は、このソリューションが多くのメモリを使用することです: d = [x for x in xrange(100000000)](1 億の値) は 3.183.344KiB のメモリを使用するため、値ごとに ~32,6 バイト、またはギガバイトごとに 32.939.450 の値になります。したがって、32GiB RAM を使用すると、約 10 億の値を管理できる可能性があります。これは良いことですが、十分ではありません。