1

在帮助学生上课时，我实施了双轴快速排序算法来准备课程并引起了兴趣。运行一些统计数据，然后解决最坏情况，然后再次运行 stats，再次解决下一个最坏情况，重复这个过程几次，得到的代码不超过 80 行简单直接的 Python 代码（有点少于弗拉基米尔的代码）。新颖的部分是如何结合一些非常简单但有效的后处理来构建 3 个分区。现在我需要一些关于如何正确测试和统计数据的帮助。

特别是关于如何计算交换：大多数交换只执行两个分配而不是三个。那么我必须将它们视为完全交换，还是仅将它们视为“2/3”交换是否公平？

将每个交换都计算为1，CninCn * N * log2(N)大约0.48在短列表（<100 个元素）和数百万0.55个元素的较长列表中。这只是Vladimir Yaroslavskiy计算的理论最小值。

相反，计算较轻的交换2/3，所需交换的数量几乎与任何列表大小相等，并且约为0.36(stdev around 0.015)。

对于200 万条记录的列表，Cn比较次数平均约为1.38（来自 2*N*ln(N)），而对于较短的列表（即1024 个元素）则更低，约为1.31.21

这是针对具有100% 唯一编号并使用 Python随机排序random.shuffle()的列表。

所以我的问题是：

这样计算较轻的掉期是否可以，结果是否确实有希望？

另外有趣的是：

  • 列表中的相等元素越多，排序越快。Cn是0.03和0.1分别用于交换和比较所有相等元素的200 万个列表。
  • Cn对于排序和反向排序的列表对于所有大小几乎都是相同的：对于交换（用 计数）0.3和比较。12/3

我将很快发布一个包含更多统计信息的列表，其中包括最大堆栈深度、除交换和比较之外的递归调用数。还有其他我应该计算的东西吗？

此外，是否有一些“标准”测试套件包含各种情况的文件（等于、部分排序等），可以用来测试排序算法，并使结果与其他排序算法具有可比性。

5 月 5 日添加：我改进了算法，特别是针对排序列表。这是每个运行 20 次的结果。这是好结果吗？

New statistics:
Random.shuffle(), unique number
  Length        Swaps/Nlog2(N)      Comparisons/Nlog2(N)   Maximum Stack/log2(N)
      16        0.367               0.922                  0.250
      64        0.360               1.072                  0.500
     256        0.342               1.122                  0.625
    1024        0.358               1.156                  0.800
    4096        0.359               1.199                  0.917
   16384        0.359               1.244                  1.071
   65536        0.360               1.244                  1.125
  262144        0.360               1.269                  1.167
 1048576        0.362               1.275                  1.200

Sorted, unique numbers
  Length        Swaps/Nlog2(N)      Comparisons/Nlog2(N)   Maximum Stack/log2(N)
      16        0.172               0.531                  0.250
      64        0.117               0.586                  0.333
     256        0.087               0.609                  0.375
    1024        0.075               0.740                  0.500
    4096        0.060               0.732                  0.500
   16384        0.051               0.726                  0.500
   65536        0.044               0.722                  0.500
  262144        0.041               0.781                  0.556
 1048576        0.036               0.774                  0.550
 2097152        0.035               0.780                  0.571

 Reversed order, unique numbers
   Length        Swaps/Nlog2(N)     Comparisons/Nlog2(N)   Maximum Stack/log2(N)
      16        0.344               0.828                  0.250
      64        0.279               0.812                  0.333
     256        0.234               0.788                  0.375
    1024        0.210               0.858                  0.500
    4096        0.190               0.865                  0.500
   16384        0.172               0.855                  0.500
   65536        0.158               0.846                  0.500
  262144        0.153               0.900                  0.556
 1048576        0.143               0.892                  0.550
 2097152        0.140               0.895                  0.571
4

1 回答 1

3

我选择计算对要排序的元素执行的分配，而不是“交换”。不计算索引的分配和比较。

我将 Vladimir Yaroslavskiy 包含在他的文档（最后更新时间：2009 年 9 月 22 日）中的代码转换为 Python，并以与我在自己的实现中相同的方式添加计数器。代码包含在最后。

欢迎任何意见。

这是结果，10 次运行的平均值。

标记的列VY是 Vladimir 实现的结果，标记的列JB是我自己的实现。

 Length        F  Function call  Assignements   Comparisons    Maximum Stack
 of list          per N          per N.log2(N)  per N.log2(N)  per log2(N)

