何时从无序列表切换到排序列表?[优化]

问题总是归结为哪个操作符最常见、访问或添加。 如果您有一个无序的列表,那么添加到其中不需要花费时间,并且访问特定的项目需要额外的时间。 如果您有一个已排序的列表,添加到其中需要更多的时间,但是访问它更快。

大多数应用程序花费大部分时间访问数据,而不是将其添加到数据中,这意味着创建排序列表的(运行)时间开销通常会被访问列表所节省的时间所平衡或覆盖。 如果您的数据中存在大量的混乱(听起来不像这样),那么维护一个排序列表并不一定是明智的,因为您将不断地将该列表作为相当大的CPU成本。

只有当数据结构的复杂性 不能 以有用的方式分类。如果它们能被分类,那么你就必须通过启发式的

访问次数:更改次数

以确定排序是否是一个好主意。

希米克,这听起来真的像是你想先做的事情,简单一点,然后看看它是如何表现的。任何类型的GPU体素化方法对于系统细节来说都是相当脆弱的,至少当你进入大容量(你似乎没有)。如果没有其他原因,我绝对希望首先简单地实现……。

在考虑了所有的答案之后,我发现,后来用来避免重复计算的方法,由于在数据结构中维护和导航的努力,效率会降低。此外,初始方法很容易与几个小内核例程并行,因此更适合于GPU实现。

回顾我最初的方法,我还发现了显著的优化机会,使体积削减方法远远落后。

因为我必须选择一个答案,所以我选择了Devinb,因为他回答了这个问题,但是西蒙的评论,在托比亚斯·沃尔的评论的支持下,对我来说同样有价值。

感谢你们帮助我解决这个问题。 堆栈溢出是一项令人印象深刻的服务。