循环创建双打并将其插入C中的排序数组中 [英] Loop that creates doubles and insert them into sorted array, in C
问题描述
假设我有一组排序的双打.
Suppose I have a set of sorted doubles.
{ 0.124, 4.567, 12.3 }
由代码的另一部分创建一个正的，非零的double，需要将其插入到此set中，同时保持其排序.例如，如果创建的double是7.56，则最终结果是
A positive, non-zero double is created by another part of the code, and needs to be inserted into this set while keeping it sorted. For example, if the created double is 7.56, the final result is,
{ 0.124, 4.567, 7.56, 12.3 }
在我的代码中，此创建双精度并插入排序集"过程将重复很多次.可能有50万到100万次.我不知道总共会确切创建多少个双打，但是我知道上限.
In my code, this "create double and insert in sorted set" process is then repeated a great number of times. Possibly 500k to 1 million times. I don't know how many doubles will be created in total exactly, but I know the upper bound.
尝试
我幼稚的第一种方法是创建一个数组，该数组的长度=上限，并用零填充，然后向其添加初始的双精度集("add" =用双精度值替换0值的条目).每当创建一个double时，我都会将其添加到数组中并进行插入排序，我读过此插入排序对排序有序数组很有用.
My naive first approach was to create an array with length = upper bound and fill it with zeros, then adding the initial set of doubles to it ("add" = replace a 0 valued entry with the double). Whenever a double is created, I add it to the array and do an insertion sort, which I read is good for sorting ordered arrays.
问题
我觉得运行500k到100万个插入插槽将是一个严重的性能问题. (或者我错了吗?)在C中是否有更有效的数据结构和/或算法?
I have a feeling running 500k to 1 million insertion slots will be a serious performance issue. (or am I wrong?) Is there a more efficient data structure and/or algorithm for doing this in C?
我要保持集合排序的原因是因为在每个创建双精度并插入排序集合中"过程之后，我需要能够查找该集合中的最小元素(并可能通过替换将其删除)与0).我认为最好的方法是保持集合排序.
The reason why I want to keep the set sorted is because after every "create double and insert in sorted set" process, I need to be able to look up the smallest element in that set (and possibly remove it by replacing it with a 0). I thought the best way to do this would be to keep the set sorted.
但是如果不是这样，也许还有其他选择吗?
But if that is not the case, perhaps there is an alternative?
推荐答案
Since all you want to do is pull out the minimum element in every iteration, use a min-heap instead. You can implement them to have O(1) insertion, O(1) find-min, and O(1) decrease-key operations (though note that removing the minimum element always takes O(log n) time). For what you are doing, a heap will be substantially faster.
这篇关于循环创建双打并将其插入C中的排序数组中的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
