Disk-persisted-lazy-cacheable-List ™ в Scala - PullRequest
Новая
       3

Disk-persisted-lazy-cacheable-List ™ в Scala

15 голосов
/ 30 января 2012

Мне нужен очень и очень длинный список пар (X, Y) в Scala. Такой большой, что он не помещается в памяти (но хорошо помещается на диске).

  • Все операции обновления являются минусами (добавление заголовка).
  • Все обращения к чтению начинаются с головы и упорядоченно пересекают список, пока не найдет заранее определенную пару.
  • Кеш был бы хорош, так как большинство обращений к чтению будут хранить одни и те же данные снова и снова.

Итак, это в основном «диск-постоянный-ленивый-кешируемый список» ™

Любые идеи о том, как получить один, прежде чем я начну развертывать свои собственные?

Приложение: да .. mongodb или любой другой не встраиваемый ресурс является излишним. Если вас интересует конкретный вариант использования для этого, см. Класс Timeline здесь . По сути, у меня очень и очень большой график времени (миллионы пар за месяцы), хотя мои матчи должны касаться только последних часов.

Ответы [ 4 ]

4 голосов
/ 04 февраля 2012

Вы пишете:

mongodb или любой другой не встраиваемый ресурс является излишним

Знаете ли вы, что существуют механизмы встраиваемых баз данных, включая некоторые действительномаленькие?Если вы знаете, я не уверен в ваших точных требованиях и почему бы вам их не использовать.

Вы уверены, что Hibernate + встраиваемая БД (скажем, SQLite) будет недостаточно?В качестве альтернативы BerkeleyDB Java Edition , HSQLDB или других встроенных баз данных может быть вариантом.

Если вы не выполняете запросы к самому объекту (и это действительно звучиткак вы этого не делаете), возможно, сериализация будет проще, чем объектно-реляционное отображение для сложных объектов, но я никогда не пробовал, и я не знаю, что будет быстрее.Но сериализация, вероятно, является единственным способом быть полностью универсальным в типе, предполагая, что выбранная вами структура предлагает подходящий интерфейс для записи [T <: Serializable].Если нет, вы можете написать [T: MySerializable] после создания своего собственного «класса типов» MySerializable[T] (как, например, Ordering[T] в стандартной библиотеке Scala).

Однако вы не хотите использоватьстандартная Java-сериализация для этой задачи.«Все, что сериализуемо» звучит плохо, потому что для этого предлагается использовать сериализацию, но я думаю, вы можете смягчить это до «всего, что сериализуемо с моей предпочтительной платформой».Сериализация крайне неэффективна во времени и пространстве и не предназначена для сериализации одного объекта, вместо этого она возвращает файл, заполненный специальными заголовками.Я бы предложил использовать несколько другой механизм сериализации - посмотрите здесь для сравнения.

Дополнительные причины не , чтобы пойти по пути пользовательской реализации

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

Более того, как отметил Крис Шейн в комментарии выше, вам нужно будет использовать решение на основе страниц, и вы 'мне нужно справиться с объектами переменного размера.

4 голосов
/ 30 января 2012

Самый простой способ сделать что-то подобное - расширить Traversable. Вам нужно только определить foreach, и вы имеете полный контроль над обходом, так что вы можете делать такие вещи, как открывать и закрывать файл.

Вы также можете расширить Iterable, что требует определения iterator и, конечно, возврата какого-то Iterator. В этом случае вы, вероятно, создадите Iterator для данных на диске, но будет гораздо сложнее управлять такими вещами, как открытые файлы.

Вот один пример Traversable, такой как я описал, написанный Джошом Суеретом: 

class FileLinesTraversable(file: java.io.File) extends Traversable[String] {
  override def foreach[U](f: String => U): Unit = {
     val in = new java.io.BufferedReader(new java.io.FileReader(file))
     try {
       def loop(): Unit = in.readLine match {
          case null => ()
          case line => f(line); loop()
       }
       loop()
     } finally {
       in.close()
     }
  }
}
2 голосов
/ 08 февраля 2012

Если вы не хотите переходить на одну из встраиваемых БД, как насчет стека в файлах с отображением в памяти ?

  • Кажется, стек соответствует вашим желаемым характеристикам доступа. (Передать кучу данных и часто повторять самые последние переданные данные)
  • Вы можете использовать Java MappedByteBuffer напрямую из Scala. Вы получаете доступ к файлу как к его памяти, не пытаясь фактически загрузить файл в память.
  • Таким образом, вы получите бесплатное кеширование от ОС, поскольку отображенный файл будет работать как виртуальная память. Недавно написанные / доступные страницы будут оставаться в файловом кеше ОС, пока ОС не сочтет нужным сбросить их (или вы сбросили их вручную) обратно на диск
  • Вы можете создать свой стек с любого конца файла, если вы беспокоитесь о производительности последовательного чтения, но если вы обычно читаете только что записанные данные, я не ожидаю, что это будет проблемой, так как это все еще будет в памяти. (Хотя, если вы читаете данные, которые вы записывали в течение нескольких часов / дней на страницах, это может быть проблемой)
  • Размер файла, адресованного таким образом, ограничен 2 ГБ даже на 64-битной JVM, но вы можете использовать несколько файлов, чтобы обойти это ограничение.
2 голосов
/ 01 февраля 2012

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

http://code.google.com/p/vanilla-java/wiki/HugeCollections

...