У меня есть несколько файлов, которые нужно сортировать в соответствии с идентификатором в начале каждой строки. Файлы составляют около 2-3 грамм.
Я попытался прочитать все данные в ArrayList и отсортировать их. Но памяти недостаточно, чтобы держать их всех. Это не работает.
Линии выглядят как
0052304 0000004000000000000000000000000000000041 John Teddy 000023 0022024 0000004000000000000000000000000000000041 George Clan 00013
Как я могу сортировать файлы?
Это не совсем проблема Java. Вам нужно изучить эффективный алгоритм сортировки данных, которые не полностью считываются в память. Несколько адаптаций к Merge-Sort могут достичь этого.
Взгляните на это: http://en.wikipedia.org/wiki/Merge_sort
и: http://en.wikipedia.org/wiki/External_sorting
В основном идея состоит в том, чтобы разбить файл на более мелкие части, отсортировать их (либо с помощью сортировки слияния, либо с помощью другого метода), а затем использовать Merge из merge-sort для создания нового, отсортированного файла.
Для этого вам нужна внешняя сортировка слияния. Здесь - это реализация Java, которая сортирует очень большие файлы.
Поскольку ваши записи уже находятся в текстовом формате с плоским файлом, вы можете подключить их к UNIX sort(1), например. sort -n -t' ' -k1,1 < input > output. Он автоматически разбивает данные и выполняет сортировку слияния с использованием доступной памяти и /tmp. Если вам нужно больше места, чем у вас есть доступная память, добавьте -T /tmpdir в команду.
Очень забавно, что все говорят вам загружать огромные библиотеки С# или Java или реализовывать слияние-сортировку самостоятельно, когда вы можете использовать инструмент, который доступен на каждой платформе и существует уже несколько десятилетий.
Вместо того, чтобы сразу загружать все данные в память, вы можете читать только ключи и индекс, где начинается линия (и, возможно, длина), например.
class Line {
int key, length;
long start;
}
Это будет использовать около 40 байт в строке.
После того как вы отсортировали этот массив, вы можете использовать RandomAccessFile для чтения строк в том порядке, в котором они появляются.
Примечание: поскольку вы будете случайно попадать на диск, вместо использования памяти это может быть очень медленным. Типичный диск занимает 8 мс для случайного доступа к данным, и если у вас 10 миллионов строк, это займет около одного дня. (Это самый худший случай). В памяти это займет около 10 секунд.
Вы можете использовать файл SQL Lite db, загружать данные в db, а затем разрешать сортировку и возвращать результаты для вас.
Преимущества: Не нужно беспокоиться о написании лучшего алгоритма сортировки.
Недостаток: вам потребуется дисковое пространство, медленная обработка.
https://sites.google.com/site/arjunwebworld/Home/programming/sorting-large-data-files
Что вам нужно сделать, так это объединить файлы через поток и обработать их отдельно. Затем вы можете объединить файлы вместе, поскольку они уже будут отсортированы, это похоже на то, как работает сортировка слияния.
Ответ на этот вопрос SO будет полезен: Поток больших файлов
Операционные системы поставляются с мощной утилитой сортировки файлов. Простая функция, вызывающая bash script, должна помочь.
public static void runScript(final Logger log, final String scriptFile) throws IOException, InterruptedException {
final String command = scriptFile;
if (!new File (command).exists() || !new File(command).canRead() || !new File(command).canExecute()) {
log.log(Level.SEVERE, "Cannot find or read " + command);
log.log(Level.WARNING, "Make sure the file is executable and you have permissions to execute it. Hint: use \"chmod +x filename\" to make it executable");
throw new IOException("Cannot find or read " + command);
}
final int returncode = Runtime.getRuntime().exec(new String[] {"bash", "-c", command}).waitFor();
if (returncode!=0) {
log.log(Level.SEVERE, "The script returned an Error with exit code: " + returncode);
throw new IOException();
}
}
Вам нужно выполнить внешний вид. Это своего рода ведущая идея Hadoop/MapReduce, так как она не учитывает распределенный кластер и работает на одном узле.
Для лучшей производительности вы должны использовать Hadoop/Spark.
Измените эти строки в соответствии с вашей системой. fpath - ваш один большой файл ввода (протестирован с 20 ГБ). shared путь - это где хранится журнал выполнения. fdir - это промежуточные файлы, которые будут сохранены и объединены. Измените эти пути в соответствии с вашим устройством.
public static final String fdir = "/tmp/";
public static final String shared = "/exports/home/schatterjee/cs553-pa2a/";
public static final String fPath = "/input/data-20GB.in";
public static final String opLog = shared+"Mysort20GB.log";
Затем запустите следующую программу. Ваш окончательный отсортированный файл будет создан с именем op401 в пути fdir. последняя строка Runtime.getRuntime().exec("valsort " + fdir + "op" + (treeHeight*100)+1 + " > " + opLog); проверяет, сортируется ли выход. Удалите эту строку, если у вас нет установленного valsort или входной файл не генерируется с помощью gensort (http://www.ordinal.com/gensort.html).
Также не забудьте изменить int totalLines = 200000000; к общим строкам в вашем файле. и количество потоков (int threadCount = 16) должно всегда быть в силе 2 и достаточно большим, чтобы количество (суммарный размер * 2/нет потока) количество данных могло находиться в памяти. Изменение счетчика потоков приведет к изменению имени конечного выходного файла. Как и для 16, это будет op401, для 32 будет op501, для 8 будет op301 и т.д.
Наслаждаться.
import java.io.*;
import java.nio.file.Files;
import java.nio.file.Paths;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.stream.Stream;
class SplitFile extends Thread {
String fileName;
int startLine, endLine;
SplitFile(String fileName, int startLine, int endLine) {
this.fileName = fileName;
this.startLine = startLine;
this.endLine = endLine;
}
public static void writeToFile(BufferedWriter writer, String line) {
try {
writer.write(line + "\r\n");
} catch (Exception e) {
throw new RuntimeException(e);
}
}
public void run() {
try {
BufferedWriter writer = Files.newBufferedWriter(Paths.get(fileName));
int totalLines = endLine + 1 - startLine;
Stream<String> chunks =
Files.lines(Paths.get(Mysort20GB.fPath))
.skip(startLine - 1)
.limit(totalLines)
.sorted(Comparator.naturalOrder());
chunks.forEach(line -> {
writeToFile(writer, line);
});
System.out.println(" Done Writing " + Thread.currentThread().getName());
writer.close();
} catch (Exception e) {
System.out.println(e);
}
}
}
class MergeFiles extends Thread {
String file1, file2, file3;
MergeFiles(String file1, String file2, String file3) {
this.file1 = file1;
this.file2 = file2;
this.file3 = file3;
}
public void run() {
try {
System.out.println(file1 + " Started Merging " + file2 );
FileReader fileReader1 = new FileReader(file1);
FileReader fileReader2 = new FileReader(file2);
FileWriter writer = new FileWriter(file3);
BufferedReader bufferedReader1 = new BufferedReader(fileReader1);
BufferedReader bufferedReader2 = new BufferedReader(fileReader2);
String line1 = bufferedReader1.readLine();
String line2 = bufferedReader2.readLine();
//Merge 2 files based on which string is greater.
while (line1 != null || line2 != null) {
if (line1 == null || (line2 != null && line1.compareTo(line2) > 0)) {
writer.write(line2 + "\r\n");
line2 = bufferedReader2.readLine();
} else {
writer.write(line1 + "\r\n");
line1 = bufferedReader1.readLine();
}
}
System.out.println(file1 + " Done Merging " + file2 );
new File(file1).delete();
new File(file2).delete();
writer.close();
} catch (Exception e) {
System.out.println(e);
}
}
}
public class Mysort20GB {
//public static final String fdir = "/Users/diesel/Desktop/";
public static final String fdir = "/tmp/";
public static final String shared = "/exports/home/schatterjee/cs553-pa2a/";
public static final String fPath = "/input/data-20GB.in";
public static final String opLog = shared+"Mysort20GB.log";
public static void main(String[] args) throws Exception{
long startTime = System.nanoTime();
int threadCount = 16; // Number of threads
int totalLines = 200000000;
int linesPerFile = totalLines / threadCount;
ArrayList<Thread> activeThreads = new ArrayList<Thread>();
for (int i = 1; i <= threadCount; i++) {
int startLine = i == 1 ? i : (i - 1) * linesPerFile + 1;
int endLine = i * linesPerFile;
SplitFile mapThreads = new SplitFile(fdir + "op" + i, startLine, endLine);
activeThreads.add(mapThreads);
mapThreads.start();
}
activeThreads.stream().forEach(t -> {
try {
t.join();
} catch (Exception e) {
}
});
int treeHeight = (int) (Math.log(threadCount) / Math.log(2));
for (int i = 0; i < treeHeight; i++) {
ArrayList<Thread> actvThreads = new ArrayList<Thread>();
for (int j = 1, itr = 1; j <= threadCount / (i + 1); j += 2, itr++) {
int offset = i * 100;
String tempFile1 = fdir + "op" + (j + offset);
String tempFile2 = fdir + "op" + ((j + 1) + offset);
String opFile = fdir + "op" + (itr + ((i + 1) * 100));
MergeFiles reduceThreads =
new MergeFiles(tempFile1,tempFile2,opFile);
actvThreads.add(reduceThreads);
reduceThreads.start();
}
actvThreads.stream().forEach(t -> {
try {
t.join();
} catch (Exception e) {
}
});
}
long endTime = System.nanoTime();
double timeTaken = (endTime - startTime)/1e9;
System.out.println(timeTaken);
BufferedWriter logFile = new BufferedWriter(new FileWriter(opLog, true));
logFile.write("Time Taken in seconds:" + timeTaken);
Runtime.getRuntime().exec("valsort " + fdir + "op" + (treeHeight*100)+1 + " > " + opLog);
logFile.close();
}
}