内存优化的 OrderBy 和 Take？

Question

我有 9 GB 数据，但我只需要 10 行。当我这样做时：

 data.OrderBy(datum => datum.Column1)
     .Take(10)
     .ToArray();

我收到一个 OutOfMemoryException。我想使用经过优化以降低内存消耗的 OrderByAndTake 方法。写起来很容易，但我想已经有人写过了。我在哪里可以找到它。

编辑：这是 Linq-to-objects。数据来自文件。如果每行的 Column1 值小于当前列表中的 10 个最大值，则可以丢弃该行。

Answer 1

我假设您在 Linq to Objects 中执行此操作。你可以做类似的事情......

var best = data
    .Aggregate(new List<T>(), (soFar, current) => soFar
                                                 .Concat(new [] { current })
                                                 .OrderBy(datum => datum.Column1)
                                                 .Take(10)
                                                 .ToList());

这样，并不是所有的项目都需要保存在一个新的排序集合中，只有你感兴趣的最好的 10 个项目。

这是最少的代码方式。由于您知道 soFar 列表已排序，因此可以优化测试插入 current 的位置/是否插入。我不想为你做所有的工作。 ;-)

PS：将 T 替换为您的类型。

编辑：想想看，最有效的方法实际上是一个普通的旧 foreach ，它将每个项目与最佳 10 项的运行列表进行比较。

Answer 2

可以看出：OrderBy 是一个 Sort，需要存储所有元素（延迟执行被取消）。

当 data 是 IQueryable 时，它​​应该有效地工作，然后由数据库决定。

---

  // just 4 fun
  public static IEnumerable<T> TakeDistinctMin<T, TKey>(this IEnumerable<T> @this, 
        int n, Func<T, TKey> selector)            
         where TKey: IComparable<TKey>
  {
        var tops = new SortedList<TKey, T>(n+1);

        foreach (var item in @this)
        {
            TKey k = selector(item);

            if (tops.ContainsKey(k))
                continue;

            if (tops.Count < n)
            {
                tops.Add(k, item);
            }
            else if (k.CompareTo(tops.Keys[tops.Count - 1]) < 0)
            {
                tops.Add(k, item);
                tops.RemoveAt(n);
            }                                    
        }

        return tops.Values;
    }

Answer 3

要对一组无序对象进行排序，您必须查看所有对象，不是吗？

我不明白你如何能够避免解析所有 9 GB 的数据以获取以某种方式排序的前 10 个数据，除非 9 GB 的数据已经以这种方式排序或者如果有索引或其他辅助数据可以利用的结构。

您能否就您的问题提供更多背景信息。您是否使用 LINQ to SQL 或实体框架或其他 O/RM 查询数据库？

Answer 4

您可以将类似的内容与 投影比较器：

public static IEnumerable<T> OrderAndTake<T>(this IEnumerable<T> seq,int count,IComparer<T> comp)
{
  var resultSet=new SortedSet<T>(comp);
  foreach(T elem in seq)
  {
    resultSet.Add(elem);
    if(resultSet.Count>count)
        resultSet.Remove(resultSet.Max);
  }
  return resultSet.Select(x=>x);
}

运行时应该是O(log(count)*seq.Count())并且space O(min(log(count),seq.Count()))

一个问题是，如果有两个元素 comp.Compare(a,b)= ，它就会中断=0 因为该集合不允许重复条目。