Welche persistente Datenstruktur für eine Menge von teilweise geordneten Elementen?

Ich muss Sätze von Elementen vom Typ a speichern. Typ a ist teilweise geordnet, sodass der Vergleich von und kleiner, größer, gleich oder unvergleichbar sein kann. $a_1$ $a_2$

Ein Problem mit Hashtabellen besteht darin, dass zwei gleiche Elemente unterschiedlich dargestellt werden können und ich keinen Zugriff auf eine mit Gleichheit konsistente Hashfunktion habe.

Das Vergleichen von zwei Elementen kann ein langwieriger Prozess sein, daher wäre es interessant, Vergleiche zu minimieren. Bei Bedarf können Anrufe an den Vergleichsoperator gespeichert werden. Mir ist jetzt klar, dass ich nur Antichains aufbewahren muss (oder nehmen wir es an). Genauer gesagt, sind die Operationen, die ich ausführen muss, wie folgt:

Entferne ein Element von der Kette.
Versuchen Sie, ein Element hinzuzufügen. Wenn das Element kleiner als ein Element ist, fügen Sie es nicht hinzu. Andernfalls fügen Sie es hinzu und entfernen Sie jedes Element, das kleiner als es ist.

Ich kann auch jedes Element durch zwei ganze Zahlen binden. Wenn ich also weiß, dass und , dann gibt mir das , dass sofort . Natürlich bedeutet nicht ... Das Finden von Ganzzahlgrenzen ist im Vergleich zu einem vollständigen eine relativ kostengünstige Operation. $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
quelle

Ich denke, wir müssen mehr wissen, um Ihre Frage intelligent zu beantworten. Speichern Sie die Elemente und die Teilreihenfolge ist einfach zu berechnen? Oder speichern Sie die Teilbestellung auch in einer Art Nachschlagetabelle? Wie wollen Sie die Teilbestellung nutzen? Hoffen Sie, dass Sie es genauso verwenden, wie die lineare Reihenfolge zum Speichern von Mengen verwendet wird (z. B. in Suchbäumen)?

Andrej Bauer

Nachdem mir klar wurde, dass ich nur Antichains haben werde, bin ich mir nicht sicher, ob es etwas Besseres gibt als die naive Lösung, die Ergebnisse in einer Liste zu speichern. Wenn ja, entschuldigen Sie die Mühe!

Abdallah

Wenn Sie der Meinung sind, dass Ihre Frage jetzt unbeantwortet ist, sollten Sie sie möglicherweise zum Löschen / Schließen markieren.

Suresh Venkat

Zwei beliebige Elemente in der Menge sind unvergleichlich, dies bedeutet jedoch nicht, dass die naive Darstellung das Beste ist, was Sie tun können. Betrachten Sie beispielsweise endliche Multisets, die nach Inklusion geordnet sind (= ganze Zahlen, die nach Teilbarkeit geordnet sind): Abhängig von Ihrer Datendarstellung (unter Verwendung der Kardinalität, unter Verwendung des Unterstützungssatzes, ...) besteht ein großes Optimierungspotenzial. Diese Optimierungen hängen stark von der Art des Auftragsverhältnisses ab. Dann gibt es die separate Frage, ob es sich lohnt, Informationen über jetzt gelöschte Elemente aufzubewahren: Werden Sie sie häufig mit neuen Elementen vergleichen?

Gilles 'SO- hör auf böse zu sein'

OK danke. Daher habe ich einige Informationen hinzugefügt (die Möglichkeit der Ganzzahlbegrenzung), die zu Optimierungen führen können.

Abdallah

Antworten:

Die Arbeit "Sorting and Selection in PoSets" von Daskalakis, Karp, Mossel, Risensefield, Verbin, 2008 beschreibt eine dynamische Darstellung von PoSets auf der Basis von Antichains.

Möglicherweise interessieren Sie sich auch für die Veröffentlichung "Succinct Posets" von Munro, Nicholson, 2012, die kürzlich auf Arxiv veröffentlicht wurde, und für die darin enthaltene Bibliographie. Ihre Datenstruktur ist statisch, aber ich gehe davon aus, dass der nächste Schritt eine dynamische Datenstruktur ist.

Jeremy
quelle

Sortieren und Selektieren in Posets ist großartig, um eine Vorstellung davon zu bekommen, was für eine Datenstruktur benötigt wird, aber die Algorithmen setzen voraus, dass Elemente im Poset mit markiert sind (z. B. genau das Problem, das wir im ersten Schritt lösen möchten) place!), um die Beziehung zwischen zwei Elementen in ) zu berechnen, nachdem die Datenstruktur in Abfragen aufgebaut wurde. Das Papier geht also davon aus, dass Abfragen der Beziehung zwischen zwei Elementen teuer und das Abbilden von Elementen von Posets trivial sind, wohingegen Kartendatenstrukturen normalerweise das Gegenteil von ersteren annehmen, um letztere zu lösen.

O (1)

$\mathcal{O}(1)$

O (1)

$\mathcal{O}(1)$

O (q n)

$\mathcal{O}(qn)$

Sebastian Graf

Karten als (minimale) Zerlegung von Ketten darstellen zu lassen, ist ein guter Einblick. Es ist jedoch schwierig, diese Invariante durch Löschen beizubehalten.

Sebastian Graf

Haben Sie sich Heeringa et al. "Suchen in dynamischen baumartigen Teilordnungen" angesehen ? Sie geben eine dynamische Datenstruktur für das Vorgängerproblem auf Posets an. Es ist für einen RAM ausgelegt, aber Sie können Arrays als ausgeglichene Binärbäume darstellen und nur einen multiplikativen -Overhead verursachen, während die Struktur rein funktional ist. $O(\lg n)$

Apfel
quelle

Beachten Sie, dass dies nur 'baumartige' Teilaufträge abdeckt, z. B. Meet-Semilattices, bei denen alle Elemente, die kleiner oder gleich einem Element esind, eine Kette bilden.

Sebastian Graf