в Java, что лучше - три массива логических значений или 1 массив байтов?

Question

Я знаю, что вопрос звучит глупо, но учтите это: у меня есть массив ints (1..N) и алгоритм маркировки. в любой момент элемент, который представляет int, находится в одном из трех состояний. Текущая версия хранит эти состояния в массиве byte, где 0, 1 и 2 представляют три состояния. В качестве альтернативы я мог бы иметь три массива boolean - по одному для каждого состояния. что лучше (потребляет меньше памяти) зависит от того, как jvm (версия sun) хранит массивы - логическое значение представлено 1 битом? есть ли какая-то другая магия за кулисами? (p.s. не начинайте со всего, что «это не так, как работает OO / Java» - я знаю, но здесь производительность идет впереди. Плюс алгоритм прост и отлично читается даже в такой форме).

Большое спасибо

Answer 1

Теоретически, с 3 логическими массивами вам нужно сделать:

firstState[n] = false;
secondState[n] = true;
thirdState[n] = false;

каждый раз, когда вы хотите изменить состояние n-го элемента. Здесь вы можете видеть 3 взятия элемента по индексным операциям и 3 операции присваивания.

С 1-байтовым массивом вам понадобится:

elements[n] = 1;

Это более читабельно и в 3 раза быстрее. И еще одно преимущество этого решения в том, что вы можете легко добавлять столько новых состояний, сколько захотите (когда с логическими массивами вам нужно будет вводить новые массивы).

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

UPD : на самом деле я бы сделал это более Java-способом (не смотря на то, что вы не находите простых путей) и использовал бы массив enums . Это сделает это намного более понятным и даст вам некоторую гибкость (возможно, в будущем вы решите, что упс не так уж и плохо):

enum ElementState {
   FIRST, SECOND, THIRD;
}

ElementState[] elementStates = new ElementState[N];
...
elementStates[i] = ElementState.FIRST;

Answer 2

Вместо двух логических значений или 1 int просто используйте BitSet - http://java.sun.com/j2se/1.4.2/docs/api/java/util/BitSet.html

Вы можете иметь два бита на метку / состояние. А BitSet является стандартным Java-классом, и вы, вероятно, получите хорошую производительность.

Answer 3

Спецификация второго издания JVM (http://java.sun.com/docs/books/jvms/second_edition/html/Overview.doc.html) указывает, что логические массивы кодируются как (0,1), но не указывает используемый тип. Поэтому конкретная JVM может использовать или не использовать бит - это может используйте int.

Однако, если производительность имеет первостепенное значение, использование одного байта в любом случае может показаться вам лучшим вариантом.

РЕДАКТИРОВАТЬ: я неправильно сказал, что логические массивы хранятся в виде битовых массивов - это возможно, но зависит от реализации.

Answer 4

Массив байтов намного лучше!

1. A boolean использует в каждом языке программирования 1 байт! Таким образом, вы будете использовать для каждого состояния 3 байта, и вы можете сделать это только с 1 байтом (теоретически вы можете уменьшить его до 1 бита (см. Другие посты).
2. с байтовым массивом, вы можете просто изменить его на нужный вам байт. С тремя массивами вы должны изменить значение в каждом массиве!
3. Когда вы разрабатываете свое приложение, возможно, вам нужно дополнительное состояние. Итак, это означает, что вы должны снова создать массив. Плюс нужно изменить 4 значения (вторая точка)

Итак, я надеюсь, мы вас убедили!

Answer 5

Если вы хотите гарантированный минимум, вы можете использовать три java.util.BitSets. Они будут использовать только один бит на флаг (хотя у вас будут дополнительные издержки на объекты, которые могут перевесить преимущества, если число флагов невелико). Я бы сказал, если у вас есть большое количество объектов, BitSet может быть лучшей альтернативой, в противном случае массив байтовых констант или перечислений приведет к более читабельному коду (и дополнительная память не должна быть реальной проблемой).