Jaka trwała struktura danych dla zestawu częściowo uporządkowanych elementów?

Muszę przechowywać zestawy elementów typu a. Typ a jest częściowo uporządkowany, więc porównanie i może zwrócić mniejsze, większe, równe lub nieporównywalne. $a_1$ $a_2$

Jednym z problemów z tablicami skrótów jest to, że dwa równe elementy mogą być reprezentowane w różny sposób i nie mam dostępu do funkcji haszującej zgodnej z równością.

Porównywanie dwóch elementów może być długim procesem, dlatego interesujące byłoby zminimalizowanie porównań. W razie potrzeby można zapamiętać połączenia z operatorem porównania. Teraz zdaję sobie sprawę, że będę musiał przechowywać tylko antichains (lub załóżmy, że tak). Dokładniej, operacje, które będę musiał wykonać, są następujące:

Usuń element z antichain;
Spróbuj dodać element. Jeśli element jest mniejszy niż element, nie dodawaj go, w przeciwnym razie dodaj go i usuń każdy element mniejszy niż element.

Mogę również powiązać każdy element dwiema liczbami całkowitymi, więc jeśli wiem, że i , to znajomość natychmiast daje mi . Oczywiście, nie oznacza ... Znalezienie granic całkowitych jest względnie tanią operacją w porównaniu do porównania pełnego elementu. $i_1 < a < i_2$ $i_3 < b < i_4$ $i_2 < i_3$ $a < b$ $i_2 \not< i_3$ $a \not < b$

ds.data-structures functional-programming sorting Abdallah
źródło

Myślę, że musimy wiedzieć więcej, aby inteligentnie odpowiedzieć na twoje pytanie. Czy przechowujesz elementy, a częściowa kolejność jest łatwa do obliczenia? A może przechowujesz częściową kolejność w jakiejś tabeli odnośników? Jak zamierzasz skorzystać z częściowego zamówienia? Czy chcesz używać go w ten sam sposób, w jaki do przechowywania zestawów używana jest kolejność liniowa (na przykład w drzewach wyszukiwania)?

Andrej Bauer,

Teraz, gdy zdałem sobie sprawę, że będę mieć tylko antichains, nie jestem pewien, czy istnieje coś lepszego niż naiwne rozwiązanie przechowywania wyników na liście. Jeśli tak, przepraszamy za kłopoty!

Abdallah

Jeśli uważasz, że twoje pytanie jest teraz dyskusyjne, może powinieneś zgłosić je do usunięcia / zamknięcia?

Suresh Venkat

Wszelkie dwa elementy w zestawie będą nieporównywalne, ale to nie znaczy, że naiwna reprezentacja jest najlepsza, co możesz zrobić. Rozważmy na przykład skończone multisety uporządkowane według włączenia (= liczby całkowite uporządkowane z podzielnością): istnieje duży potencjał optymalizacji w zależności od reprezentacji danych (przy użyciu liczności, przy użyciu zestawu wsparcia,…). Te optymalizacje będą silnie zależeć od charakteru relacji zamówienia. Następnie jest osobna kwestia decydowania, czy warto zachować informacje o usuniętych elementach: czy zamierzasz często porównywać je z nowymi dodatkami?

Gilles 'SO - przestań być zły'

Ok dziękuję. Dodałem więc trochę informacji (możliwość ograniczenia liczb całkowitych), które mogą prowadzić do optymalizacji.

Abdallah

Odpowiedzi:

Artykuł „Sorting and Selection in PoSets” autorstwa Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008, który opisuje dynamiczną reprezentację PoSets w oparciu o antichains.

Być może zainteresuje Cię także artykuł „Succinct Posets” Munro, Nicholson, 2012, opublikowany niedawno w Arxivie oraz zawarta w nim bibliografia. Ich struktura danych jest statyczna, ale zakładam, że następnym krokiem jest posiadanie dynamicznej struktury danych.

Jeremy
źródło

Sortowanie i selekcja w pozycjach jest świetna, aby dowiedzieć się, co jest potrzebne do struktury danych, ale algorytmy zakładają otagowanie

elementów w zestawie (np. Dokładnie problem, który chcemy rozwiązać w pierwszej kolejności!), Aby obliczyć relację między dwoma elementami w

po zbudowaniu struktury danych w zapytaniach

. Zatem w artykule zakłada się, że relacje między dwoma elementami są drogie, a elementy odwzorowujące posety są trywialne, podczas gdy struktury danych map zwykle zakładają odwrotność pierwszego z nich, aby rozwiązać drugi.

O (1)

$\mathcal{O}(1)$

O (1)

$\mathcal{O}(1)$

O (q n)

$\mathcal{O}(qn)$

Sebastian Graf

Posiadanie map reprezentowanych jako (minimalny) rozkład łańcuchów jest dobrym wglądem. Zachowanie tego niezmiennika poprzez usuwanie jest jednak trudne.

Sebastian Graf

Czy spojrzałeś na „Wyszukiwanie w dynamicznych częściowych zamówieniach podobnych do drzewa” ? Dają dynamiczną strukturę danych dla problemu poprzednika dotyczącego zestawów. Jest przeznaczony do pamięci RAM, ale możesz reprezentować tablice jako zrównoważone drzewa binarne i ponosić tylko zwielokrotniony narzut jednocześnie czyniąc strukturę czysto funkcjonalną. $O(\lg n)$

jbapple
źródło

Zauważ, że obejmuje to tylko częściowe „drzewiaste” zamówienia, np. Spotkania semilattices, w których wszystkie elementy mniejsze lub równe niektórym elementom etworzą łańcuch.

Sebastian Graf,