順序を維持しながらリストから重複を削除するにはどうすればよいですか?
https://stackoverflow.com/questions/480214
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian質問
順序を維持しながら、Pythonのリストから重複を削除する組み込みはありますか?セットを使用して重複を削除できることはわかっていますが、そうすると元の順序が破壊されます。また、次のように自分でロールできることも知っています。
def uniq(input):
output = []
for x in input:
if x not in output:
output.append(x)
return output
ただし、可能であれば、組み込みのイディオムまたはより Python 的なイディオムを利用したいと考えています。
関連する質問: Python で、リストから重複を削除してすべての要素を一意にするための最速のアルゴリズムは何ですか? 秩序を保ちながら?
解決
ここではいくつかの代替手段があります。 http://www.peterbe.com/plog/uniqifiers-benchmark
最速のもの:
def f7(seq):
seen = set()
seen_add = seen.add
return [x for x in seq if not (x in seen or seen_add(x))]
割り当てる理由 seen.add に seen_add ただ電話するだけではなく seen.add?Python は動的言語であり、 seen.add 各反復はローカル変数を解決するよりもコストがかかります。 seen.add 反復の間に変更された可能性がありますが、ランタイムはそれを排除できるほど賢くありません。安全策を講じるには、毎回オブジェクトをチェックする必要があります。
同じデータセットでこの関数を頻繁に使用する予定がある場合は、順序付きセットを使用した方がよいでしょう。 http://code.activestate.com/recipes/528878/
○(1) 操作ごとの挿入、削除、およびメンバーのチェック。
(ちょっとした追記: seen.add() 常に戻ってきます None, 、それで、 or 上記は、セットの更新を試みる方法としてのみ存在し、論理テストの不可欠な部分として存在するものではありません。)
他のヒント
編集2016年
としてのレイモンド 指摘, は、python3.5+る OrderedDict が実施され、リスト内包のアプローチするよりも遅れ OrderedDict (されない限りは、必要のリストの末ともできたし、とても満足している場合にのみ、入力が非常にいいます）が運用しています。そのベストソリューション3.5+は OrderedDict.
重要なの編集2015
として @abarnert 注、 more_itertools 図書館(pip install more_itertools)が含まれて unique_everseen 機能内蔵されたこの問題を解決するな 読む (not seen.add) 突然変異 リスト理解.これも最速の解決をもたらせ
>>> from more_itertools import unique_everseen
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(unique_everseen(items))
[1, 2, 0, 3]
一つだけの簡単な図書館の輸入なhacks.これらの実施にitertoolsレシピ unique_everseen を次のように記述されています。
def unique_everseen(iterable, key=None):
"List unique elements, preserving order. Remember all elements ever seen."
# unique_everseen('AAAABBBCCDAABBB') --> A B C D
# unique_everseen('ABBCcAD', str.lower) --> A B C D
seen = set()
seen_add = seen.add
if key is None:
for element in filterfalse(seen.__contains__, iterable):
seen_add(element)
yield element
else:
for element in iterable:
k = key(element)
if k not in seen:
seen_add(k)
yield element
Python 2.7+ の 受け入れ共通ム （作品がんに最適な速度は、現在利用中の unique_everseen この用途 collections.OrderedDict:
ランタイム: O(N)
>>> from collections import OrderedDict
>>> items = [1, 2, 0, 1, 3, 2]
>>> list(OrderedDict.fromkeys(items))
[1, 2, 0, 3]
これは素晴らしい以外:
seen = set()
[x for x in seq if x not in seen and not seen.add(x)]
な活用を 醜いhack:
not seen.add(x)
に依存していること set.add することができますので場所る方法で返します None なので not None 評価 True.
ただし、ハッキングを解速度が速くなり生速度も同じ実行時の計算量O(N)
Python2.7, は、新しいものから重複を削除するlistを維持しながら、確性と客観性を保証するためには:
>>> from collections import OrderedDict
>>> list(OrderedDict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']
Python3.5, のOrderedDictはCの実装です。私のタイミングをすることもに最速最短の様々なアプローチPython3.5.
Python3.6, 一般の辞ともなったが、注文されたコンパクトです。(この機能は保持のためのCPythonとPyPyことができない恐れがある現在の実装).ることのできる新しい最速のdedupingつめ
>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']
Python3.7, 一般の辞書が両方の注文の全てになります。 なので、最短、最速液には:
>>> list(dict.fromkeys('abracadabra'))
['a', 'b', 'r', 'c', 'd']
対@max:一度に移3.6 3.7利用の辞書の代わりに OrderedDict, なので本当にビートスマートフォン関連その他。辞書に緻密で容易に変換するリストのほとんどないオーバーヘッド。のターゲットリストの前の小さなlen(d)を実現するすべてのサイズを発生するリストを理解したりしています。また、内部キリストが密集して、コピーのポインタはほとんどの高速リストとしてコピーします。
sequence = ['1', '2', '3', '3', '6', '4', '5', '6']
unique = []
[unique.append(item) for item in sequence if item not in unique]
ユニーク→['1', '2', '3', '6', '4', '5']
from itertools import groupby
[ key for key,_ in groupby(sortedList)]
、十分条件は、等しい値が一緒にグループ化されることである。
の編集：私は「秩序を維持すること」リストは、実際に注文していることを意味していることを想定。そうでない場合は、MizardXからの解決策は正しいものです。の
コミュニティ編集：これはしかし、「単一の要素に重複した連続する要素を圧縮する」ための最もエレガントな方法である。
（この質問は非常に古く、すでに良い答えをたくさん持っている）が、ここでは多くの状況で非常に高速で、使い方が簡単に死んでいるパンダを使用したソリューションである死んだ馬を蹴るまでもありません。
import pandas as pd
my_list = [0, 1, 2, 3, 4, 1, 2, 3, 5]
>>> pd.Series(my_list).drop_duplicates().tolist()
# Output:
# [0, 1, 2, 3, 4, 5]
あなたは秩序を維持したい場合、私が思うに、
あなたはこれを試すことができます。
list1 = ['b','c','d','b','c','a','a']
list2 = list(set(list1))
list2.sort(key=list1.index)
print list2
または同様に、あなたがこれを行うことができます：
list1 = ['b','c','d','b','c','a','a']
list2 = sorted(set(list1),key=list1.index)
print list2
あなたもこれを行うことができます
list1 = ['b','c','d','b','c','a','a']
list2 = []
for i in list1:
if not i in list2:
list2.append(i)`
print list2
list1 = ['b','c','d','b','c','a','a']
list2 = []
for i in list1:
if not i in list2:
list2.append(i)`
print list2
また、このように記述することができます
list1 = ['b','c','d','b','c','a','a']
list2 = []
[list2.append(i) for i in list1 if not i in list2]
print list2
list1 = ['b','c','d','b','c','a','a']
list2 = []
[list2.append(i) for i in list1 if not i in list2]
print list2
外部モジュールからそのような機能の別の（非常にパフォーマンスの高い）実装を追加するだけです1: iteration_utilities.unique_everseen:
>>> from iteration_utilities import unique_everseen
>>> lst = [1,1,1,2,3,2,2,2,1,3,4]
>>> list(unique_everseen(lst))
[1, 2, 3, 4]
タイミング
いくつかのタイミング (Python 3.6) を実行しましたが、テストした他のすべての代替手段よりも高速であることがわかりました。 OrderedDict.fromkeys, f7 そして more_itertools.unique_everseen:
%matplotlib notebook
from iteration_utilities import unique_everseen
from collections import OrderedDict
from more_itertools import unique_everseen as mi_unique_everseen
def f7(seq):
seen = set()
seen_add = seen.add
return [x for x in seq if not (x in seen or seen_add(x))]
def iteration_utilities_unique_everseen(seq):
return list(unique_everseen(seq))
def more_itertools_unique_everseen(seq):
return list(mi_unique_everseen(seq))
def odict(seq):
return list(OrderedDict.fromkeys(seq))
from simple_benchmark import benchmark
b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
{2**i: list(range(2**i)) for i in range(1, 20)},
'list size (no duplicates)')
b.plot()
そして、念のため、違いが生じるかどうかを確認するために、より多くの重複を使用してテストも行いました。
import random
b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
{2**i: [random.randint(0, 2**(i-1)) for _ in range(2**i)] for i in range(1, 20)},
'list size (lots of duplicates)')
b.plot()
そして、値を 1 つだけ含むもの:
b = benchmark([f7, iteration_utilities_unique_everseen, more_itertools_unique_everseen, odict],
{2**i: [1]*(2**i) for i in range(1, 20)},
'list size (only duplicates)')
b.plot()
これらすべての場合において、 iteration_utilities.unique_everseen この関数は（私のコンピュータでは）最速です。
これ iteration_utilities.unique_everseen この関数は、入力内のハッシュ不可能な値も処理できます (ただし、 O(n*n) の代わりにパフォーマンス O(n) 値がハッシュ可能な場合のパフォーマンス)。
>>> lst = [{1}, {1}, {2}, {1}, {3}]
>>> list(unique_everseen(lst))
[{1}, {2}, {3}]
1 免責事項:私はそのパッケージの作成者です。
他の非常に遅い回答を別のものとを義務付けられている:
の itertools レシピ 機能を持っているところは、 seen セットの技術が
- を取り扱い基準
key機能です。 - を使用しないunseemly hacks.
- 最適ループによる事前結合
seen.addくみっNます。(f7受ける必要がありますが、一部のバージョンになります。) - 最適なループを使用
ifilterfalse, ましてループの独自の要素がPythonではなく、全員について記入してください。続に対して繰り返し処理を実行すべての内ifilterfalse, もちろん、そのことで、より高速にします。)
では実際よりも早く f7?によって異なりますので、おのデータがありますので，そこでしっかりしている試験です。したい場合はリストに f7 使用listcompがあるわけではない方法が確立されてきています。(あります。 append の代わりに yieldング、食糧を供給することができ、発電機の list 機能がなで検索したい単語を入力して下LIST_APPEND内listcomp.) で、通常は、押し出し、数マイクロ秒単位でくなってしまうことが重要と簡単-わかりやすく、再利用可能な、すでに書き機能を必要としないDSUしたいときに飾る
すべてのレシピもご用意 more-iterools.
また、無key の場合、できる簡素化す:
def unique(iterable):
seen = set()
seen_add = seen.add
for element in itertools.ifilterfalse(seen.__contains__, iterable):
seen_add(element)
yield element
MizardX者に基づいていないハッシュ可能なタイプ（リストの例リスト）について：
def f7_noHash(seq)
seen = set()
return [ x for x in seq if str( x ) not in seen and not seen.add( str( x ) )]
リストのHaskellのnub機能をdefininingに使用される再帰的なアイデアを借り、これは再帰的なアプローチになります：
def unique(lst):
return [] if lst==[] else [lst[0]] + unique(filter(lambda x: x!= lst[0], lst[1:]))
例えば：ます。
In [118]: unique([1,5,1,1,4,3,4])
Out[118]: [1, 5, 4, 3]
私は成長しているデータサイズのためにそれを試してみましたが、サブ線形時の複雑さを見ました（決定的ではないが、これは通常のデータの罰金する必要があります示唆して）ます。
In [122]: %timeit unique(np.random.randint(5, size=(1)))
10000 loops, best of 3: 25.3 us per loop
In [123]: %timeit unique(np.random.randint(5, size=(10)))
10000 loops, best of 3: 42.9 us per loop
In [124]: %timeit unique(np.random.randint(5, size=(100)))
10000 loops, best of 3: 132 us per loop
In [125]: %timeit unique(np.random.randint(5, size=(1000)))
1000 loops, best of 3: 1.05 ms per loop
In [126]: %timeit unique(np.random.randint(5, size=(10000)))
100 loops, best of 3: 11 ms per loop
私はまた、これは容易に他の操作によって一意に一般化することができることは興味深いことだと思います。このように：
import operator
def unique(lst, cmp_op=operator.ne):
return [] if lst==[] else [lst[0]] + unique(filter(lambda x: cmp_op(x, lst[0]), lst[1:]), cmp_op)
たとえば、あなたはそれが一意目的のための「平等」であるかのように、このように、同じ整数に丸めるという概念を使用する関数に渡すことができます：
def test_round(x,y):
return round(x) != round(y)
、一意（some_list、test_round）は一意性はなくなりました（この問題に対するセットベースまたはdictのキー・ベースのアプローチの任意の並べ替えを使用することによって暗示される）伝統的な平等を意味し、リストのユニークな要素を提供する代わりになり要素は丸める可能性があることをそれぞれ可能な整数KのためにKに丸め最初の要素だけを取るためのものに、例えばます：
In [6]: unique([1.2, 5, 1.9, 1.1, 4.2, 3, 4.8], test_round)
Out[6]: [1.2, 5, 1.9, 4.2, 3]
5×速いバリアントを減らすことが、より洗練された
>>> l = [5, 6, 6, 1, 1, 2, 2, 3, 4]
>>> reduce(lambda r, v: v in r[1] and r or (r[0].append(v) or r[1].add(v)) or r, l, ([], set()))[0]
[5, 6, 1, 2, 3, 4]
説明：
default = (list(), set())
# use list to keep order
# use set to make lookup faster
def reducer(result, item):
if item not in result[1]:
result[0].append(item)
result[1].add(item)
return result
>>> reduce(reducer, l, default)[0]
[5, 6, 1, 2, 3, 4]
MizardXの答えは、複数のアプローチの良いコレクションを与えます。
これは、私は声を出して考えながら思い付いたものです。
mylist = [x for i,x in enumerate(mylist) if x not in mylist[i+1:]]
あなたは「[1] _」リスト内包表記を参照することができます。
たとえば、次の関数のリスト内包を参照することにより、その順序を変更することなく、要素のリストをユニークに-ifiesます。
def unique(my_list):
return [x for x in my_list if x not in locals()['_[1]']]
デモます：
l1 = [1, 2, 3, 4, 1, 2, 3, 4, 5]
l2 = [x for x in l1 if x not in locals()['_[1]']]
print l2
出力：
[1, 2, 3, 4, 5]
あなたは醜いリスト内包ハックの並べ替えを行うことができます。
[l[i] for i in range(len(l)) if l.index(l[i]) == i]
_sorted_ numpyアレイと比較的効果的なアプローチ：
b = np.array([1,3,3, 8, 12, 12,12])
numpy.hstack([b[0], [x[0] for x in zip(b[1:], b[:-1]) if x[0]!=x[1]]])
を出力します：
array([ 1, 3, 8, 12])
l = [1,2,2,3,3,...]
n = []
n.extend(ele for ele in l if ele not in set(n))
Oを使用するジェネレータ式（1）新しいリスト内の要素を含めるかどうかを決定するために、セットのルックアップ
単純な再帰解決策ます：
def uniquefy_list(a):
return uniquefy_list(a[1:]) if a[0] in a[1:] else [a[0]]+uniquefy_list(a[1:]) if len(a)>1 else [a[0]]
あなたは1つのライナーを必要とする場合は、多分これは役立つだろう。
reduce(lambda x, y: x + y if y[0] not in x else x, map(lambda x: [x],lst))
...動作しますが、私が間違っているなら、私を修正する必要があります。
pandas の使用、および美学は、パフォーマンスよりも優先されている場合は、は、それから考えるビルトイン関数pandas.Series.drop_duplicates：
import pandas as pd
import numpy as np
uniquifier = lambda alist: pd.Series(alist).drop_duplicates().tolist()
# from the chosen answer
def f7(seq):
seen = set()
seen_add = seen.add
return [ x for x in seq if not (x in seen or seen_add(x))]
alist = np.random.randint(low=0, high=1000, size=10000).tolist()
print uniquifier(alist) == f7(alist) # True
タイミングます：
In [104]: %timeit f7(alist)
1000 loops, best of 3: 1.3 ms per loop
In [110]: %timeit uniquifier(alist)
100 loops, best of 3: 4.39 ms per loop
これは順序を保持し、O（n）の時間で実行されます。基本的なアイデアが見つかりました。重複がある場所に穴を作成して、一番下にそれを沈めることです。読み取りおよび書き込みポインタを使用しています。重複しただけリードポインタの進歩を発見し、書き込みされるたびにポインタがそれを上書きする重複エントリに残ります。
def deduplicate(l):
count = {}
(read,write) = (0,0)
while read < len(l):
if l[read] in count:
read += 1
continue
count[l[read]] = True
l[write] = l[read]
read += 1
write += 1
return l[0:write]
インポートモジュールまたはセットを使用せずに溶液
text = "ask not what your country can do for you ask what you can do for your country"
sentence = text.split(" ")
noduplicates = [(sentence[i]) for i in range (0,len(sentence)) if sentence[i] not in sentence[:i]]
print(noduplicates)
出力を与えます：
['ask', 'not', 'what', 'your', 'country', 'can', 'do', 'for', 'you']
アンインプレース方法
この方法では、我々はリストのすべての要素のリストに線形のルックアップを持っているので（それまで我々が原因delのリストを並べ替えるのコストを追加する必要があります）、次です。
私たちは、リストの末尾から始まり、
その左でサブリストに存在する各用語を削除し、原点に向かって進んでいる場合、所定の位置に操作することが可能である、と述べたことコード内のこの考え方は単純です。
for i in range(len(l)-1,0,-1):
if l[i] in l[:i]: del l[i]
の実装の簡単なテストの
In [91]: from random import randint, seed
In [92]: seed('20080808') ; l = [randint(1,6) for _ in range(12)] # Beijing Olympics
In [93]: for i in range(len(l)-1,0,-1):
...: print(l)
...: print(i, l[i], l[:i], end='')
...: if l[i] in l[:i]:
...: print( ': remove', l[i])
...: del l[i]
...: else:
...: print()
...: print(l)
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5, 2]
11 2 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4, 5]
10 5 [6, 5, 1, 4, 6, 1, 6, 2, 2, 4]: remove 5
[6, 5, 1, 4, 6, 1, 6, 2, 2, 4]
9 4 [6, 5, 1, 4, 6, 1, 6, 2, 2]: remove 4
[6, 5, 1, 4, 6, 1, 6, 2, 2]
8 2 [6, 5, 1, 4, 6, 1, 6, 2]: remove 2
[6, 5, 1, 4, 6, 1, 6, 2]
7 2 [6, 5, 1, 4, 6, 1, 6]
[6, 5, 1, 4, 6, 1, 6, 2]
6 6 [6, 5, 1, 4, 6, 1]: remove 6
[6, 5, 1, 4, 6, 1, 2]
5 1 [6, 5, 1, 4, 6]: remove 1
[6, 5, 1, 4, 6, 2]
4 6 [6, 5, 1, 4]: remove 6
[6, 5, 1, 4, 2]
3 4 [6, 5, 1]
[6, 5, 1, 4, 2]
2 1 [6, 5]
[6, 5, 1, 4, 2]
1 5 [6]
[6, 5, 1, 4, 2]
In [94]:
シーケンス内の重複値を排除するが、残りの項目の順序を維持します。汎用ジェネレータ機能の使用ます。
# for hashable sequence
def remove_duplicates(items):
seen = set()
for item in items:
if item not in seen:
yield item
seen.add(item)
a = [1, 5, 2, 1, 9, 1, 5, 10]
list(remove_duplicates(a))
# [1, 5, 2, 9, 10]
# for unhashable sequence
def remove_duplicates(items, key=None):
seen = set()
for item in items:
val = item if key is None else key(item)
if val not in seen:
yield item
seen.add(val)
a = [ {'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 1, 'y': 2}, {'x': 2, 'y': 4}]
list(remove_duplicates(a, key=lambda d: (d['x'],d['y'])))
# [{'x': 1, 'y': 2}, {'x': 1, 'y': 3}, {'x': 2, 'y': 4}]
ZMKのアプローチは非常に高速ですリストの内包を使用して、まだ自然の順序を保持します。敏感な文字列を小文字ために適用することは容易に変更することができます。また、これはオリジナルのケースを保存します。
def DelDupes(aseq) :
seen = set()
return [x for x in aseq if (x.lower() not in seen) and (not seen.add(x.lower()))]
密接に関連する機能があります：
def HasDupes(aseq) :
s = set()
return any(((x.lower() in s) or s.add(x.lower())) for x in aseq)
def GetDupes(aseq) :
s = set()
return set(x for x in aseq if ((x.lower() in s) or s.add(x.lower())))
