любая быстрая сортировка для огромного файла CSV

Question

Я ищу реализацию Java алгоритма сортировки. Файл может быть ОГРОМНЫМ, скажем, 20000 * 600 = 12 000 000 строк записей. Строка разделена запятой с 37 полями, и мы используем 5 полей в качестве ключей. Можно ли это быстро отсортировать, скажем, за 30 минут?

Если у вас есть другой подход, кроме java, приветствуется, если его можно легко интегрировать в систему java. Например, утилита unix.

Спасибо.

Редактировать: строки должны быть отсортированы по 600 файлам, по 20000 строк по 4 МБ для каждого файла. Наконец я хотел бы, чтобы они были 1 большим отсортированным файлом.

Я пытаюсь рассчитать время сортировки Unix, обновлю это потом.

Edit:

Я добавил все файлы в один большой и попробовал функцию сортировки Unix, это довольно хорошо. Время сортировки файла 2 ГБ составляет 12-13 минут. Действие добавления требует 4 минуты для 600 файлов.

sort -t ',' -k 1,1 -k 4,7 -k 23,23 -k 2,2r big.txt -o sorted.txt

Answer 1

Вызов Unix-программы сортировки должен быть эффективен .Это делает многократные проходы, чтобы гарантировать, что это не боров памяти.Вы можете разветвлять процесс с помощью Java Runtime, но выходные данные процесса перенаправляются, поэтому вам придется немного поработать с , чтобы перенаправление работало правильно :

public static void sortInUnix(File fileIn, File sortedFile)
        throws IOException, InterruptedException {
    String[] cmd = {
           "cmd", "/c", 
           // above should be changed to "sh", "-c" if on Unix system
           "sort " + fileIn.getAbsolutePath() + " > "
               + sortedFile.getAbsolutePath() };

    Process sortProcess = Runtime.getRuntime().exec(cmd);

    // capture error messages (if any)
    BufferedReader reader = new BufferedReader(new InputStreamReader(
        sortProcess.getErrorStream()));
    String outputS = reader.readLine();
    while (outputS != null) {
        System.err.println(outputS);
        outputS = reader.readLine();
    }

    sortProcess.waitFor();
}

Answer 2

Как данные попадают в формат CSV?Это происходит из реляционной базы данных?Вы можете сделать так, чтобы любой процесс, создавший файл, записывал свои записи в правильном порядке, поэтому вам не придется решать эту проблему в дальнейшем.

Если вы выполняете простой лексикографический порядок, вы можете попробоватьunix sort, но я не уверен, как это будет работать с файлом такого размера.

Answer 3

Используйте библиотеку Java big-sorter , которая публикуется в Maven Central и имеет необязательную зависимость от commons-csv для обработки CSV. Он обрабатывает файлы любого размера, разбивая их на промежуточные файлы, сортируя промежуточные файлы и объединяя их.

Вот пример:

Учитывая файл CSV ниже, мы будем сортировать по второму столбцу (столбец «число»):

name,number,cost
WIPER BLADE,35,12.55
ALLEN KEY 5MM,27,3.80

Serializer<CSVRecord> serializer = Serializer.csv(
  CSVFormat.DEFAULT
     .withFirstRecordAsHeader()
     .withRecordSeparator("\n"),
  StandardCharsets.UTF_8);
Comparator<CSVRecord> comparator = (x, y) -> {
    int a = Integer.parseInt(x.get("number"));
    int b = Integer.parseInt(y.get("number"));
    return Integer.compare(a, b);
};
Sorter 
  .serializer(serializer) 
  .comparator(comparator) 
  .input(inputFile) 
  .output(outputFile)
  .sort();

Результат:

name,number,cost
ALLEN KEY 5MM,27,3.80
WIPER BLADE,35,12.55

Я создал CSV-файл с 12 миллионами строк и 37 столбцами и заполнил сетку случайными целыми числами от 0 до 100 000. Затем я отсортировал файл объемом 2,7 ГБ в 11-м столбце, используя big-sorter , и потребовалось 8 минут , чтобы выполнить однопоточность на i7 с твердотельным накопителем и максимальной кучей, установленной на 512 м (-Xmx512m).

Подробнее см. Проект README .

Answer 4

Используйте Map / Reduce Hadoop, чтобы выполнить сортировку. Я рекомендую Spring Data Hadoop.Java.

Answer 5

Поскольку у вас есть 600 файлов меньшего размера, может быть быстрее отсортировать их все одновременно. Это съест 100% процессорного времени. В этом суть, верно?

