algorithm - 生成数据的最有效排序算法

Question

我有以下公式:A=(x+x0)^.5 * (y+y0) * (z+z0)^.5

x0、y0 和 z0 对于给定的运行是常量，但在程序的运行之间可能会发生变化。 x, y, z 是为一个项目随机生成的，并且是 [0, 15] 内的均匀整数。这意味着有 16^3=4096 种可能的组合。

我正在尝试找到最有效的方法来获取给定 A 值的百分位数(也将给出 x0、y0 和 z0)。我有两个问题:

1. 有没有一种方法可以创建一个分析公式来直接求解百分位数，而无需生成所有可能的 A 并对其进行排序？
2. 如果没有，考虑到我有一些关于数据结构的信息，对这些数据进行排序的最有效方法是什么？

我假设 #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 件事:

1. 数组(0)<数组(1)<数组(2)...
2. 数组(0) <数组(16) <数组(32) ...
3. 数组(0)<数组(256)<数组(512)...

到目前为止，我最好的工作算法是从列表大小 16 开始的合并排序。但是这忽略了上面的 2) 和 3)。

注意:我的问题是关于效率的。我有一个解决方案，速度很慢，但有效，所以我正在寻找的是最有效的方法。

编辑:这是我开始想出的一个解决方案，感觉它是最有效的，但它不起作用。不知道能不能挽回。

将您的值放入一个 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 的数字”作为答案。

Answer 1

如果您只需要知道 A 在已排序的可能性列表中的位置，那么实际上没有必要对这些可能性进行排序 (O(n log n))。计算小于或等于 A (O(n)) 的可能性数量就足够了。

在这种情况下，函数是单调的，您可以进一步减少工作量:给定一些确定的值 x' 和 z'，您可以求解 <A = f(x', y', z') 中的 em>y'。然后你知道有 ma​​x(0, min(16, floor(y') + 1) ) 三元组 <x', y, z'> 其值小于或等于 A。

这个解决方案非常简单。给定

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

要将 count_le 的结果转换为百分位数，您必须将它乘以 100/4096。