3

この配列があるとしましょう(実際には 255 の長さで、int.MaxValue までの値です) :

int[] lows = {0,9,0,0,5,0,0,8,4,1,3,0,0,0,0};

この配列から、自分の数値以下の値のインデックスを取得したいと考えています。

number = 7 -> index = 4
number = 2 -> index = 9
number = 8 -> index = 7
number = 9 -> index = 1

それを見つける最速の方法は何ですか？

これまで線形検索を使用してきましたが、この配列の長さは 255 しかありませんが、値が数百万回検索されるため、それは私のニーズに対して非効率的であることが判明しました。

Javaで使用されるTreeSet.floor(E)と同等のものが必要です。Dictionaryを使用したかったのですが、必要なように最初に小さい値または等しい値を見つけることができるかどうかわかりません。

4

4 に答える 4

3

配列を並べ替えてから、バイナリ検索を実行して値を見つけます。

見る：

https://en.wikipedia.org/wiki/Binary_search

と

Array.BinarySearch メソッド

于 2012-11-04T00:59:57.360 に答える
1

まず、データを正規化します。

public static Dictionary<int, int> GetNormalised(int[] data)
{
    var normalised = data.Select((value, index) => new { value, index })
        .GroupBy(p => p.value, p => p.index)
        .Where(p => p.Key != 0)
        .OrderBy(p => p.Key)
        .ToDictionary(p => p.Key, p => p.Min());
    return normalised;
}

検索方法:

public static int GetNearest(Dictionary<int, int> normalised, int value)
{
    var res = normalised.Where(p => p.Key <= value)
        .OrderBy(p => value - p.Key)
        .Select(p => (int?)p.Value)
        .FirstOrDefault();

    if (res == null)
    {
        throw new ArgumentOutOfRangeException("value", "Not found");
    }

    return res.Value;
}

単体テスト:

[TestMethod]
public void GetNearestTest()
{
    var data = new[] { 0, 9, 0, 0, 5, 0, 0, 8, 4, 1, 3, 0, 0, 0, 0 };
    var normalised = Program.GetNormalised(data);

    var value = 7;
    var expected = 4;
    var actual = Program_Accessor.GetNearest(normalised, value);
    Assert.AreEqual(expected, actual);

    value = 2;
    expected = 9;
    actual = Program_Accessor.GetNearest(normalised, value);
    Assert.AreEqual(expected, actual);

    value = 8;
    expected = 7;
    actual = Program_Accessor.GetNearest(normalised, value);
    Assert.AreEqual(expected, actual);

    value = 9;
    expected = 1;
    actual = Program_Accessor.GetNearest(normalised, value);
    Assert.AreEqual(expected, actual);        
}

パフォーマンスを最適化するには、使用されたすべての結果をキャッシュします。

于 2012-11-04T03:15:47.063 に答える
1

ソートされていない場合 (または、検索を支援できるメンバー間に関係があるデータ構造に保持されている場合)、すべてのメンバーを調べて正しいメンバーを見つける必要があります。

最も簡単な解決策は、おそらくそれを並べ替えてから、バイナリ チョップ/検索を実行して、条件に一致する要素を見つけることです。

ソートされていない配列を引き続き使用できるようにして効率を高めたい場合はsorted、リストがソートされていることを示すフラグを配列のどこかに維持します (つまり、すべてをインジケータと配列を含むクラスに変換します)。

false次に、配列が変更されるたびにこのフラグを設定します。

検索を実行する時点で、最初にsortedフラグをチェックし、配列が設定されている場合は配列を並べ替えますfalse(そのプロセスの一部として設定trueします)。フラグが の場合はtrue、並べ替えをバイパスします。

そうすれば、必要なときにのみソートできます。配列が最後の並べ替えから変更されていない場合は、再並べ替えの意味がありません。

ユーザーがそれを必要とする場合は、元のソートされていないリストを維持し、ソートされたリストをクラス内の追加の配列として保持することもできます (配列をクラス化するもう 1 つの利点)。そうすれば、何も失うことはありません。ユーザーが取得するためのオリジナルの手つかずのデータと、目的の要素を効率的に見つけるための迅速な手段があります。

オブジェクト（ソート時）には次が含まれます。

int[] lows       = {0,9,0,0,5,0,0,8,4,1,3,0,0,0,0};
int[] sortedlows = {0,0,0,0,0,0,0,0,0,1,3,4,5,8,9};
boolean isSorted = true;

次に に変更that_object[0]すると3、次のようになります。

int[] lows       = {3,9,0,0,5,0,0,8,4,1,3,0,0,0,0};
int[] sortedlows = {0,0,0,0,0,0,0,0,0,1,3,4,5,8,9};
boolean isSorted = false;

を検索する前にソートが必要であることを示しますsortedLows。

これをクラスに変換する必要はないことに注意してください。パフォーマンスが心配な場合 (具体的には getter メソッドを介して配列要素にアクセスする場合)、配列を維持し、並べ替えられていない配列への直接アクセスを許可しながら自分自身にフラグを立てることができます。配列を変更するコード内のすべての場所でもフラグが正しく設定されていることを確認する必要があります。

ただし、このパスを使用する前にパフォーマンスを測定する必要があります。オブジェクト自体がすべてを制御するため、クラスベースの方法は「より安全」です。

于 2012-11-04T01:00:42.463 に答える