一致する要素でリストを分割するPythonicで効率的な方法は何ですか？

Question

これはPython: split a list based on a condition?に非常に類似しており、またhttps://nedbatchelder.com/blog/201306/filter_a_list_into_two_parts.htmlではなく、述語に基づいて2つのリストに個々の要素を分割するのは、私は述語を失敗した最初の要素で二つの部分にリストを分割したいです。 （我々は条件を複数回評価する必要はありません

入力リストがソートされない場合があり

• 入力リストが含まれていてもよい重複要素理想的
：

>>> divide_list(lambda x: x < 7, list(range(10))) 
([0, 1, 2, 3, 4, 5, 6], [7, 8, 9]) 

>>> divide_list(lambda x: x < 7, [1, 3, 5, 7, 9, 5]) 
([1, 3, 5], [7, 9, 5]) 

>>> divide_list(lambda x: x < 7, [7, 9, 5]) 
([], [7, 9, 5]) 

>>> divide_list(lambda x: x < 7, [1, 3, 5]) 
([1, 3, 5], []) 

>>> divide_list(lambda x: x['a'], [{'a': True, 'b': 1}, {'a': True}, {'a': False}]) 
([{'a': True, 'b': 1}, {'a': True}], [{'a': False}]) 

物事

は注意します各要素について、値が重複しているならば、それは大丈夫です）
• 理想的には、入力（すなわちのみ入力データに対する単一のパスを行うことができます）
0123としてイテレータを受け入れるだろうの
• 返すイテレータは、物事が転がり取得する

Answer 1

ナイーブな実装可能です。ここで

def divide_list(pred, lst): 
    before, after = [], [] 
    found = False 
    for item in lst: 
     if not found: 
      if pred(item): 
       before.append(item) 
      else: 
       found = True 
     if found: 
      after.append(item) 
    return before, after 

Answer 2

私の比較的効率的な試みです：あなたは他の回答ベンチマークにこれをした場合

from collections import Hashable 

def divide_list(pred, list): 
    # The predicate may be expensive, so we can 
    # store elements that have already been checked 
    # in a set for fast verification. 
    elements_checked = set() 

    # Assuming that every element of the list is of 
    # the same type and the list is nonempty, we can 
    # store a flag to check if an element is hashable. 
    hashable = isinstance(list[0], Hashable) 

    for index, element in enumerate(list): 
     if hashable and element in elements_checked: 
      continue 

     if not pred(element): 
      return list[:index], list[index:] 

     if hashable: 
      elements_checked.add(element) 

    return list, [] 

、私はこれが最も速くなると思う。

ところでこの質問が大好きです！

Answer 3

私はあなたが実際に出力としてイテレータを必要としない限り、naive implementationはおそらく最高だと思います。入力ストリームがイテレータであり、一度にすべてを実現するための十分なメモリがない場合に便利です。

この場合、itertoolsは素晴らしいと思います。私の最初の腸の本能は次のようなものでした：

# broken :-(
def divide_iter(pred, lst): 
    i = iter(lst) 
    yield itertools.takewhile(lst, pred) 
    yield i 

残念ながら、これはさまざまな理由でうまくいきません。最も顕著なのは、要素を落とすことです。たとえそうでなくても、takewhile全体を消費せずに次のリストに進むことができれば、問題に遭遇する可能性があります。この第2の問題はイテレーター全般を扱うときに起こる問題であると思われます。だから、それは一種の厄介ですが、リスト全体を実現するよりも要素ごとに処理するために支払う代金です一度。

代わりに、のは述語がまだtrueを返したかどうかに基づいてアイテムをグループ化について考えてみましょう。その後、groupbyはもっと魅力的になります - 唯一のことは、述語がTrueを返すかどうかを追跡する必要があることです。ステートフル機能はとても代わりに、私たちはクラスを使用してgroupbyへの鍵引数としてバインドされたメソッドを渡すことができます多くの楽しみではありません。

import itertools 

class _FoundTracker(object): 
    def __init__(self, predicate): 
     self.predicate = predicate 
     self._found = False 

    def check_found(self, value): 
     if self._found: 
      return True 
     else: 
      self._found = self.predicate(value) 
      return self._found 

def split_iterable(iterable, predicate): 
    tracker = _FoundTracker(predicate) 
    for i, (k, group) in enumerate(itertools.groupby(iterable, key=tracker.check_found)): 
     yield group 
    if i == 0: 
     yield iter(()) 

if __name__ == '__main__': 
    for group in split_iterable(xrange(10), lambda x: x < 5): 
     print(list(group)) 

これはまた、いくつかの可能性がファンキーな行動を持っている...検討し、実証するために：

g1, g2 = split_iterable(xrange(10), lambda x: x > 5) 
print(list(g1)) 
print(list(g2)) 

あなたが:-)いくつかの本当に奇妙な動作を取得することを確認できます。代わりに：

g1, g2 = map(list, split_iterable(range(10), lambda x: x > 5)) 
print(g1) 
print(g2) 

は正常に動作するはずです。

Answer 4

これは基本的に単純な試みですが、述部が失敗したときを判別するために別個のブール・フラグを使用しません。最初の1つのリストへの参照を使用し、次にもう1つのリストへの参照を使用して追加を行います。

def divide_list(pred, lst): 
    a, b = [], [] 
    curr = a 
    for x in lst: 
     if curr is a and not pred(x): 
      curr = b 
     curr.append(x) 
    return a, b