Сортировка миллионов пар int/string с использованием Java

У меня есть 50 000 000 (целых, строковых) пар в текстовом файле. Целые числа представляют собой раз в миллисекундах, а также 13 цифр (например, 1337698339089).

Записи в текстовом файле выглядят следующим образом:

1337698339089|blaasdasd
1337698339089|asdasdas
1337698338089|kasda

Здесь могут быть одинаковые записи.

Я хочу сортировать записи в целых числах (в порядке возрастания), сохраняя любые повторяющиеся целые числа и сохраняя пары (целые, строковые). Подход, который я принял, приводит к ошибкам памяти, и поэтому я ищу альтернативные подходы.

Мой подход похож на этот (с использованием некоторого псевдокода):

// declare TreeMap to do the sorting
TreeMap<Double, String> sorted = new TreeMap<Double, String>();

// loop through entries in text file, and put each in the treemap:
for each entry (integer, string) in the text file:

   Random rand = new Random();
   double inc = 0.0;

   while (sorted.get(integer + inc) != null) {
       inc = rand.nextDouble();
   }

   sorted.put(integer + inc, string);

Я использую случайные числа здесь, чтобы гарантировать, что дублирующие целые числа могут быть введены в treemap (путем увеличения их на double от 0 до 1).

// to print the sorted entries:
for (Double d : sorted.KeySet()) {
    System.out.println(Math.round(d) + "|" + sorted.get(d));
}

Этот подход работает, но разбивается на 50 000 000 записей (я думаю, потому что treemap становится слишком большим или, возможно, потому, что цикл while работает слишком долго).

Я хотел бы знать, какой подход потребуют более опытные программисты.

Большое спасибо!

Ответы

Ответ 1

Вы должны иметь возможность сделать это со списком, если у вас достаточно памяти. Я бы создал отдельный класс для записи:

class Foo : Comparable<Foo> {
    private final long time;
    private final String text;

    // Constructor etc
}

С точки зрения памяти вы должны иметь возможность хранить 50 миллионов экземпляров и ссылаться на них. В 32-битной JVM это будет:

  • 8 байтов служебных данных для каждого объекта (IIRC)
  • 8 байтов для time
  • 4 байта для поля text
  • ~ 54 байта для строки (8-байтовые служебные + три int поля IIRC + char[] ссылка массива + ~ 32 байта для 10-символьного массива)
  • 4 байта для ссылки в массиве или ArrayList

Итак, примерно 80 байт на экземпляр - скажем, 100 для округления. Чтобы сохранить 50 000 000 из них, потребуется 5 000 000 000 байт, что на 5 ГБ, что больше, чем я считаю, что 32-разрядная JVM справится с этим.

Таким образом, чтобы сделать все это в памяти, вам понадобится 64-разрядная машина и 64-разрядная JVM, а затем накладные расходы потенциально несколько увеличиваются из-за больших ссылок и т.д. Возможно, но не очень приятно.

Большая часть этого из-за строк, однако. Если вы действительно хотите быть эффективными, вы можете создать гигантский массив char, а затем сохранить смещения в нем в пределах Foo. Прочитайте в массиве при чтении текстовых данных, а затем используйте его для записи данных после сортировки. Более сложный и уродливый, но значительно более эффективный с точки зрения памяти.

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

Ответ 2

Я мог бы использовать базу данных (например, H2, что удобно, так как вы можете перенести ее прямо в свой проект Java) и настроить индекс так, как вы этого хотите. Базы данных уже решили проблему обработки большого количества данных и ее организации. Затем вы можете выполнить SQL-запрос, чтобы получить результаты в порядке и записать их обратно.

Результирующий набор будет передавать данные вам в кусках; не пытайтесь загрузить все в один список.

Пока H2 поддерживает в памяти; Я бы настроил его на использование диска в этом случае, если у вас много ОЗУ и 64-битной Java.

Ответ 3

Зачем использовать double для хранения long?

A Map<Long, String> не может иметь дубликатов ключей. Один будет перезаписывать другой.

Я сомневаюсь, что вы можете вместить все это в память. Это 0,5 ГБ только для хранения длин, больше для строк. Вы, вероятно, не можете сделать это с 32-разрядной JVM.

Ответ 4

Вы дали JVM больше памяти? Попробуйте запустить его с помощью командной строки -Xmx1024M. И treeMap кажется излишне сложным, вы можете использовать встроенные команды Java

Ответ 5

Ваша проблема состоит из двух частей:

  • Алгоритм: Я бы рекомендовал использовать некоторые из алгоритмов сортировки java. Легко найти ссылки на google, такие как this.
  • JVM: Корень вашей проблемы звучит так, будто у вас может не хватить памяти, выделенной для вашей виртуальной машины Java. Я бы рекомендовал увеличить максимальный размер, так как вы имеете дело с количеством информации о спусках.

Аргументы JVM, которые вы ищете, должны быть:

  • -Xms указывает начальный размер кучи Java и

  • -Xmx максимальный размер кучи Java.

Ссылка: http://www.rgagnon.com/javadetails/java-0131.html

Ответ 6

Какова была ошибка? Можете ли вы успешно загрузить все данные в память? Я предлагаю вам попробовать класс Java Comparator. Возможно, я попробую что-то вроде создания пользовательского объекта для представления пары:

class Entry{
    long i;
    String s;
}

Затем создайте пользовательский Компаратор

class IComp implements Comparator<Entry>{
    public int compare(Entry e1, Entry e2){
      if(e1.i < e2.i) return -1;
      //complete the rest

    }
}

Затем поместите все объекты в запись Entry [] и создайте компаратор IComp icomp Используйте Arrays.sort(запись, icomp)

Поскольку вы будете создавать 50 миллионов объектов, вам необходимо обеспечить достаточное количество кучи.

Если у вас большое количество повторяющихся строк и если эти строки неизменяемы; вы можете создать набор для хранения строк и переработать их для создания объектов с более легким весом в вашей записи

Entry.s = set.get()...

Ответ 7

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

Ответ 8

Я не уверен, что вы собираетесь использовать все значения, когда закончите сортировку. Но число 50 миллионов дает мне подсказку о том, что вы можете просто взять верхние значения X после сортировки и сделать с ними что-то.

В этом случае: просто используйте кучу минут, каждый раз, когда вы сталкиваетесь с числом, большим, чем верхняя часть кучи, удалите min из кучи и добавьте новый номер. Таким образом, вам не нужно хранить все числа в памяти, только X из них.