pythonの集合(set)を最も速く並び替えるアルゴリズム

Question

実現したいこと

python3で集合を並び替えたい場合、組み込み関数sorted()よりも早く実現できるアルゴリズムは何かありますか？
集合には要素の重複がありませんが、リストと同じアルゴリズムを利用するのでしょうか...？

よろしくお願いいたします。

コードの例を追記しますと、

node = {1:0, 2:[1,0,1],3:[2,1,3],4:[3,1,5]}
nodes = [0,1,2,2,3,1,4]
nodes = sorted(set(nodes))[2:]
#　sorted とマージさせた方が速い...?
s = 1
for j in nodes:
    if node[j][1]==1:
        s *= 3
print(s)
#この時点でnodesがソートされていて欲しい

このような場合、sorted()を使うよりも速い方法はありますか?

Comments

[toast-uz]

速い遅いは、集合の中身や全体の処理にも依存しますし、多少の変更は誤差であることも多いです。また「○○を速くしたい」と手段を限定して質問される場合、コード全体をみてみたら、そもそも○○ではない△△を使う方が100倍効率的です、みたいなことが、とてもよくあります。またそもそもPythonじゃ無理です、みたいな回答をしたことも実際にございます。

よって、まずは「遅い」と感じられているコードブロックを提示して、現在質問者様の環境でどのくらいの時間がかかっているのかを明示するとともに、できれば理由も添えて何秒以内にしたいみたいなことまで提示いただくと、よい回答がつきやすいです。

逆に、単純な技術的興味や、学校の宿題で必要になったためなど、背景をあまり表現できない場合は、そうお知らせください。

[LouiS0616]

@runanana さん
集合の要素は何ですか。
特定範囲の整数しか入らないのであれば、改善の余地があります。

[runanana]

@toast-uzさん
ご返信ありがとうございます。
速度が遅いコードを改善したいというのではなく、
単純な技術的興味で、
集合を並び替えるときにsorted()を使うよりも良い、高速な方法はあるのか気になった次第です。

[runanana]

@LouiS0616さん
ご返信ありがとうございます。
今後使う場合、特定範囲の整数のみなのですが、改善方法を是非教えてください。
よろしくお願いいたします。

[runanana]

@toast-uzさん
自分が今後書くであろうコードを追記してみました。

Answer 1

今後使う場合、特定範囲の整数のみなのですが、改善方法を是非教えてください。

よろしくお願いいたします。

バケットソートを検討してみて下さい。
取り得る値が離散的かつ範囲が限定されているときに真価を発揮するアルゴリズムです。

性質上、値が重複するときの方がより高効率です。集合でも使えはします。

bucket = [0 for _ in range(10)]

src = [3, 1, 4, 1, 5, 9, 2]
for e in src:
    bucket[e] += 1
    
dst = []
for e, num in enumerate(bucket):
    dst.extend([e] * num)

# 内包表記でも可。
# dst = [
#     e
#     for e, num in enumerate(bucket)
#     for _ in range(num)
# ]
    
print(dst)  # => [1, 1, 2, 3, 4, 5, 9]

重複を排除するついでにソートしても良いです。

dst = [
    e for e, num in enumerate(bucket) if num
]

取り得る値の範囲が非常に広い場合は、基数ソートが強力でしょう。

---

ただし、sortedを超える保証はありません。
要素数が非常に多く、ついでに重複も多い場合は期待できます。O(n)なので。

Comments

[runanana]

ありがとうございます。
質問にコードを追記してみたのですが、
このような場合にも有効でしょうか？

[LouiS0616]

ちょうど同タイミングで回答に追記したのですが、重複を排除するついでにソートすることも可能です。

[runanana]

ありがとうございます。バケットソート、基数ソートという方法を初めて知ることができました。

Answer 2

Pythonの集合には「順序」という概念がありませんので、集合をソートしたいという発想そのものが無いと思います。ですので、集合ならではのソートアルゴリズムを求めるのではなく、リストとしてのソートアルゴリズムを求めるべきと思います。

*上記の「順序」は、ソートとしての順序ですので、要素を列挙して順番に取り出せることとは別の意味です。
*集合の特性である「重複要素が無い」ことを生かした、リストソートのアルゴリズムがあるかもしれません。

Pythonのsorted()はiterableを対象にしていますので、コードとしては実行可能です。ただしこれは集合をソートしているのではなく、集合から列挙した要素の並び（リストと等価な構造）をソートしています。

