0

これはプログラミングの問題ではないかもしれませんが、最近仕事で発生した問題です。いくつかの背景：パフォーマンスに特別な関心を持つBigCの開発。

整数のセットがあり、別の指定された整数のメンバーシップをテストしたいと思います。最初のセットに含まれる整数の空間全体を表すために整数のみを使用して、最小限の代数関数のセットでそれをチェックできるアルゴリズムを実装したいと思います。

たとえば、複合Cantorペアリング関数を試しましたが、30要素のセットでは複雑すぎるようで、パフォーマンスに焦点を当てても意味がありません。XORや否定などの操作をいくつか試しましたが、メンバーシップの見積もりが低くなります。それから私は追加の連続で試みました、そして最終的に迷子になりました。

何か案は？

4

3 に答える 3

2

サイズが 30のセットのunsigned long場合、次の方法がかなり明白な方法の 1 つです。

  • 各セットを並べ替えられた配列として格納し30 * sizeof(unsigned long)ます (セットごとのバイト数)。
  • 整数を検索するには、二分探索を数ステップ実行し、続いて線形探索を実行します (二分探索の最適なステップ数を把握するためのプロファイル - 私の勝手な推測では 2 ステップですが、異なることがわかるかもしれません。もちろん、テストbsearchして十分に速い場合は、そのまま使用できます）。

したがって、次の質問は、なぜ大規模なソリューションが必要なのかということです。これにより、「十分に満足できない」以外に、このソリューションの何が問題なのかがわかります。

大きな数学のソリューションは、これよりも遅くなると思います。N 桁の数値に対する単一の算術演算は、少なくとも N の線形時間かかります。セットを表す単一の数値は、区切り文字を挟んで端から端まで配置されたセットの要素よりもはるかに小さくすることはできません。したがって、セット内の線形検索でさえ、大きな数に対する単一の算術演算とほぼ同じくらい高速です。nゲーデル表現の可能性のある例外を除いて、1番目の素数が見つかったら 1 つの除算でそれを行うことができますが、セットの巧妙な数学的表現は、メンバーシップを確立するために複数の算術演算を必要とします。

また、「セット内の整数を検索する」のパフォーマンスを気にする理由は 2 つあります。

  • 1 つのセットで多数の異なる整数を検索しています。この場合、そのデータのカスタム ルックアップ関数を作成することで高速化できる場合があります。もちろん、C では、(a) その「関数」を実行する単純な仮想マシン、(b) ランタイム コード生成、または (c) コンパイル時にセットを知る必要があることを意味します。どれも必ずしも簡単ではありません。
  • 多くの異なるセットで同じ整数を検索しています (それが属するすべてのセットのシーケンスを取得するため)。 .

非常にまれに、それぞれが異なるセットにある多くの異なる整数を検索している可能性があるため、どちらの理由にも当てはまらないと思います。これがそれらの 1 つである場合は、そのようなものを無視できます。

于 2012-08-28T09:51:11.340 に答える
0

ブルーム フィルターを試すことから始めるとよいでしょう。基本的に、これは確率的データ構造であり、偽陰性はありませんが、偽陽性がいくつかあります。したがって、整数がブルーム フィルターと一致する場合は、それが実際にセットに一致するかどうかを確認する必要がありますが、チェックするセットの数を大幅に減らすことで大幅な高速化を実現できます。

于 2012-08-28T09:38:38.303 に答える
0

私があなたを正しく理解していれば、Pythonの例:

>>> a=[1,2,3,4,5,6,7,8,9,0]
>>>
>>>
>>> len_a = len(a)
>>> b = [1]
>>> if len(set(a) - set(b)) < len_a:
...     print 'this integer exists in set'
...
this integer exists in set
>>>

数学ベース: http://en.wikipedia.org/wiki/Euler_diagram

于 2012-08-28T09:39:05.367 に答える