2

私はhttp://comicjk.com/comic.php/906を読んでいました。そこでは、あるリストが別のリストの順列であるかどうかをチェックする問題が提示され、2つの解決策が提案されています。

「cbrain」ソリューション「リストには常に4つ少ない数が含まれ、各数は256未満になるため、すべての順列を32ビットintにバイトパックできます...」

「pythonbrain」ソリューションは、両方を並べ替えてから比較することです。これはより明白に思えますが、より効率的な（そして低レベルの）ソリューションに興味があります。

私の最初のアプローチは次のとおりです。

int permutations(int a[4], int b[4]){
  int A = a[0] | a[1]*1<<8 | a[2]*1<<16 | a[3]*1<<24;
  int B = b[0] | b[1]*1<<8 | b[2]*1<<16 | b[3]*1<<24;

  unsigned int c=0, i=0;

  for( i=0xFF; i>0; i<<=8 ){
      if( 
        A&i == B&0xFF ||
        A&i == B&0xFF00 ||
        A&i == B&0xFF0000 ||
        A&i == B&0xFF000000
      ) c |= i;
  }

  if( c == 0xFFFFFFFF )
    return 1;
  return 0;
}

しかし、A＆iとB * 0xxxxxxxxxの両方を同じバイトに配置する簡単な方法を見つけられない限り、これは機能しません（私たちが見ているバイトの後の末尾の0を削除します）。だから何かのような

(a&i>>al)>>ar == b(&j>>bl)>>br

ここで、al + ar == bl + br == 4であり、調べているバイトを判別するために使用されます。

別のアプローチ

コメントボックスの誰かが「Cでは、適切なサイズのメモリのセクションを動的に割り当てて、それを単一の数値として扱ってみませんか？確かに、intを使用するよりも少し遅くなりますが、制限もありません。 4つ以下の要素または最大数の256を含み、それでもソートよりも高速です（CまたはPythonのどちらでも）...」

ビット単位の長さが最大数よりも大きい配列を作成できる場合は、適切なビットを設定して配列を比較できますが、これを1つの大きな数として効率的に処理できない限り、比較を行うため、より多くの比較が可能になります。 cで。

x86（私は学習を始めたばかりです）にはSBC命令があるので、各部分を減算でき、結果がすべてゼロの場合（JNE / JNZでテストできます）、それらは等しくなります。

私が知る限り、私たちはまだやらなければならないでしょう/SBCとジャンプ

実際の質問

方法を知りたい

  1. バイトパッキング
  2. リスト全体を1つの大きな数として扱う

リストが別のリストの順列であるかどうかを確認するために使用できます（リストが4項目以下で、各項目が256未満であると想定）

4

3 に答える 3

2

結果がおそらく「いいえ」であると仮定した最適化：各リストの合計（またはxor、またはその他の安価な結合法則演算子）を計算します。合計が異なる場合、さらにテストしなければ答えはノーです。合計が同じである場合は、より高価なテストを実行して、決定的な答えを取得します。

于 2012-06-01T23:04:57.643 に答える
1

順列の影響を受けないハッシュが必要だと思います。加算は1つの方法として提供されました。ブルームフィルターと互換性のある方法を考えていたので、もっと多くのことができるようになりました。

ブルームフィルターは、任意の長さと任意のサイズの数のリストで機能します。これは、リストがリストのグループと同じ順列を持っているかどうかを確認するために使用できます。これは、要素がリストに存在する可能性があるかどうかを確認するために使用できます。

ブルームフィルターは基本的にビットの配列です。ブルームフィルターを作成するために、リストを構成する要素のビットを「または」一緒に作成します。同じ要素を任意の順序で含むリストには、同じビットが設定されます。小さなリストの場合、ビット配列に整数サイズの数値を使用することで回避できます。

unsigned char b = a1|a2|a3|a4; // where a1..n are items (8 bit numbers)

アイテムa1とブルームbのリストがあり、a1がリストに含まれているかどうかを知りたい場合：

fPossibleMatch = ((a1&b) == a1);

ブルームb1、b2を持つ任意の長さの2つのリストがあり、b1のすべてのアイテムがb2に存在する可能性があるかどうかを知りたい場合：

fPossibleMatch = ((b1&b2) == b1);

同じ要素数のリストb1とb2が互いに順列であるかどうかを知りたい場合。

fPossibleMatch = (b1==b2);

誤検知を減らすには、ブルームフィルターを広げます。64ビットブルームを使用した場合、この任意に選択したアルゴリズムを使用してビットを分散させることができます。

unsigned long long b = (a1<<(a1&0x1F)) | (a2<<(a2&0x1F)) | (a3<<(a3&0x1F)) | a4<<(a4&0x1F);

ブルームを広げるための私のアルゴリズムは良くないように感じます。すべてのビットをマッシュに設定するだけかもしれません。他の誰かがもっと良い方法を知っているかもしれません。私はあなたがその考えを理解していると思います。

私はこれがより良いと思います：

#define MUNGE(a) ((a)<<(((a)&7)<<3))
unsigned long long b = MUNGE(a1)|MUNGE(a2)|MUNGE(a3)|MUNGE(a4)

私はハッシュを作成するのが苦手です。

ブルームフィルターが一致するリストを再確認する必要があります。誤検知の数は、リストの長さと要素のサイズが大きくなるにつれて増加します。ブルームサイズが大きくなると、誤検知は減少します。

于 2012-06-02T00:44:29.147 に答える
1

ハッシュテーブルを使用して、各リストを繰り返し処理します。これにより、O（n）時間とO（n）メモリを必要とするソリューションが得られます。

于 2012-06-02T18:21:28.120 に答える