Вызов Roundrobin по результатам группы itertools

Question

Я ищу более эффективный и Pythonic способ использования itertools roundrobin рецепт по группам, образованным itertools.groupby(),

В частности, у меня есть список URL-адресов (не отсортированных), и я хочу изменить их порядок так, чтобы упорядочение их результатов размещало максимальное "расстояние" (или, возможно, диверсификацию) между каждым уникальным netloc (хостом), как определено атрибут из urllib.parse, Воспроизводимый пример ниже.

Я сейчас пользуюсь itertools.groupby() плюс его рецепт Roundrobin, но из-за характера groupby(),

Возвращенная группа сама по себе является итератором, который разделяет основную итерацию с groupby(), Поскольку источник является общим, когда groupby() объект расширен, предыдущая группа больше не видна. Таким образом, если эти данные понадобятся позже, они должны быть сохранены в виде списка.

... это, кажется, требует формирования промежуточного списка из каждой группы.

Пример данных:

import itertools as it
import urllib.parse

bases = ('https://www.google.com', 'https://www.youtube.com',
         'https://docs.scipy.org', 'https://www.group.me')
urls = []
counts = (1, 5, 10, 15)
for c, b in zip(counts, bases):
    for i in range(c):
        urls.append(f'{b}/{i}')

pprint(urls)
# ['https://www.google.com/0',
#  'https://www.youtube.com/0',
#  'https://www.youtube.com/1',
#  'https://www.youtube.com/2',
#  'https://www.youtube.com/3',
#  'https://www.youtube.com/4',
#  'https://docs.scipy.org/0',
#  'https://docs.scipy.org/1',
#  'https://docs.scipy.org/2',
#  'https://docs.scipy.org/3',
#  'https://docs.scipy.org/4',
#  'https://docs.scipy.org/5',
#  'https://docs.scipy.org/6',
#  'https://docs.scipy.org/7',
#  'https://docs.scipy.org/8',
#  'https://docs.scipy.org/9',
#  'https://www.group.me/0',
#  'https://www.group.me/1',
#  'https://www.group.me/2',
#  'https://www.group.me/3',
#  'https://www.group.me/4',
#  'https://www.group.me/5',
#  'https://www.group.me/6',
#  'https://www.group.me/7',
#  'https://www.group.me/8',
#  'https://www.group.me/9',
#  'https://www.group.me/10',
#  'https://www.group.me/11',
#  'https://www.group.me/12',
#  'https://www.group.me/13',
#  'https://www.group.me/14']

Текущее решение (возьмите 1 из каждой группы или пропустите группу, если она пуста, пока все группы не поднимут StopIteration):

grp = it.groupby(sorted(urls), key=lambda u: urllib.parse.urlsplit(u).netloc)
shuffled = list(roundrobin(*(list(g) for _, g in grp)))
#                            ^^ Each group is otherwise lost because
#                               groupby() itself is an iterator

Ожидаемый результат для образца следующий:

['https://docs.scipy.org/0',
 'https://www.google.com/0',
 'https://www.group.me/0',
 'https://www.youtube.com/0',
 'https://docs.scipy.org/1',
 'https://www.group.me/1',
 'https://www.youtube.com/1',
 'https://docs.scipy.org/2',
 'https://www.group.me/10',
 'https://www.youtube.com/2',
 'https://docs.scipy.org/3',
 'https://www.group.me/11',
 'https://www.youtube.com/3',
 'https://docs.scipy.org/4',
 'https://www.group.me/12',
 'https://www.youtube.com/4',
 'https://docs.scipy.org/5',
 'https://www.group.me/13',
 'https://docs.scipy.org/6',
 'https://www.group.me/14',
 'https://docs.scipy.org/7',
 'https://www.group.me/2',
 'https://docs.scipy.org/8',
 'https://www.group.me/3',
 'https://docs.scipy.org/9',
 'https://www.group.me/4',
 'https://www.group.me/5',
 'https://www.group.me/6',
 'https://www.group.me/7',
 'https://www.group.me/8',
 'https://www.group.me/9']

Каков более эффективный способ сделать это?

Answer 1

Не огромное улучшение, но вы могли бы использовать itertools.zip_longest добиться того же эффекта с помощью небольшой настройки:

shuffled = list(x for i in it.zip_longest(*(list(g) for _, g in grp)) for x in i if x)
# flattening the sublists and only returning the non-None values

Преимущество в том, что вам не нужно определять roundrobin рецепт. Однако экономия времени незначительна (рассчитано на n=10000):

# 3.7466756048055094 # zip_longest
# 4.077965201903506  # roundrobin

Я чувствую, что есть другое решение, которое может использовать collections.Counter или использовать sort(key=...) на sorted(list), но я еще не взломал этот случай, похоже, что временная сложность может быть более серьезной, чем ваша реализация, поскольку она может полагаться на больше кода Python, чем на скомпилированные модули. Это интересная проблема, хотя, вероятно, вернемся к этому позже.