もちろん、32行は機能しませんでした。 235になりました。
しかし、結果は最初の投稿として十分に使用できるように思えました-厳密に判断しないでください;）
最初に、整数の配列を処理するトライアルバージョンを取得し、バイナリファイルに保存しました。 動作した後（ところで、p4-3.2では2.3秒）、アーキテクチャと型への緊密なバインドは正しい方法ではないように思われました。 結局のところ、コレクションがJavaで作成されて、あらゆるタイプのデータを処理できるのは何の理由もありませんでした。
2時間を費やした後、Comparable型を消化するかなりの労働者階級を得ました。
「それ」の構成：
テスト -ヘルスをチェックするためのクラス。 私はユニットテストを気にしませんでした。
FileSort-実際には、主な従業員、料理人、大工。
FileSortStorageObject-オブジェクトのリストを一時ファイルに保存するアシスタント。
FileSortStorage-ヘルパーインターフェイス。 実際、シリアル化（ObjectOutputStreamおよびObjectInputStream）はアルゴリズムの動作を遅くするため、希望する人は別の保存方法を実装できます。
仕組み：
大量のデータがあるため、それらを完全な配列として提示することは意味がありません。 イテレータを使用してそれらを操作できるように思えました。
1.イテレータを使用して、データの一部が読み取られ、メモリに収まります（レコード数が設定されます）。
2.読み取りブロックは、同じクイックソートでソートされます（メモリオーバーヘッドは大きくありません）。
3.次に、ソートされたブロックが一時ファイルに追加されます。
4.データがある限り、p1-3が繰り返されます
5.ここにはN個のファイルがあり、各ファイルにはソートされたデータのチャンクが含まれています。
6.既存のファイルを単にマージするイテレーターが作成されます。
マージ時には、個々のファイルから次のレコードを選択するイテレーターも使用します（何をすべきか、私は気に入っています）。 選択したレコードから、最小値が選択され、戻ります。 外部で発行されたレコードの代わりに、対応するファイルの次のオブジェクトがすぐに計算されます。
だから、ソース。 突然、誰かが遊んでみたい
メインクラス：
package ru.dchekmarev.test.FileSort;
import java.io.*;
import java.util.*;
/**
*
*/
public class FileSort<T extends Comparable<T>> implements Iterable<T> {
private int bufferSize = 10000;
private List<FileSortStorage> partFiles = new LinkedList<FileSortStorage>();
private Iterator<T> source;
private List<T> part = new LinkedList<T>();
/**
* ,
*/
public FileSort() {
}
/**
* -
*/
public FileSort(Iterator<T> newSource) {
setSource(newSource);
}
/**
* -
*/
public FileSort(Iterator<T> newSource, Integer newSize) {
this(newSource);
setBufferSize(newSize);
}
/**
*
*/
public void setBufferSize( int newSize) {
bufferSize = newSize;
}
/**
* ,
*/
public void setSource(Iterator<T> newSource) {
source = newSource;
try {
sortParts();
} catch (IOException e) {
throw new RuntimeException(e);
}
Collections.sort(part);
}
/**
*
*/
public Iterator<T> iterator() {
if (partFiles.size() == 0) {
// ,
return part.iterator();
}
return new Iterator<T>() {
Long t = 0L;
List<T> items = new ArrayList<T>();
List<Iterator<T>> iterators = new ArrayList<Iterator<T>>();
Integer minIdx = null ;
// ,
// ,
{
iterators.add(part.iterator());
for (FileSortStorage f : partFiles) {
iterators.add(f.iterator());
}
for (Iterator<T> item : iterators) {
if (item.hasNext()) {
items.add(item.next());
} else {
throw new RuntimeException( "failed to get first for iterator" );
}
}
}
/**
* ,
*/
public boolean hasNext() {
if (minIdx == null ) {
for ( int i = 0; i < items.size(); i++) {
if (items.get(i) != null &&
(minIdx == null ||
items.get(i).compareTo(items.get(minIdx)) < 0)) {
minIdx = i;
}
}
}
return minIdx != null ;
}
/**
* - ,
*
*/
public T next() {
T res = null ;
if (hasNext()) {
res = items.get(minIdx);
if (iterators.get(minIdx).hasNext()) {
items.set(minIdx, iterators.get(minIdx).next());
} else {
items.set(minIdx, null );
}
}
minIdx = null ;
return res;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
}
/**
*
*/
void sortParts() throws IOException {
while (source.hasNext()) {
part.add((T)source.next());
if (part.size() >= bufferSize && source.hasNext()) {
Collections.sort(part);
partFiles.add( new FileSortStorageObject(part));
part.clear();
}
}
}
}
ディスクに保存するためのインターフェース：
package ru.dchekmarev.test.FileSort;
import java.util.List;
import java.io.IOException;
public interface FileSortStorage<T> extends Iterable<T> {
public void setObjects(List<T> objects) throws IOException;
}
シリアル化されたオブジェクトをディスクに保存する実装：
package ru.dchekmarev.test.FileSort;
import java.io.*;
import java.util.*;
/**
*
*/
public class FileSortStorageObject<T> implements FileSortStorage<T> {
private final File file;
/**
* ,
*/
public FileSortStorageObject(List<T> objects) throws IOException {
file = File.createTempFile( "FileSort" , "dat" );
setObjects(objects);
}
/**
*
*/
public void setObjects(List<T> objects) throws IOException {
ObjectOutputStream wr = new ObjectOutputStream( new FileOutputStream(file));
for (T item : objects) {
wr.writeObject(item);
}
wr.close();
}
/**
* -
*/
public Iterator<T> iterator() {
try {
return new Iterator<T>() {
private ObjectInputStream fr =
new ObjectInputStream( new FileInputStream(file));
T obj;
public boolean hasNext() {
if (obj == null ) {
try {
obj = (T)fr.readObject();
} catch (ClassNotFoundException e) {
throw new RuntimeException(e);
} catch (IOException e) {
obj = null ;
}
}
return obj != null ;
}
public T next() {
hasNext();
T res = obj;
obj = null ;
return res;
}
public void remove() {
throw new UnsupportedOperationException();
}
};
} catch (IOException e) {
throw new RuntimeException(e);
}
}
/**
*
*/
protected void finalize() {
file.delete();
}
}
そして、テストクラスでは、常に視覚的な結果を確認する必要があります。
package ru.dchekmarev.test.FileSort;
import java.util.*;
public class Test {
public static void main(String[] args) {
System.out.println( "Test start" );
// -
FileSort<Double> sort = new FileSort<Double>(
// -
//
new Iterator<Double>() {
private int i = 0;
private Random rand = new Random();
public boolean hasNext() {
if (i >= 1000) {
System.out.println( "generator finish" );
}
return i < 1000;
}
public Double next() {
i++;
return rand.nextDouble();
}
public void remove() {
throw new UnsupportedOperationException();
}
});
int i = 0;
//
for (Double res : sort) {
if (++i % 10000 == 0) {
//
//
System.out.println(i);
}
System.out.println( " == " + res);
}
}
}
コード...はい、より良く書くことができます。
アルゴリズム...はい、確かに正しくありません。 しかし、それは動作します:)
私のオリジナル