Pythonのheapqにタプルは避けたいという話

# TL;DR
pythonのheapqにtupleはおそいので、ハッシュ化しましょう。

# 1. はじめに
はじめまして、snmsnbです。
先日、[ABC409](https://atcoder.jp/contests/abc409)に参加した際、heapqでのtupleの遅さを痛感したので備忘録として書いておきます。

# 2. 計測
ある数$N$を定めて、要素数が$N$に到達するまでheappushを行い、そこから$N$回だけ`pop`と`push`を繰り返す実験を10回行い平均と分散を取っています。

条件は
- tupleの要素数を2、３個にする場合
- heapqの要素が$10^4$、$10^5$、$10^6$にした場合

を組み合わせた12パターンで、atcoderのコードテストで計測しました。使用言語はpypyで、単位は秒です。

## 要素が２つの場合
| heapqの要素\heapqの要素数  | $10^4$ | $10^5$ | $10^6$ |
| - | - | - | - |
| (i, j) | ave:0.02027<br>var:0.06974 | ave:0.07533<br>var:0.17644 | ave:0.95970<br>var:0.58200 |
| i*(1 << 20) + j | ave:0.01627<br>var:0.06880 | ave:0.03958<br>var:0.09585 | ave:0.33724<br>var:0.22353 |
| 平均時間差 | 0.00400(-19.7%) | 0.03548(-47.1%) | 0.62246(-64.9%) |

要素数の増加に伴って、実行時間に対する影響が表れているのが分かります。

## 要素が３つの場合
| heapqの要素\heapqの要素数  | $10^4$ | $10^5$ | $10^6$ |
| - | - | - | - |
| (i, j, k) | ave:0.03369<br>var:0.09102 | ave:0.23662<br>var:0.20992 | ave:5.22803<br>var:2.06670 |
| i*(1 << 40) + j*(1 << 20) + k | ave:0.02335<br>var:0.08787 | ave:0.06169<br>var:0.17638 | ave:0.40682<br>var:0.33941 |
| 平均時間差 | 0.01034(-30.7%) | 0.17493(-73.9%) | 4.82121(-92.2%) |

:::note warn
(i, j, k)の $N=10^6$ のみ、手動集計です。
:::

要素数が２つの場合に比べて、速度の差がかなり顕著です。特に $N \ge 10^5$ では、オーダーのレベルで実行速度に差が出ています。

# 3. まとめ
heapqにタプルはおそいので、ハッシュ化したほうがよさそうです。

# 比較に使用したコード

<details><summary>(i, j)をあつかうheapq</summary>

```Python
import heapq
import random
import time
from math import sqrt

RANGE = 10**6

def rand():
    return random.randint(0, 100000)

h = []
for _ in range(RANGE):
    i, j = rand(), rand()
    heapq.heappush(h, (i, j))

def main():
    for _ in range(RANGE):
        heapq.heappop(h)
        i, j = rand(), rand()
        heapq.heappush(h, (i, j))

if __name__ == '__main__':
    res = []
    for _ in range(10):
        start = time.time()
        main()
        res.append(time.time() - start)
    ave = sum(res)/len(res)
    var = sqrt(sum((ele-ave)**2 for ele in res))
    print(f'ave:{ave:.5f}<br>var:{var:.5f}')
```
</details>

<details><summary>(i, j, k)をあつかうheapq</summary>

```Python
import heapq
import random
import time
from math import sqrt

RANGE = 10**6

def rand():
    return random.randint(0, 100000)

h = []
for _ in range(RANGE):
    i, j, k = rand(), rand(), rand()
    heapq.heappush(h, (i, j, k))

def main():
    for _ in range(RANGE):
        heapq.heappop(h)
        i, j, k = rand(), rand(), rand()
        heapq.heappush(h, (i, j, k))

if __name__ == '__main__':
    res = []
    for _ in range(10):
        start = time.time()
        main()
        res.append(time.time() - start)
    ave = sum(res)/len(res)
    var = sqrt(sum((ele-ave)**2 for ele in res))
    print(f'ave:{ave:.5f}<br>var:{var:.5f}')
```
</details>

<details><summary>i*(1 << 20) + jをあつかうheapq</summary>

```Python
import heapq
import random
import time
from math import sqrt

RANGE = 10**6

def rand():
    return random.randint(0, 100000)

def make_hash(i, j):
    return i * (1 << 20) + j

h = []
for _ in range(RANGE):
    i, j = rand(), rand()
    heapq.heappush(h, make_hash(i, j))

def main():
    for _ in range(RANGE):
        heapq.heappop(h)
        i, j = rand(), rand()
        heapq.heappush(h, make_hash(i, j))

if __name__ == '__main__':
    res = []
    for _ in range(10):
        start = time.time()
        main()
        res.append(time.time() - start)
    ave = sum(res)/len(res)
    var = sqrt(sum((ele-ave)**2 for ele in res))
    print(ave, var)
```
</details>

<details><summary>i*(1 << 40)+ j*(1 << 20) + kをあつかうheapq</summary>

```Python
import heapq
import random
import time
from math import sqrt

RANGE = 10**6

def rand():
    return random.randint(0, 100000)

def make_hash(i, j, k):
    return i * (1 << 40) + j * (1 << 20) + k

h = []
for _ in range(RANGE):
    i, j, k = rand(), rand(), rand()
    heapq.heappush(h, make_hash(i, j, k))

def main():
    for _ in range(RANGE):
        heapq.heappop(h)
        i, j, k = rand(), rand(), rand()
        heapq.heappush(h, make_hash(i, j, k))

if __name__ == '__main__':
    res = []
    for _ in range(10):
        start = time.time()
        main()
        res.append(time.time() - start)
    ave = sum(res)/len(res)
    var = sqrt(sum((ele-ave)**2 for ele in res))
    print(f'ave:{ave:.5f}<br>var:{var:.5f}')
```
</details>