Random.shuffle(), unique number
Version             VY     JB      VY     JB      VY     JB      VY     JB
      64        1  0.170  0.266   1.489  1.029   1.041  1.028   0.417  0.633
     256        1  0.171  0.270   1.463  1.016   1.066  1.138   0.575  0.812
    1024        1  0.167  0.275   1.451  1.046   1.089  1.165   0.690  1.010
    4096        1  0.164  0.273   1.436  1.069   1.119  1.189   0.800  1.075
   16384        1  0.166  0.273   1.444  1.077   1.117  1.270   0.843  1.221
   65536        1  0.166  0.273   1.440  1.108   1.126  1.258   0.919  1.281
  262144        1  0.166  0.273   1.423  1.102   1.134  1.278   0.950  1.306
 1048576        1  0.166  0.273   1.426  1.085   1.131  1.273   0.990  1.290

Sorted, unique numbers
Version             VY     JB      VY     JB      VY     JB      VY     JB
      64        1  0.203  0.203   1.036  0.349   0.643  0.586   0.333  0.333
     256        1  0.156  0.156   0.904  0.262   0.643  0.609   0.375  0.375
    1024        1  0.118  0.355   0.823  0.223   0.642  0.740   0.400  0.500
    4096        1  0.131  0.267   0.840  0.181   0.679  0.732   0.500  0.500
   16384        1  0.200  0.200   0.926  0.152   0.751  0.726   0.500  0.500
   65536        1  0.150  0.150   0.866  0.131   0.737  0.722   0.500  0.500
  262144        1  0.113  0.338   0.829  0.124   0.728  0.781   0.500  0.556
 1048576        1  0.147  0.253   0.853  0.108   0.750  0.774   0.550  0.550

Reversed order, unique numbers
Version             VY     JB      VY     JB      VY     JB      VY     JB
      64        1  0.203  0.203   1.320  0.836   0.841  0.802   0.333  0.333
     256        1  0.156  0.156   1.118  0.703   0.795  0.783   0.375  0.375
    1024        1  0.118  0.312   1.002  0.631   0.768  0.852   0.400  0.500
    4096        1  0.125  0.267   0.977  0.569   0.776  0.861   0.500  0.500
   16384        1  0.200  0.200   1.046  0.516   0.834  0.852   0.500  0.500
   65536        1  0.150  0.150   0.974  0.475   0.813  0.844   0.500  0.500
  262144        1  0.113  0.338   0.925  0.459   0.795  0.896   0.500  0.556
 1048576        1  0.145  0.253   0.938  0.430   0.811  0.890   0.550  0.550

Random, with increasing frequency of the numbers.
The last row is a list of the same number
Version             VY     JB      VY     JB      VY     JB      VY     JB
   65536        1  0.166  0.273   1.429  1.051   1.113  1.251   0.881  1.156
   65536        2  0.167  0.270   1.404  1.075   1.112  1.238   0.894  1.194
   65536        4  0.168  0.273   1.373  1.039   1.096  1.213   0.906  1.238
   65536        8  0.151  0.245   1.302  1.029   1.069  1.199   0.900  1.262
   65536       16  0.132  0.127   1.264  0.970   1.020  1.150   0.912  1.188
   65536       32  0.090  0.064   1.127  0.920   0.950  1.099   0.856  1.119
   65536       64  0.051  0.032   1.000  0.845   0.879  0.993   0.819  1.019
   65536      128  0.026  0.016   0.884  0.792   0.797  0.923   0.725  0.931
   65536      256  0.013  0.008   0.805  0.704   0.728  0.840   0.675  0.856
   65536      512  0.006  0.004   0.690  0.615   0.652  0.728   0.588  0.669
   65536     1024  0.003  0.002   0.635  0.557   0.579  0.654   0.519  0.625
   65536     2048  0.002  0.001   0.541  0.487   0.509  0.582   0.438  0.463
   65536     4096  0.001  0.000   0.459  0.417   0.434  0.471   0.369  0.394
   65536     8192  0.000  0.000   0.351  0.359   0.357  0.405   0.294  0.300
   65536    16384  0.000  0.000   0.247  0.297   0.253  0.314   0.206  0.194
   65536    32768  0.000  0.000   0.231  0.188   0.209  0.212   0.125  0.081
   65536    65536  0.000  0.000   0.063  0.125   0.063  0.125   0.062  0.000

这是 Vladimir 排序在 Python 中的代码：

DIST_SIZE = 13
TINY_SIZE = 17