waitlist= 
for f in ${SOURCE}/*
do 
    sort -t ',' -k 1,1 -k 4,7 -k 23,23 -k 2,2r -o ${f}.srt ${f} &
    waitlist="$waitlist $!"
done
wait $waitlist
LIST=`echo $SOURCE/*.srt`
sort --merge -t ',' -k 1,1 -k 4,7 -k 23,23 -k 2,2r -o sorted.txt ${LIST}

Это отсортирует 600 небольших файлов одновременно, а затем объединит отсортированные файлы. Это может быть быстрее, чем пытаться отсортировать один большой файл.

Answer 6

Вы действительно должны убедиться, что у вас есть правильные инструменты для работы. (Сегодня я надеюсь получить 3,8 ГГц ПК с 24 ГБ памяти для домашнего использования. Уже давно я купил себе новую игрушку.;)

Однако, если вы хотите отсортировать эти строки и у вас недостаточно аппаратного обеспечения, вам не нужно разбивать данные, потому что они уже в 600 файлах.

Сортируйте каждый файл по отдельности, затем выполните 600-кратную сортировку слиянием (вам нужно сохранить только 600 строк в памяти одновременно). Это не так просто, как делать их все сразу, но вы, вероятно, можете сделать это на мобильном телефоне. , ;)

Answer 7

Поскольку ваш набор данных огромен, как вы упомянули.Сортировка всего за один раз займет много времени в зависимости от вашей машины (если вы попробуете QuickSort).Но так как вы хотели бы, чтобы это было сделано в течение 30 минут.Я бы посоветовал вам взглянуть на Map Reduce, используя Apache Hadoop в качестве сервера приложений.

Пожалуйста, имейте в виду, что это не простой подход, но в долгосрочной перспективе вы можете легко масштабироватьв зависимости от вашего размера данных.Я также указываю вам на отличную ссылку на Настройка Hadoop

Пройдите через настройку одного узла и перейдите к кластеру Hadoop.Я был бы рад помочь вам, если вы застряли где-нибудь.

Answer 8

Вы не упоминаете платформу, поэтому трудно прийти к соглашению с указанным временем. 12x10 ^ 6 записей не так много, но сортировка довольно трудоемкая задача. Скажем, 37 полей, скажем, 100 байт / поле будет 45 ГБ? Это немного для большинства машин, но если записи в среднем составляют 10 байт / поле, ваш сервер должен уместить весь файл в ОЗУ, что было бы идеально.

Мое предложение: разбить файл на части, составляющие 1/2 доступной оперативной памяти, отсортировать каждый фрагмент, а затем объединить и отсортировать полученные отсортированные фрагменты. Это позволяет вам выполнять всю сортировку в памяти, а не нажимать своп, что, как я подозреваю, вызывает любое замедление.

Скажите (куски 1G, в каталоге, где вы можете поиграть):

split --line-bytes=1000000000 original_file chunk
for each in chunk* 
do
  sort $each > $each.sorted
done
sort -m chunk*.sorted > original_file.sorted

Answer 9

Ну, так как вы говорите о ОГРОМНЫХ наборах данных, это означает, что вам все равно понадобится какой-то внешний алгоритм сортировки. Есть некоторые для Java и почти любой другой язык - так как результат должен быть сохранен на диске в любом случае, какой язык вы используете, довольно неинтересно.

Answer 10

Python на большом сервере.

import csv
def sort_key( aRow ):
    return aRow['this'], aRow['that'], aRow['the other']
with open('some_file.csv','rb') as source:
   rdr= csv.DictReader( source )
   data = [ row for row in rdr ]
   data.sort( key=sort_key )
   fields= rdr.fieldnames
with open('some_file_sorted.csv', 'wb') as target:
   wtr= csv.DictWriter( target, fields }
   wtr.writerows( data )

Это должно быть достаточно быстро.И это очень гибко.

На небольшом компьютере разбейте его на три этапа: украсить, отсортировать, убрать с декорации

Украсить:

import csv
def sort_key( aRow ):
    return aRow['this'], aRow['that'], aRow['the other']
with open('some_file.csv','rb') as source:
   rdr= csv.DictReader( source )
   with open('temp.txt','w') as target:
       for row in rdr:
           target.write( "|".join( map(str,sort_key(row)) ) + "|" + row )

Часть 2 - операционная системасортировать используя "|"в качестве разделителя полей

Undecorate:

with open('sorted_temp.txt','r') as source:
   with open('sorted.csv','w') as target:
       for row in rdr:
           keys, _, data = row.rpartition('|')
           target.write( data )