22

Pythonでソートされた一意のリストを取得する高速な方法は何ですか? (私はハッシュ可能なもののリストを持っていて、反復できるものを持ちたいと思っています - リストがその場で変更されているか、新しいリストを取得しているか、イテラブルを取得しているかは問題ではありません。私の具体的なユースケースでは、私は '使い捨てリストでこれを行うので、インプレースの方がメモリ効率が高くなります。)

私は次のような解決策を見てきました

input = [5, 4, 2, 8, 4, 2, 1]
sorted(set(input))

しかし、最初に一意性をチェックしてからソートするのは無駄に思えます (リストをソートするときは、基本的に挿入ポイントを決定する必要があるため、副作用として一意性テストを取得する必要があるため)。たぶん、UNIXのラインに沿ってもっと何かがあるでしょう

cat list | sort | uniq

すでにソートされたリストで連続した重複を選択するだけですか?


' Python でリストを一意化する最速の方法 ' リストはソートされておらず、' Python リストでソートと uniq を実行する最もクリーンな方法は何ですか? ' 最もクリーンで最も Pythonic な方法を要求し、受け入れられた答えはsorted(set(input))、私が改善しようとしている を示唆しています。

4

5 に答える 5

28

私はsorted(set(sequence))それを行う最速の方法だと信じています。はい、setシーケンスを繰り返しますが、これは C レベルのループであり、Python レベルで行うループよりもはるかに高速です。

groupbyあなたがまだ持っていても、O(n) + O(nlogn) = O(nlogn)最悪のことgroupbyは、Pythonレベルのループが必要になることです。これにより、定数が劇的に増加しO(n)、最終的に最悪の結果が得られます。

CPython について話すとき、物事を最適化する方法は、C レベルでできる限りのことを行うことです (直観に反するパフォーマンスの別の例については、この回答を参照してください)。より高速なソリューションを得るには、C 拡張で並べ替えを再実装する必要があります。それでも、python の Timsort と同じくらい速く何かを取得できて幸運です!

「正規のソリューション」とソリューションの小さな比較groupby:

>>> import timeit
>>> sequence = list(range(500)) + list(range(700)) + list(range(1000))
>>> timeit.timeit('sorted(set(sequence))', 'from __main__ import sequence', number=1000)
0.11532402038574219
>>> import itertools
>>> def my_sort(seq):
...     return list(k for k,_ in itertools.groupby(sorted(seq)))
... 
>>> timeit.timeit('my_sort(sequence)', 'from __main__ import sequence, my_sort', number=1000)
0.3162040710449219

ご覧のとおり、3 倍遅いです。

jdm が提供するバージョンは、実際にはさらに悪いものです。

>>> def make_unique(lst):
...     if len(lst) <= 1:
...         return lst
...     last = lst[-1]
...     for i in range(len(lst) - 2, -1, -1):
...         item = lst[i]
...         if item == last:
...             del lst[i]
...         else:
...             last = item
... 
>>> def my_sort2(seq):
...     make_unique(sorted(seq))
... 
>>> timeit.timeit('my_sort2(sequence)', 'from __main__ import sequence, my_sort2', number=1000)
0.46814608573913574

ほぼ 5 倍遅くなります。Timsort はスペースを使用するため、常にいくらかの再割り当てがあるため、使用seq.sort()make_unique(seq)ても実際にはタイミングがあまり変わらないことに注意してください。make_unique(sorted(seq))O(n)sorted(seq)

jdm のベンチマークは、彼が使用している入力が小さすぎて、常にtime.clock()呼び出しに時間がかかっているため、異なる結果を示しています。

于 2012-11-28T12:58:01.700 に答える
5

これはあなたが探している答えではないかもしれませんが、とにかく、これを考慮に入れる必要があります。

基本的に、リストには 2 つの操作があります。

unique_list = set(your_list)       # O(n) complexity
sorted_list = sorted(unique_list)  # O(nlogn) complexity

さて、「最初に一意性をチェックしてからソートするのは無駄に思えます」とあなたは言いますが、あなたは正しいです。しかし、その冗長なステップは本当に悪いのでしょうか? n = 1000000 を取る:

# sorted(set(a_list))
O(n) => 1000000
o(nlogn) => 1000000 * 20 = 20000000
Total => 21000000

# Your fastest way
O(nlogn) => 20000000
Total: 20000000

速度ゲイン: (1 - 20000000/21000000) * 100 = 4.76 %

n = 5000000 の場合、スピード ゲイン: ~1.6 %

さて、その最適化はそれだけの価値がありますか?

于 2012-11-28T11:35:29.200 に答える
3

これは私が数分で作り上げたものです。この関数は、所定の場所にあるリストを変更し、連続する繰り返しを削除します。

def make_unique(lst):
    if len(lst) <= 1:
        return lst
    last = lst[-1]
    for i in range(len(lst) - 2, -1, -1):
        item = lst[i]
        if item == last:
            del lst[i]
        else:
            last = item

いくつかの代表的な入力データ:

inp = [
(u"Tomato", "de"), (u"Cherry", "en"), (u"Watermelon", None), (u"Apple", None),
(u"Cucumber", "de"), (u"Lettuce", "de"), (u"Tomato", None), (u"Banana", None),
(u"Squash", "en"), (u"Rubarb", "de"), (u"Lemon", None),
]

両方のバリアントが希望どおりに機能することを確認します。

print inp
print sorted(set(inp))
# copy because we want to modify it in place
inp1 = inp[:]
inp1.sort()
make_unique(inp1)
print inp1

次に、テストを行います。リストのコピーの時間を計りたくないので、timeitを使用していません。ソートのみを行っています。time1sorted(set(...)、の後に、time2list.sort()続きmake_unique、はAvinashYによるtime3解です。itertools.groupby

import time
def time1(number):
    total = 0
    for i in range(number):
        start = time.clock()
        sorted(set(inp))
        total += time.clock() - start
    return total

def time2(number):
    total = 0
    for i in range(number):
        inp1 = inp[:]
        start = time.clock()
        inp1.sort()
        make_unique(inp1)
        total += time.clock() - start
    return total

import itertools 

def time3(number): 
    total = 0 
    for i in range(number): 
        start = time.clock() 
        list(k for k,_ in itertools.groupby(sorted(inp))) 
        total += time.clock() - start 
    return total

sort + make_uniqueとほぼ同じ速さsorted(set(...))です。どちらが潜在的に高速であるかを確認するには、さらに2、3回の反復を行う必要がありますが、バリエーション内では非常に似ています。バージョンはitertools少し遅いです。

# done each 3 times
print time1(100000)
# 2.38, 3.01, 2.59
print time2(100000)
# 2.88, 2.37, 2.6
print time3(100000)
# 4.18, 4.44, 4.67

より大きなリストがあります(+ str(i)重複を防ぐためです):

old_inp = inp[:]
inp = []
for i in range(100):
    for j in old_inp:
        inp.append((j[0] + str(i), j[1]))

print time1(10000)
# 40.37
print time2(10000)
# 35.09
print time3(10000)
# 40.0

リストに重複がたくさんある場合は、最初のバージョンの方がはるかに高速であることに注意してください(ソートが少ないため)。

inp = []
for i in range(100):
    for j in old_inp:
        #inp.append((j[0] + str(i), j[1]))
        inp.append((j[0], j[1]))

print time1(10000)
# 3.52
print time2(10000)
# 26.33
print time3(10000)
# 20.5
于 2012-11-28T12:56:27.070 に答える
1
>>> import itertools
>>> a=[2,3,4,1,2,7,8,3]
>>> list(k for k,_ in itertools.groupby(sorted(a)))
[1, 2, 3, 4, 7, 8]
于 2012-11-28T11:50:50.313 に答える