Мне предоставили реализовать класс, который наследует SegmentedArray и характеризуется следующим:
- принимает большой массив
- элементы массива — 0 и 1
- частые запросы get() и set()
Чтобы была возможность хранить очень большой массив, я решила построить класс с помощью битовых операций. Это было возможно, так как элемент моего массива — это 0 и 1, и любое число можно представить в виде последовательности нулей и единиц. Поэтому внутри класса если массив long, в одной ячейке которого может храниться до 64 элементов. Так была решена проблема с расходом памяти.
Из-за представления чисел в двоичном коде, к ним легко применимы битовые операции. Например, для реализации метода get() достаточно использовать битовый сдвиг и битовое «и». Следовательно, метод работает за О(1).
В реализации метода set() мне помогла блочная структура (64 элемента в 1 ячейке массива). А именно: я проверяю границы заданного отрезка, а ячейки, которые попали внутрь полностью просто приравниваю константе: 0 — если все элементы ячейки нули, -1 — если все элементы ячейки единицы.
Точно так же реализован метод add().
С методом min() всё и того проще: ответом служит либо 0, либо 1. Первый же ноль, встреченный на заданном отрезке, определяет ответ.
Также я предположила, что, как и в большинстве олимпиадных задач, индексация массива начинается с единицы. То есть в методе get(), set(), add() и min() необходима сначала уменьшить каждый индекс на единицу, а лишь потом проводить операции над массивом, так как индексация в нём начинается с нуля.
Теоретическая оценка сложности методов:
- get(i): O(1);
- set(x, y, val): O((y-x)/64);
- add(x, y, val): O((y-x)/64) — для val%2==1, и O(1) — для val%2==0;
- min(x, y) — O((x-y)/64) — в худшем случае (на отрезке все элементы нули), O(1) — в лучшем случае (на отрезке все элементы единицы).
Код программы:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 |
import java.util.*; import java.lang.*; import java.io.*; interface SegmentedArray { long size(); // <= 2^31 - 1 long get(long index); SegmentedArray set(int start, int end, long value); // [start, end) <- value % 2 SegmentedArray add(int start, int end, long value); // [start, end) += value % 2 int min(int start, int end); // [start, end) } class BitSegmentedArray implements SegmentedArray { long size; long realSize; long []storage; public BitSegmentedArray(long size) { this.size = size; if (size%64!=0) this.realSize = size/64 + 1; else this.realSize = size/64; storage = new long [(int)realSize]; for (int i = 0; i < realSize; i++) { storage[i] = 0; } } public long size() { return size; } public long get(long index) { index--; return storage[(int)index/64] >> (index%64) & 1; } public void print() { for (int i = 0; i < this.realSize; i++) { for (int j = 0; j < 64; j++) { System.out.print(this.storage[i] >> j & 1); System.out.print(" "); } } System.out.println(); } public SegmentedArray set(int start, int end, long value) { start--; end--; int realStart = start/64; int realEnd = end/64; if (realStart != realEnd) { for (int i = start%64; i < 64; i++) { if (value%2 == 1) storage[realStart] |= (value&1) << i; else if (this.get(i+1) == 1) storage[realStart] ^= ((long)1 << i); } for (int i = realStart + 1; i < realEnd; i++) { if (value%2 == 0) storage[i] = 0; else storage[i] = -1; } for (int i = 0; i < end%64; i++) { if (value%2 == 1) storage[realEnd] |= (value&1) << i; else if (this.get(i+1) == 1) storage[realEnd] ^= ((long)1 << i); } } else { for (int i = start%64; i < end%64; i++) { if (value%2 == 1) storage[realStart] |= (value&1) << i; else if (this.get(i+1) == 1) storage[realStart] ^= ((long)1 << i); } } return this; } public SegmentedArray add(int start, int end, long value) { if (value % 2 == 0) return this; start--; end--; int realStart = start/64; int realEnd = end/64; if (realStart != realEnd) { for (int i = start%64; i < 64; i++) { storage[realStart] ^= (value&1) << i; } for (int i = realStart + 1; i < realEnd; i++) { if (storage[i] == 0) storage[i] = -1; else storage[i] = 0; } for (int i = 0; i < end%64; i++) { storage[realEnd] ^= (value&1) << i; } } else { for (int i = start%64; i < end%64; i++) { storage[realStart] ^= (value&1) << i; } } return this; } public int min(int start, int end) { start--; end--; int realStart = start/64; int realEnd = end/64; if (realStart != realEnd) { for (int i = start%64; i < 64; i++) { long tmp = (storage[realStart] >> i) & 1; if (tmp != 1) return 0; } for (int i = realStart + 1; i < realEnd; i++) { if (storage[i] != -1) return 0; } for (int i = 0; i < end%64; i++) { long tmp = (storage[realEnd] >> i) & 1; if (tmp != 1) return 0; } } else { for (int i = start%64; i < end%64; i++) { long tmp = (storage[realStart] >> i) & 1; if (tmp != 1) return 0; } } return 1; } public static void main(String[] args) { BitSegmentedArray b = new BitSegmentedArray (10000); long start, end; start = System.nanoTime(); b.set(50, 4566, 1); end = System.nanoTime(); System.out.println("Set в BitSegmentedArray отрабатывает за " + (end - start) + " нс."); b.set(130, 740, 0); b.set(1000, 1084, 0); b.set(3006, 3070, 0); start = System.nanoTime(); long get = b.get(111); end = System.nanoTime(); System.out.println("Get в BitSegmentedArray отрабатывает за " + (end - start) + " нс."); System.out.println(get); start = System.nanoTime(); b.add(76, 830, 1); end = System.nanoTime(); System.out.println("Add в BitSegmentedArray отрабатывает за " + (end - start) + " нс."); b.add(60, 92, 0); start = System.nanoTime(); int minimum = b.min(130, 1400); end = System.nanoTime(); System.out.println("Min в BitSegmentedArray отрабатывает за " + (end - start) + " нс."); System.out.println(minimum); } } |
Протестировать программу можно здесь.
Простейшая реализация интерфейса: SimpleSegmentedArray.
Сравнение скорости работы методов:
|
1 2 3 4 5 6 |
Set в BitSegmentedArray отрабатывает за 25626 нс. Get в BitSegmentedArray отрабатывает за 717 нс. 1 Add в BitSegmentedArray отрабатывает за 16785 нс. Min в BitSegmentedArray отрабатывает за 6521 нс. 0 |
|
1 2 3 4 5 6 |
Set в SimpleSegmentedArray отрабатывает за 200334 нс. Get в SimpleSegmentedArray отрабатывает за 10362 нс. 1 Add в SimpleSegmentedArray отрабатывает за 43084 нс. Min в SimpleSegmentedArray отрабатывает за 52949 нс. 0 |