在Python中随机查找列表中可用位置的一种有效算法

Question

我需要将列表中的一个位置随机分配给一个输入。我需要先检查一下是否没有被占用，然后再使用。我能想出的最佳算法如下：

def get_random_addr(input_arr):

    while True:
        addr = random.randrange(1, len(input_arr))
        if input_arr[addr] is None:
            break
    return addr

这显然不是有效的，因为当我们占用更多的插槽时，循环需要更长的时间来找到空插槽，甚至可能需要永远的时间（假设只剩下一个空插槽）。你有什么更好的解决办法吗？

我是怎么做的

# Create a list of indexes at the beginning when all the values are None 
available_index = list(range(1, len(input_arr)))
random.shuffle(available_index)

# To get a random index simply pop from shuffled available index
random_index = available_index.pop()

Answer 1

如果不能使用numpy，id保留一组已知包含none的索引。每次添加或删除none时，将更新此索引集