Структура данных для представления кусочно-непрерывного диапазона? - PullRequest
3 голосов
/ 16 ноября 2010

Допустим, у меня есть целочисленный индекс длиной 400, и я хочу выделить несколько элементов с начала, много с конца и кое-что из середины, но без изменения исходного массива.То есть вместо циклического прохождения массива с помощью индексов {0...399} я хочу использовать кусочно-непрерывный диапазон , например

{3...15} ∪ {18...243} ∪ {250...301} ∪ {305...310}

Какая хорошая структура данных для описания этого видадиапазонов индексов?Очевидное решение состоит в том, чтобы создать еще один массив «индекс-посредник», содержащий сопоставления от непрерывного индексирования на основе нуля к новым координатам, указанным выше, но это выглядит довольно расточительно, поскольку почти все элементы в нем будут просто последовательными числами, с несколькими случайными«прыгает».Кроме того, что если я обнаружу, что я хочу немного изменить диапазон?Весь индексный массив должен быть перестроен.Не приятно.

Несколько замечаний:

  • Диапазоны никогда не перекрываются.Если в структуру данных добавлен новый диапазон, и он перекрывается с существующими диапазонами, все это должно быть объединено.То есть, если я добавлю в вышеприведенный пример диапазон {300... 308}, он должен вместо этого заменить последние два диапазона на {250...310}.
  • Это будет довольно дешево просто loop throughвесь диапазон.
  • Также следует относительно дешево запросить значение напрямую: «Дайте мне исходный индекс, соответствующий 42-му индексу в отображенных координатах».
  • Это должно быть возможно (хотя, может быть, не совсем дешево) работать наоборот: «Дайте мне сопоставленную координату, соответствующую 42 в исходных координатах, или скажите, отображается ли она вообще».Я хотел бы знать, существует ли хорошо известная структура данных, которая элегантно решает этот класс проблем.

    Спасибо!

1 Ответ

2 голосов
/ 16 ноября 2010

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

Редактировать: Если подумать, эта проблема как раз то, что должен делать индекс базы данных. Если целочисленные пары не обязательно должны быть в числовом порядке, вы можете легче обрабатывать разбиения. Если числовая последовательность должна оставаться в порядке, вам нужна структура данных, которая позволяет добавлять целые пары в середину массива или списка.

Для разбиения потребуется изменить целочисленную пару (6, 12) на (6, 9) (11, 12), когда в качестве примера удалено 10

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

True. Возможно, одна целочисленная пара должна измениться. В худшем случае вам придется перестроить весь массив или список.

...