Самый быстрый Java-способ удалить первую / верхнюю строку файла (например, стек)

Question

Я пытаюсь улучшить реализацию внешней сортировки в Java.

У меня есть куча объектов BufferedReader, открытых для временных файлов. Я неоднократно удаляю верхнюю строку из каждого из этих файлов. Это расширяет границы кучи Java. Я хотел бы более масштабируемый способ сделать это без потери скорости из-за большого количества вызовов конструктора.

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

Итак, используя библиотеки Java, это самый эффективный способ сделать это.

- Edit -

Для внешней сортировки обычным способом является разбиение большого файла на несколько файлов чанка. Сортировка каждого из кусков. А затем обработайте отсортированные файлы как буферы, извлеките верхний элемент из каждого файла, наименьший из всех - глобальный минимум. Затем продолжайте пока для всех предметов. http://en.wikipedia.org/wiki/External_sorting

Мои временные файлы (буферы) в основном являются объектами BufferedReader. Операции, выполняемые с этими файлами, аналогичны операциям со стеком / очередью (просмотр и всплывающее окно, не требуется push)

Я пытаюсь повысить эффективность этих операций. Это связано с тем, что использование множества объектов BufferedReader занимает слишком много места.

Answer 1

У меня есть куча объектов BufferedReader, открытых для временных файлов. Я неоднократно удаляю верхнюю строку из каждого из этих файлов. Это расширяет границы кучи Java.

Это действительно удивительное утверждение. Если вы не открываете тысячи файлов одновременно, это никак не отразится на куче. Размер буфера по умолчанию для BufferedReader составляет 8192 байта, и должно быть мало дополнительного места. 8192 * 1000 составляет всего ~ 8 Мбайт, и это мало по сравнению с использованием памяти типичным приложением Java.

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

(Или, может быть, ваше представление о том, что такое «слишком много места», нереально).

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

Нет сомнений, что это будет значительно медленнее! Просто не существует эффективного способа удалить первую строку из файла. Не на Java или на любом другом языке. Удаление символов из начала или середины файла влечет за собой копирование файла в новый, пропуская символы, которые необходимо удалить. Нет более быстрой альтернативы.

Answer 2

В данный момент я удален от своего компилятора, но я думаю, что это будет работать. Редактировать : отлично работает.

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

public class FileStack {
  private File file;
  private long position = 0;
  private String cache = null;

  public FileStack(File file) {
    this.file = file;
  }

  public String peek() throws IOException {
    if (cache != null) {
      return cache;
    }

    BufferedReader r = new BufferedReader(new FileReader(file));
    try {
      r.skip(position);
      cache = r.readLine();
      return cache;
    } finally {
      r.close();
    }
  }

  public String pop() throws IOException {
    String r = peek();
    if (r != null) {
      // if you have \r\n line endings, you may need +2 instead of +1
      // if lines could end either way, you'll need something more complicated
      position += r.length() + 1;
      cache = null;
    }
    return r;
  }
}

Answer 3

Если основное внимание уделяется пространству кучи, используйте [2-ю форму конструктора BufferedReader] [1] и укажите небольшой размер буфера.

[1]: http://java.sun.com/j2se/1.5.0/docs/api/java/io/BufferedReader.html#BufferedReader(java.io.Reader, int)