Что это за абстрактный тип данных?

Является ли следующий общий тип данных (т.е. имеет ли он имя)?

Его уникальная характеристика, в отличие от обычного Set, состоит в том, что он содержит «вселенную» при инициализации с O(C) накладными расходами памяти и максимальными накладными расходами памяти O(N/2) (что происходит только при удалении всех остальных элементов):

> s = new Structure(701)
s = Structure(0-700)

> s.remove(100)
s = Structure(0-99, 101-700)

> s.add(100)
s = Structure(0-700)

> s.remove(200)
s = Structure(0-199, 201-700)

> s.remove(202)
s = Structure(0-199, 201, 203-700)

> s.removeAll()
s = Structure()

У чего-то подобного есть стандартное имя?


collections algorithm abstraction abstract-data-type
person Lawrence Wagerfield    schedule 10.09.2017    source источник
comment
дерево диапазонов? Операция удаления здесь будет эквивалентна операции разделения узла + изменения размера в дереве диапазонов.   -  person meowgoesthedog    schedule 10.09.2017
comment
Что заставляет вас думать, что что-то настолько конкретное должно иметь имя? Это звучит как замаскированный запрос на отсутствие исследований для реализации, которая может достичь этого.   -  person Bernhard Barker    schedule 10.09.2017
comment
Нет имени, но есть пара идей о том, как это реализовать: -consecutive-int/" title="эффективная структура данных для хранения длинной последовательности в основном последовательных int"> stackoverflow.com/questions/39522165/   -  person m69 ''snarky and unwelcoming''    schedule 11.09.2017
comment
@Dukeling уже реализовал это в Scala (я знаю, что в стандартных коллекциях библиотек нет ничего подобного). Просто хотел выбрать приличное имя для своего типа (раньше называл его SparseRange).   -  person Lawrence Wagerfield    schedule 11.09.2017
comment
Я бы назвал это бит-вектором с кодированием длин серий, потому что его семантика является бит-вектором, а его печатное представление показывает непрерывные блоки.   -  person Ralf Kleberhoff    schedule 11.09.2017
comment
Немного не по теме: при его использовании просто убедитесь, что накладные расходы на управление списком диапазонов того стоят по сравнению с простым битовым вектором.   -  person Ralf Kleberhoff    schedule 11.09.2017

Ответы (2)


arrow_upward
0
arrow_downward

Я использовал это много раз в прошлом и видел, как это использовалось в таких вещах, как алгоритмы развертки плоскости для отсечения полигонов.

Иногда абстрактный тип данных, который он представляет, представляет собой просто набор, а структура данных представляет собой оптимизацию. Я использую это для представления набора совпадающих символов, заданного выражением регулярного выражения, например [^a-zA-z0-9.-], и для выполнения пересечения, объединения и других операций над этими наборами.

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

Однако мне нравится идея дать ему имя, поскольку, как я уже сказал, я сам использовал его много раз. Может быть, я бы назвал это «вход и выход» в честь сети гамбургеров, которые мне больше всего нравились, когда я ел гамбургеры.

person Matt Timmermans    schedule 10.09.2017

arrow_upward
0
arrow_downward

It's a Compressed Bit Set or Compressed Bitmap.

Bit Set или Bitmap — это набор, специально разработанный для хранения Integer. Большинство языков предлагают их стандартную реализацию. Обычно они работают, присваивая 1 N биту во внутреннем массиве Integers, где N — это число, которое вы добавляете к набору. 0 указывает, что значение отсутствует. Использование памяти для этих типов Bit Sets определяется наибольшим числом, которое вы храните.

Compressed Bit Set — это тот, который сжимает диапазоны 0s и 1s.

В этом случае вопрос демонстрирует тип сжатия, называемый «кодирование длины цикла» (спасибо, @Ralf Kleberhoff), так что это конкретно Run-length Encoded Bitmap.

Общие реализации Compressed Bitmaps (от самого нового к самому старому):

person Lawrence Wagerfield    schedule 13.09.2017