20

あるタイプのコレクションがあるとしましょう。

IEnumerable<double> values;

次に、いくつかのパラメーターkについて、そのコレクションからk個の最高値を抽出する必要があります。これは、これを行うための非常に簡単な方法です。

values.OrderByDescending(x => x).Take(k)

ただし、これは（私がこれを正しく理解している場合）最初にリスト全体をソートし、次に最初のk個の要素を選択します。しかし、リストが非常に大きく、kが比較的小さい（log nよりも小さい）場合、これはあまり効率的ではありません-リストはO（n * log n）でソートされますが、リストからk個の最高値を選択すると思いますO（n * k）のようにする必要があります。

それで、これを行うためのより良い、より効率的な方法について誰かが何か提案がありますか？

4

4 に答える 4

6

これにより、パフォーマンスが少し向上します。降順ではなく昇順ですが、再利用できるはずです（コメントを参照）：

static IEnumerable<double> TopNSorted(this IEnumerable<double> source, int n)
{
    List<double> top = new List<double>(n + 1);
    using (var e = source.GetEnumerator())
    {
        for (int i = 0; i < n; i++)
        {
            if (e.MoveNext())
                top.Add(e.Current);
            else
                throw new InvalidOperationException("Not enough elements");
        }
        top.Sort();
        while (e.MoveNext())
        {
            double c = e.Current;
            int index = top.BinarySearch(c);
            if (index < 0) index = ~index;
            if (index < n)                    // if (index != 0)
            {
                top.Insert(index, c);
                top.RemoveAt(n);              // top.RemoveAt(0)
            }
        }
    }
    return top;  // return ((IEnumerable<double>)top).Reverse();
}
于 2013-02-26T12:51:30.490 に答える
2

以下の方法を検討してください。

static IEnumerable<double> GetTopValues(this IEnumerable<double> values, int count)
{
    var maxSet = new List<double>(Enumerable.Repeat(double.MinValue, count));
    var currentMin = double.MinValue;

    foreach (var t in values)
    {
        if (t <= currentMin) continue;
        maxSet.Remove(currentMin);
        maxSet.Add(t);
        currentMin = maxSet.Min();
    }

    return maxSet.OrderByDescending(i => i);
}

そしてテストプログラム：

static void Main()
{
    const int SIZE = 1000000;
    const int K = 10;
    var random = new Random();

    var values = new double[SIZE];
    for (var i = 0; i < SIZE; i++)
        values[i] = random.NextDouble();

    // Test values
    values[SIZE/2] = 2.0;
    values[SIZE/4] = 3.0;
    values[SIZE/8] = 4.0;

    IEnumerable<double> result;

    var stopwatch = new Stopwatch();

    stopwatch.Start();
    result = values.OrderByDescending(x => x).Take(K).ToArray();
    stopwatch.Stop();
    Console.WriteLine(stopwatch.ElapsedMilliseconds);

    stopwatch.Restart();
    result = values.GetTopValues(K).ToArray();
    stopwatch.Stop();
    Console.WriteLine(stopwatch.ElapsedMilliseconds);
}

私のマシンの結果は1002と14です。

于 2013-02-26T13:03:16.987 に答える
0

これを行う別の方法 (何年も C# を使用していないため、疑似コードです。申し訳ありません) は次のようになります。

highestList = []
lowestValueOfHigh = 0
   for every item in the list
        if(lowestValueOfHigh > item) {
             delete highestList[highestList.length - 1] from list
             do insert into list with binarysearch
             if(highestList[highestList.length - 1] > lowestValueOfHigh)
                     lowestValueOfHigh = highestList[highestList.length - 1]
   }
于 2013-02-26T12:44:45.857 に答える
0

プロファイリングなしでは、パフォーマンスについては何も述べません。この回答ではO(n*k)、1つの最大値に対して1つの列挙を取るアプローチを実装しようとします。個人的にはオーダー方式の方が優れていると思います。ともかく：

public static IEnumerable<double> GetMaxElements(this IEnumerable<double> source)
    {
        var usedIndices = new HashSet<int>();
        while (true)
        {
            var enumerator = source.GetEnumerator();
            int index = 0;
            int maxIndex = 0;
            double? maxValue = null;
            while(enumerator.MoveNext())
            {
                if((!maxValue.HasValue||enumerator.Current>maxValue)&&!usedIndices.Contains(index))
                {
                    maxValue = enumerator.Current;
                    maxIndex = index;
                }
                index++;
            }
            usedIndices.Add(maxIndex);
            if (!maxValue.HasValue) break;
            yield return maxValue.Value;
        }
    }

使用法：

var biggestElements = values.GetMaxElements().Take(3);

欠点:

  1. メソッドは、ソース IEnumerable に順序があることを前提としています
  2. メソッドは、追加のメモリ/操作を使用して、使用済みのインデックスを保存します。

アドバンテージ：

  • 次の最大値を取得するには、1 つの列挙が必要であることを確認できます。

実行中を参照してください

于 2013-02-26T13:25:30.883 に答える