Перегородка набора в питоне

Question

У меня есть b ведра 0 .... b-1 и m яблоки 0 .... м-1. В начале все яблоки помещаются в ведро 0.

Затем, после некоторого анализа, яблоки перемещаются между ведрами. Я уже реализовал это, имея 2D-список (как ведра), в котором идентификаторы apple удаляются и добавляются, когда им нужно перемещать между ведрами. Это, однако, очень неэффективно для моего анализа, поскольку эти движения находятся в порядке миллионов или миллиардов. Итак, мне было интересно, есть ли лучшее решение для реализации такой структуры?

Кстати, название было выбрано так, как это очень похоже на разделы заданной проблемы, в которых ни один член не может быть помещен в более чем 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

Проблема с удаления элемент из списка является то, что он принимает О (п): он принимает заказ количества элементов в списке, чтобы удалить этот элемент.

Лучше использовать 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]