Использование памяти BitSet в Scala

Question

Я хотел бы знать, каково использование памяти BitSet в Scala. Например, если я делаю:

  var bitArray:BitSet=new BitSet(10)
  bitArray.add(0)
  bitArray.add(2)
  bitArray.add(4)
  bitArray.add(6)
  bitArray.add(8)

Как это сравнить с массивом, содержащим четные числа 0,2,4,6,8?

Как насчет записи числа в двоичном виде:

  var bitArray:BitSet=new BitSet(32)
  bitArray.add(5)
  bitArray.add(3)
  bitArray.add(2)
  bitArray.add(1)
  bitArray.add(0)

Как это сравнить с числом 47?

Я спрашиваю здесь об использовании памяти. Но как более открытый вопрос, если вы знаете, каковы преимущества / недостатки или использование BitSet (WR перед другими распространенными типами данных).

Спасибо

Answer 1

Вы можете посмотреть на реализацию BitSet в Scala 2.8 здесь: scala.collection.mutable.BitSet .

Он реализован на основе массива Longs. Размер массива зависит только от наибольшего числа, хранящегося в нем. Разделите наибольшее число, хранящееся в нем, на 64, округлив, и вы получите размер массива. Каждый элемент в массиве занимает 8 байтов.

Это означает, что деление на 8 наибольшего числа, хранящегося в нем, примерно дает размер в байтах BitSet. «Примерно» из-за накладных расходов на управление памятью виртуальной машины, потому что указателю на массив также требуется некоторое количество памяти и потому что сам массив имеет некоторые накладные расходы.

Порядок вставки или фактическое количество элементов, хранящихся в BitSet, не влияют на размер выделяемой памяти.

Для двух приведенных вами примеров для хранения чисел требуется только один длинный элемент с использованием 8 байтов памяти, поскольку в обоих примерах наибольшее число меньше 64.

Массив Ints, хранящий любые пять чисел, будет занимать 5 * 4 байта = 20 байтов плюс накладные расходы. Для хранения n чисел нужно примерно n * 4 байта.

Таким образом, вы сравниваете (наибольшийNumberStored / 8) байт с (countOfNumbersStored * 4) байтами.