Algorithmus gesucht

mazal

Idee:

Annahme jede Liste liegt sortiert vor.

Du hast die linken Listen

L1 a_11, a_12, .. a_1m
..
Ln a_n1, a_n2, ...a_nm

verkette die linken Listen zu einem "String"

$ a_11 .. a_1m $ a_21 .. a_2m $ .. $ a_n1 .. a_nm $

$ ist ein Trenner der in keiner Liste vorkommt

Bis hier hin O( n*m), wenn ich annehme, dass Sortieren kostenlos ist.

Dann erstellst du ein Suffix-Array (dafür gibt es Linearzeit-Algorithmen)

Dann gehst du die rechen Listen durch baust dir einen String

$ a_i1 .. a_im $

Weil die Listen sortiert sind sehen sie falls sie gleiche Elemente enthalten in Stringform gleich aus.

Suchen mithilfe des Suffix-Arrays

kostet O( log (n*m))

Suchphase insgesammt also O ( n*( log (n*m)))

Damit, wenn ich mich alles täuscht O( n*m)

knivil

Ich hab's nicht verstanden ...

volkard

mazal schrieb:

Suffix-Array

Das klingt gut.

volkard

knivil schrieb:

Ich hab's nicht verstanden ...

Ich glaube, ich hab's.
Aus der Ausgangsaufgabe

a[1,2,6]   d[3,4,5] 
b[2,4,6]   e[1,2,5] 
c[1,3,6]   f[1,5,6]

"Sind hier ein linker und ein rechter disjunkt?", baue ich die neue Aufgabe

"Sind alle Strings 3450, 1250 und 1560 im String 126024601360 enthalten?".
Und kann deswegen auf ein reichhaltiges Angebot von Algorithmen zur Stringsuche zugreifen. http://en.wikipedia.org/wiki/String_searching_algorithm

Ähm, dann sehe ich doch nur, ob ein linker und ein rechter gleich sind? Das wollte ich gar nicht.
Verwirrt bin.

mazal

Oops dann hab ich dein Problem falsch verstanden

Der Algo soll nur false zurückgeben wenn links und rechts die gleichen listen stehen?

volkard

mazal schrieb:

Oops dann hab ich dein Problem falsch verstanden

Der Algo soll nur false zurückgeben wenn links und rechts die gleichen listen stehen?

Nein.

Wenn es zwei Listen gibt, wie

a[1,2,6]   d[3,4,5]

, die kein gemeinsames Element haben, dann soll er das melden.

Du kannst nicht vielleicht so nett sein zu diesem Wettbewerb ein Beispielsatz an Datan hochzuladen und vielleicht welche Zeit deine CPU gebraucht hat?
Eine Referenzimplementation wäre natürlich , um Zeiten vergleichen zu können.

Dankä

hustbaer

@volkard:
Ich hab zwar keinen Lösungsvorschlag, aber dafür Fragen

Brauchst du nur die Info ja/nein, oder auch das Paar/die Paare?
Und falls es mehr als nur ein Paar gibt, brauchst du alle Paare, oder nur ein beliebiges?

Und auf welchen Fall sollte optimiert werden - den dass kein Paar gefunden wird, oder den dass eines/mehrere Paare gefunden werden?

volkard

hustbaer schrieb:

@volkard:
Ich hab zwar keinen Lösungsvorschlag, aber dafür Fragen
Brauchst du nur die Info ja/nein, oder auch das Paar/die Paare?

(Letztendlich brauche ich alle Paare. Um diese Listen bzw die Listengenerierung überhaupt so zu verändern, daß bald keine Paare mehr existieren.)

Und falls es mehr als nur ein Paar gibt, brauchst du alle Paare, oder nur ein beliebiges?

(Letztendlich alle. Aber eins reicht erstmal vollkommen.)

Und auf welchen Fall sollte optimiert werden - den dass kein Paar gefunden wird, oder den dass eines/mehrere Paare gefunden werden?

Schon bald soll Generierung der Listen so gut sein, daß bei Hunderten von Programmläufen nur ein einziger überhaupt noch ein Paar aufweist. Wenn ein Lauf zufällig doch mal ein disjunktes Paar aufweist, kann ich das auch langsam suchen.
Falls ein Verfahren also zufällig ohne Geschwindigkeitsverlust eins oder alle Paare auswirft, ist das ein netter Bonus. Aber es ist nicht nötig.

volkard

Optimiza schrieb:

Du kannst nicht vielleicht so nett sein zu diesem Wettbewerb ein Beispielsatz an Datan hochzuladen und vielleicht welche Zeit deine CPU gebraucht hat?
Eine Referenzimplementation wäre natürlich , um Zeiten vergleichen zu können.

Leider nicht. Das Programm mag ich erst bauen, wenn ich in eine andere Komplexitätsklasse komme.

volkard schrieb:

Das Programm mag ich erst bauen, wenn ich in eine andere Komplexitätsklasse komme.

Geht das überhaupt? Muss man nicht im Worst Case immer alle Elemente mit allen vergleichen, um dann genau beim letzten festzustellen, dass es keine unterschiedlichen gibt?

volkard

m2l schrieb:

volkard schrieb:

Das Programm mag ich erst bauen, wenn ich in eine andere Komplexitätsklasse komme.

Geht das überhaupt? Muss man nicht im Worst Case immer alle Elemente mit allen vergleichen, um dann genau beim letzten festzustellen, dass es keine unterschiedlichen gibt?

