Scala BitSet и операции сдвига

Я ищу способ представить набор целых чисел с помощью битового вектора (который будет характеристической функцией этого набора целых чисел) и иметь возможность выполнять побитовые операции с этим набором.

Сначала я подумал, что BitSet от scala будет идеальным кандидатом. Однако похоже, что BitSet не поддерживает операции переключения в соответствии с документацией 1. При дальнейшем исследовании я также обнаружил, что соответствующая реализация Java BitSet не поддерживает операции сдвига 2.

Остался ли у меня единственный вариант реализации моего собственного класса BitSet, который поддерживает операции сдвига? Более того, согласно описанию, приведенному в 3, это не так сложно поддерживать сдвига операций в реализации Scala BitSet, или я что-то неправильно понял?

Заранее спасибо.


scala bit-shift bitset
person Asiri Rathnayake    schedule 07.09.2011    source источник

Ответы (2)


arrow_upward
6
arrow_downward

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

class ShiftableBitSet(bs: BitSet) {
  def shiftLeft(n: Int): BitSet = ... //impl goes here
}

implicit def bitsetIsShiftable(bs: BitSet) = new ShiftableBitSet(bs)

val sample = BitSet(1,2,3,5,7,9)
val shifted = sample.shiftLeft(2)

Измените shiftLeft на любое имя и с любыми аргументами, которые вы предпочитаете.

ОБНОВЛЕНИЕ

Если вы точно знаете, что у вас будет неизменяемый BitSet, тогда подход (немного хакерский) для доступа к необработанному базовому массиву заключается в сопоставлении с шаблоном. Не слишком болезненно, поскольку для неизменяемого BitSet есть только 3 возможных конкретных подкласса:

import collection.immutable.BitSet
val bitSet = BitSet(1,2,3)
bitSet match {
  case bs: BitSet.BitSet1 => Array(bs.elems)
  case bs: BitSet.BitSetN => bs.elems 
  case _ => error("unusable BitSet")
}

Досадно, что параметр elems1 для BitSet2 не является val, а параметр elems изменяемого BitSet помечен как защищенный. Так что это не идеально, но должно помочь, если ваш набор нетривиален и неизменен. Для тривиальных случаев «нормальный» доступ к набору не будет слишком дорогим.

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

person Kevin Wright    schedule 07.09.2011
comment
Поскольку BitSet внутренне использует массив Long для представления битового вектора, доступ к этому массиву будет жизненно важен для эффективной реализации операций сдвига (поскольку операции сдвига на Long изначально поддерживаются). Однако в реализации оболочки, подобной той, которую вы предложили, можно было бы реализовать указанную функциональность только с использованием операций, поддерживаемых самим интерфейсом BitSet, что не было бы таким эффективным IMHO. - person Asiri Rathnayake; 08.09.2011
comment
Спасибо за обновление, звучит (хакерско, но) умно! Я думал об использовании изменяемого BitSet, чтобы избежать ненужного создания объектов, но, как вы упомянули, этот трюк работает только для неизменяемого BitSet. Кстати, я думаю, вы хотели сказать BitSet вместо BitMap в последнем абзаце (?). - person Asiri Rathnayake; 08.09.2011
comment
Это, несомненно, хакерский и ненадежный перед лицом будущих реализаций BitSet. Но пока вы готовы с этим справиться ... - person Kevin Wright; 08.09.2011

arrow_upward
-3
arrow_downward

Вы можете просто использовать карту, например, чтобы переместиться влево на 4 позиции:

import collection.immutable.BitSet
val bitSet = BitSet(1,2,3)
bitSet map (_ + 4)
person Anton Kovsharov    schedule 25.12.2015
comment
Это не (побитовый) сдвиг. Вы добавляете 4 ко всем элементам в наборе. - person Asiri Rathnayake; 26.12.2015