def dualPivotQuicksort(a, left, right, nesting=0):
  global assignements, comparisons, oproepen, maxnesting
  oproepen += 1
  maxnesting = max(maxnesting, nesting)

  length = right - left
  if length < TINY_SIZE: # insertion sort on tiny array
    # note by JB: rewritten to minimize the assignements
    for i in xrange(left+1, right+1):
      key = a[i]
      assignements += 1

      while i > left:
        comparisons += 1
        if key < a[i - 1]:
          assignements += 1
          a[i] = a[i-1]
          i -= 1
        else:
          break

      assignements += 1
      a[i] = key

    return

  # median indexes
  sixth = length / 6
  m1 = left + sixth
  m2 = m1 + sixth
  m3 = m2 + sixth
  m4 = m3 + sixth
  m5 = m4 + sixth
  assignements += 9*3
  comparisons += 9
  ## 5-element sorting network
  if a[m1] > a[m2]: a[m1],a[m2] = a[m2],a[m1]
  if a[m4] > a[m5]: a[m4],a[m5] = a[m5],a[m4]
  if a[m1] > a[m3]: a[m1],a[m3] = a[m3],a[m1]
  if a[m2] > a[m3]: a[m2],a[m3] = a[m3],a[m2] 
  if a[m1] > a[m4]: a[m1],a[m4] = a[m4],a[m1] 
  if a[m3] > a[m4]: a[m3],a[m4] = a[m4],a[m3] 
  if a[m2] > a[m5]: a[m2],a[m5] = a[m5],a[m2] 
  if a[m2] > a[m3]: a[m2],a[m3] = a[m3],a[m2] 
  if a[m4] > a[m5]: a[m4],a[m5] = a[m5],a[m4]

  # pivots: [ < pivot1 | pivot1 <= && <= pivot2 | > pivot2 ]
  assignements += 2
  pivot1 = a[m2]
  pivot2 = a[m4]

  comparisons += 1
  diffPivots = pivot1 != pivot2

  assignements += 2
  a[m2] = a[left]
  a[m4] = a[right]

  # center part pointers
  less = left + 1
  great = right - 1

  # sorting
  if (diffPivots):
    k = less
    while k <= great:
      assignements += 1
      x = a[k]

      comparisons += 2
      if (x < pivot1):
        comparisons -= 1
        assignements += 2
        a[k] = a[less]
        a[less] = x
        less += 1

      elif (x > pivot2):
        while k < great:
          comparisons += 1
          if a[great] > pivot2:
            great -= 1
          else:
            break

        assignements += 3
        a[k] = a[great]
        a[great] = x
        great -= 1
        x = a[k]

        comparisons += 1
        if (x < pivot1):
          assignements += 2
          a[k] = a[less]
          a[less] = x
          less += 1

      k += 1

  else:
    k = less
    while k <= great:
      assignements += 1
      x = a[k]

      comparisons += 1
      if (x == pivot1):
        k += 1
        continue

      comparisons += 1
      if (x < pivot1):
        assignements += 2
        a[k] = a[less]
        a[less] = x
        less += 1

      else:
        while k < great:
          comparisons += 1
          if a[great] > pivot2:
            great -= 1
          else:
            break

        assignements += 3
        a[k] = a[great]
        a[great] = x
        great -= 1
        x = a[k]

        comparisons += 1
        if (x < pivot1):
          assignements += 2
          a[k] = a[less]
          a[less] = x
          less += 1

      k += 1

  # swap
  assignements += 2
  a[left] = a[less - 1]
  a[less - 1] = pivot1

  assignements += 2
  a[right] = a[great + 1]
  a[great + 1] = pivot2

  # left and right parts
  dualPivotQuicksort(a, left, less - 2, nesting+1)
  dualPivotQuicksort(a, great + 2, right, nesting+1)

  # equal elements
  if (great - less > length - DIST_SIZE and diffPivots):
    k = less
    while k <= great:
      assignements += 1
      x = a[k]

      comparisons += 2
      if (x == pivot1):
        comparisons -= 1
        assignements += 2
        a[k] = a[less]
        a[less] = x
        less += 1

      elif (x == pivot2):
        assignements += 3
        a[k] = a[great]
        a[great] = x
        great -= 1
        x = a[k]

        comparisons += 1
        if (x == pivot1):
          assignements += 2
          a[k] = a[less]
          a[less] = x
          less += 1

      k += 1

  # center part
  if (diffPivots):
      dualPivotQuicksort(a, less, great, nesting+1)

这段代码大约 190 行，我当前使用相同格式编写的实现大约 110 行。

所以欢迎大家发表意见。

于 2013-05-14T07:41:40.260 回答