Задача
Необходимо реализовать некоторую коллекцию индексированных данных некоторого типа T, выглядящую как несколько необычный массив. Вместо операции присваивания значения элементу массива в нём имеется операция присваивания одинаковых значений всем элементам для некоторого диапазона индексов. Также и операции поиска минимума и максимума должны работать для некоторого диапазона значений индексов.
При написании класса, реализующего данный интерфейс необходимо стремиться к максимальной эффективности выполнения наиболее частых операций и учитывать особенности использования отражённые в следующей таблице с заданиями:
| Big array |
Small |T| |
Often | Student | |||
|---|---|---|---|---|---|---|
| get() | set() | indexOf() | min()/max() | |||
| 1 | 0 | 0 | 0 | 1 | 0 | Швандт |
Тест
| input | output |
| set 2 2 H | ok |
| set 3 3 E | ok |
| set 4 5 L | ok |
| set 6 6 O | ok |
| set8 8 W | ok |
| set 9 9 O | ok |
| set 10 10 R | ok |
| set 11 11 L | ok |
| set 12 12 D | ok |
| set 13 13 ! | ok |
| set 14 14 ! | ok |
| set 15 15 ! | ok |
| show | segment#0 { null null H E } segment#1 { L L O null } segment#2 { W O R L } segment#3 { D ! ! ! } |
| exit | N/A |
Структура программы
Код программы состоит из следующих элементов, объединенных в пакет odessa.uni.imem.maxim:
- Интерфейс SegmentedArray, который описывает заданную функциональность доступа к сегментированному массиву
- Класс SegmentedArrayImpl, имплементирует данный интерфейс
- Класс SegmentedArrayApp, который имплементирует тестевое приложение, он содержит метод main и вспомогательные методы ввода данных и вывода результата.
Интерфейс SegmentedArray
|
1 2 3 4 5 6 7 8 |
package odessa.uni.imem.maxim; public interface SegmentedArray<Comparable> { int indexOf(Comparable value, int fromIndex); void set(int fromIndex, int toIndex, Comparable value); Comparable min(int fromIndex, int toIndex); } |
Методы интерфейса:
- indexOf — возвращает абсолютный индекс элемента в массиве начиная с заданного индекса.
- set — присваивает последовательности элементов массива одно и тоже значение в заданном диапазоне
- min — возвращает минимальный элемент в заданном диапазоне
Класс SegmentedArrayImpl
|
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 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 |
package odessa.uni.imem.maxim; public class SegmentedArrayImpl<Item extends Comparable<Item>> implements SegmentedArray<Item> { private int size; private int segmentSize; private Object[][] segments; public SegmentedArrayImpl(int aSegmentSize, int aSegmentCount) { segmentSize = aSegmentSize; size = segmentSize * aSegmentCount; segments = new Object[aSegmentCount][segmentSize]; } public int indexOf(Item value, int fromIndex) { if (fromIndex >= size) { return -1; } int segmentIndex = findSegmentIndex(fromIndex); int indexInSegment = fromIndex - segmentIndex * segmentSize; while (segmentIndex < segments.length) { // @SuppressWarnings("unchecked") if (((Item) (segments[segmentIndex][indexInSegment])).compareTo(value) == 0) { return segmentIndex * indexInSegment; } indexInSegment++; if (indexInSegment == segmentSize) { indexInSegment = 0; segmentIndex++; } } return -1; } public void set(int fromIndex, int toIndex, Item value) { if (fromIndex >= size || toIndex >= size || fromIndex > toIndex) { return; } int index = fromIndex; int segmentIndex = findSegmentIndex(fromIndex); int indexInSegment = fromIndex - segmentIndex * segmentSize; while (segmentIndex < segments.length && index <= toIndex) { // @SuppressWarnings("unchecked") segments[segmentIndex][indexInSegment] = value; index++; indexInSegment++; if (indexInSegment == segmentSize) { indexInSegment = 0; segmentIndex++; } } } public Item min(int fromIndex, int toIndex) { if (fromIndex >= size || toIndex >= size || fromIndex > toIndex) { return null; } int index = fromIndex; int segmentIndex = findSegmentIndex(fromIndex); int indexInSegment = fromIndex - segmentIndex * segmentSize; Item minimum = null; while (segmentIndex < segments.length && index < toIndex) { // @SuppressWarnings("unchecked") Item val = (Item) segments[segmentIndex][indexInSegment]; if (minimum == null || val.compareTo(minimum) < 0) { minimum = val; } index++; indexInSegment++; if (indexInSegment == segmentSize) { indexInSegment = 0; segmentIndex++; } } return null; } // check if the absolute index falls into given segment index private int compareIndexToSegment(int index, int segmentIndex) { int lowerIndex = segmentIndex * segmentSize; int higherIndex = (segmentIndex + 1) * segmentSize - 1; if (index < lowerIndex) // index falls before segment { return -1; } else if (index > higherIndex) // index falls after segment { return 1; } return 0; } // find segment that contains given absolute index using binary search // in array private int findSegmentIndex(int index) { int lo = 0; // lower segment index int hi = segments.length - 1; // higher segment index while (lo <= hi) { int mid = lo + (hi - lo) / 2; // middle segment index int cmp = compareIndexToSegment(index, mid); if (cmp < 0) { hi = mid - 1; } else if (cmp > 0) { lo = mid + 1; } else if (cmp == 0) { return mid; } } return lo; } public void show() { for (int i = 0; i < segments.length; i++) { System.out.printf("segment#%d { ", i); for (int j = 0; j < segmentSize; j++) { System.out.print((Item) segments[i][j]); System.out.print(" "); } System.out.printf("}\n"); } } } |
Данный класс реализует интерфейс SegmentedArray с учетом требования задачи, а именно:
- Допускаются массивы очень большого размера
- Методы indexOf и max должны работать максимально быстро
Используемый алгоритм
С учетом условий задачи был выбран алгориnм, описанный в статье Segmented Tree.
Согласно условию задачи, массив может быть очень большим, а это означает очень широкий диапазон индексов элементов. Следовательно, стоит задача максимально быстро находить начальный и конечный сегменты, которые покрывают индексы диапазона, заданные в качестве параметров методов интерфейса.
Выбранный алгоритм позволяет быстрыое нахождение нужных сегментов благодаря бинарному дереву, которым описывается набор диапазонов.
Алгоритм поиска нужного сегмента реализован с помощью методов findSegmentIndex и compareIndexToSegment.
Первый метод — это обычный двоичный поиск в массиве отсортированных элементов, которыми являются номера сегментов в порядке их следования. Данный метод заимствован из Coursera. Внутри он использует второй метод compareIndexToSegment для проверки попадания заданного абсолютного индекса в сегмент с заданным номером, т. е. он реализует нобходимый для бинарного поиска метод сравнения, где фактически абсолютный индекс сравнивается с сегментом с целью его выбора.
Методы родительского интерфейса
- indexOf — находит нужный сегмент посредством findSegmentIndex и далее — индекс в сегменте, затем производит поиск в этом и последующих сегментах нужного значения
- set — находит первый и последний сегменты посредством findSegmentIndex, которые покрывают входные индексы диапазона, затем выполняет запись начиная с начального сегмента и индекса в нем, и заканчивая последним сегментом и индексом в нем.
- min — находит диапазон сегментов для поиска таким же образом, как и метод set и находит минимальное значения в данном диапазоне сегментов
Собственные методы
- конструктор — принимает 2 аргумента — размер и количество сегментов
- compareIndexToSegment — проверяет, попадает ли абсолютный индекс в данный сегмент и возвращает одно из значений: -1 — если индекс перед сегментом, 0 — если попадает в сегмент, 1 — если после сегмента
- findSegmentIndex — находит сегмент, который содержит данный абсолютный индекс используя бинарный поиск в массиве
- show — диагностическая печать содержимого
Класс SegmentedArrayApp
|
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 |
package odessa.uni.imem.maxim; import java.util.*; public class SegmentedArrayApp { public static Vector<String> parseTextToTokens(String text) { Vector<String> tokens = new Vector<String>(); StringTokenizer st = new StringTokenizer(text); while (st.hasMoreTokens()) { tokens.add(st.nextToken()); } return tokens; } public static Integer strToInt(String s) { Integer x = null; try { x = Integer.parseUnsignedInt(s); } catch (NumberFormatException e) { } return x; } public static void main(String[] args) { SegmentedArrayImpl<String> storage = new SegmentedArrayImpl<String>(4, 4); Scanner in = new Scanner(System.in); for (;;) { String inputLine = in.nextLine(); if (inputLine.isEmpty()) { continue; } String cmd = null; String arg1 = null; String arg2 = null; String arg3 = null; { Vector<String> inputTokens = parseTextToTokens(inputLine); if (inputTokens.size() > 0) { cmd = inputTokens.get(0); } if (inputTokens.size() > 1) { arg1 = inputTokens.get(1); } if (inputTokens.size() > 2) { arg2 = inputTokens.get(2); } if (inputTokens.size() > 3) { arg3 = inputTokens.get(3); } } if (cmd.equals("exit")) { break; } else if (cmd.equals("show")) { storage.show(); } else if (cmd.equals("index")) { String value = (arg1 != null && !arg1.isEmpty()) ? arg1 : null; Integer fromIndex = (arg2 != null) ? strToInt(arg2) : null; if (value == null || fromIndex == null) { System.out.printf("*** ERROR: wrong arguments: <%s> <%s> <%d>\n", cmd, arg1, arg2); continue; } System.out.println(storage.indexOf(value, fromIndex)); } else if (cmd.equals("set")) { Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null; Integer toIndex = (arg2 != null) ? strToInt(arg2) : null; String value = (arg3 != null && !arg3.isEmpty()) ? arg3 : null; if (fromIndex == null || toIndex == null || value == null) { System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d> <%s>\n", cmd, arg1, arg2, arg3); continue; } storage.set(fromIndex, toIndex, value); System.out.println("Ok"); } else if (cmd.equals("min")) { Integer fromIndex = (arg1 != null) ? strToInt(arg1) : null; Integer toIndex = (arg2 != null) ? strToInt(arg2) : null; if (fromIndex == null || toIndex == null) { System.out.printf("*** ERROR: wrong arguments: <%s> <%d> <%d>\n", cmd, arg1, arg2); continue; } System.out.println(storage.min(fromIndex, toIndex)); } } in.close(); } } |
Данный класс реализует тестовое приложение для интерфейса. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста.
Методы класса
- parseTextToTokens — разбирает входной текст на слова используя известный класс StringTokenizer и возвращает вектор слов
- strToInt — превращает строку в число с подавлением исключения NumberFormatException
- main — реализует простейший интерпритатор команд, в котором каждая команда представляет соостветствующий интерфейсный метод, состоит из цикла, где в каждом цикле посредством объекта Scanner читается полностью входная строка, которая затем разбирается на команду и ее аргументы посредством parseTextToTokens, это в дальнейшем превращается в соответствующие вызовы интерфейсных методов.
Ссылка на Ideone: https://ideone.com/BknxiN