2006年4月20日の日記

NeoMuplに新たな問題ですよ。
まずソートプログラムがO(n²)の処理時間なので数が多くなるとソートが圧倒的に遅くなること。
予想はしていたんですが項目が数千個になるとかなり時間がかかりますよ。
そしてもう一つ、こっちのほうが深刻です。
リストのロードとセーブに時間がかかるんです。
計算したらやはりO(n²)の処理時間。
項目のソートに関してはクイックソートを使うことで、ロードとセーブについては読み込んだ結果の参照が遅いということがわかっているので読み込んだ時点で読み込み結果をソートして、ソートされていることを前提とした検索で目的のデータを探すことにすれば、いずれもO(nlogn)の処理時間に抑えることができそうです。