Эффективный алгоритм случайного поиска доступных мест в списке в 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

Это, очевидно, неэффективно, поскольку, поскольку мы занимаем больше слотов, циклу требуется больше времени для поиска пустого слота, и даже это может занять вечность (предположим, что остался только один пустой слот). Есть ли у вас лучшие решения?

Как я это сделал

Исходя из выбранного ответа, я так и сделал. Это очень быстро и эффективно по сравнению с решениями, которые выполняют поиск по всему списку, находят элементы None и случайным образом выбирают из найденного набора. Я думаю, что узким местом был random.choice метод, который кажется очень медленным.

# 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()

Хотя этот метод имеет дополнительную O (n) сложность памяти, на практике он очень эффективен и быстр.

Answer 1

В моем подходе я выбираю произвольный адрес в целевом массиве, и если он свободен, я добавляю его в список вывода, но если это не так, я сопоставляю этот адрес с адресом, который содержит 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() может работать со списком напрямую, что в любом случае является основным фактором сокращения времени.

Я бы также рекомендовал проверить, что решения, которые он производит, действительны. Я провел некоторое тестирование с моей стороны, но я вполне мог что-то пропустить.

Answer 2

Аналогично идее 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

Answer 3

Ваша функция может возвращаться произвольно долго. В частности, вы попадете в бесконечный цикл, если ни один элемент не является 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]

Answer 4

Просто используйте 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, если свободного места больше нет.

Answer 5

Если вы не можете использовать numpy, я бы оставил набор индексов, которые, как известно, содержат None. Каждый раз, когда None добавляется или удаляется, этот набор индексов будет обновляться