Python эквивалент фильтра (), получая два выходных списка (то есть раздел списка) - PullRequest
Новая
       41

Python эквивалент фильтра (), получая два выходных списка (то есть раздел списка)

51 голосов
/ 02 января 2011

Допустим, у меня есть список и функция фильтрации.Используя что-то вроде 

>>> filter(lambda x: x > 10, [1,4,12,7,42])
[12, 42]

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

Edit: порядок элементов должен быть сохранен, и я могу иметь идентичные элементы несколько раз.

Ответы [ 11 ]

44 голосов
/ 02 января 2011

Попробуйте: 

def partition(pred, iterable):
    trues = []
    falses = []
    for item in iterable:
        if pred(item):
            trues.append(item)
        else:
            falses.append(item)
    return trues, falses

Использование: 

>>> trues, falses = partition(lambda x: x > 10, [1,4,12,7,42])
>>> trues
[12, 42]
>>> falses
[1, 4, 7]

Существует также предложение по реализации в рецептах itertools : 

from itertools import filterfalse, tee

def partition(pred, iterable):
    'Use a predicate to partition entries into false entries and true entries'
    # partition(is_odd, range(10)) --> 0 2 4 6 8   and  1 3 5 7 9
    t1, t2 = tee(iterable)
    return filterfalse(pred, t1), filter(pred, t2)

Рецепт взят из документации по Python 3.x.В Python 2.x filterfalse называется ifilterfalse.

21 голосов
/ 02 января 2011 
>>> def partition(l, p):
...     return reduce(lambda x, y: (x[0]+[y], x[1]) if p(y) else (x[0], x[1]+[y]), l,  ([], []))
... 
>>> partition([1, 2, 3, 4, 5], lambda x: x < 3)
([1, 2], [3, 4, 5])

и немного более уродливая, но более быстрая версия приведенного выше кода: 

def partition(l, p):
    return reduce(lambda x, y: x[0].append(y) or x if p(y) else x[1].append(y) or x, l,  ([], []))

Это второе редактирование, но я думаю, что это важно: 

 def partition(l, p):
     return reduce(lambda x, y: x[not p(y)].append(y) or x, l, ([], []))

Второй и третий такие же быстрые, как итеративный верхний, но меньше кода.

6 голосов
/ 20 апреля 2012

Я думаю, что groupby может быть более уместным здесь:

http://docs.python.org/library/itertools.html#itertools.groupby

Например, разбиение списка на нечетные и четные числа (или может быть произвольным числом групп): 

>>> l=range(6)
>>> key=lambda x: x % 2 == 0
>>> from itertools import groupby
>>> {k:list(g) for k,g in groupby(sorted(l,key=key),key=key)}
    {False: [1, 3, 5], True: [0, 2, 4]}
3 голосов
/ 14 сентября 2017

TL; DR

Ответ , получивший наибольшее количество голосов [1] Марк Байерс 

def partition(pred, iterable):
    trues = []
    falses = []
    for item in iterable:
        if pred(item):
            trues.append(item)
        else:
            falses.append(item)
    return trues, falses

является самым простым и быстрый.

Сравнительный анализ различных подходов

Различные предложенные подходы можно классифицировать в целом в трех категориях,

  1. прямое манипулирование списком с помощью lis.append, возвращающее 2-кортеж списков,
  2. lis.append опосредовано функциональным подходом, возвращая 2-кортеж списков,
  3. по каноническому рецепту, указанному в штрафе itertools документация, возвращающая 2 кортежа, свободно говоря, генераторов.

Здесь следует ванильная реализация трех техник, сначала функциональный подход, то itertools и в итоге два разных реализации прямого манипулирования списком, альтернатива использование False - ноль, True - один трюк.

Обратите внимание, что это Python3 - следовательно, reduce происходит от functools - и этот OP запросить кортеж типа (positives, negatives), но мой реализации все возвращают (negatives, positives)… 

