为什么maxmin划分和征服实现比其他maxmin算法慢？

3 回答

• 1

  尽管分而治之的方法保证了最小的比较次数，但程序的实际复杂性取决于程序中执行的操作总数 .

  在您的情况下，您执行大约4或5次操作来进行大约n / 2次函数调用（函数调用的二叉树的叶节点），以及大约16次内部节点操作（计算所有赋值，算术运算，比较，和元组结构） . 总计约10n个操作总计 .

  在第一个程序中，操作总数基本上是2.x * n（其中x取决于执行的赋值数） .

  这与程序1中程序2中操作的相对简单性相结合，导致在两个程序中观察到因子5 .

  此外，分而治之算法的比较数应为3n / 2，而不是2n / 3 .

  回复于 2024-04-28T03:42:48+08:00
• 3

  事实证明，您的代码中似乎存在错误或分析中存在错误 - 但这并不重要 . 我会在最后得到它 .

  如果你看看你的结果，很明显两者之间的差异大约为5倍 . 这意味着第二个算法的复杂性并不比第一个算法复杂，它只是得到了一个更高的常数乘数 - 你做了相同数量的步骤，但每个步骤都要多得多 .

  ---

  这可能只是你测试这么窄范围的一个神器，只有10个因子 . 但运行你的测试有更广泛的值，如下所示：

  for i in 100, 1000, 10000, 100000, 1000000, 10000000:
      v = [random.random() for _ in range(i)]
      t1 = timeit.timeit(lambda: maxmin1(v), number=1)
      t2 = timeit.timeit(lambda: maxmin4(v, 0, len(v)), number=1)
      print('{:8}: {:.8f} {:.8f} (x{:.8f})'.format(i, t1, t2, t2/t1))
  

  ......你可以看到模式坚持：

  100: 0.00002003 0.00010014 (x5.00000000)
      1000: 0.00017500 0.00080800 (x4.61716621)
     10000: 0.00172400 0.00821304 (x4.76393307)
    100000: 0.01630187 0.08839488 (x5.42237660)
   1000000: 0.17010999 0.76053309 (x4.47083153)
  10000000: 1.77093697 8.32503319 (x4.70092010)
  

  ---

  那么，为什么第二个版本中更高的常量开销呢？好吧，第一个版本只是进行一个简单的 for 迭代，两个比较，以及每个元素的1个赋值 . 第二个是调用函数，构建和爆炸元组，进行更多的比较等等 . 这实际上慢了5倍（或者实际上，慢了15倍，如果你需要进行一些分析，或者至少查看字节码 . 但是我不值得这么做 .

  ---

  故事的寓意是有一个原因2（n-1）和2n / 3-2都是O（n）：当你有两个不同的复杂性类别，如O（n）和O（n ** 2），这对于大n来说总是有所不同;当你在同一个类中有两个算法时，实现中的常量（每个步骤的成本）很容易超过步数中的常量 .

  ---

  同时，我们如何验证2n / 3-2分析？简单，只需添加一个全局计数器，每次调用maxmin4时都会递增一次 . 以下是预期和实际结果：

  100:         65        127
      1000:        665       1023
     10000:       6665      11807
    100000:      66665     131071
   1000000:     666665    1048575
  10000000:    6666665   11611391
  

  但这只是意味着你做了大约2 / 3rds的步骤而不是大约1/3，所以每个步骤的不变成本是7.5倍而不是15倍 . 最后，这并不会真正影响分析 .

  回复于 2024-04-28T03:42:48+08:00
• 4

  我会非常惊讶地看到Python递归比Python迭代运行得更快 . 尝试maxmin的这个实现，一次取两个值 .

  def minmax(seq):
  
      def byTwos(seq):
          # yield values from sequence two at a time
          # if an odd number of values, just return
          # the last value twice (won't hurt minmax
          # evaluation)
          seq = iter(seq)
          while 1:
              last = next(seq)
              yield last,next(seq,last)
  
      seqByTwos = byTwos(seq)
      # initialize minval and maxval
      a,b = next(seqByTwos,(None,None))
      if a < b:
          minval,maxval = a,b
      else:
          minval,maxval = b,a
  
      # now walk the rest of the sequence
      for a,b in seqByTwos:
          if a < b:
              if a < minval:
                  minval = a
              if b > maxval:
                  maxval = b
          else:
              if b < minval:
                  minval = b
              if a > maxval:
                  maxval = a
      return minval, maxval
  

  如果要计算比较，则传递实现 __lt__ 和 __gt__ 的一系列对象，并使这些方法更新全局计数器 .

  回复于 2024-04-28T03:42:48+08:00