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

None 添加或删除此索引集将被更新

你的职能可能需要很长时间才能恢复。尤其是,如果没有任何项 None .

相反,恢复 无 和使用 random.choices 随机返回 k 其中。

import random

def get_random_addr(input_arr, k=1, target=None):
    return random.choices([i for i, v in enumerate(input_arr) if v is target], k=k)

使用

l = [0, None, 2, 3, None, None]

for i in get_random_addr(l, k=2):
    l[i] = i

print(l) # [0, None, 2, 3, 4, 5]

类似于Deepspace的想法,除了 O(1) 内存和 O(n) 时间,但速度更快,因为它只迭代数组中一半的槽。

1. 跟踪空槽的数量。
2. 遍历列表。
3. 如果一个槽是空的,用概率返回您的新值 1/number_empty_slots
4. 如果我们没有返回,并且槽是空的,那么在其他空槽上重新分配概率质量。

代码:

def get_random_addr(input_arr, num_empty_slots):
    # num_empty_slots contains the number of empty slots in input_arr
    for index, elem in enumerate(arr): 
        if elem is None: 
            if random.random() < 1 / num_empty_slots:
                return index
            num_empty_slots -= 1

简单使用 enumerate 要首先索引您的列表,请筛选出 None ,然后使用 random.choice 选择一个可用空间。

from random import choice
def get_random_addr(input_arr):
    return choice([index for index, value in enumerate(input_arr) if value is None])
print(get_random_addr([None, 1, None, 2]))

这个输出或者 0 或 2 随机,或 无 如果没有更多可用空间。

None

from random import random

def randint(max_val):
    return int(random() * max_val)

def assign(values, target):
    output = []
    mapping = dict()
    mmax = 0
    size = len(target)
    for val in values:
        idx = randint(size)
        while target[idx] != None:
            if idx in mapping:
                idx = mapping.pop(idx)
                mmax = max(mapping or [0])
                break

            min_size = max(idx, mmax)
            try:
                size -= target[size-1:min_size:-1].index(None)
            except:
                size = min_size + 1

            if target[size-1] == None:
                size -= 1
                mapping[idx] = size
                if idx > mmax:
                    mmax = idx
            elif size-1 in mapping:
                size -= 1
                mapping[idx] = mapping.pop(size)
                mmax = max(mapping or [0])

            idx = randint(size)
        target[idx] = val
        output.append(idx)
    return output

请注意,这将修改传递给它的目标列表。如果您不想修改它,您实际上有两个选项:实现一些额外的逻辑来检查“空闲”地址是否已经被使用,或者复制整个列表(在这种情况下,反转它并修补索引,以便 .index()