В своей прошлой «математической» статье я пообещал привести пример реализации того, что, казалось бы, и без нас уже реализовано :). Это будет не совсем игрушечный пример, я взял его из своего реального опыта, адаптировав для статьи. Речь пойдет о том, как реализовать собственную структуру данных, причем не простую, а вероятностную. Постараюсь описать все просто и понятно, не забыв при этом оставить задел для усложнения и модернизации.

 

Введение

Трудно найти то, что до нас уже не было написано на языке Java. А вот сама джава была написана сравнительно давно, в те времена, когда два гигабайта считались весьма солидным размером (здесь была бы уместна старая цитата Билла Гейтса про «достаточно каждому» :)). Поэтому адресация массивов, а также всех адресуемых коллекций в Java позволяет обращаться только примерно к 2 миллиардам элементов. Теперь представим, что тебе нужно сделать массив из 10 миллиардов элементов… В моем же случае все выглядело еще хуже, мне была нужна вероятностная структура данных с long-адресацией. Здесь я постараюсь «крупными мазками» воспроизвести всю задачу целиком, в результате мы создадим библиотеку для работы с коллекциями, где индексы могут быть больше, чем int.

 

Фильтр Блума

Поставим задачу так: нам нужна структура, называемая фильтром Блума. Она представляет собой битовый сет, с помощью которого можно определить, принадлежит ли элемент заданному множеству или нет, не сохраняя сам элемент, а устанавливая лишь небольшое количество битов в этом сете. Конечно, при такой постановке задачи мы теряем данные, но зато в случае, если данного элемента в этом множестве нет, то мы знаем это точно, что позволяет нам здорово сэкономить на сравнении, обращении к диску и прочем. Формализуем задачу так: нам нужно сделать класс с методом для добавления объекта и для проверки того, есть ли он там:

public class LBloomFilter {
  public void addBytes(byte[] bytes) {
    ...
  }

  public boolean containsBytes(byte[] bytes) {
    ...
  }
}

Первый вопрос, который возникает: почему массив байтов? Для ответа на него начнем с самого начала — постараемся понять, как это вообще работает.

В основе алгоритма добавления и проверки в фильтре Блума лежит хеширование. Все алгоритмы хеширования работают с массивами байтов, а то, как эти массивы были получены из реальных объектов, — совершенно другой вопрос, который известен как сериализация. Есть соблазн просто сериализовать объект в ByteArrayOutputStream, но я бы так делать не стал: упаковать объект не получится, если какая-то из его частей не сериализуется, а такое встречается очень часто. Поэтому если очень хочется, то можно сделать какой-нибудь специальный интерфейс:

public interface LPackable {
  byte[] pack();
}

Тогда код с дженериками будет выглядеть примерно так:

public class LGenericBloomFilter<T extends LPackable> extends LBloomFilter {
  public void add(T obj) {
    addBytes(obj.pack());
  }

  public boolean contains(T obj) {
    return containsBytes(obj.pack());
  }
}

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

Вроде все просто, мы вернемся к деталям реализации чуть позже, а сейчас попробуем разобраться, что именно для реализации вообще нужно. Для начала сообразим, зачем нам большой битовый сет.

Если мы хотим использовать фильтр Блума для большого количества объектов (десятки миллиардов), то нам нужно много битов для того, чтобы обеспечить подходящую точность. Таким образом, мы сталкиваемся со следующей проблемой: в нашем распоряжении есть старый добрый java.util.BitSet, но, как и у всех Java-коллекций, индексирование у него int:

public void set(int bitIndex) ...

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

Начнем с реализации массивов большей длины. Строго говоря, если бы даже в Java существовала адресация с помощью long, то я все равно не стал бы выделять 16 Гбайт одним непрерывным куском, просто потому, что память может быть фрагментирована и такого большого свободного куска там может и не быть. Это наводит на мысль, что то, что мы сейчас напишем, актуально и для повседневных задач. Мы реализуем наши массивы как массивы массивов, то есть как набор кусков, и для каждого индекса мы будем вычислять индекс куска и индекс элемента в куске. Держим в голове, что нам нужен эффективный битовый сет, а это значит, что массив у нас будет из long:

