生成数据的最高效排序算法

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，这是我目前的进展：

数据将通过三个嵌套循环生成：

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

我们至少知道这些数据的三个特点：

1.数组(0)<数组(1)<数组(2)...

2.数组(0)<数组(16)<数组(32)...

3.数组(0)<数组(256)<数组(512)...

迄今为止，我最好的工作算法是从列表大小16开始的归并排序。然而，它忽略了上述的第二和第三点。

注意：我的问题是关于效率的。我有一个解决方案，虽然速度慢，但可以工作，所以我要找的是最有效的方法。

编辑：这里是一个我开始想出来的解决方案，感觉它应该是最有效的，但它不起作用。我不确定它是否可以被挽救。

将您的值放入三维数组(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的数量”作为答案。

- Kalev Maricq

---

在计算百分位数时，您是根据当前生成的集合还是理论集合（当 n-->oo 时）进行计算？您是想要计算出 4096 种不同可能组合中的百分位数吗？ - Checkmate

x0、y0和z0是非负数吗？我从您提出的解决方案中推断是这样的。此外，公式中真的只有两个平方根吗？ - rici

另外，您只需要给定 <x0, y0, z0> 的单个 A 的百分位数，还是需要计算多个百分位数？ - rici

你的数组包含4,096个元素需要排序？那真是一个非常小的数组。你确定库提供的原地排序不够快吗？我怀疑排序数据所需的时间比生成数据少。 - Jim Mischel

你在这里尝试计算什么？“给定A值的百分位”是什么意思？你是想知道在给定x0、y0、z0的范围内，那个A值在4,096个结果中的位置吗？ - Jim Mischel

Answer 1

如果您只需要知道在可能性排序列表中A的位置，实际上无需对可能性进行排序（O(n log n)）。仅需计算小于或等于A的可能性的数量就足够了（O(n))。

在这种情况下，当函数是单调函数时，您甚至可以进一步减少工作量：给定一些确定的值x'和z'，您可以解出A = f(x', y', z')中的y'。然后您就知道有max(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。

- rici

Answer 2

有趣的问题！

这里有一个想法，可能不是最有效的。

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)的时间内完成，例如当将A(x,y,z)添加到堆中时，执行Flags[x][y][z] = True。还要在向堆中添加元素时执行一些边界检查。

弹出最小值需要O(logn)的时间。向堆中添加元素需要O(logn)的时间。因此，最坏情况下的时间复杂度仍然是O(nlogn)。

其优点包括：

• 当找到所需的A值时，可以立即停止计算。也就是说，您不需要计算所有可能的A值，而且肯定不需要对它们进行排序。
• 如果给定的A值很大，可以使用最大堆。

- wookie919

---

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Kalev Maricq

@KalevMaricq 在这里：https://en.wikipedia.org/wiki/Heap_(data_structure) 和 https://en.wikipedia.org/wiki/Binary_heap 中能够找到更多相关信息。简而言之，从最小堆中取出最小值，只需要取出堆的根节点，然后花费 O(logn) 的时间重新排列剩余项，以形成一个适当的堆即可。要向堆中添加一个项目，则应将其添加到底部，然后再花费 O(logn) 的时间来形成适当的堆。 - wookie919