#java #performance #memory #bitset
Вопрос:
Предположим BitSet java.util.BitSet; , используется значение from. Цель состоит в том, чтобы быстро найти все битовые значения, для которых установлено значение true . Эти значения не упорядочены и не имеют определенного шаблона. Максимальный индекс BitSet будет равен 2^31 - 48 . Общее количество битов, для которых будет установлено true (2^31 - 48)/2 значение, равно . Другими словами, существует два миллиарда битов, которые могут быть true / false , как я могу эффективно найти все true биты?
Каждый раз , когда установлен бит true , требуется выполнить запуск, чтобы посетить все true биты в BitSet . Вы можете понять, почему каждый раз перебирать все 2^31 - 48 биты не так эффективно, когда дело доходит до производительности.
Вот решение , которое не соответствует моим потребностям: создайте int[] indices размер (2^31 - 48)/2 и каждый раз i , когда установлен бит true , сохраняйте значение i в следующем доступном слоте indices . Хотя это помогает в выполнении запроса, это добавит около 32 * (2^31 - 48)/2 бит в память, которая составляет около 4,3 Гб.
Основное внимание уделяется производительности и повторяющимся вычислениям. Использование файлов ввода/вывода или чего-то другого, кроме BitSet нежелательного.
Каков самый быстрый подход к достижению желаемого поведения? Или… что такое достаточно быстрый подход, который также использует значительно меньше памяти?
Комментарии:
1. Подождите… так вы говорите, что вероятность установки значения true/false для «Коллекции» равна 50/50, И вы хотите, чтобы это было сделано БОЛЕЕ ЭФФЕКТИВНО, чем подсчет или хранение положительных индексов? Возможно, используйте сжатие, такое как LZW, а затем разберите биты в словаре и их расположение, но это действительно далеко… и вам нужны ошибки 0/0, поэтому о любом другом статистическом или аналитическом трюке не может быть и речи… «Каждый раз, когда бит установлен в значение true, требуется выполнить запуск, чтобы посетить все истинные биты»… почему? Я думаю, что здесь кроется центр проблемы…
2. Расширение вашего решения (
int[] indices): вместо использования абсолютных адресов вы можете сохранить дельту индекса до следующего индекса в виде байта или, в зависимости от возможности, в еще меньшем количестве битов. И если так случится, что дельта больше, чем вы можете сохранить, имейте значение индикатора, которое указывает на больший скачок и требует большего количества считываемых данных, в основном, как UTF-8 преобразует байты в символы.3. Набор бит java 1.8
stream, который создает цель — вы смотрели на его реализацию? docs.oracle.com/javase/8/docs/api/java/util/…
Ответ №1:
Каков самый быстрый подход к достижению желаемого поведения?
Если вы ограничиваете себя API BitSet, то я думаю, что вам нужен цикл, который многократно вызывает BitSet.nextSetBit . Да, это повлечет за собой 2^30 звонков. Но я думаю, что это так же хорошо, как вы собираетесь использовать BitSet API.
Если вы хотите что-то более быстрое, вам нужно будет либо придумать свою собственную структуру данных для этого (а у меня нет действительно хороших идей), либо изменить проблему.
Наблюдение: изучение 2^30 бит каждый раз, когда меняется один бит, будет очень дорогостоящим с точки зрения вычислений, независимо от того, как вы это делаете.
Если бы это была моя проблема, я бы сначала поискал более разумное решение, которое вообще не требовало бы этого. Если бы не было разумного решения, я бы, вероятно, использовал массив int вместо a BitSet и нашел способ распараллелить сканирование по 8 / 16 / 32 ядра 1. (Но это также зависит от того, что вам нужно сделать для каждого бита, который есть true .)
1 — Это предполагает, что у вас есть незанятые ядра / питание / охлаждение, чтобы решить эту проблему.
Или… что такое достаточно быстрый подход, который также использует значительно меньше памяти?
AFAIK, вы не можете представлять 2^N случайные истинные / ложные значения в лучших O(2^N) битах. Ваша единственная надежда была бы, если бы битовый шаблон был неслучайным и легко сжимаемым. И даже в этом случае у вас возникают проблемы с затратами процессора на сжатие / распаковку, а также проблема эффективного обновления бита в сжатой последовательности битов. Осуществимо ли это, будет зависеть от характера вашего битового потока.
Комментарии:
1. Почему вы думаете, что распараллеливание обработки массива int лучше, чем просто распараллеливание обработки набора битов?
2. Хмм… теперь, когда вы упомянули об этом, у меня нет хорошего ответа на этот вопрос.