$ ipython
Python 3.6.2 |Continuum Analytics, Inc.| (default, Jul 20 2017, 13:51:32) 
Type 'copyright', 'credits' or 'license' for more information
IPython 6.1.0 -- An enhanced Interactive Python. Type '?' for help.

In [1]: import functools
   ...: 
   ...: def partition_fu(p, l, r=functools.reduce):
   ...:     return r(lambda x, y: x[p(y)].append(y) or x, l, ([], []))
   ...: 

In [2]: import itertools
   ...: 
   ...: def partition_it(pred, iterable,
   ...:               filterfalse=itertools.filterfalse,
   ...:               tee=itertools.tee):
   ...:     t1, t2 = tee(iterable)
   ...:     return filterfalse(pred, t1), filter(pred, t2)
   ...: 

In [3]: def partition_li(p, l):
   ...:     a, b = [], []
   ...:     for n in l:
   ...:         if p(n):
   ...:             b.append(n)
   ...:         else:
   ...:             a.append(n)
   ...:     return a, b
   ...: 

In [4]: def partition_li_alt(p, l):
   ...:     x = [], []
   ...:     for n in l: x[p(n)].append(n)
   ...:     return x
   ...:

Нам нужен предикат для применения к нашим спискам и спискам (опять же, свободно говоря) на котором оперировать. 

In [5]: p = lambda n:n%2

In [6]: five, ten = range(50000), range(100000)

Чтобы преодолеть проблему при тестировании подхода itertools, это было сообщено joeln в 31 октября 2013 года в 6:17

Ерунда. Вы рассчитали время, необходимое для создания генераторы в filterfalse и filter, но вы не повторяли через вход или вызывается pred один раз! Преимущество itertools рецепт состоит в том, что он не материализует ни один список, или выглядит дальше впереди на входе, чем необходимо. Он вызывает pred в два раза часто и занимает почти вдвое дольше, чем Байерс и др.

Я думал о пустом цикле, который просто создает все пары элементов в двух итерациях, возвращаемых другим разделом функции.

Сначала мы используем два фиксированных списка, чтобы иметь представление о подразумевается перегрузка (используя очень удобную магию IPython %timeit) 

In [7]: %timeit for e, o in zip(five, five): pass
4.21 ms ± 39.4 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)

Далее мы используем разные реализации, одну за другой 

In [8]: %timeit for e, o in zip(*partition_fu(p, ten)): pass
53.9 ms ± 112 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [9]: %timeit for e, o in zip(*partition_it(p, ten)): pass
44.5 ms ± 3.84 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [10]: %timeit for e, o in zip(*partition_li(p, ten)): pass
36.3 ms ± 101 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [11]: %timeit for e, o in zip(*partition_li_alt(p, ten)): pass
37.3 ms ± 109 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

In [12]:

Комментарии

Самый простой из подходов также самый быстрый.

Использование трюка x[p(n)] бесполезно, потому что на каждом шагу вы нужно индексировать структуру данных, давая вам незначительное штраф - это Однако приятно знать, если вы хотите убедить выжившего в снижении культура при питонировании.

Функциональный подход, который оперативно эквивалентен альтернативная реализация append, на ~ 50% медленнее, возможно, из-за тот факт, что у нас есть дополнительная функция (w / r для оценки предиката) вызов для каждого элемента списка.

Подход itertools имеет (обычные) преимущества, которых нет создается потенциально большой список, и input входной список не полностью обработан, если вы выйдете из потребительской петли, но когда мы использовать его медленнее из-за необходимости применять предикат на обоих концы tee

Помимо

Я влюбился в object.mutate() or object идиому, которая был разоблачен Марией в их ответ показ функциональный подход к проблеме - боюсь, что рано или поздно Я собираюсь злоупотреблять этим.

Сноска

