Segmented Array

Задача

Необходимо реализовать некоторую коллекцию индексированных данных некоторого типа 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:

  1. Интерфейс SegmentedArray, который описывает заданную функциональность доступа к сегментированному массиву
  2. Класс SegmentedArrayImpl, имплементирует данный интерфейс
  3. Класс SegmentedArrayApp, который имплементирует тестевое приложение, он содержит метод main и вспомогательные методы ввода данных и вывода результата.

Интерфейс SegmentedArray

Методы интерфейса:

  • indexOf — возвращает абсолютный индекс элемента в массиве начиная с заданного индекса.
  • set — присваивает последовательности элементов массива одно и тоже значение в заданном диапазоне
  • min — возвращает минимальный элемент в заданном диапазоне

Класс SegmentedArrayImpl

Данный класс реализует интерфейс SegmentedArray с учетом требования задачи, а именно:

  • Допускаются массивы очень большого размера
  • Методы indexOf и max должны работать максимально быстро

Используемый алгоритм

С учетом условий задачи был выбран алгориnм, описанный в статье Segmented Tree.

Согласно условию задачи, массив может быть очень большим, а это означает очень широкий диапазон индексов элементов. Следовательно, стоит задача максимально быстро находить начальный и конечный сегменты, которые покрывают индексы диапазона, заданные в качестве параметров методов интерфейса.

Выбранный алгоритм позволяет быстрыое нахождение нужных сегментов благодаря бинарному дереву, которым описывается набор диапазонов.

Алгоритм поиска нужного сегмента реализован с помощью методов findSegmentIndex и compareIndexToSegment.

Первый метод — это обычный двоичный поиск в массиве отсортированных элементов, которыми являются номера сегментов в порядке их следования. Данный метод заимствован из Coursera. Внутри он использует второй метод compareIndexToSegment для проверки попадания заданного абсолютного индекса в сегмент с заданным номером, т. е. он реализует нобходимый для бинарного поиска метод сравнения, где фактически абсолютный индекс сравнивается с сегментом с целью его выбора.

Методы родительского интерфейса

  • indexOf — находит нужный сегмент посредством findSegmentIndex и далее — индекс в сегменте, затем производит поиск в этом и последующих сегментах нужного значения
  • set — находит первый и последний сегменты посредством findSegmentIndex, которые покрывают входные индексы диапазона, затем выполняет запись начиная с начального сегмента и индекса в нем, и заканчивая последним сегментом и индексом в нем.
  • min — находит диапазон сегментов для поиска таким же образом, как и метод set и находит минимальное значения в данном диапазоне сегментов

Собственные методы

  • конструктор — принимает 2 аргумента — размер и количество сегментов
  • compareIndexToSegment — проверяет, попадает ли абсолютный индекс в данный сегмент и возвращает одно из значений: -1 — если индекс перед сегментом, 0 — если попадает в сегмент, 1 — если после сегмента
  • findSegmentIndex — находит сегмент, который содержит данный абсолютный индекс используя бинарный поиск в массиве
  • show — диагностическая печать содержимого

Класс SegmentedArrayApp

Данный класс реализует тестовое приложение для интерфейса. Он содержит вспомогательные функции ввода и функцию main, содержащую код теста.

Методы класса

  1. parseTextToTokens — разбирает входной текст на слова используя известный класс StringTokenizer и возвращает вектор слов
  2. strToInt — превращает строку в число с подавлением исключения NumberFormatException
  3. main — реализует простейший интерпритатор команд, в котором каждая команда представляет соостветствующий интерфейсный метод, состоит из цикла, где в каждом цикле посредством объекта Scanner читается полностью входная строка, которая затем разбирается на команду и ее аргументы посредством parseTextToTokens, это в дальнейшем превращается в соответствующие вызовы интерфейсных методов.

Ссылка на Ideone: https://ideone.com/BknxiN

Добавить комментарий

Ваш e-mail не будет опубликован. Обязательные поля помечены *