実際、質問者様が例示されているnodes = [0,1,2,2,3,1,4]は、setに入れた時点で、以下に示すように順序は無くなり集合の列挙順番での表示となります（最初のnodesの並びを変えてもsetに入れた時点で同じ結果になります）。なお、これは質問者様が期待するソート結果順に並んでいると思いますので、列挙された結果をさらにsorted()や他の独自ソートアルゴリズムにかけることは不要になっています。たたし、この列挙順はPythonに保証されているわけではありませんので、set()することでソートされるとは考えないようにお願いします。また、他の順番でソートしたい、という要望も、列挙した後のリストと等価な構造に対しての操作であり、結果はリストとして保持すると思います。その結果を再度集合に変換した時点で、順序が無くなりますので、操作したことは無に帰します。

nodes = [0,1,2,2,3,1,4]
print(set(nodes))
#{0, 1, 2, 3, 4}

集合とリストの違いを確認するためのサンプルコード

import random

num = 10
random_list = random.sample(list(range(num)), num)
print('random_list =', random_list)
random_set = set(random_list)
print('random??_set =', random_set)
sorted_list = sorted(random_list)
print('sorted_list =', sorted_list)
sorted_set = set(sorted(random_set))
print('sorted_set =', sorted_set)
print('random_list == sorted_list ?', random_list == sorted_list)
print('random_set == sorted_set ?', random_set == sorted_set)

サンプルコードの実行結果

random_list = [2, 5, 4, 9, 0, 3, 1, 6, 7, 8]
random??_set = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
sorted_list = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
sorted_set = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
random_list == sorted_list ? False
random_set == sorted_set ? True

Comments

[LouiS0616]

@toast-uz さん
『setはミュータブルなので比較演算子が機能します』とは、どういう意味でしょうか？

[toast-uz]

数値の集合は中の数値含めて一致しているかを==で判断できる、くらいの意味です。言い方が正確でない部分、もしくは例外があれば、教えていただけますと助かります。あ、イミュータブルの間違いでした。

[toast-uz]

なんかタプルと勘違いしていました。その行消しておきます。

[LouiS0616]

タプルも集合もリストも == で各々比較可能ですし、ミュータブル／イミュータブルは関係ないと思います。

[Zuishin]

> Pythonの集合には「順序」という概念がありませんので、集合をソートしたいという発想そのものが無いと思います。

集合に含まれる要素をより速くソートできるかという質問で、ソートは現にできます。
「できない」は明らかに間違った回答です。

[toast-uz]

「できない」とは回答には書かれていません。発想そのものが無い = 実用上の意味が無い、と言っています。

[Zuishin]

実用上の意味はありますし、それは発想とは無関係のように思います。回答の意図が違うなら、きちんと結論がわかるよう書き直してください。

[LouiS0616]

> setに入れた時点で、以下に示すようにソート（とは言いませんが）された状態になっております

どういう意味でしょうか。

[toast-uz]

nodes = [4,1,2,2,3,1,0] とかでも、print(set(nodes))　が、{0, 1, 2, 3, 4} になることを表現しているつもりですが、もっとよい表現はありますでしょうか？

[LouiS0616]

それこそ『集合には順序の概念が無い』ことに尽きると思います。
挿入順を維持する環境、ハッシュ順に並べる環境、さまざまありますので。
（追記：集合の挿入順序維持については要検証。辞書の場合はそういう環境もあるのですが。）

CPython3.8.3
>>> {1000, 2000, 3000, 4000}
{1000, 4000, 3000, 2000}

[toast-uz]

なるほど。記述を見直してみました。ご確認いただけますと幸いです。

[Zuishin]

集合に順序の発想が無いと書きながら set に入れることでソートされるなど、むちゃくちゃです。

[toast-uz]

LouiS0616様、Pythonの集合のイテレーション順番はドキュメント化されていないかもですね。hashをオブジェクトに設定して数値とあわせて集合作ってみると、必ずしもhash順にならんでいません。そのことについて混同が無いように、少し回答を修正してみます。

[LouiS0616]

表示順について前に解析した記憶があったのですが、ようやく見つけました。
(hash値 % 内部テーブル長) 順に並んでいます。
https://teratail.com/questions/224546

ただしこれもCPythonの特定のバージョンに限った話ではあります。

[toast-uz]

ありがとうございます。

[runanana]

色々と教えてくださり、本当にありがとうございます。