2

多数の注文があり、各注文には購入したItemオブジェクトが含まれています。

1 : {Item1, Item2, Item3, Item4, Item5}  
2 : {Item2, Item8, Item4, Item3, Item11, Item5} 
3 : { ... }

私の目標は、それらの各アイテムが一緒に購入され、O(1) で結果を得ることができる頻度を確立することです。

私の考えは、サブセット項目に基づいて注文を繰り返すことでした-特定の配列の要素を増やします。これにより、O(1) で必要な値を抽出できるようになります。

例えば。Item3 と Item4 は 2 回購入されました。

int frequency = myArray[getHash(Item3+Item4)]

print frequency;

Output : 2

問題：

int getHash(...)アイテムのサブセットをハッシュできる関数を開発します。

注: {Item1, Item2} = {Item2, Item1}

どうもありがとうございました！より良いアイデアの助けを歓迎します！

4

2 に答える 2

4

{A,B} = {B,A}続行する前に、まずリストを並べ替える必要があるためです。何をソートするかは問題ではありませんが、順序付けで交換可能でない限り、ソートの目的で等しいと見なされる値がないことを確認する必要があります。

次に、任意の単純なハッシュ アルゴリズムが機能するはずです。一般的な手法は、2 つの素数を使用することです。私はそれらcを と と呼びますp。

int hash = c;
foreach(Item i in items) hash = hash * p + i.GetHashCode()
return hash;

pが素数であるだけでなく、コンパイラがビットシフトと減算に解決するため、31 が選択されることがあります。これは、乗算よりもはるかに高速です。x * 31と同じです(x << 5) - 1（適切なシフトを使用したと仮定します...私は時々それを台無しにします、笑）。

于 2012-10-19T15:34:31.287 に答える
0

申し訳ありませんが、私はハッシュを使用していませんが、私が行う方法で試してみました。そのような課題を解決しようとするのが好きです。

Dictionary<Item, Dictionary<Item, Count>> combine = new Dictionary<Item, Dictionary<Item, Count>>();

foreach (Item item in Sell)
{
    Dictionary<Item, int> key;
    if (!combine.TryGetValue(item, out key))
    {
        key = new Dictionary<Item, Count>();
        combine.Add(item, key);
    }

    foreach (Item otherItem in Sell)
    {
        if (item == otherItem)
            continue;

        Count count;
        if (key.TryGetValue(otherItem, out count))
            count++;
        else
            key.Add(otherItem, new Count());
    }
}

それはおそらく非常にばかげています。各アイテムについて、カウンターで同時に購入した他のすべてのアイテムの辞書が作成されるからです。また、Item1 が Item2 AND Item3 と Item2 OR Item3 と同時に購入されているかどうかを知りたい場合は、どうすればよいでしょうか。私に構わずに。

于 2012-10-19T15:47:16.077 に答える