100万個の整数のソート

2491
482
112
..
1044

のように、100万個の整数をテキストファイルから読み込んで、ソートするプログラムを作ることになりました。

これをjavaでやるのは現実的でしょうか？
（１日で終わる？）

java だと Arrays.sort というメソッドがあるとまでは聞いたのですが、個数が多くてもプログラムがちゃんと動くのか不安です。

No.3 ベストアンサー 回答者： kakusuke 回答日時： 2007/09/30 08:53

ファイルのソートの方法はとりあえず２種類あると思います。

１．ファイルから１件（行？）ずつ読み込みながら、別ファイルに書き込んでいくやり方
・データ件数が多いときにメモリの圧迫を防ぐ。
・ＨＤＤフル稼働になる。
※ＮＥＣソフトのソートマージツール（￥５０万）では、
１００バイト×１０００万行＝１３０秒で処理可能。

２．すべてメモリに読み込み、
　　メモリ内でソートするやり方
・データ件数が多いときにメモリが圧迫される。
・メモリ上で操作するので速い。
※クイックソートと同等のスピードでメモリの肥大化を防ぐ、
コムソート（combsort）というソートのやり方があります。

整数値の平均が６バイトとして、
６バイト×１００万件＝６Ｍバイト
まぁ大丈夫でしょう…。

ちなみにコムソートのロジックはこんな感じです。
　　public void ComSort(long[] data) {
　　　　double sf = 1.3;
　　　　long gap = data.length;
　　　　boolean flag = true;
　　　　int j = 0;
　　　　while (flag || (gap > 1)) {
　　　　　　gap = (long) Math.floor(gap / sf);
　　　　　　if (gap == 9 || gap == 10) gap = 11;
　　　　　　if (gap < 1)
　　　　　　　　gap = 1;
　　　　　　flag = true;
　　　　　　for (int i = 0; i < data.length - gap; i++) {
　　　　　　　　j = i + gap;
　　　　　　　　if (data[i] > data[j]) {
　　　　　　　　　　long buf;
　　　　　　　　　　buf = data[i];
　　　　　　　　　　data[i] = data[j];
　　　　　　　　　　data[j] = buf;

　　　　　　　　　　flag = false;
　　　　　　　　}
　　　　　　}
　　　　}
　　}

この回答へのお礼

ありがとうございました！

お礼日時：2007/10/19 23:44

No.2 回答者： sakusaker7 回答日時： 2007/09/30 01:37

ソート対象の数が多いときにどうなのかという質問だとして、

http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ …[])

public static void sort(int[] a)

指定された int 値の配列を数値の昇順でソートします。ソートアルゴリズムは調整されたクイックソートで、『Software-Practice and Experience, Vol. 23(11)』(1993 年 11 月) の 1249 ～ 1265 ページの Jon L. Bentley と M. Douglas McIlroy による「Engineering a Sort
Function」という記事から応用したものです。このアルゴリズムは、他のクイックソートアルゴリズムでは n の二乗のパフォーマンスに低下させる多くのデータセットにおいて、n*log(n) のパフォーマンスを提供します。

ということなので、アルゴリズム的な問題はないと思います。
とりあえず乱数で百万個の整数を生成してそれをソートするという
プログラムを組んで試してみましたが

>java SortArray
start :Sun Sep 30 01:28:29 JST 2007
finish :Sun Sep 30 01:28:32 JST 2007

>java SortArray
start :Sun Sep 30 01:32:31 JST 2007
finish :Sun Sep 30 01:32:31 JST 2007

>java SortArray
start :Sun Sep 30 01:32:33 JST 2007
finish :Sun Sep 30 01:32:33 JST 2007

>java SortArray
start :Sun Sep 30 01:32:42 JST 2007
finish :Sun Sep 30 01:32:43 JST 2007

>java SortArray
start :Sun Sep 30 01:32:48 JST 2007
finish :Sun Sep 30 01:32:48 JST 2007

それなりのマシンで動かすならそんなに心配する必要はないのでは?
ファイルの読み込みをするとそれで時間がかかることは明らかですが、
ざっと一行あたり10バイトとしてそれが百万行で一千万バイト。
ほぼ10メガバイトとみても一日仕事にはならないでしょう。

この回答へのお礼

ありがとうございました！

お礼日時：2007/10/19 23:45

No.1 回答者： XkakizakiX 回答日時： 2007/09/29 23:51

現実的とはどういう意味なのかが良くわかりませんが、

javaでそのようなプログラムを作ることは可能ですし、
経験者であればさほど時間も掛からないと思います。
未経験であっても、それなりにjavaを学習していれば問題ないレベルだと思います。
また、java以外でと考えているのであればCのほうがより機械語に近いので処理速度的には早いでしょう。
ただしCの場合は領域の確保をよりシビアにしないといけないかもしれません。
領域の確保を気にしないのであればC++のほうがクラスを使って楽に作れそうな気もします。

この回答へのお礼

ありがとうございました！

お礼日時：2007/10/19 23:45