5

次の (サンプル) コードでパフォーマンスを改善しようとしています。

Object[] inputKeys = new Object[10];
inputKeys[0] = "4021";
inputKeys[1] = "3011";
inputKeys[2] = "1010";
inputKeys[3] = "1020";
inputKeys[4] = "1030";

次に、入力キーが比較されます。

for (int i = 0; i < 5; i++)
{
    for (int j = 0; j < 5; j++)
    {
        bool result = inputKeys[i].Equals(inputKeys[j]);
    }
}

inputKeys はすべてstring、int32またはのタイプにすることができますDateTime。

.Equals何百万回もヒットすると、パフォーマンスが大幅に低下します。

この行 (等価チェック) のパフォーマンスを改善する方法について何か提案はありますか?

私はこれを試しました: オブジェクト配列の代わりに以下のクラスの配列を使用してキーを保持します。そこで、キーの種類とキーの値を保持します。

public class CustomKey : IEquatable<CustomKey>{
    internal int KeyType { get; private set; }

    internal string ValueString { get; private set; }
    internal int ValueInteger { get; private set; }
    internal DateTime ValueDateTime { get; private set; }

    internal CustomKey(string keyValue)
    {
        this.KeyType = 0;
        this.ValueString = (string)keyValue;
    }

    internal CustomKey(int keyValue)
    {
        this.KeyType = 1;
        this.ValueInteger = (int)keyValue;
    }

    internal CustomKey(DateTime keyValue)
    {
        this.KeyType = 2;
        this.ValueDateTime = (DateTime)keyValue;
    }

    public bool Equals(CustomKey other)
    {
        if (this.KeyType != other.KeyType)
        {
            return false;
        }
        else
        {
            if (this.KeyType == 0)
            {
                return this.ValueString.Equals(other.ValueString);
            }
            else if (this.KeyType == 1)
            {
                return this.ValueInteger.Equals(other.ValueInteger);
            }
            else if (this.KeyType == 2)
            {
                return this.ValueDateTime.Equals(other.ValueDateTime);
            }
            else
            {
                return false;
            }
        }
    }
}

しかし、パフォーマンスは最悪でした。

4

5 に答える 5

2

比較ループは非効率的です。使用してみることをお勧めします：

Distinct<TSource>(this IEnumerable<TSource> source, IEqualityComparer<TSource> comparer)

そのタイプのを定義IEqualityComparerし、それをそのメソッドに渡します。ブール値は取得されませんが、IEnumerable重複のないリストを含むものが取得されます。

于 2012-12-18T17:55:02.410 に答える
2

アルゴリズム効率の例として、最初のコードを書き直すことができます

for (int i = 0; i < 5; i++)
{
    for (int j = i; j < 5; j++)
    {
        bool result = inputKeys[i].Equals(inputKeys[j]);
    }
}

x.Equals(y) は y.Equals と同じ結果になるため、両方の方法をチェックする必要はありません。 http://msdn.microsoft.com/en-us/library/ms173147(v=vs.80).aspx

Equals の新しい実装は、次のすべての保証に従う必要があります。

x.Equals(y) は、y.Equals(x) と同じ値を返します。

于 2012-12-18T18:07:08.483 に答える
1

コメントで述べたように、アルゴリズムの主な負担は、すべてをすべてと比較する必要があることであり、パフォーマンスが低下します。100k^2 を意味する 100K 要素の場合...または約 10,000 万の組み合わせ...どこに問題があるかがわかります。最善の選択肢はアルゴリズムを修正することですが、まだ決心している場合、または他に選択肢がない場合は、次のことを検討してください。

最初にオブジェクトを分割し、後で比較します:

例: 100,000 個のオブジェクトが均等に分散されている場合、33,000 個の int、33,000 個の文字列、および 33,000 個の日時があり、これらを相互に比較して、それらの間の組み合わせを無視することができます。

100K^2 = 10,000,000

(30K^2) * 3 = 27 億の組み合わせ + リスト内の各要素を注文するための 100K

グループを拡張する

メモリをあまり気にしない場合は、結果をハッシュしてグループをさらに絞り込むことができます。基本的にグリッドを構築します...これはあなたの問題に応じて非常に具体的です。

この背後にあるアイデアは、実際には等しくないものを分離することです。これは前のアイデアの拡張ですが、グループが多いほど、グループが小さいほどパフォーマンスが速くなります

そうすれば、10個のグループを持つことができます

  • 5 文字未満の文字列
  • 5 ～ 50 文字の文字列
  • 50 文字を超える文字列

等々...

計算をやり直す場合 (サンプルが均等に分散されている場合)

反復の合計 = 10K^2 * 10 + 100K ~ 1 億反復 (10 グループ + それらのグループを構成する価格)

実際の複雑さ = (n/m)^2 * m + n (ここで、n = 要素の数、m = 均等な分布を仮定したグループの数。

于 2012-12-18T18:15:34.733 に答える
0

すべてのオブジェクトのハッシュコードを取得して、それらを。と比較してみてくださいobject.GetHashCode()。数百万回呼び出すオーバーヘッドについてはわかりませんGetHashCode()が、2つのintを比較する方が、メソッドよりもはるかに高速になる可能性がありEquals(object)ます。

于 2012-12-18T17:55:29.123 に答える
0

ハッシュテーブル（またはより良い辞書）を使用してアイテムを保存します。アプローチは（N ^ 2）の順序で、ハッシュテーブルを使用することで、実行時間の複雑さをO（N）に減らすことができます.Nは数値です。

これを達成するには、ハッシュ キーを使用してハッシュ テーブルを作成します。競合が発生した場合は、アイテムをリンク リストに追加します。同じバケット内のオブジェクトが等しいかどうかをチェックするだけでよい場合。

これが明確で役立つことを願っています。

于 2012-12-18T18:12:42.980 に答える