Algorithmus gesucht

volkard

m2l schrieb:

volkard schrieb:
für alle rechten Listen //n-mal
  possible=alleNamenVonLinks=[a,b,c] //billig
  Liste (zb d[3,4,5]) nehmen und die passenden Values (hier [c,b]) aus possible wegstreichen
  //m Nachgucker zu O(1) bei Hashtable 
  //und da jede Zahl in fast jeder Liste ist, pro Nachgucker n Streichungen
  Wenn was übrig bleibt 
    Das ist ein Fund.
Macht O(n*n*m)
Das hatte ich Anfangs schon, nur einfacher zu implementieren.
Aber m Nachgucker mit n Streichungen ist doch relativ unrealistisch, weil es insgesamt nur n Streichungen gibt, also wäre possible schnell leer.

Ja, aber das ist, fürchte ich, das gleiche Argument, das beim Ursprungsalgo auch zieht.
Hier: Sobald possible ganz leer ist, kann ich frühzeitig aus dieser Schleife raus. Das passiert schlimmstenfalls erst ganz zum Schluß. Aber normalerweise schon viel früher, gerne schon in den ersten 10%.
Dort: Sobald zwei Listen einen Gleichen haben, kann ich frühzeitig aussteigen. Das passiert schlimmstenfalls erst ganz zum Schluß. Aber normalerweise schon viel früher, gerne schon in den ersten 10%.

volkard

knivil schrieb:

Bei der jetzigen Darstellung wirst du wohl jede Liste mit jeder anderen vergleichen muessen.

Das Erstellen der Listen dauert sehr lange und geschieht durch mich. Ich kann sie problemlos als doppelt verkettete Listen, als Bäume, als Hashtables oder was auch immer darstellen. Auch Dancing_Links, wenn das passen würde.

knivil schrieb:

Wie sieht denn das uebergeordnete Problem aus? Es scheint eine Variation von http://en.wikipedia.org/wiki/Exact_cover zu sein, nur ohne "excat". Dafuer gibt es z.B. http://en.wikipedia.org/wiki/Dancing_Links .

Tut nichts zur Sache, glaube ich. Das würde nur die Diskussion umwerfen. Vor dem ersten edit suchte ich nach dem Maximum der Minima aller möglichen Links-Rechts-Schnittmengen, aber die neue Frage fühlt sich schneller und einfacher an und läßt sich nachher überführen.

Ich habe vorher Zeit um Listen zum Beispiel in anderes Format zu bringen. Ich habe nachher Zeit zum Auswerten. Entführten Algorithmen gebe ich auch eine Chance, wenn die Übersetzung nicht ganz plem ist. Angenommen, SeppJs allgemeines Verfahren, aus n Mengen zwei disjunkte Mengen herauszufinden, wäre prinzipiell schnell. Dann würde ich einfach zwei Zahlen dl und dr basteln, die noch nirgends vorkommnen, allen linken Listen dl zufügen, allen rechten Listen dr zufügen und das Verfahren abfeuern. Falls es disjunkte Mengen findet, sind sie auomatisch auch auf verschiedenen Seiten.

Damit ist die Ausweichfrage aufgemacht worden: Wie findet man n Mengen zu m Elementen zwei disjunkte Mengen raus? Und braucht man O(n^2*m) Zeit? Das hat zwar weniger Einschränkungen als die Ausgangfrage und ist damit potenziell lahmer, aber supi googlebar, was ich jetzt mal machen werde.

volkard schrieb:

...
Zwischenlisten:

1:a,c         1:e,f 
2:b,c         2:d,e 
4:a           4:d 
5:b           5:e,f 
6:a,b,c       6:d,f

ich meinte das eher als eine liste, in etwa

1:a,c,e,f 
2:b,c,d,e 
4:a,d 
5:b,e,f 
6:a,b,c,d,f

bzw

1:a
1:c
1:e
1:f 
2:b
2:c
2:d
2:e 
4:a
4:d 
5:b
5:e
5:f 
6:a
6:b
6:c
6:d
6:f