[1] Принят и получил наибольшее количество голосов по состоянию на сегодня, 14 сентября 2017 года - но, конечно, я возлагаю на него самые большие надежды!

3 голосов
/ 02 января 2011

Если у вас нет дублирующего элемента в вашем списке, вы определенно можете использовать set: 

>>> a = [1,4,12,7,42]
>>> b = filter(lambda x: x > 10, [1,4,12,7,42])
>>> no_b = set(a) - set(b)
set([1, 4, 7])

или вы можете сделать список понятным: 

>>> no_b = [i for i in a if i not in b]

N.B: это не функция, а просто зная первый результат fitler (), вы можете вывести элемент, который не соответствует критерию фильтра.

2 голосов
/ 29 августа 2017

Вы можете посмотреть на решение django.utils.functional.partition: 

def partition(predicate, values):
    """
    Splits the values into two sets, based on the return value of the function
    (True/False). e.g.:

        >>> partition(lambda x: x > 3, range(5))
        [0, 1, 2, 3], [4]
    """
    results = ([], [])
    for item in values:
        results[predicate(item)].append(item)
    return results

На мой взгляд, это самое элегантное решение , представленное здесь.

Эта часть не документирована, только исходный код можно найти на https://docs.djangoproject.com/en/dev/_modules/django/utils/functional/

2 голосов
/ 15 августа 2012

У меня просто было именно это требование.Я не заинтересован в рецепте itertools, поскольку он включает в себя два отдельных прохода данныхВот моя реализация: 

def filter_twoway(test, data):
    "Like filter(), but returns the passes AND the fails as two separate lists"
    collected = {True: [], False: []}
    for datum in data:
        collected[test(datum)].append(datum)
    return (collected[True], collected[False])
2 голосов
/ 02 января 2011 
from itertools import ifilterfalse

def filter2(predicate, iterable):
    return filter(predicate, iterable), list(ifilterfalse(predicate, iterable))
1 голос
/ 08 августа 2013

Кажется, все думают, что их решение лучшее, поэтому я решил использовать timeit, чтобы протестировать их все. Я использовал «def is_odd (x): return x & 1» в качестве моей функции предиката и «xrange (1000)» в качестве итерируемого. Вот моя версия Python: 

Python 2.7.3 (v2.7.3:70274d53c1dd, Apr  9 2012, 20:52:43) 
[GCC 4.2.1 (Apple Inc. build 5666) (dot 3)] on darwin

А вот результаты моего тестирования: 

Mark Byers
1000 loops, best of 3: 325 usec per loop

cldy
1000 loops, best of 3: 1.96 msec per loop

Dan S
1000 loops, best of 3: 412 usec per loop

TTimo
1000 loops, best of 3: 503 usec per loop

Все они сопоставимы друг с другом. Теперь давайте попробуем использовать пример, приведенный в документации по Python. 

import itertools

def partition(pred, iterable,
              # Optimized by replacing global lookups with local variables
              # defined as default values.
              filter=itertools.ifilter,
              filterfalse=itertools.ifilterfalse,
              tee=itertools.tee):
    'Use a predicate to partition entries into false entries and true entries'
    # partition(is_odd, range(10)) --> 0 2 4 6 8   and  1 3 5 7 9
    t1, t2 = tee(iterable)
    return filterfalse(pred, t1), filter(pred, t2)

Кажется, это немного быстрее. 

100000 loops, best of 3: 2.58 usec per loop

Пример кода itertools превосходит всех желающих как минимум в 100 раз! Мораль такова: не изобретай колесо заново.

0 голосов
/ 15 октября 2018

Краткий код для добавления в целевой список 

    def partition(cond,inputList):
        a,b= [],[]
        for item in inputList:
            target = a if cond(item) else b
            target.append(item)
        return a, b


    >>> a, b= partition(lambda x: x > 10,[1,4,12,7,42])
    >>> a
    [12, 42]
    >>> b
    [1, 4, 7]
Страница:
...