0

对于数据库测试，我需要生成查询。为了降低复杂性，假设只有“插入”和“选择”查询，我们只存储最多 2^64 的整数。数据库中的条目聚集在两个级别上：主键和集群键。每个主键最多可以有 2^64 个唯一的簇键，也可以有最多 2^64 个唯一的数据项。

对于每个插入查询，都会给出两个机会值：

  1. 它是否会创建一个新的主键和
  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的。

任何想法如何以更好的方式解决这个问题？

编辑：到目前为止，我想出的唯一想法是构建一个整数列表。列表[n] 是：

  • n，如果 n 用于生成一个全新的项目，主键 = 集群键
  • 某个主键 k < n，如果为 n 生成了一个新簇，则主键 = k，簇键 = n

问题是，此解决方案使用大量内存：d = [x for x in xrange(100000000)]（1 亿个值）使用 3.183.344KiB 内存，因此每个值约 32.6 字节，或每 GB 32.939.450 个值。因此，使用 32GiB RAM，一个人可能管理大约 10 亿个值——很好，但还不够好。

4

0 回答 0