Сортировка + объединение строк нескольких файлов по временной метке

Question

У меня есть несколько текстовых файлов, которые представляют записи журнала, которые мне нужно проанализировать позже. Каждый из файлов имеет размер до 1 МБ, и у меня есть приблизительно 10 файлов. Каждая строка имеет следующий формат:

Timestamp\tData

Я должен объединить все файлы и отсортировать записи по значению временной метки. Нет гарантии, что записи в 1 файле находятся в правильном хронологическом порядке.

Какой будет самый умный подход? Мой псевдо-код выглядит так:

List<FileEntry> oneBigList = new ArrayList<FileEntry>();
for each file {
  parse each line into an instance of FileEntry;
  add the instance to oneBigList;
}
Collections.sort(oneBigList according to FileEntry.getTimestamp());

Answer 1

Если вы не уверены, что ваша задача поместится в доступную память, вам лучше вставить строки после анализа в таблицу базы данных и попросить базу данных беспокоиться о том, как упорядочить данные (индекс в столбце отметки времени поможет : -)

Если вы уверены, что с памятью нет проблем, я бы использовал TreeMap, чтобы выполнить сортировку, пока добавляю в нее строки.

Убедитесь, что ваш класс FileEntry реализует hashCode(), equals() и Comparable в соответствии с вашим порядком сортировки.

Answer 2

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

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

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

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