Python は、私がやりたいことを実行するには十分に高速ではないため、既に作成した Python コードを C++ または別の高速言語に変換したいと考えています。ただし、問題のコードは、Python セットの印象的な機能の一部、特に、パフォーマンスが重要なループ内でスパムする平均 O(1) メンバーシップ テストを悪用しており、別の言語で Python セットを実装する方法がわかりません。
Python の Time Complexity Wiki ページでは、セットには平均で O(1) メンバーシップ テストがあり、最悪の場合は O(n) であると記載されています。私はこれを個人的に使用してtimeitテストし、N が大きい場合でも、非常に高速な Python セットがメンバーシップ テストを行うことに驚きました。このスタック オーバーフローの回答findを見て、操作を使用して要素が特定のメンバーであるかどうかを確認するときに C++ セットがどのように比較されるかを確認しました。設定すると、O（log（n））であるとのことでした。
findC++ std ライブラリ セットがある種のバイナリ ツリーで実装されているという点で、 の時間の複雑さは対数的であると仮定します。Python セットには平均 O(1) メンバーシップ テストと最悪の場合 O(n) があるため、要素を簡単に検索してダミー値をテストできるバケットを備えたある種の連想配列で実装されている可能性があります。これは、要素がセットの一部ではないことを示します。
問題は、別の言語に切り替えることでコードのどの部分も遅くしたくないということです (それが最初に修正しようとしている問題であるため)。どうすれば独自のバージョンの Python セットを実装できますか (特に迅速なメンバーシップ テストのみ）別の言語で？Python セットがどのように実装されているかについて何か知っている人はいますか? そうでない場合は、正しい方向に向けるための一般的なヒントを教えてもらえますか?
私が探しているのはソース コードではありません。始めるのに役立つ一般的なアイデアとリンクを探しているだけです。
連想配列について少し調査しましたが、その実装の背後にある基本的な考え方は理解していると思いますが、メモリ使用量についてはわかりません。Python セットが実際に連想配列である場合、メモリの使用を最小限に抑えてそれらを実装するにはどうすればよいでしょうか?
追加メモ: 使用したい問題のセットには最大 50,000 の要素があり、セットの各要素は大きな範囲になります ([-999999999, 999999999] など)。