[Python] コラッツ予想の計算を利用したデータ構造の比較

はじめに

コラッツ予想のテレビ番組を見てプログラムの教材に丁度良いと思ったので計算するプログラムを作ってみました。
証明ではありません。
工夫する事で速度向上が出来そうでしたのでいくつかのデータ構造を使って比較してみました。

公開当時は大分酷いコードを載せていましたが更新しました。

環境

環境

Windows 11 Pro
Python 3.11.4 (tags/v3.11.4:d2340ef, Jun  7 2023, 05:45:37) [MSC v.1934 64 bit (AMD64)]

コード

collatzConjecture.py

import sys
import argparse
import pickle
import timeit
import gc

import numpy as np

import Utility as U
import Decorator as D


class Collatz():

  def __init__(self, start, end):
    self.start = start
    self.end = end

  def isOk(self, n, done):
    return n <= done or n == 1

  def calc(self, n, doPrint=False):
    m = n - 1
    if doPrint:
      print(f"\ncalc : {n}", end="")
    while not self.isOk(n, m):
      q, r = divmod(n, 2)
      n = q if r == 0 else 3 * n + 1
      if doPrint:
        print(f" -> {n}", end="")
    if doPrint:
      print("")

  @D.printStartEndExecuteTime
  def search(self, doPrint=False):
    print(f"Collatz conjecture: {self.start} -> {self.end}")
    l = U.getDigits(self.end)
    for i in range(self.start, self.end + 1):
      print(f"\r\x1b[1M{i:0{l}}", end="")
      self.calc(i, doPrint)
    print(" done")

  def print(self):
    print(f"total size   : {sys.getsizeof(self)}")
    print()


class CollatzSet(Collatz):

  def __init__(self, start, end, name="dumpSet.dat", load=False):
    super().__init__(start, end)
    self.max = start - 1
    self.name = name
    self.checked = set()
    self.work = set()
    if load:
      self.load()

  def isOk(self, n):
    return n <= self.max or n in self.checked or n == 1

  def addWork(self, n):
    self.work.add(n)

  def calc(self, n, doPrint=False):
    m = n
    if doPrint:
      print(f"\ncalc : {m}", end="")
    while not self.isOk(m):
      q, r = divmod(m, 2)
      m = q if r == 0 else 3 * m + 1
      if m > n:
        self.addWork(m)
      if doPrint:
        print(f" -> {m}", end="")
    if doPrint:
      print(f"\n{sorted(self.work)}")
      print(f"{sorted(self.checked)}")

  def update(self, n):
    if n <= self.max:
      return
    self.max = n
    self.checked.difference_update([self.max])
    self.checked.update(self.work)
    self.work.clear()

  @D.printStartEndExecuteTime
  def search(self, doPrint=False):
    print(f"Collatz conjecture: {self.start} -> {self.end}")
    l = U.getDigits(self.end)
    for i in range(self.start, self.end + 1):
      print(f"\r\x1b[1M{i:0{l}}", end="")
      self.calc(i, doPrint)
      self.update(i)
    print(" done")
    self.dump()

  def print(self, printChecked=False):
    print(f"total size   : {sys.getsizeof(self)+sys.getsizeof(self.checked)}")
    print(f"checked len  : {len(self.checked)}")
    print(f"checked size : {sys.getsizeof(self.checked)}")
    if printChecked:
      print(sorted(self.checked))
    print()

  def dump(self):
    obj = {
      "max": self.max,
      "checked": self.checked,
    }
    with open(self.name, "bw") as file:
      pickle.dump(obj, file)

  def load(self):
    with open(self.name, "br") as file:
      obj = pickle.load(file)
    self.max = obj["max"]
    self.checked = obj["checked"]


class CollatzList(CollatzSet):

  def __init__(self, start, end, name="dumpList.dat", load=False):
    super().__init__(start, end, name, load)
    self.checked = []
    self.work = []
    if load:
      self.load()

  def addWork(self, n):
    self.work.append(n)

  def update(self, n):
    if n <= self.max:
      return
    self.max = n
    if len(self.work) > 0:
      work = [x for x in self.checked if x > self.max and x not in self.work]
      self.checked = work + self.work
      self.work.clear()


class CollatzNp(CollatzSet):

  def __init__(self, start, end, name="dumpNp.dat", load=False):
    super().__init__(start, end, name, load)
    self.checked = np.array([], np.int32)
    self.work = np.array([], np.int32)
    if load:
      self.load()

  def addWork(self, n):
    self.work = np.append(self.work, n)

  def update(self, n):
    if n <= self.max:
      return
    self.max = n
    if len(self.work) > 0:
      self.checked = np.union1d(self.checked[self.checked > self.max], self.work)
      self.work = np.array([], np.int32)


