如何从Python中的迭代器生成随机分区

Question

给定想要的分区数量，这些分区的大小应该尽量相等。这个问题讨论了如何处理一个列表的情况。虽然它们没有随机的特性，但这个特性可以很很容易添加。我的问题是，我的输入是一个迭代器，所以不能使用shuffle。这样做的原因是我想随机分割图的节点。因为图可能非常大，所以我在寻找一种解决方案，不仅仅是创建一个中间列表。

我最初的想法是使用compress()，并用一个随机数函数作为选择器。但这样只适用于两个分区。

Answer 1

你可以通过调整权重来让列表的长度更均匀，这个权重是根据每个分区目前生成的节点数量来决定的。如果你选择一个合适的函数，当某个分区的节点数量超过总节点数除以分区数时，权重就会变成0，这样它们的长度就会大致相等。具体来说，权重的计算公式是：

weight[i] = max(numNodes/numPartitions - nodesSoFar[i],0)

这里的max()是为了防止出现负权重的情况，比如当你有4个节点和3个分区时，可能会出现负数。

接下来，从1到权重总和之间随机选一个数字（或者从0到权重总和减1之间），然后根据这个数字来选择相应的分区。

compress()函数可以正常工作，只要你为每个分区使用不同的选择器；比如可以用 (x == n for x in random_partition_numbers)，其中random_partition_numbers是一个生成器。当然，你需要为每个分区复制random_partition_numbers。这个设计本身会比较慢，因为它需要遍历每个分区的节点列表。

Answer 2

你只是处理不同的分区，对吧？

def dealer( iterator, size ):
    for item in iterator
        yield random.randrange( size ), item

这样做不会让你通过给每个项目分配一个分区来开始吗？

然后你可以像这样做一些列表。虽然这可能不是个好主意，但它展示了如何使用这个功能。

def make_lists( iterator, size ):
    the_lists = []*size
    for partition, item in dealer( iterator, size ):
        the_lists[partition].append(item)
    return the_lists

Answer 3

你可以创建 k 个列表。当你收到一个值时，随机选择一个从 0 到 k-1 的整数 x，然后把这个值放到第 x 个列表里。

平均来说，每个列表会包含 N/k 个元素，但它们的数量会有一定的波动，波动的程度可以用 √(N * 1/k * (1-1/k)) 来表示。

def random_partition(k, iterable):
  results = [[] for i in range(k)]
  for value in iterable:
    x = random.randrange(k)
    results[x].append(value)
  return results