python 中的一组分区

Question

我有 b 个桶 0....b-1 和 m 个苹果 0....m-1。一开始所有的苹果都放在桶0.

然后运行一些分析导致苹果在桶之间移动。我已经通过一个 2D 列表（作为桶）实现了这一点，其中的 apple id 会在需要在桶之间移动时被删除和附加。然而，这对我的分析来说效率非常低，因为这些运动的数量级为数百万或数十亿。所以，我想知道是否有更好的解决方案来实现这样的结构？

顺便说一句，选择标题是因为这与集合问题的划分非常相似，其中任何成员都不能放置在超过 1 个子集中。这里还有一个例子，有 4 个苹果和 3 个水桶，以使其更清楚：

time 0:
a=[[0,1,2,3],[],[]]
time 1: (say apple 3 needs to be moved to bucket 2)
a=[[0,1,2],[],[3]]

Answer 1

从列表中删除一个元素的问题是它需要O(n)：它采用数字的顺序列表中的元素数以删除该项目。

您最好使用 set 或更好的 bitarray，它可以在 O(1) 中运行。

例如：

m = 50 #the number of apples
b = 10 #the number of buckets
fls = [False]*m
a = [bitarray(fls) for _ in range(b)]
a[0] = bitarray([True]*m) #add a filled bucket at index 0

def move_apple(apple_id,from_bucket,to_bucket):
    a[from_bucket][apple_id] = False
    a[to_bucket][apple_id] = True

Answer 2

只需使用一个数组来存储每个苹果的桶号吗？

time 0:
a=[0,0,0,0]
time 1: (say apple 3 needs to be moved to bucket 2)
a=[0,0,0,2]

python 中的一组分区

Partition of a set in python

python

set

subset

partition