def argParser():
  parser = argparse.ArgumentParser()
  parser.add_argument("end", type=int, help="End value.")
  parser.add_argument("-s", "--start", type=int, default=1, help="Start value.")
  # parser.add_argument("-i", "--name", default="dump.dat", help="file name.")
  parser.add_argument("-l", "--load", action="store_true", help="load.")
  parser.add_argument("-p", "--print", action="store_true", help="print.")
  return parser.parse_args()


if __name__ == "__main__":
  args = argParser()

  clz = Collatz(args.start, args.end)
  clz.search(args.print)
  clz.print()

  clz = CollatzSet(args.start, args.end, load=args.load)
  clz.search(args.print)
  clz.print(False)

  clz = CollatzList(args.start, args.end, load=args.load)
  clz.search(args.print)
  clz.print(False)

  clz = CollatzNp(args.start, args.end, load=args.load)
  clz.search(args.print)
  clz.print(False)

Utility.py

def getDigits(number):
  return len(str(number))

Decorator.py

import time
import functools
import gc
import inspect

import TimeUtility as TU
import Utility as U

def printStartEndExecuteTime(func):

  @functools.wraps(func)
  def wrapper(*args, **kwargs):
    gc.collect()
    gc.disable()
    print(f"{TU.getNowTime()} - Start {func.__name__}")
    start = time.perf_counter()
    result = func(*args, **kwargs)
    end = time.perf_counter()
    diff = end - start
    print(f"{TU.getNowTime()} - End   {func.__name__} {TU.secToTime(diff)}({diff:.3f})")
    gc.enable()
    return result

  return wrapper

TimeUtility.py

import time
import datetime

# 現在時刻を取得
def getNowTime():
  return datetime.datetime.now().strftime('%H:%M:%S.%f')[:-3]
  # return time.strftime("%H:%M:%S")

実行結果例

計算過程を表示

> py .\collatzConjecture.py 10 -p
01:34:53.485 - Start search
Collatz: 1 -> 10
01
calc : 1
02
calc : 2 -> 1
03
calc : 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2
04
calc : 4 -> 2
05
calc : 5 -> 16 -> 8 -> 4
06
calc : 6 -> 3
07
calc : 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5
08
calc : 8 -> 4
09
calc : 9 -> 28 -> 14 -> 7
10
calc : 10 -> 5
 done
01:34:53.486 - End   search 00:00:00.002(0.002)
total size   : 56

01:34:53.491 - Start search
CollatzSet: 1 -> 10
01
calc : 1
[]
[]
02
calc : 2 -> 1
[]
[]
03
calc : 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2
[4, 5, 8, 10, 16]
[]
04
calc : 4
[]
[4, 5, 8, 10, 16]
05
calc : 5
[]
[5, 8, 10, 16]
06
calc : 6 -> 3
[]
[8, 10, 16]
07
calc : 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10
[10, 11, 13, 17, 20, 22, 26, 34, 40, 52]
[8, 10, 16]
08
calc : 8
[]
[8, 10, 11, 13, 16, 17, 20, 22, 26, 34, 40, 52]
09
calc : 9 -> 28 -> 14 -> 7
[14, 28]
[10, 11, 13, 16, 17, 20, 22, 26, 34, 40, 52]
10
calc : 10
[]
[10, 11, 13, 14, 16, 17, 20, 22, 26, 28, 34, 40, 52]
 done
01:34:53.494 - End   search 00:00:00.002(0.002)
total size   : 784
checked len  : 12
checked size : 728

01:34:53.499 - Start search
CollatzList: 1 -> 10
01
calc : 1
[]
[]
02
calc : 2 -> 1
[]
[]
03
calc : 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2
[4, 5, 8, 10, 16]
[]
04
calc : 4
[]
[4, 5, 8, 10, 16]
05
calc : 5
[]
[4, 5, 8, 10, 16]
06
calc : 6 -> 3
[]
[4, 5, 8, 10, 16]
07
calc : 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10
[10, 11, 13, 17, 20, 22, 26, 34, 40, 52]
[4, 5, 8, 10, 16]
08
calc : 8
[]
[8, 10, 11, 13, 16, 17, 20, 22, 26, 34, 40, 52]
09
calc : 9 -> 28 -> 14 -> 7
[14, 28]
[8, 10, 11, 13, 16, 17, 20, 22, 26, 34, 40, 52]
10
calc : 10
[]
[10, 11, 13, 14, 16, 17, 20, 22, 26, 28, 34, 40, 52]
 done
01:34:53.503 - End   search 00:00:00.003(0.003)
total size   : 216
checked len  : 13
checked size : 160

