有没有一种方法可以在不分配任何内存的情况下对数组进行排序? [英] Is there a way to sort arrays without allocating any memory?

问题描述

我需要非常频繁地对一个较大的集合(上百个/下千个项目)进行排序，即每帧以60 fps的速度(我使用Unity).计算每个项目的密钥速度很慢，因此需要对其进行缓存.

I need to sort a rather big collection (high hundreds/low thousands of items) very frequently, that is every frame at 60 fps (I'm using Unity). Computing the key for each item is sort of slow so it needs to be cached.

我尝试了各种方法:

• 具有IComparer的List.Sort()，每次都会计算密钥:超级慢
• SortedList:速度更快，但是生成GC分配(每帧30KB):为什么?他们的钥匙盒装了吗(我用了很长时间)?分配了键/值对吗?如果将long封装在一个类中，则GC减半，所以我的猜测是两者":1个分配给该对，一个分配给该键将值类型装箱...
• Array.Sort(keyArray，valueArray):太可怕了！慢&每帧产生256KB的GC！

很遗憾，因为SortedList似乎很适合这项工作，我是否缺少任何无GC的替代方案?

It's a shame because SortedList seemed perfect for the job, is there any GC-free alternative that I'm missing?

推荐答案

如果计算键太慢，则可以将 key 属性添加到项目类中，在进行排序之前先对其进行计算，然后再使用使用 IComparer 的第一种方法只是比较键.

If computing keys is so slow, you can add key property to your item class, calculate it before sorting, and then use your first method with IComparer simply comparing keys.

这篇关于有没有一种方法可以在不分配任何内存的情况下对数组进行排序?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！