aber ich glaube am resultat aendert es nicht allzuviel.

Bei ungefähr 20000 Zahlen kommen auf jede Liste 20000/4096=50 Zahlen
und das macht 2500 Paare und das *20000 = 50Mio.
Im Gegensatz zu am Anfang ca 80Mio schnelleren Operationen kein Gewinn.

ich wuste nicht welche range "m" bei dir hat, ich haette gedacht es gibt wenig ueberlappungen und dann waere es ein sehr sparsames ueber-ein-array-gehen und nur wirklich die konflicktstellen auszumaskieren.

btw. pro zeile der matrix ein counter als ++

SeppJ

In welchem Bereich liegen die Zahlen eigentlich?

Falls es eine bekannte Obergrenze gibt und diese nicht zu groß ist, könnte man für jede Liste ein Bitset anlegen und diese dann verUNDen.

volkard

SeppJ schrieb:

In welchem Bereich liegen die Zahlen eigentlich?
Falls es eine bekannte Obergrenze gibt und diese nicht zu groß ist, könnte man für jede Liste ein Bitset anlegen und diese dann verUNDen.

Ich rechne so mit 20000, kann mir kaum mehr als 30000 vorstellen, als Länge der Bitsets. Da klingt std::set_intersection schon lecker.

SeppJ

volkard schrieb:

SeppJ schrieb:

In welchem Bereich liegen die Zahlen eigentlich?
Falls es eine bekannte Obergrenze gibt und diese nicht zu groß ist, könnte man für jede Liste ein Bitset anlegen und diese dann verUNDen.

Ich rechne so mit 20000, kann mir kaum mehr als 30000 vorstellen, als Länge der Bitsets. Da klingt std::set_intersection schon lecker.

Ok, hatte zwar auf so etwas wie 128 als Obergrenze gehofft, aber 30000 geht ja eigentlich auch noch.

Doch, oh weh! Es sind n*m mäßig teure Operationen zum Berechnen der Sets und ((n/2)^2 * Obergrenze) ziemlich billige Vergleichsoperationen (wobei man hiervon sehr viele einsparen kann durch frühzeitiges Abbrechen). Klingt so betrachtet eigentlich nicht ganz so gut wie vor einer Stunde als ich die Idee hatte.

volkard

SeppJ schrieb:

Doch, oh weh! Es sind n*m mäßig teure Operationen zum Berechnen der Sets und ((n/2)^2 * Obergrenze) ziemlich billige Vergleichsoperationen (wobei man hiervon sehr viele einsparen kann durch frühzeitiges Abbrechen). Klingt so betrachtet eigentlich nicht ganz so gut wie vor einer Stunde als ich die Idee hatte.

Die Vergleichsoperationen mit 20000 langen Bitsets ist eben nicht soo billig. Obwohl, 20000/64=313 Verglichen mit der Alternative http://www.cplusplus.com/reference/algorithm/set_intersection/
Es wäre hier nicht von Bedeutung. Das miese ((n/2)^2) würde ich gerne tot haben.

SeppJ

Man müsste irgendeine Vergleichsoperation definieren, die komplett disjunkte Mengen als gleich ansieht. Dann könnte man mit Sortieralgorithmen auf n*log(n) als Vorfaktor kommen, indem man die Listen nach ihrer Ungleichheit sortiert. Das Problem ist, dass man dazu auch noch strenge schwache Ordnung braucht. Und da hakt es bei mir. Vermutlich geht das gar nicht. Ich werde nochmal ein bisschen drüber nachdenken, vielleicht gibt es ja ein geniales Vergleichkriterium, welches alles erfüllt oder ein einsichtiges Argument, warum es so etwas nicht geben kann.

edit: Ok, das einleuchtende Gegenargument ist natürlich, dass bei einer solchen Ordnung A<A gelten würde, aber auch A>A.
Und wenn man nach Ähnlichkeit sortiert, kommst man auch schnell auf Gegenbeispiele.

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.