algorithm - 統計をソートするためのスワップのカウント - 割り当てが 3 つではなく 2 つしかないスワップの場合

Question

学生の授業を手伝いながら、デュアルピボットクイックソートアルゴリズムを実装してセッションを準備し、興味をそそられました。いくつかの統計を実行し、次に最悪の状況を解決し、次に統計を再度実行し、次の最悪の状況を解決し、このプロセスを数回繰り返した後、結果のコードは 80 行以下の単純で直接的な Python コード (少しウラジミールのコードより少ない)。新しい部分は、3 つのパーティションが、非常にシンプルでありながら効果的な後処理と組み合わせて構築される方法です。ここで、統計を適切にテストして作成する方法について、いくつかの助けが必要です。

特にスワップの数え方について: ほとんどのスワップは 3 つではなく 2 つの割り当てしか実行しません。では、それらをフルスワップとしてカウントする必要がありますか、それとも「2/3」スワップとしてのみカウントするのが公平でしょうか?

すべてのスワップをとして数える1と、CninCn * N * log2(N)は0.48短いリスト ( <100 要素) と、数百万0.55要素の長いリストの周りにあります。これは、 Vladimir Yaroslavskiyによって計算された理論上の最小値です。

代わりに軽いスワップを数えると2/3、必要なスワップの数は、どのリストサイズでもほぼ等しく、およそ0.36(stdev around 0.015) です。

比較のCn数の平均は、 200 万1.3レコードのリストの場合で、これは理論上の 1.38 (2*N*ln(N) から) よりも小さく、短いリストの場合、つまり1024 要素の場合はそれよりも低くなります。1.21

これは、100% の一意の番号を持ち、Python のでランダムに並べられrandom.shuffle()たリスト用です。

だから私の質問は：

より軽いスワップをそのように数えても大丈夫ですか、そして結果は本当に有望ですか?

また、興味深いのは次のとおりです。

リスト内の要素が等しいほど、ソートは高速になります。Cnis0.03およびは、すべての等しい要素の200 万個のリストの0.1スワップと比較をそれぞれ表します。
Cnソートされたリストと逆順のソートされたリストは、すべてのサイズでほぼ同じです0.3。1スワップ（でカウント2/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

score 3 · Accepted Answer

「スワップ」ではなく、ソート対象の要素に対して実行された割り当てをカウントすることを選択しました。インデックスの割り当てと比較はカウントされません。

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

Python での Vladimirs ソートのコードは次のとおりです。

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 行です。

ですので、どんなご意見でも構いません。

algorithm - 統計をソートするためのスワップのカウント - 割り当てが 3 つではなく 2 つしかないスワップの場合

1 に答える 1

Related

Reference