Слияние N списков путем случайного выбора элементов в каждом индексе

Question

У меня есть парные списки с баджиллионом, каждая пара одинакового размера. Я хочу «объединить» каждый, выбрав случайный элемент из каждого индекса, но моя текущая реализация очень медленная - даже при многопроцессорной обработке. (FWIW, мой код должен быть потоковым).

def rand_merge(l1, l2):
    newl = []
    for i in range(len(l1)):
        q = random.choice([l1, l2])
        newl.append(q[i])
    return newl

Довольно простой, но при работе с 20k списками размеров ~ 5-25, это занимает сумасшедшее время - я предполагаю, что это случайный выбор. Но я также пробовал другие версии random, например, создание строки из 0 и 1 для ссылки, не ходите.

EDIT: Больше ясности: это Генетический Алгоритм, разработанный для написания предложений путем сопоставления с корпусом. Рассматриваемые списки - это предложения, разделенные по словам. GA - это «слияние» выигрывающих фитнес «родителей» с детьми, каждый из которых является слиянием «генов» двух родительских предложений. Это означает, что «списки» должны совпадать и не могут вытягивать из большого списка списков (я не думаю).

Вот код ...

from multiprocessing import Pool as ThreadPool
import random

def offspring(parents):
    child = []
    p1 = parents[0].split(' ')
    p2 = parents[1].split(' ')
    for i in range(min(len(p1), len(p2))):
        q = random.choice([p1, p2])
        child.append(q[i])
    child = ' '.join([g for g in child]).strip()
    return child

def nextgen(l): #l is two lists of previous generation and grammar seed
    oldgen = l[0][:pop] # Population's worth of previous generation
    gramsent = l[1] # this is the grammar seed
    newgen = []
    newgen.append(tuple([oldgen[0][0], oldgen[0][0]]))  # Keep the winner!
    for i in range(len(oldgen) - len(oldgen)//4):
        ind1 = oldgen[0][0] # paired off against the winner - for larger pools, this is a random.sample/"tournament"
        ind2 = oldgen[i][0]
        newgen.append(tuple([ind1, ind2]))
    pool = ThreadPool(processes=8)
    newgen = pool.map(offspring, newgen)
    pool.close()
    pool.join()

Население и поколения могут объединяться в большие числа, и каждое предложение проходит. С тех пор, как вопрос был опубликован изначально, будучи обеспокоен тем, что на прохождение каждого поколения уходило так много времени, я обнаружил (для меня головокружение), что длительное время обработки фактически не имеет (почти) никакого отношения к размеру или численности "населения" списков. Мутация каждого поколения заняла ~ 15 секунд. Я увеличил население с 50 до 50000, и поколения выросли с 15 секунд до 17 или около того. Так что медлительность, видимо, скрывается в другом месте.

Answer 1

Попробуйте объединить все 20 000 списков одновременно, а не два одновременно.

from itertools import zip_longest
from functools import partial
import random

lists = [l1, l2, ...]

idxvals = map(partial(filter, None), itertools.zip_longest(*lists))
newl = [random.choice([*i]) for i in idxvals]

Поскольку вы хотите выбрать случайный элемент в каждом индексе, имеет смысл выбирать из всех 20 000 списков одновременновместо 2 за один раз.

---

>>> lists = [[1, 2, 3], [10], [20, 30, 40, 5]]

zip_longest перейдет к самому длинному списку, заполнив пропущенные значения None.

>>> list(itertools.zip_longest(*lists))
[(1, 10, 20), (2, None, 30), (3, None, 40), (None, None, 5)]

Эти None необходимо будет отфильтровать перед выборомшаг.filter поможет с этим.

>>> f = partial(filter, None)
>>> list(map(list, map(f, itertools.zip_longest(*lists))))
[[1, 10, 20], [2, 30], [3, 40], [5]]

Должно быть понятно, что я пытаюсь сделать.I-й индекс выходных данных содержит элементы, присутствующие в l[i], для каждого l в lists.

Теперь итерируйте по idxvals и выберите:

>>> idxvals = map(f, itertools.zip_longest(*lists))
>>> [random.choice([*i]) for i in idxvals]
[10, 30, 3, 5]