- 2005-06-03 (Fri) 03:15
- プログラミング
ということで，横でゲームをしつつ冪を下位桁からの辞書順にソートするプログラムを組んでみた．冪をソートするときにはその桁数が大きすぎてメモリに載らないことが問題になる．そこで，基本的にメモリの節約をメインに考えて作成した．節約のための重要点は，冪をソートするといってもその全ての桁が必要ではなく，基本的には下位の桁の一部しか必要でないこと．そして，冪の下位桁は上位桁を計算しなくても正確に求められ，再計算も簡単であること．これらに基づき，最初は下位の一部を計算しておき，ソートのときに区別が付かなければより上位の桁まで再計算するようにした．
実際に計算してみると，２の冪の場合には冪が20000000になっても下位16桁だけでソートが完了．思いのほか下位桁がバラバラのようである．このときのメモリ使用量は 1G強．時間は... 分単位．それなりに動くプログラムが出来上がって満足．単位は去年とってしまったけど課題を提出しても良いかなぁ？
- Newer: AWK - はじめ