Какова постоянная структура данных для набора частично упорядоченных элементов?

15

Мне нужно хранить наборы элементов типа а. Тип a частично упорядочен, поэтому сравнение и может вернуть меньшее, большее, равное или несопоставимое.2a1a2

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

Сравнение двух элементов может быть длительным процессом, поэтому было бы интересно минимизировать сравнения. При необходимости можно запомнить звонки оператору сравнения. Теперь я понимаю, что мне нужно будет хранить только антицепи (или, допустим, так). Точнее, операции, которые мне нужно будет выполнить, следующие:

  • Удалить элемент из антицепи;
  • Попробуйте добавить элемент. Если элемент меньше члена, не добавляйте его, в противном случае добавьте его и удалите каждый элемент меньше его.

Я также могу связать каждый элемент двумя целыми числами, так что если я знаю, что и , то знание мгновенно дает мне . Конечно, не означает a \ not <b ... Поиск целочисленных границ - относительно дешевая операция по сравнению с полным сравнением элементов.я1<a<я2я3<б<я4я2<я3a<бя2я3aб

Абдаллах
источник
1
Я думаю, что нам нужно знать больше, чтобы разумно ответить на ваш вопрос. Вы храните элементы, и частичный порядок легко вычисляется? Или вы также храните частичный порядок в какой-то таблице поиска? Как вы собираетесь использовать частичный заказ? Вы надеетесь использовать его так же, как линейный порядок для хранения наборов (например, в деревьях поиска)?
Андрей Бауэр
Теперь, когда я понял, что у меня будут только антицепи, я не уверен, что есть что-то лучше, чем наивное решение сохранить результаты в списке. Если так, извините за беспокойство!
Абдалла
Если вы думаете, что ваш вопрос сейчас спорный, может, стоит пометить его для удаления / закрытия?
Суреш Венкат
1
Любые два элемента в наборе будут несопоставимы, но это не означает, что наивное представление - лучшее, что вы можете сделать. Например, рассмотрим конечные мультимножества, упорядоченные по включению (= целые числа, упорядоченные с делимостью): существует большой потенциал для оптимизации, в зависимости от вашего представления данных (использование количества элементов, использование набора поддержки,…). Эти оптимизации будут сильно зависеть от характера отношения порядка. Кроме того, существует отдельный вопрос: стоит ли хранить информацию об удаленных элементах: будете ли вы часто сравнивать их с новыми добавлениями?
Жиль "ТАК - перестань быть злым"
Хорошо спасибо. Поэтому я добавил некоторую информацию (возможность целочисленного ограничения), которая может привести к оптимизации.
Абдалла

Ответы:

8

Статья «Сортировка и отбор в PoSets», написанная Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008, которая описывает динамическое представление PoSets на основе антицепей.

Возможно, вас также заинтересует опубликованная недавно на Arxiv статья «Сжатые позы», выпущенная Munro, Nicholson 2012, и библиография в ней. Их структура данных является статической, но я предполагаю, что следующим шагом будет создание динамической структуры данных.

Джереми
источник
О(1)О(1)О(QN)
Представление карт в виде (минимального) разложения цепей является хорошим пониманием. Сохранение этого инварианта с помощью удалений - вот что сложно.
Себастьян Граф
4

О(Л.Г.N)

jbapple
источник
1
Обратите внимание, что это охватывает только «древовидные» частичные порядки, например, встретить-полурешетки, где все элементы, меньшие или равные некоторому элементу, eобразуют цепь.
Себастьян Граф