(cache) 100万個の整数のソート

○○だけど…

質問する

詳細検索

解決済みの質問

質問:No.3388055

▼

white-tiger

困ってます

お気に入り投稿に追加する (0人が追加しました)

回答数3

100万個の整数のソート

2491
482
112
..
1044

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

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

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

投稿日時 - 2007-09-29 23:41:35

通報する

ブックマーク▼

メールで紹介

質問者が選んだベストアンサー

回答:No.3

▼

kakusuke

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

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

２．すべてメモリに読み込み、
　　メモリ内でソートするやり方
・データ件数が多いときにメモリが圧迫される。
・メモリ上で操作するので速い。
※クイックソートと同等のスピードでメモリの肥大化を防ぐ、
コムソート（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-09-30 08:53:21

通報する

この回答を支持する

(現在0人が支持しています)

お礼

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

投稿日時 - 2007-10-19 23:44:51

この質問は役に立ちましたか？

0人が「このQ&Aが役に立った」と投票しています

別のキーワードで再検索する

詳細検索

ベストアンサー以外の回答

並び替え
新着順
支持数順

回答:No.2

▼

sakusaker7

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

http://sdc.sun.co.jp/java/docs/j2se/1.4/ja/docs/ja/api/java/util/Arrays.html#sort(int[])

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-09-30 01:37:52

通報する

この回答を支持する

(現在0人が支持しています)

お礼

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

投稿日時 - 2007-10-19 23:45:14

回答:No.1

▼

XkakizakiX

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

投稿日時 - 2007-09-29 23:51:49

通報する

この回答を支持する

(現在0人が支持しています)

お礼

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

投稿日時 - 2007-10-19 23:45:07

別のキーワードで探す

もっと聞いてみる

質問する

関連するQ&Aはこちら

javascritp「sort」メソッドについて