5

関連する質問が複数ありますが、私のケースに固有の解決策を探しています。(通常) 14 個の整数の配列があり、それぞれが 1 ～ 34 の範囲にあります。特定の静的リスト内の各 int がこの配列に少なくとも 1 回出現するかどうかをすばやく確認するにはどうすればよいでしょうか?

参考までに、私は現在このコードを使用しています。このコードは可能な限り仕様に似せて作成されているため、大幅に改善される可能性があります。

if (array.Count < 13) {
    return;
}

var required = new int[] {
    0*9 + 1,
    0*9 + 9,
    1*9 + 1,
    1*9 + 9,
    2*9 + 1,
    2*9 + 9,                
    3*9 + 1,
    3*9 + 2,
    3*9 + 3,
    3*9 + 4,
    3*9 + 5,
    3*9 + 6,
    3*9 + 7,
};

IsThirteenOrphans = !required.Except (array).Any ();

必要なリストは動的ではありません。つまり、実行時に常に同じになります。Linq の使用はオプションです。主な側面はパフォーマンスです。

編集：

  • 入力配列はソートされていません。
  • 入力値は複数回表示される場合があります。
  • 入力配列には、少なくとも 14 個の項目が含まれます。つまり、必要な配列よりも 1 つ多くなります。
  • 必要な配列は 1 つだけで、静的です。
  • 必須の値は異なります。
  • ヒストグラムは安価に作成できると考えるかもしれません。

更新:ソートされた入力配列のソリューションにも興味があります。

4

7 に答える 7

1

アイデア1
複数のリストと比較する必要がある場合はrequired、入力リストを並べ替えてから、繰り返して比較するだけです。しかし、ソートはもちろん速すぎませんが、遅すぎません。ただし、いくつかの必須リストと比較すると、並べ替えのオーバーヘッドはすぐに償却される可能性があります。

配列がソートされると、比較は簡単です。

for(int i = 0; i < 14; i++)
  if(arr[i] != required[i]) return false;

return true;

アイデア2
または、14個の整数が異なる/一意である場合はrequired、HashSetを作成して実行できます。

input.Count(i => required.Contains(i)) == 14

しかし、それがソートよりも速いかどうかは、実際にテストせずにわかりません。

アイデア
314intの順列の下で不変であるクイックハッシュを計算し、それをの既知の値と比較しますrequire。ハッシュが一致する場合にのみ、よりコストのかかる比較が行われます。

//Prepare/precalculated
int[] hashes = new int[34];
Random random = new Random();
for(int i = 0; i < 34; i++)
  hashes[i] = random.NextInt();

//On each list
int HashInts(int[] ints)
{
  int result = 0;
  foreach(int i in ints)
    result += hashes[i - 1];

  return result;
}

の値を賢く選択hashesすると少し改善されるかもしれませんが、ランダムな値で十分です。

アイデア4
ヒストグラムを作成する：

int[] CreateHistogram(int[] ints)
{
  int[] counts = new int[34];
  foreach(int i in ints)
  {
    counts[i - 1]++;
  }

  return counts;
}

パフォーマンスが本当に重要な場合は、既存のアレイを再利用することで、アレイの作成を回避できます。

于 2010-11-16T10:24:23.177 に答える
1

高速な方法が必要な場合は、linqを使用しないでください。特定のリストアイテムがすべて35以下の場合、以下if (lst[i] < 35) の回答トラバースリストを一度に削除できます。次のように動作しcounting sortます。

public bool FindExactMatch(int[] array, List<int> lst)
{
    bool[] a34 = new bool[35];

    foreach(var item in array)
    {
        a34[item] = true;
    }

    int exact = 0;

    for (int i = 0; i < lst.Count; i++)
    {
        if (a34[lst[i]])
        {
            exact++;
            if (exact == array.Length) return true;

            a34[lst[i]] = false;
        }
    }

    return false;
}

ソートされたリストの場合、リストサイズが大きい場合はlst.BinarySearch(array[i])、最大で14 * log（n）* c1を使用できます。実装した場合も十分に効率的であると思います。また、バイナリ検索をテストしませんでした。独自の実装ですが、linqでの最小、最大、並べ替えは、独自の（適切な）実装よりも遅くなります（4〜10倍）。また、ソートされたリストのサイズが小さい場合c1は、上記のアルゴリズムでは定数が小さく、バイナリ検索アルゴリズムでは定数が大きくなる可能性があるため、上記のようなアルゴリズムを使用することをお勧めします。

于 2010-11-16T11:26:33.987 に答える
1

これは、required の値が明確で静的で、1 から 34 の間であるため、ビット単位の演算に適しているように見えます。required を配列として保存する代わりに、const ulong として保存します。チェックする配列で、各値を左シフトし、ビット単位の OR で設定された新しい ulong を作成します。

