提问人：Kalev Maricq 提问时间：7/26/2016 最后编辑：Kalev Maricq 更新时间：8/5/2016 访问量：140
生成数据的最有效排序算法
Most Efficient Sorting Algorithm for Generated Data
问：
我有以下公式：A=（x+x0）^.5 * （y+y0） * （z+z0）^.5
x0、y0 和 z0 对于给定的运行是常量，但可能会在程序运行之间更改。x、y 和 z 是为项目随机生成的，是 [0， 15] 中的统一整数。这意味着有 16^3=4096 种可能的组合。
我正在尝试找到最有效的方法来获取给定 A 值的百分位数（也将给出 x0、y0 和 z0）。我有两个问题：
- 有没有办法创建一个解析公式，直接求解百分位数，而不生成所有可能的 A 并对其进行排序？
- 如果没有，鉴于我有一些关于如何构建数据的信息，对这些数据进行排序的最有效方法是什么？
我有点假设#1的答案是“否”，但如果有人能想出一个分析解决方案，我会感到惊喜。继续#2，这是我目前的进度：
数据将通过 3 个嵌套循环生成：
For x = 0 to 15
For y = 0 to 15
For z = 0 to 15
array(n) = A(x,y,z)
n=n+1
Next z
Next y
Next x
关于这些数据，我们（至少）知道 3 件事：
- 数组（0） < 数组（1） < 数组（2）...
- 数组（0） < 数组（16） < 数组（32） ...
- 数组（0） < 数组（256） < 数组（512）...
到目前为止，我最有效的算法是以列表大小 16 开头的合并排序。但是，这忽略了上面的 2） 和 3）。
注意：我的问题是关于效率的。我有一个解决方案，虽然很慢，但很有效，所以我正在寻找最有效的方法。
编辑：这是我开始提出的一个解决方案，感觉它是最有效的，但它不起作用。我不确定它是否可以挽救。
将值放入三维数组 （x， y， z） 中。以 （0,0,0） 开头，这必须是最小值。下一个值必须是 （1,0,0）、（0,1,0） 或 （0,0,1）。测试和添加。假设它是 （1,0,0）。然后下一个值必须是 （2,0,0）、（0,1,0） 或 （0,0,1）。继续，直到在 O（n） 时间内添加所有值。
缺陷：可能性的数量并不总是限制在 3 个。我无法想出一种方法来告诉计算机哪些细胞是可能的，而不会扼杀效率的提高。也许有办法，但我只是没有想到。
编辑 2：我仍然对单调函数生成的值的最有效排序算法感兴趣，因为从理论上讲这是一个有趣的问题。然而，由于我首先询问是否有获得百分位数的捷径，因此我选择了非常简单的“计算小于 A 的数字”作为答案。
答：
1赞
wookie919
7/26/2016
#1
有趣的问题！
这里有一个想法，它可能是最有效的，也可能不是最有效的。
Initialize a min-heap with A(0, 0, 0)
numItems = 0
While True:
A(x, y, z) = pop minimum from heap
numItems = numItems + 1
If A(x, y, z) matches given A value:
break
else:
Add to heap A(x + 1, y, z)
Add to heap A(x, y + 1, z)
Add to heap A(x, y, z + 1)
请注意，您需要维护一组标志，以确保不会向堆中添加重复项。这可以及时完成，例如 何时添加到堆中。还有另一个小注意事项，即在添加到堆时执行一些边界检查。O(1)Flags[x][y][z] = TrueA(x,y,z)
流行最小值需要时间。添加到堆中需要时间。因此，最坏的情况时间复杂度仍然是 。O(logn)O(logn)O(nlogn)
优点是：
- 一旦找到给定的值，就可以停止。也就是说，你不需要计算所有可能的值，当然也不需要对它们进行排序。
AA - 如果给定的值很大，则可以使用最大堆。
A
评论
0赞
Kalev Maricq
7/27/2016
有趣的解决方案。我以前没有使用过堆。您能告诉我如何将项目添加到堆中并从中获取（我目前正在使用 VBA）吗？它只是一个集合，我将项目添加到其中，然后循环以找到这个最小值，还是我总是以有序的方式将项目添加到堆中，或者完全不同的东西？
0赞
wookie919
7/28/2016
@KalevMaricq这里：en.wikipedia.org/wiki/Heap_（data_structure） 还有这里：en.wikipedia.org/wiki/Binary_heap 总而言之，要从 min-heap 中获取最小值，您只需获取堆的根，然后花时间重新排列剩余的项目以再次形成一个合适的堆。若要将项目添加到堆中，请将它们添加到底部，然后再次花时间形成适当的堆。O(logn)O(logn)
2赞
rici
7/27/2016
#2
如果你只需要知道 A 在排序的可能性列表中的位置，那么实际上没有必要对可能性进行排序 （O（n log n））。计算小于或等于 A （O（n）） 的可能性数就足够了。
在这种情况下，如果函数是单调的，则可以进一步减少工作：给定一些确定的值 x' 和 z'，可以在 中求解 y'。然后您知道有 max（0， min（16， floor（y'） + 1）） 三元组 <x'， y， z'>其值小于或等于 A。A = f(x', y', z')
这个解决方案非常简单。鉴于
A=(y' + y0) * ((x'+x0) * (z'+z0))^.5
我们有
y' = A / ((x'+x0) * (z'+z0))^.5 - y0
Python（可被视为伪代码）：
def gmean(x, y):
return (x * y) ** 0.5
def count_le(A, x0, y0, z0):
count = 0
for x in range(16):
for z in range(16):
gm = gmean(x + x0, z + z0)
if gm == 0:
count += 16
else:
y = A / gm - y0
if y >= 0:
count += min(16, 1 + int(y))
return count
要将结果转换为百分位数，您必须将其乘以 100/4096。count_le
评论
<x0, y0, z0>