python中的一组分区

我有b存储区0 .... b-1和m苹果0 .... m-1。在开始时，所有的苹果都放在桶0中。python中的一组分区

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

顺便说一句，标题被选中，因为这是非常相似的设置问题的分区，其中没有成员可以放置在超过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]]

来源

2017-01-16 user2517676

与除去从列表中的一个元素是，它需要的问题为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

来源

2017-01-16 20:06:48

'[错误范围（m）]'是过度杀伤性的。对于不可变的对象，你可以做'[False] * m'。使用'bitarray'是一个非常好的主意。 –

@ Jean-FrançoisFabre：谢谢你的建议。 –

不客气（那是次要的）。我冒昧地稍微修改了你的帖子。删除“（带套）”，并将“beter”修改为“better”。很多像这样的:) –

，其中对于每个苹果你存储桶数只需使用一个数组？

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

来源

2017-01-16 20:13:49

我需要反向结构来避免在脚本中稍后使用索引。 Index（）也很重。 O（n）我假设。 – user2517676

python中的一组分区

回答

相关问题