Python のオブジェクトmost_commonによって提供される機能の複雑さはどれくらいですか?collections.Counter
より具体的には、Counterカウント中にある種の並べ替えられたリストを保持しているため、(一意の) アイテムの数がカウンターに追加される場合most_commonよりも高速に操作を実行できますか? 参考までに、大量のテキスト データを処理して、n 番目に頻度の高いトークンを見つけようとしています。O(n)n
CPython wiki の公式ドキュメントとTimeComplexity の記事を確認しましたが、答えが見つかりませんでした。
collections.pyのソース コードから、返される要素の数を指定しない場合most_common、カウントの並べ替えられたリストが返されることがわかります。これはO(n log n)アルゴリズムです。
を使用して要素most_commonを返す場合は、 を使用します。これは基本的に線形であるため、小さな定数に非常に適したアルゴリズムです。部分は初期カウントのヒープ化から、2 番目の部分はメソッド呼び出しから、3 番目の部分は要素の最終ヒープのソートから得られます。複雑さは次のように結論付けることができるため、k > 1heapq.nlargestO(k) + O((n - k) log k) + O(k log k)kO(k)kn - kheappushpopkk <= n
O(n log k)
その場合k = 1、複雑さが次のとおりであることを示すのは簡単です。
の上）