有没有办法在不分配任何内存的情况下对数组进行排序? [英] 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.

我尝试了各种方法:

• List.Sort() 和 IComparer，每次都计算key:超慢
• 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?

推荐答案

如果计算keys很慢，你可以将key属性添加到你的item类中，在排序之前计算它，然后使用你的使用 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屋！