Пары из единого списка

100

Достаточно часто мне приходилось обрабатывать список попарно. Мне было интересно, какой питонический и эффективный способ сделать это, и я нашел это в Google:

pairs = zip(t[::2], t[1::2])

Я думал, что это достаточно питонично, но после недавнего обсуждения идиом в сравнении с эффективностью , я решил провести несколько тестов:

import time
from itertools import islice, izip

def pairs_1(t):
    return zip(t[::2], t[1::2]) 

def pairs_2(t):
    return izip(t[::2], t[1::2]) 

def pairs_3(t):
    return izip(islice(t,None,None,2), islice(t,1,None,2))

A = range(10000)
B = xrange(len(A))

def pairs_4(t):
    # ignore value of t!
    t = B
    return izip(islice(t,None,None,2), islice(t,1,None,2))

for f in pairs_1, pairs_2, pairs_3, pairs_4:
    # time the pairing
    s = time.time()
    for i in range(1000):
        p = f(A)
    t1 = time.time() - s

    # time using the pairs
    s = time.time()
    for i in range(1000):
        p = f(A)
        for a, b in p:
            pass
    t2 = time.time() - s
    print t1, t2, t2-t1

Вот результаты на моем компьютере:

1.48668909073 2.63187503815 1.14518594742
0.105381965637 1.35109519958 1.24571323395
0.00257992744446 1.46182489395 1.45924496651
0.00251388549805 1.70076990128 1.69825601578

Если я их правильно интерпретирую, это должно означать, что реализация списков, индексации списков и нарезки списков в Python очень эффективна. Результат одновременно успокаивающий и неожиданный.

Есть ли другой, «лучший» способ попарного обхода списка?

Обратите внимание, что если в списке нечетное количество элементов, то последний не будет ни в одной из пар.

Как правильно обеспечить включение всех элементов?

Я добавил эти два предложения из ответов на тесты:

def pairwise(t):
    it = iter(t)
    return izip(it, it)

def chunkwise(t, size=2):
    it = iter(t)
    return izip(*[it]*size)

Вот результаты:

0.00159502029419 1.25745987892 1.25586485863
0.00222492218018 1.23795199394 1.23572707176

Результаты на данный момент

Самый питонический и очень эффективный:

pairs = izip(t[::2], t[1::2])

Наиболее эффективные и очень питонические:

pairs = izip(*[iter(t)]*2)

Мне потребовалось время, чтобы понять, что в первом ответе используются два итератора, а во втором - один.

Чтобы иметь дело с последовательностями с нечетным числом элементов, было предложено увеличить исходную последовательность, добавив один element ( None), который соединяется с предыдущим последним элементом, что может быть достигнуто с помощью itertools.izip_longest().

в заключение

Обратите внимание, что в Python 3.x zip()ведет себя как itertools.izip()и itertools.izip() отсутствует.

Апалала
источник
RE: «правильный путь» - нет «правильного» пути! Это зависит от варианта использования.
Эндрю Джаффе,
@Andrew Jaffe В данном случае я дал критерии «лучшего»: эффективный и питонический.
Apalala
@Apalala: Я имею в виду, что результат наличия нечетного числа зависит от использования. Например: вы можете просто опустить последний элемент, или добавить определенный известный фиктивный элемент, или продублировать последний
Эндрю Джаффе,
2
@Apalala: потому что вы используете какую-то ерунду вместо timeitмодуля.
SilentGhost 08
1
n-duplicated: просто в быстром поиске: stackoverflow.com/questions/4501636 , stackoverflow.com/questions/4170295 , stackoverflow.com/questions/434287
tokland

Ответы:

52

Мой любимый способ сделать это:

from itertools import izip

def pairwise(t):
    it = iter(t)
    return izip(it,it)

# for "pairs" of any length
def chunkwise(t, size=2):
    it = iter(t)
    return izip(*[it]*size)

Когда вы хотите объединить все элементы в пары, вам, очевидно, может понадобиться значение fill:

from itertools import izip_longest
def blockwise(t, size=2, fillvalue=None):
    it = iter(t)
    return izip_longest(*[it]*size, fillvalue=fillvalue)
Йохен Ритцель
источник
Кажется, что первая (попарная) функция пропускает клонирование и продвижение второго итератора. См. itertoolsРаздел рецептов.
Apalala
@Apalala: zip продвигает один и тот же итератор дважды.
Йохен Ритцель 07
Конечно, вы правы, и попарно пока наиболее эффективно, я не знаю почему.
Apalala
1
Мне нравится это решение: оно ленивое, и в нем очень эффективно используется состояние итераторов. Вы даже можете сделать его однострочным, хотя, возможно, за счет удобочитаемости:izip(*[iter(t)]*size)
Ченнинг Мур
для вашего второго решения, разве вы не хотели бы избежать создания списка, если хотите, чтобы производительность?
max
41