Würde man zwei Gleiche suchen oder zwei Ungleiche, wäre es, glaube ich, sauschnell und sogar einfach. Oder zwei, die mindestens ein gemeinsames Element haben. Aber zwei, die kein gemeinsames Element haben, das fuckt mich total ab.

Vielleicht gabs den Vorschlag schon, ich versuche es mal:

Beispiel:

links           rechts
a [1 2 3]       x [1 4 5]
b [1 3 5]       y [2 3 5]
c [2 4 6]       z [1 3 5]

Hash table aufbauen für rechts (einmal jedes Element anfassen O(n*m))

h(1)    a b
h(2)    a c
h(3)    a b
h(4)    c
h(5)    b
h(6)    c

Hashoperationen schätze ich mit O(1) ab.

Jetzt die rechten Listen durchgehen und jeweils in die Tabelle gucken, mit welchen linken Listen es überdeckungen gibt:

x: h(1): a b   h(4): c  [ eigentlich hier schon fertig ]  h(5) b  --> keine disjunkte Menge
y: h(2): a c   h(3): a b [ eigentlich hier schon fertig ]  h(5) b  --> keine disjunkte Menge
y: h(1): a b   h(3): a b  h(5) b  --> y und c sind disjunkt

Hierfür müssen wir O(n*m) mal in die Tabelle gucken. Wie voll wird denn ein bucket? Wenn es weniger als O(n) ist, dann ist das gut. Wenn da O(n) oder mehr Elemente drin sind, bringt es nix.

knivil

Ja, den Vorschlag gab es auch schon.

Jester

Okay, neue Idee. Ich löse jetzt erst ein anderes Problem, dann löse ich mit dessen Hilfe das urpsrüngliche Problem ganz ineffizient und beschleunige es anschließend im letzten Schritt. (Wenn alles gut geht. ;))

Schritt 1:

Neues Problem FINDSUBLIST: Gesucht wird eine linke Liste, die vollständig in einer rechten Liste enthalten ist.

- Sortiere die linken und rechten Listen. => O(n*m*log(m)) Zeit.
- Sortiere die rechten Listen lexikographisch. => O(m*n*log(n)) Zeit.
- Führe für jede linke List (x_1,...,x_m) folgendes aus:
- Lokalisiere die Range an rechten Listen, die x_1 enthält => O(log n) binäre Suchschritte
- Lokalisiere in dieser Range die rechten Listen, die auch x_2 enthalten => O(log n) binäre Suchschritte
- usw. bis x_m

Ist die Endrange nicht leer, dann enthält sie gerade alle gültigen Listen. Die Laufzeit für den letzten Schritt ergibt sich wie folgt. Jeder binäre Suchschritt dürfte sich in O(log m) Zeit implementieren lassen. Damit ergibt sich für jedes x_i eine Laufzeit von O(log n* log m) und da wir das für jedes x_i jeder Liste einmal machen müssen insgesamt O(n*m*log n * log m) Zeit.

Soweit so gut, der theoretische Informatiker ist also angekommen, hat sich ein neues Problem definiert und es gelöst.

Schritt 2: Reduziere das ursprüngliche Problem FINDDISJOINTLIST auf FINDSUBLIST.

Das ist einfach. Wir tauschen einfach die rechten Listen gegen ihre Komplementlisten aus. Wirf den Algo aus Schritt 1 an und gib das Ergebnis zurück.

Laufzeit: oh weia, das taugt wirklich nur als theoretische Lösung. Da die Zahlen leider groß sind, sind die neuen rechten Listen riesig!

Schritt 3: (klappt das hier alles so?)

Implementiere die Invertierung der rechten Listen nur implizit durch Verwendung eines geeigneten Vergleichsoperators beim Sortieren und bei der binären Suche. Da Nachschauen ob ein Wert vorhanden oder nicht vorhanden ist beides in O(log m) Zeit geht, dürfte sich an der Laufzeitanalyse aus Schritt 1 nichts ändern.

Damit komme ich auf eine Gesamtlaufzeit von O(n*m*log(n)*log(m)) Zeit.

edit: evtl. kann man mit hashen sogar noch die log(m) wegsparen oder so.

knivil schrieb:

Ja, den Vorschlag gab es auch schon.

Und wo war das Problem?

SeppJ

Mups schrieb:

knivil schrieb:

Ja, den Vorschlag gab es auch schon.

Und wo war das Problem?

Gleiche Laufzeitklasse, wenn man genauer drüber nachdenkt.

life

"Lokalisiere die Range an rechten Listen, die x_1 enthält => O(log n) binäre Suchschritte"
Wie soll das gehen?

Beispiel:
x_1 := 5, right_lists = [ [1,5,9], [2,6,9], [3,5,8] ]
Damit ist die "Range" an rechten Listen, die x_1 enthält:
[0,0] \cup [2,2]

Klingt für mich nicht sehr nach log(n) Aufwand, sondern eher nach O(n)..

Jester

life schrieb:

"Lokalisiere die Range an rechten Listen, die x_1 enthält => O(log n) binäre Suchschritte"
Wie soll das gehen?

Beispiel:
x_1 := 5, right_lists = [ [1,5,9], [2,6,9], [3,5,8] ]
Damit ist die "Range" an rechten Listen, die x_1 enthält:
[0,0] \cup [2,2]

Klingt für mich nicht sehr nach log(n) Aufwand, sondern eher nach O(n)..

wahh, stimmt. das funktioniert nur, wenn man ne identische Liste sucht. Für eine Subliste klappts nicht.

wer bringt mal bischen code an start?