Вызов Roundrobin по результатам группы itertools - PullRequest
Новая
       28

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

0 голосов
/ 18 ноября 2018

Я ищу более эффективный и 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']

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

1 Ответ

0 голосов
/ 18 ноября 2018

Не большое улучшение, но вы можете использовать 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, чем скомпилированные модули. Это интересная проблема, хотя, возможно, вернемся к этому позже.

...