const ulong comparator = (1UL << 1) | (1UL << 9) | (1UL << 10) | (1UL << 18) | (1UL << 19) | (1UL << 27) | (1UL << 28) | (1UL << 29) | (1UL << 30) | (1UL << 31) | (1UL << 32) | (1UL << 33) | (1UL << 34);

public static bool ContainsDistinct13Values(int[] array)
{
    ulong word = 0;
    foreach (int i in array)
    {
        word |= (1UL << i);
    }
    return word == comparator;
}
于 2016-06-19T16:21:45.263 に答える
1

34 ビット以上の整数型が利用可能で、C スタイルのビット操作がある場合、変数リストからそのような整数 V を計算できます (リストが v[0]、v[1]、... の場合、V は(1 << v[0]) | (1 << v[1]) ... ここで、1 は V) と同じ型であり、同様に計算された静的リストの定義済み整数 S を持ちます。静的リストが変数リストに含まれているかどうかを確認するテストは、(S & ~V) == 0 です。

于 2010-11-16T12:06:58.013 に答える
1

1 つの可能性は、データの保存方法を変更することです。可能な値の範囲は 1 ～ 34 に制限されているため、数値のリストを格納する代わりに、存在する各数値のカウントを格納できます。

int[] counts = new int[34];

リストに 1 と 2 の 3 がある場合、counts[0] == 1 && counts[2] = 2 となります (処理が速くなる (減算が少なくなる) 場合は、代わりに 1 ベースのインデックスを使用できます)。

リスト内の各 int が少なくとも 1 回出現することを評価するには、x ごとに順番に配列にインデックスを付け、すべての counts[x] > 0 であることを確認します。データを counts 形式からリスト フォームのデータを頻繁に表示する必要がある場合にのみ問題になります。このストレージ形式のもう 1 つの利点は、カウントへの追加/削除に 1 つ以上の配列要素が含まれないことです。リスト形式では、リストの途中にある要素を削除すると、複数の要素がコピーされます。

于 2010-11-16T15:00:24.560 に答える
0

項目を簡単にループして、欠落している項目がないかを調べることができます。あなたの例では、必要なアイテムが配列にないかどうかを知りたいだけだと理解しています。あなたが書くことができるように

bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;
    }

    if (notContains == false) break;
}

これはあなたのアプローチよりもはるかに高速です。タイマーが追加された以下のコードを確認してください。あなたのアプローチには5ミリ秒かかりましたが、新しいアプローチには0ミリ秒かかります

System.Diagnostics.Stopwatch aTimer = new System.Diagnostics.Stopwatch();
aTimer.Start();

var IsThirteenOrphans = !required.Except(array).Any();
aTimer.Stop();

System.Diagnostics.Stopwatch bTimer = new System.Diagnostics.Stopwatch();
bTimer.Start();
bool notContains = false;

foreach (var iddd in required)
{
    foreach (var ar in array)
    {
        if (iddd == ar) notContains=true;            
    }

    if (notContains == false) break;
}

bTimer.Stop();
于 2010-11-16T10:43:16.380 に答える
0

編集： だから私はあなたの質問を理解し、おそらくいくつかの複雑すぎる解決策を持っています。もう 1 つの問題は、パフォーマンスがどれだけ優れているかです。

static void Main(string[] args)
{
    var required = new int[]
                       {
                           0*9 + 1,
                           0*9 + 9,
                           1*9 + 1,
                           1*9 + 9,
                           2*9 + 1,
                           2*9 + 9,
                           3*9 + 1,
                           3*9 + 2,
                           3*9 + 3,
                           3*9 + 4,
                           3*9 + 5,
                           3*9 + 6,
                           3*9 + 7,
                       };

    precomputed = required.Select((x, i) => new { Value = x, Offset = (UInt16)(1 << i) }).ToDictionary(x => x.Value, x => x.Offset);

    for (int i = 0; i < required.Length; i++)
    {
        precomputedResult |= (UInt16)(1 << i);
    }

    int[] array = new int[34]; // your array goes here..
    Console.WriteLine(ContainsList(array));

    Console.ReadKey();
}

// precompute dictionary
private static Dictionary<int, UInt16> precomputed;
// precomputed result
private static UInt16 precomputedResult = 0;

public static bool ContainsList(int[] values)
{
    UInt16 result = 0;
    for (int i = 0; i < values.Length; i++)
    {
        UInt16 v;
        if (precomputed.TryGetValue(values[i], out v))
            result |= v;
    }

    return result == precomputedResult;
}
于 2010-11-16T10:48:11.260 に答える