R7RS で整数の分割を列挙する Jerome Kelleher 氏のアルゴリズムを実装した。これで R7RS でも高速に整数の分割を簡単に生成できるようになった。
Conversation
Notices
-
きゅーけー (tojoqk@mastodon.tojo.tokyo)'s status on Friday, 23-Aug-2024 01:36:22 JST きゅーけー -
きゅーけー (tojoqk@mastodon.tojo.tokyo)'s status on Friday, 23-Aug-2024 01:54:12 JST きゅーけー これは私が自力で解いた愚直な整数分割の列挙の実装。
再帰は専門知識ゼロでとりあえず動くアルゴリズムを実装できるという意味で強い。accel-asc は下記の画像の実装とは比較にならないレベルで速いのですごい。n が12くらいになると体感できるくらい差がひらく。
-
きゅーけー (tojoqk@mastodon.tojo.tokyo)'s status on Sunday, 25-Aug-2024 17:01:06 JST きゅーけー もう一回再帰で実装しなおしたら爆速になった。
max を cons するという発想が悪くて無駄な組み合わせを大量に計算していたっぽい。
なんでそんな発想をしてしまったんだろうか。もともと整数を分割しようとして作ったプログラムではなかったというのが大きい気がする。
改良版
-
きゅーけー (tojoqk@mastodon.tojo.tokyo)'s status on Sunday, 25-Aug-2024 17:14:53 JST きゅーけー まあ、一回まぬけな実装をしたおかげで accel_asc をしれたと思えばいいか。
-