public class LLongArray {
  private long[][] chunks;
  private static final long serialVersionUID = 1L;

  public LLongArray(long length, int chunkSizeLog2) {
    super(length, chunkSizeLog2);

    chunks = new long[numChunks][];
    for (int i = 0; i < numChunks; i++)
      chunks[i] = new long[chunkSize];
  }

  public long get(long index) {
    LInt2 a = address(index);
    return chunks[a._1][a._2];
  }

  public void set(long index, long value) {
    LInt2 a = address(index);
    chunks[a._1][a._2] = value;
  }

  LInt2 address(long index) {
    // (index / chunkSize, index % chunkSize)
    return new LInt2((int) (index >> chunkSizeLog2), (int) (index & (chunkSize - 1)));
  }
}

Здесь LInt2 — это класс для пары элементов типа int:

public class LInt2 {
  public final int _1, _2;

  public LInt2(int _1, int _2) {
    this._1 = _1;
    this._2 = _2;
  }
}

Для удобства размер куска будем задавать степенью двойки, это позволит улучшить производительность, заменив деление сдвигом вправо, а вычисление остатка — двоичным И.

Если мы хотим реализовать не только массив типа long, но и другие, то имеет смысл выделить метод address() в отдельный класс LArray и наследовать уже от него, так как правила адресации будут одинаковы. Такой подход к адресации вообще позволяет нам сделать много интересного: к примеру, если мы хотим иметь массив изменяемой длины, то нам всего лишь нужно использовать что-нибудь вроде ArrayList<long[]>() для chunks вместо long[], тогда мы сможем спокойно добавлять куски к нашему массиву.

Теперь, когда у нас есть массив, мы можем сделать битовый сет. Тут доступны несколько вариантов. Можно, конечно, унаследовать битовый сет от нашего массива, но лучше сделать массив полем. В общем случае мы могли бы вообще передавать реализацию нашего массива прямо в конструктор:

Продолжение доступно только подписчикам

Вариант 1. Оформи подписку на «Хакер», чтобы читать все материалы на сайте

Подписка позволит тебе в течение указанного срока читать ВСЕ платные материалы сайта. Мы принимаем оплату банковскими картами, электронными деньгами и переводами со счетов мобильных операторов. Подробнее о подписке

Вариант 2. Купи один материал

Заинтересовала информация, но нет возможности оплатить подписку? Тогда этот вариант для тебя! Обрати внимание: этот способ покупки доступен только для материалов, опубликованных более двух месяцев назад.


4 комментария

  1. Аватар

    Jeffrey Davis

    19.08.2016 at 16:00

    Помнится, когда-то на форуме, который временно выключили навсегда, запускалась тема с почти таким же названием, где на топикстартере тут же весело оттянулись все, кто просто мимо пройти, не пнув веселья ради, не могли. А вот бы сегодня несчастный утёр нос всем обидчикам (а себе сопли).
    Но не судьба.

  2. Аватар

    MaXaMaR

    21.08.2016 at 01:52

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

  3. Аватар

    Markus28

    22.08.2016 at 20:27

    Сразу извиняюсь, если оффтоп (если что, укажите, где можно этот вопрос задать). Ищу систему и компетентную программу по оптимизации работы предприятия. Ищу для себя, объем работы большой. Половина из предложенного списка необходимо выполнить:konsom.ru/solutions Может кто-то подскажет, где искать. Этих ребят тоже рассматриваю.

  4. Аватар

    sstrolls

    26.08.2016 at 17:31

    Это часть 3? Точно часть 3?
    А где тогда часть 2?

Оставить мнение

Check Also

Вредительский контроль. Чем опасны приложения для ограничения функций iPhone

В конце апреля в средствах массовой информации прокатилась очередная волна публикаций на т…