01:34:53.510 - Start search
CollatzNp: 1 -> 10
01
calc : 1
[]
[]
02
calc : 2 -> 1
[]
[]
03
calc : 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2
[4, 5, 8, 10, 16]
[]
04
calc : 4
[]
[4, 5, 8, 10, 16]
05
calc : 5
[]
[4, 5, 8, 10, 16]
06
calc : 6 -> 3
[]
[4, 5, 8, 10, 16]
07
calc : 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10
[10, 11, 13, 17, 20, 22, 26, 34, 40, 52]
[4, 5, 8, 10, 16]
08
calc : 8
[]
[8, 10, 11, 13, 16, 17, 20, 22, 26, 34, 40, 52]
09
calc : 9 -> 28 -> 14 -> 7
[14, 28]
[8, 10, 11, 13, 16, 17, 20, 22, 26, 34, 40, 52]
10
calc : 10
[]
[10, 11, 13, 14, 16, 17, 20, 22, 26, 28, 34, 40, 52]
 done
01:34:53.514 - End   search 00:00:00.004(0.004)
total size   : 220
checked len  : 13
checked size : 164

新規に100000まで計算した時の計算時間

> py .\collatzConjecture.py 100000
01:38:24.283 - Start search
Collatz: 1 -> 100000
100000 done
01:38:27.399 - End   search 00:00:03.116(3.116)
total size   : 56

01:38:27.405 - Start search
CollatzSet: 1 -> 100000
100000 done
01:38:30.729 - End   search 00:00:03.324(3.324)
total size   : 4194576
checked len  : 117212
checked size : 4194520

01:38:30.739 - Start search
CollatzList: 1 -> 100000
100000 done
01:42:42.961 - End   search 00:04:12.221(252.221)
total size   : 937816
checked len  : 117213
checked size : 937760

01:42:42.972 - Start search
CollatzNp: 1 -> 100000
100000 done
01:43:09.201 - End   search 00:00:26.229(26.229)
total size   : 469020
checked len  : 117213
checked size : 468964

100000まで計算した結果を使って200000まで計算した時の計算時間

> py .\collatzConjecture.py 200000 -l
01:48:33.760 - Start search
Collatz: 1 -> 200000
200000 done
01:48:39.990 - End   search 00:00:06.230(6.230)
total size   : 56

01:48:40.004 - Start search
CollatzSet: 1 -> 200000
200000 done
01:48:46.262 - End   search 00:00:06.258(6.258)
total size   : 8388880
checked len  : 233729
checked size : 8388824

01:48:46.280 - Start search
CollatzList: 1 -> 200000
200000 done
02:02:08.998 - End   search 00:13:22.719(802.719)
total size   : 1869976
checked len  : 233733
checked size : 1869920

02:02:09.014 - Start search
CollatzNp: 1 -> 200000
200000 done
02:03:53.356 - End   search 00:01:44.342(104.342)
total size   : 1870032
checked len  : 233733
checked size : 1869976

200000まで新規に計算した時の計算時間

> py .\collatzConjecture.py 200000
02:06:19.541 - Start search
Collatz: 1 -> 200000
200000 done
02:06:26.120 - End   search 00:00:06.579(6.579)
total size   : 56

02:06:26.126 - Start search
CollatzSet: 1 -> 200000
200000 done
02:06:33.188 - End   search 00:00:07.062(7.062)
total size   : 8388880
checked len  : 233729
checked size : 8388824

02:06:33.200 - Start search
CollatzList: 1 -> 200000
200000 done
02:25:20.663 - End   search 00:18:47.463(1127.463)
total size   : 1869976
checked len  : 233733
checked size : 1869920

02:25:20.676 - Start search
CollatzNp: 1 -> 200000
200000 done
02:27:27.919 - End   search 00:02:07.242(127.242)
total size   : 1870032
checked len  : 233733
checked size : 1869976

解説

コラッツ予想には、

• xが1になる場合、その計算過程で出現した値は全て1になる
• xまで証明した場合、計算過程でxより小さい数が出現したらその値は1になる

という性質があります。
そこでその判定をするために計算過程のデータを保存しています。

Collatz()は、単純に計算していくだけのクラスです。
計算自体が単純なので結局一番速いです。

CollatzSet()は、計算過程のデータをsetに保存して参照するクラスです。
データを検索・更新する処理が入ったために速度が少し悪化しています。
そして、メモリ使用量が跳ね上がってしまいます。

CollatzList()は、比較のために計算過程のデータをlistに保存するクラスです。
実行時間が遅すぎて役に立たちませんが、setよりメモリ使用量は抑えられます。

CollatzNp()は、NumPyのndarrayに保存するクラスです。
listと比べると、速度・メモリ使用量に大幅な改善が見られます。
ただ、setにも劣ってしまいます。

これらのプログラムの欠点は、

• xが1にならない場合の判定が無く無限ループに陥ってしまう

という事です。

もっとも、1にならない値を見つけられたらコラッツ予想を証明出来てしまうのですが。