如何避免OrderBy内存使用问题

您可以使用 List<T>.Sort ,它使用快速排序算法。但当然,你的原始列表会被排序,这可能不是你想要的。。。

pointList.Sort((a, b) => b.Z.CompareTo(a.Z));
var selectedPoints = pointList.Take((int)(pointList.Count * N)).ToList();

编写一个方法,在列表中迭代一次并维护一组最大的M个元素。每个步骤只需要O(logm)工作来维护集合,并且您可以拥有O(M)内存和O(nlogm)运行时间。

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 元素,就像您的实现现在所做的那样。

你可以用 Indexed LINQ 对正在处理的数据建立索引。在某些情况下,这会导致显著的改善。

如果将两者结合起来,可能会少做一点工作:

List<Point> selectedPoints =  pointList
    .OrderByDescending(p=> p.Z) // First bottleneck - creates sorted copy of all data
    .Take((int) pointList.Count * N);

但基本上这种排名需要排序,这是你最大的成本。

还有一些想法:

• 如果您使用类点(而不是结构点),那么复制将少得多。

如果您的列表已经存在于内存中,我会将其就地排序,而不是制作一个副本—除非您需要再次取消排序,也就是说,在这种情况下,您必须权衡内存中有两个副本与从存储中再次加载它):

pointList.Sort((x,y) => y.Z.CompareTo(x.Z)); //this should sort it in desc. order

另外,不确定这会有多大帮助,但看起来你要浏览你的列表两次-一次找到截止值,一次选择它们。我想你这样做是因为你想让所有的关系通过,即使这意味着选择超过5%的点。但是,因为它们已经被分类了,所以你可以利用它们,在你完成后停止。

double cutoffValue = pointlist[(int) pointList.Length * (1 - N)].Z;
List<point> selectedPoints = pointlist.TakeWhile(p => p.Z >= cutoffValue)
                                      .ToList();

除非你的名单是 极其 在我看来,cpu时间很可能是性能瓶颈。是的,你的 OrderBy()

不使用列表 . 改用IEnumerable。你只是不打电话 .ToList() 在where查询的末尾。这将允许框架将所有内容组合到一个只在需要时运行的列表迭代中。它还可以提高内存使用率,因为它避免了一次将整个查询加载到内存中,而是根据需要推迟一次只加载一项。另外,使用 .Take() 而不是 .ElementAt()

double N = 0.05; // selecting only 5% of points
int count = (1-N) * pointList.Count;
var selectedPoints = pointList.OrderBy(p=>p.Z).Take(count);

另外,在三种情况下,内存使用可能会成为一个问题:

1. 你的收藏真的太多了,足以填满你的记忆。对于一个现代系统的简单点结构,我们讨论的是数百万项。这不太可能。如果您有这么大的系统,您的解决方案是使用关系数据库,这样可以相对有效地将这些项保存在磁盘上。
2. 您有一个中等大小的集合,但存在外部性能限制,例如需要与许多其他进程共享系统资源,就像您在asp.net网站中看到的那样。在这种情况下,答案是 1) 或 把工作转移到客户机上。

更新:

再读一遍你的问题,我发现你读的文件很大。在这种情况下 最好的 性能可以通过编写自己的代码来解析文件来获得。如果项目数存储在文件顶部附近,则可以执行以下操作 许多的 更好的方法是,即使您可以根据文件的大小估计记录的数量(可以肯定地猜得有点高,然后在完成后截断任何额外的记录),您也可以构建最终的集合作为您的读取。这将大大提高cpu性能和内存使用。

我会实现“半”快速排序。

在P中选择轴x。

如果N=| U |那么你就完了。

如果N<|U |然后用P:=U递归。

否则,您需要将一些项添加到U:recurse with N:=N-| U |,P:=L来添加其余的项。

如果你明智地选择了你的轴心点(例如,五个随机样本的中位数),那么这将在O(n logn)时间内运行。

嗯,再想一想,你也许可以完全避免创建新的集合,因为本质上你只是在寻找一种从原始集合中找到第n个最大项的方法。是的,我认为这会管用,所以建议2:

设M是A和Z的平均值(记住,我们这里只考虑Z坐标)。

数一数在[M,Z]范围内有多少项,称之为Q。

如果Q<那么P中第N个最大的项在[A,M]的某处。尝试M:=(A+M)/2。

如果N<那么P中第n个最大的项在[M,Z]的某个地方。尝试M:=(M+Z)/2。

现在遍历P,删除所有大于或等于M的项。

你好吗?

您可以使用以下内容:

pointList.Sort(); // Use you own compare here if needed

// Skip OrderBy because the list is sorted (and not copied)
double cutoffValue = pointList.ElementAt((int) pointList.Length * (1 - N)).Z; 

// Skip ToList to avoid another copy of the list
IEnumerable<Point> selectedPoints = pointList.Where(p => p.Z >= cutoffValue); 

如果你想要一小部分按某种标准排序的分数,你最好使用 Priority queue 数据结构;创建一个大小有限的队列(将大小设置为所需的元素数),然后只需扫描列表中插入的每个元素。扫描之后,你可以按顺序取出结果。
O(n log p) 而不是 O(n log n) 哪里 p

int resultSize = pointList.Count * (1-N);
FixedSizedPriorityQueue<Point> q =
  new FixedSizedPriorityQueue<Point>(resultSize, p => p.Z);
q.AddEach(pointList);
List<Point> selectedPoints = q.ToList();

现在您所要做的就是实现一个FixedSizedPriorityQueue,该队列一次添加一个元素,当最大的元素已满时丢弃它。

只是尝试了50000行,100次访问了其中的30%。我的绩效结果是:

2. 使用数据视图:0.01秒

试试看。

   [TestClass]
   public class UnitTest1 {
      class MyTable : TypedTableBase<MyRow> {
         public MyTable() {
            Columns.Add("Col1", typeof(int));
            Columns.Add("Col2", typeof(int));
         }

         protected override DataRow NewRowFromBuilder(DataRowBuilder builder) {
            return new MyRow(builder);
         }
      }

      class MyRow : DataRow {
         public MyRow(DataRowBuilder builder) : base(builder) {
         }

         public int Col1 { get { return (int)this["Col1"]; } }
         public int Col2 { get { return (int)this["Col2"]; } }
      }

      DataView _viewCol1Asc;
      DataView _viewCol2Desc;
      MyTable _table;
      int _countToTake;

      [TestMethod]
      public void MyTestMethod() {
         _table = new MyTable();


         int count = 50000;
         for (int i = 0; i < count; i++) {
            _table.Rows.Add(i, i);
         }

         _countToTake = _table.Rows.Count / 30;
         Console.WriteLine("SortWithLinq");
         RunTest(SortWithLinq);
         Console.WriteLine("Use DataViews");
         RunTest(UseSoredDataViews);
      }

      private void RunTest(Action method) {
         int iterations = 100;
         Stopwatch watch = Stopwatch.StartNew();
         for (int i = 0; i < iterations; i++) {
            method();
         }
         watch.Stop();
         Console.WriteLine("   {0}", watch.Elapsed);
      }

      private void UseSoredDataViews() {
         if (_viewCol1Asc == null) {
            _viewCol1Asc = new DataView(_table, null, "Col1 ASC", DataViewRowState.Unchanged);
            _viewCol2Desc = new DataView(_table, null, "Col2 DESC", DataViewRowState.Unchanged);
         }

         var rows = _viewCol1Asc.Cast<DataRowView>().Take(_countToTake).Select(vr => (MyRow)vr.Row);
         IterateRows(rows);
         rows = _viewCol2Desc.Cast<DataRowView>().Take(_countToTake).Select(vr => (MyRow)vr.Row);
         IterateRows(rows);
      }

      private void SortWithLinq() {
         var rows = _table.OrderBy(row => row.Col1).Take(_countToTake);
         IterateRows(rows);
         rows = _table.OrderByDescending(row => row.Col2).Take(_countToTake);
         IterateRows(rows);
      }

      private void IterateRows(IEnumerable<MyRow> rows) {
         foreach (var row in rows)
            if (row == null)
               throw new Exception("????");
      }
   }