(AoC Day 5) 使用二进制搜索解码字符串和二进制转换一样快？

Question

这个问题是关于 Day 5 problem for Advent of Code 2020 的（前半部分）的解决方案。

我写了两个不同的函数来得到相同的结果，即将登机牌字符串解码成行、列坐标。在第一种情况下，我根据字符串中的每个字符进行了二进制搜索：

def decode(bp):
  row = bp[:7]
  col = bp[-3:]
  row_lower, row_upper = 0, 127
  col_lower, col_upper = 0, 7
  for char in row:
      if char=='F':
          row_upper = ((row_upper+row_lower))//2
      else:
          row_lower = ((row_upper+row_lower)+1)//2
  for char in col:
      if char=='L':
          col_upper = ((col_upper+col_lower))//2
      else:
          col_lower = ((col_upper+col_lower)+1)//2
  sid = (row_lower*8)+col_lower
  return (row_lower, col_lower, sid)

然后我意识到，如果我们将字符串视为二进制数，则每行、列坐标都有一个 1:1 映射，因此我还写了这个问题的替代解决方案：

def alternative_decode(bp):
  bp = bp.replace('F', '0').replace('L', '0').replace('B', '1').replace('R', '1')
  return(int(bp[:7], 2), int(bp[-3:], 2), (int(bp[:7], 2)*8)+int(bp[-3:], 2))

我写了第二个解决方案，因为我希望它比第一个快得多，因为它是一个简单的二进制转换而不是二进制搜索。但是，在对这两种方法进行计时时，我注意到两者具有相同的运行时间，即大约在 0.0000020 和 0.0000025 秒之间。

这是什么原因？幕后是否发生了一些 Python 魔法使这两个解决方案同样高效，或者我是否以某种方式编写它们使它们同样低效？

Answer 1

在我的电脑上，如果您重复使用 row/col 结果，而不是重复 sid return:[=27= 的 int() 调用，您的替代方案会变得更快]

def alternative_decode_reuse(bp):
  bp = bp.replace('F', '0').replace('L', '0').replace('B', '1').replace('R', '1')
  row = int(bp[:7], 2)
  col = int(bp[-3:], 2)
  sid = row*8 + col
  return (row, col, sid)

将所有三个函数放入一个文件 decoding.py 后，我们得到：

tmp$ python -m timeit -s 'import decoding' -- 'decoding.decode("FFBBFBFLLR")'
1000000 loops, best of 3: 1.75 usec per loop
tmp$ python -m timeit -s 'import decoding' -- 'decoding.alternative_decode("FFBBFBFLLR")'
1000000 loops, best of 3: 1.62 usec per loop
tmp$ python -m timeit -s 'import decoding' -- 'decoding.alternative_decode_reuse("FFBBFBFLLR")'
1000000 loops, best of 3: 1.32 usec per loop

此时，大部分时间都花在了 replace() 行上。那如果我们不这样做呢？

def third_decode(bp):
    row = 0
    for c in bp[:7]:
        row <<= 1
        if c == 'B':
            row += 1
    col = 0
    for c in bp[7:]:
        col <<= 1
        if c == 'R':
            col += 1
    sid = row * 8 + col
    return (row, col, sid)

这给出：

tmp$ python -m timeit -s 'import decoding' -- 'decoding.third_decode("FFBBFBFLLR")'
1000000 loops, best of 3: 1.37 usec per loop

稍微差一点，或者至少没有明显好转。如果我们还使用所需的 sid 等价于 row/col 数字的（二进制）连接这一事实呢？

def fourth_decode(bp):
    sid = 0
    for c in bp:
        sid <<= 1
        if c in 'BR':
            sid += 1
    row = sid >> 3
    col = sid & 7
    return (row, col, sid)

是的，这有点帮助：

tmp$ python -m timeit -s 'import decoding' -- 'decoding.fourth_decode("FFBBFBFLLR")'
1000000 loops, best of 3: 1.16 usec per loop

在这一点上，我厌倦了编辑 cmdline args 以重新运行一切，所以让我们将其添加到 decoding.py 的底部：

if __name__ == '__main__':
    loops = 1000000
    funcs = (
            decode, alternative_decode, alternative_decode_reuse, replace_only,
            third_decode, fourth_decode,
    )
    from timeit import Timer
    for fun in funcs:
        cmd = 'decoding.%s("FFBBFBFLLR")' % fun.__name__
        timer = Timer(cmd, setup='import decoding')
        totaltime = min(timer.repeat(5, loops))
        fmt = '%25s returned %14r -- %8d loops, best of 5: %6d ns per loop'
        arg = (fun.__name__, fun('FFBBFBFLLR'), loops, totaltime*1000000000/loops)
        print(fmt % arg)

这让我们运行可以轻松实现所有功能：

tmp$ python decoding.py
                   decode returned   (26, 1, 209) --  1000000 loops, best of 5:   2090 ns per loop
       alternative_decode returned   (26, 1, 209) --  1000000 loops, best of 5:   1829 ns per loop
 alternative_decode_reuse returned   (26, 1, 209) --  1000000 loops, best of 5:   1414 ns per loop
             replace_only returned           None --  1000000 loops, best of 5:    700 ns per loop
             third_decode returned   (26, 1, 209) --  1000000 loops, best of 5:   1368 ns per loop
            fourth_decode returned   (26, 1, 209) --  1000000 loops, best of 5:   1123 ns per loop

在那之后，我不知道如何让它运行得更快。但是去年，一个代码求解熟人的到来告诉我他正在使用 pypy Python 实现来提高速度。也许它可以帮助？

tmp$ pypy decoding.py
                   decode returned   (26, 1, 209) --  1000000 loops, best of 5:    151 ns per loop
       alternative_decode returned   (26, 1, 209) --  1000000 loops, best of 5:      4 ns per loop
 alternative_decode_reuse returned   (26, 1, 209) --  1000000 loops, best of 5:      3 ns per loop
             replace_only returned           None --  1000000 loops, best of 5:      3 ns per loop
             third_decode returned   (26, 1, 209) --  1000000 loops, best of 5:    141 ns per loop
            fourth_decode returned   (26, 1, 209) --  1000000 loops, best of 5:    138 ns per loop

好吧，我所有的努力都白费了！ :)

看起来 pypy 的 replace() 和 int() 函数要快得多。此外，虽然它的 JIT 确实使我们的各种循环函数更快，但尽可能使用内置函数仍然更可取。

(AoC Day 5) 使用二进制搜索解码字符串和二进制转换一样快？

(AoC Day 5) Decoding the string using binary search is as fast as binary conversion?

python

binary

optimization

performance

binary-search