如何避免OrderBy内存使用问题
如何避免OrderBy内存使用问题
提问于 2010-07-26 00:24:25
让我们假设我们有一个很大的点列表List<Point> pointList (已经存储在内存中)，其中每个Point都包含X、Y和Z坐标。
现在，我想选择例如在pointList中存储的所有点中具有最大Z值的N%的点。现在我是这样做的：
N = 0.05; // selecting only 5% of points
double cutoffValue = pointList
.OrderBy(p=> p.Z) // First bottleneck - creates sorted copy of all data
.ElementAt((int) pointList.Count * (1 - N)).Z;
List<Point> selectedPoints = pointList.Where(p => p.Z >= cutoffValue).ToList();但这里有两个内存使用瓶颈:第一个是在OrderBy期间(更重要)，第二个是在选择点期间(这不太重要，因为我们通常只想选择少量的点)。
有没有办法用使用更少内存的东西代替OrderBy (或者找到这个分界点的其他方法)？
这个问题非常重要，因为LINQ复制了整个数据集，对于我正在处理的大文件，它有时会达到几百MB。
回答 7
Stack Overflow用户
回答已采纳
发布于 2010-07-26 00:35:27
您可以使用List<T>.Sort对列表进行就地排序，它使用快速排序算法。当然，您的原始列表将被排序，这可能不是您想要的……
pointList.Sort((a, b) => b.Z.CompareTo(a.Z));
var selectedPoints = pointList.Take((int)(pointList.Count * N)).ToList();如果您不介意对原始列表进行排序，这可能是内存使用和速度之间最好的平衡
Stack Overflow用户
发布于 2010-07-26 00:43:47
编写一个遍历列表一次的方法，并维护一组M个最大的元素。每一步只需要O(log M)工作来维护集合，并且您可以拥有O(M)内存和O(N log M)运行时间。
public static IEnumerable<TSource> TakeLargest<TSource, TKey>
(this IEnumerable<TSource> items, Func<TSource, TKey> selector, int count)
{
var set = new SortedDictionary<TKey, List<TSource>>();
var resultCount = 0;
var first = default(KeyValuePair<TKey, List<TSource>>);
foreach (var item in items)
{
// If the key is already smaller than the smallest
// item in the set, we can ignore this item
var key = selector(item);
if (first.Value == null ||
resultCount < count ||
Comparer<TKey>.Default.Compare(key, first.Key) >= 0)
{
// Add next item to set
if (!set.ContainsKey(key))
{
set[key] = new List<TSource>();
}
set[key].Add(item);
if (first.Value == null)
{
first = set.First();
}
// Remove smallest item from set
resultCount++;
if (resultCount - first.Value.Count >= count)
{
set.Remove(first.Key);
resultCount -= first.Value.Count;
first = set.First();
}
}
}
return set.Values.SelectMany(values => values);
}如果存在关联，那么它将包含更多的count元素，就像您现在的实现所做的那样。
Stack Overflow用户
发布于 2010-07-26 00:37:13
您可以使用Indexed LINQ对正在处理的数据建立索引。在某些情况下，这可以带来显着的改进。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/3329985
复制相关文章
相似问题