Я бы сказал, что ваше первоначальное решение pairs = zip(t[::2], t[1::2])является лучшим, потому что его легче всего читать (а в Python 3zip автоматически возвращает итератор вместо списка).

Чтобы обеспечить включение всех элементов, вы можете просто расширить список на None.

Затем, если в списке нечетное количество элементов, будет последняя пара (item, None).

>>> t = [1,2,3,4,5]
>>> t.append(None)
>>> zip(t[::2], t[1::2])
[(1, 2), (3, 4), (5, None)]
>>> t = [1,2,3,4,5,6]
>>> t.append(None)
>>> zip(t[::2], t[1::2])
[(1, 2), (3, 4), (5, 6)]
Тим Пицкер
источник
6

Я начну с небольшого отказа от ответственности - не используйте приведенный ниже код. Это вообще не Pythonic, написал просто для удовольствия. Она похожа на pairwiseфункцию @ THC4k, но использует iterи lambdaзакрывается. Он не использует itertoolsмодуль и не поддерживает fillvalue. Я поместил его сюда, потому что кому-то это может показаться интересным:

pairwise = lambda t: iter((lambda f: lambda: (f(), f()))(iter(t).next), None)
Томаш Элендт
источник
4

Что касается большинства питонов, я бы сказал, что рецепты, представленные в исходных документах Python (некоторые из которых очень похожи на ответы, предоставленные @JochenRitzel), вероятно, ваш лучший выбор;)

def grouper(iterable, n, fillvalue=None):
    "Collect data into fixed-length chunks or blocks"
    # grouper('ABCDEFG', 3, 'x') --> ABC DEF Gxx
    args = [iter(iterable)] * n
    return izip_longest(fillvalue=fillvalue, *args)

На современном питоне вам просто нужно использовать в zip_longest(*args, fillvalue=fillvalue) соответствии с соответствующей страницей документации .

Пэт
источник
2

Есть ли другой, «лучший» способ попарного обхода списка?

Я не могу сказать наверняка, но сомневаюсь в этом: любой другой обход включал бы больше кода Python, который необходимо интерпретировать. Встроенные функции, такие как zip (), написаны на C, что намного быстрее.

Как правильно обеспечить включение всех элементов?

Проверьте длину списка и, если он нечетный ( len(list) & 1 == 1), скопируйте список и добавьте элемент.

Аарон Дигулла
источник
2
>>> my_list = [1,2,3,4,5,6,7,8,9,10]
>>> my_pairs = list()
>>> while(my_list):
...     a = my_list.pop(0); b = my_list.pop(0)
...     my_pairs.append((a,b))
... 
>>> print(my_pairs)
[(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)]
Диармуид О'Брайен
источник
IndexError: извлечение из пустого списка
HQuser
@HQuser Конечно, вы получите эту ошибку, если у вас будет нечетное количество элементов в списке. Вы должны точно знать, что у вас есть пары, или проверить это состояние ошибки.
WaterMolecule
1

Только сделай это:

>>> l = [1, 2, 3, 4, 5, 6]
>>> [(x,y) for x,y in zip(l[:-1], l[1:])]
[(1, 2), (2, 3), (3, 4), (4, 5), (5, 6)]
Исраэль Гонсавес де Оливейра
источник
Ваш код эквивалентен более простому list(zip(l, l[1:])), и он не разбивает список на пары.
Апалала,
0

Вот пример создания пар / ног с помощью генератора. Генераторы свободны от ограничений стека

def pairwise(data):
    zip(data[::2], data[1::2])

Пример:

print(list(pairwise(range(10))))

Выход:

[(0, 1), (2, 3), (4, 5), (6, 7), (8, 9)]
Влад Безден
источник
Сравнение времени исполнения?
Алан
Список не разбивается на пары, так как большинство чисел в исходном списке представлены двумя кортежами. Ожидаемый результат[(0, 1), (2, 3), (4, 5)....
Апалала
@Apalala, спасибо, что указали. Я исправил код, чтобы обеспечить правильный вывод
Влад Безден
zip()уже возвращает генератор в Python 3.x, @VladBezden
апалала
если длина списка не четная, последний элемент будет удален
Даниил Охлопков
-1

На всякий случай, если кому-то понадобится алгоритм ответа, вот он:

>>> def getPairs(list):
...     out = []
...     for i in range(len(list)-1):
...         a = list.pop(0)
...         for j in a:
...             out.append([a, j])
...     return b
>>> 
>>> k = [1, 2, 3, 4]
>>> l = getPairs(k)
>>> l
[[1, 2], [1, 3], [1, 4], [2, 3], [2, 4], [3, 4]]

Но обратите внимание, что ваш исходный список также будет сокращен до последнего элемента, потому что вы использовали popего.

>>> k
[4]
фрейнмастер
источник