java - Javaの大規模なデータセットでのファイルベースのマージソート

Question

メモリに収まらない大きなデータセットがある場合、Javaで並べ替えを実行するためのライブラリまたはAPIはありますか？実装はおそらくLinuxユーティリティの並べ替えに似ています。

Answer 1

Javaは、問題に対するより大きな解決策の一部として使用できる汎用のソートルーチンを提供します。大きすぎてすべてのメモリに収まらないデータを並べ替える一般的な方法は次のとおりです。

1）メインメモリに収まるだけのデータを読み取ります。たとえば、1Gbとしましょう。

2）その1 Gbのクイックソート（ここでは、CollectionsフレームワークからのJavaの組み込みソートを使用します）

3）ソートされた1Gbを「チャンク-1」としてディスクに書き込みます

4）すべてのデータを確認し、各データチャンクを個別のファイルに保存するまで、手順1〜3を繰り返します。したがって、元のデータが9 Gbだった場合、「チャンク-1」から「チャンク-9」のラベルが付いた9つのソートされたデータチャンクが作成されます。

5）9つのソートされたチャンクを単一の完全にソートされたデータセットにマージするには、最後のマージソートが必要です。マージソートは、これらの事前にソートされたチャンクに対して非常に効率的に機能します。基本的に、9つのファイルリーダー（チャンクごとに1つ）と1つのファイルライター（出力用）を開きます。次に、各読み取りファイルの最初のデータ要素を比較し、出力ファイルに書き込まれる最小値を選択します。その選択された値が由来するリーダーは次のデータ要素に進み、最小値を見つけるための9方向の比較プロセスが繰り返され、再び出力ファイルに回答が書き込まれます。このプロセスは、すべてのデータがすべてのチャンクファイルから読み取られるまで繰り返されます。

6）ステップ5で完了したすべてのデータの読み取りが完了すると、出力ファイルに完全に並べ替えられたデータセットが含まれるようになります。

このアプローチを使用すると、ファイル名とmaxMemoryパラメータを受け取り、一時ファイルを使用してファイルを効率的にソートする、独自の汎用「メガソート」ユーティリティを簡単に作成できます。このために少なくともいくつかの実装を見つけることができると思いますが、そうでない場合は、上記のように自分で実装することができます。

Answer 2

大規模なデータセットを処理する最も一般的な方法は、メモリ（最近は1 TBのサーバーを購入できます）またはデータベースです。

データベースを使用しない（またはメモリを追加購入する）場合は、自分で簡単にデータベースを作成できます。

Map-Reduce関数の実行に役立つライブラリがありますが、保存するよりも複雑になる可能性があります。