Algorithmus gesucht

volkard

Ich habe links und rechts je n Listen zu je m Zahlen. In keiner einzelnen Liste kommen doppelte Zahlen vor.

Derzeit n=4096 und m=100.

Ich will feststellen, ob es eine linke und eine rechte Liste gibt, so daß die beiden kein gemeinsames Element haben.

Bisher mache ich das so, daß ich alle Listen sortiere, dann alle n^2 (derzeit 16Mio) Listenpaare vergleiche und pro Listenvergleich schlimmstenfalls ca 200 Integervergleiche brauche.

Geht das auch schneller?

no_code

also falls es sowas wie ein quiz ist hab ich keine ahnung. das einzige was mir einfallen würde/ich probieren würde wär sich die grenzen der listen zu merken(kleinste/größte zahl)? kommt natürlich dann auch auf die zahlen der listen an? dann könnte man evtl. den ein oder anderen vergleich früher abbrechen(liste skippen)

edit: naja also das hat man eigentlich eh schon durch die sortierung
edit2: also bei 2 sortierten listen je 409600 einträgen könnte man diese frage viel schneller beantworten, oder? lässt sich aus den einzellisten eine ganze machen?

no_code

kurz ich hab keinen plan

Liste mit möglichen ungleichen, map mit zahl zu liste -> aus Liste mit möglichen ungleichen streichen. Klar?

volkard

no_code schrieb:

also falls es sowas wie ein quiz ist hab ich keine ahnung.

Nein, kein quiz. Ich fürchte nur, ich bin gerade betriebsblind. Mir will nichts einfallen.

das einzige was mir einfallen würde/ich probieren würde wär sich die grenzen der listen zu merken(kleinste/größte zahl)? kommt natürlich dann auch auf die zahlen der listen an? dann könnte man evtl. den ein oder anderen vergleich früher abbrechen(liste skippen)

Leider nicht. Die Bereiche der Listen sind sehr ähnlich.

m wird langsam größer. Später habe ich m um 10000 zu erwarten.
edit: Das ist wohl falsch. m wird eher um 200, vielleicht auch 300 bleiben.

volkard

m2l schrieb:

Liste mit möglichen ungleichen, map mit zahl zu liste -> aus Liste mit möglichen ungleichen streichen.

m2l schrieb:

Klar?

Nein, habe den Plan nicht verstanden.

Ich bin mir nicht mal sicher ob ich alles verstanden habe, aber sind nicht Hashs ne Möglichkeit eine große Anzahl Bytes auf Gleichheit zu testen?

G hibbes

volkard

no_code schrieb:

edit2: also bei 2 sortierten listen je 409600 einträgen könnte man diese frage viel schneller beantworten, oder? lässt sich aus den einzellisten eine ganze machen?

Ja. 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.

Die Masterlisten aller vorkommenden Zahlen hätten nicht 2*4096*100 Einträge, sondern vielleicht so 20000 Zahlen. Von jeder Zahl hat man zu erwarten, daß sie in vielen Listen vorkommt.

Außerdem ist es sogar extrem unwahrscheinlich, daß eine linke und eine rechte Liste gibt, so daß die beiden kein gemeinsames Element haben. Meine Funktion wird also meistens mit false antworten. Das ist inhaltlich auch sehr toll, aber macht mir dafür auch ein paar einfache Optimierungen weg.

volkard

hibbes schrieb:

Ich bin mir nicht mal sicher ob ich alles verstanden habe, aber sind nicht Hashs ne Möglichkeit eine große Anzahl Bytes auf Gleichheit zu testen?

G hibbes

Ja. Wollte ich nur herausfinden, ob es eine linke und eine rechte Liste gibt, so daß die beiden Listen nur gleiche Elemente haben...
dann würde ich alle 2*4096 Listen schnell mal hashen. O(n*m) einfache Operationen. Und dann alle Listenvergleiche O(n^2), wobei ein Vegleich der ganzen Listenelemente nur gemacht werden muß, wenn die Hash-Werte schon gleich sind, also sehr selten.

ipsec

Nur eine fixe Idee: man bildet von jeder Liste jeweils die Summe und das Produkt aller enthaltenen Zahlen. Wenn ich mich jetzt nicht täusche, sollten beide Werte nur bei Listen mit gleichen enthaltenen Zahlen übereinstimmen (müsste man mal beweisen, auch in Hinblick auf die eventuellen Überläufe, sonst prüft man eben die wenigen übereinstimmenden Listen nochmal).
Dann muss man nur noch prüfen, ob für 2 Listen beide Werte übereinstimmen (dazu kann man z.B. die Summe-Produkt-Paare in eine weitere Liste packen, diese sortieren und dann prüfen).

Natürlich muss man auch nachmessen, ob die vielen Additionen und Multiplikationen nicht am Ende mehr Zeit brauchen.

volkard schrieb:

m2l schrieb:

Liste mit möglichen ungleichen, map mit zahl zu liste -> aus Liste mit möglichen ungleichen streichen.

m2l schrieb:

Klar?

Nein, habe den Plan nicht verstanden.

Du machst eine Map mit allen Zahlen (Key) die in allen Listen (rechts) sind und Value sind diese Listen.

Alle möglichen für Liste 1 (links) sind erst mal alle rechten.

Liste 1 (links) durchgehen, erste Zahl in Map suchen, treffer -> Value Listen aus "alle möglichen" streichen. usw. bis "alle möglichen" leer (-> keine ungleiche -> Liste 2 (links) durchgehen) oder Liste 1 (links) durchgegangen (->Treffer in alle möglichen).

SeppJ

Alle Zahlen in den Listen durchgehen. Eine Zahlenliste erstellen in der die Listen stehen in der die Zahlen vorkommen. Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

Ich hoffe das war jetzt nicht zu kompliziert beschrieben .

Das sollte O(m*n) sein. Ob das jetzt schneller ist als die Methode mit dem Sortieren bin ich nicht sicher, die Laufzeitberechnung dieses Verfahrens ist mir ein bisschen kompliziert (O(n*m*log(m)) ?). Nachteil meines Vorschlags ist, dass das Verfahren im Falle false nicht sofort abbricht, sondern erst wenn ein Großteil der Arbeit schon gemacht ist.

life

2 Ideen:

1. Definiere eine Ordnung über deine Listen und pack die Listen der rechte Seite in eine TreeMap . Anschließend schaue mittels contains , ob eine Liste der linken Seite in der rechten Seite vorkommt. Laufzeit: O(n * log(n) * m)

2. Berechne einen Hashwert für jede Liste und pack die Listen in eine HashMap . Anschließend schaue mittels contains , ob eine Liste der linken Seite in der rechten Seite vorkommt. Laufzeit je nach Anzahl der Kollisionen. Falls keine Kollisionen vorkommen, wohl sowas wie O(n * m).

Edit: Das initiale Sortieren der Listen sollte natürlich bestehen bleiben.

volkard

ipsec schrieb:

Nur eine fixe Idee: man bildet von jeder Liste jeweils die Summe und das Produkt aller enthaltenen Zahlen.

life schrieb:

2 Ideen:
1. Definiere eine Ordnung über deine Listen und pack die Listen der rechte Seite in eine TreeMap . Anschließend schaue mittels contains , ob eine Liste der linken Seite in der rechten Seite vorkommt. Laufzeit: O(n * log(n) * m)

2. Berechne einen Hashwert für jede Liste und pack die Listen in eine HashMap . Anschließend schaue mittels contains , ob eine Liste der linken Seite in der rechten Seite vorkommt. Laufzeit je nach Anzahl der Kollisionen. Falls keine Kollisionen vorkommen, wohl sowas wie O(n * m).

Edit: Das initiale Sortieren der Listen sollte natürlich bestehen bleiben.

Ich will nicht herausfinden, ob zwei der Listen alle Elemente gleich haben. Ich will herausfinden, ob zwei der Listen kein gleiches Element haben.

volkard

m2l schrieb:

volkard schrieb:

m2l schrieb:

Liste mit möglichen ungleichen, map mit zahl zu liste -> aus Liste mit möglichen ungleichen streichen.

m2l schrieb:

Klar?

Nein, habe den Plan nicht verstanden.

Du machst eine Map mit allen Zahlen (Key) die in allen Listen (rechts) sind und Value sind diese Listen.

Alle möglichen für Liste 1 (links) sind erst mal alle rechten.

Liste 1 (links) durchgehen, erste Zahl in Map suchen, treffer -> Value Listen aus "alle möglichen" streichen. usw. bis "alle möglichen" leer (-> keine ungleiche -> Liste 2 (links) durchgehen) oder Liste 1 (links) durchgegangen (->Treffer in alle möglichen).

Ich gehe davon aus, daß jede der überhaupt vorkommenden Zahlen in vielen Listen links und in vielen Listen rechts vorkommt. Dein Verfahren würde ausspucken, daß keine Zahl existiert, die in einer linken Liste aber in keiner rechten Liste vorkommt. Trotzdem kann es sein, daß eine linke Liste mit einer rechten Liste kein gemeinsames Element hat.

rapso

volkard schrieb:

Bisher mache ich das so, daß ich alle Listen sortiere, dann alle n*(n-1)/2 (derzeit 8386560) Listenpaare vergleiche und pro Listenvergleich schlimmstenfalls ca 200 Integervergleiche brauche.

Geht das auch schneller?

vermutlich waere es schneller wenn du alle zahlen (sammt herkunft, ich meine sowas wie std::pair<int,CSourceList*> )in ein vector steckst, sortierst und dann nur in der range von zahlen die sich gleichen die listen in einer matrix gegenseitig ausmaskierst (kannst dir den matrix-bitcount ja noch seperate speichern damit du spaeter die kandidaten fixer findest).

my2cent of my1min idea.

volkard

SeppJ schrieb:

Alle Zahlen in den Listen durchgehen. Eine Zahlenliste erstellen in der die Listen stehen in der die Zahlen vorkommen. Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

Ich hoffe das war jetzt nicht zu kompliziert beschrieben .

Wahrscheinlich nicht zu kompliziert. Aber mir scheint, es trifft dei Frage nicht.

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

Deine Zwischenliste:

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

Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

Keine.

Jester

volkard schrieb:

Ich will nicht herausfinden, ob zwei der Listen alle Elemente gleich haben. Ich will herausfinden, ob zwei der Listen kein gleiches Element haben.

Sind die vorkommenden Zahlen beliebig groß? Wenn nicht, kannst Du vielleicht Listen invertieren?

SeppJ

volkard schrieb:

SeppJ schrieb:

Alle Zahlen in den Listen durchgehen. Eine Zahlenliste erstellen in der die Listen stehen in der die Zahlen vorkommen. Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

Ich hoffe das war jetzt nicht zu kompliziert beschrieben .

Wahrscheinlich nicht zu kompliziert. Aber mir scheint, es trifft dei Frage nicht.
a[1,4,6]   d[2,4,6]
b[2,5,6]   e[1,2,5]
c[1,2,6]   f[1,5,6]
Deine Zwischenliste:
1:a,c,e,f
2:b,c,d,e
4:a,d
5:b,f
6:a,b,c,d,f
Die Zahlenliste durchgehen und gucken welche Listen immer nur einzeln in den Listenlisten vorkommen.

Keine.

Ist das nicht die Frage? Es gibt hier ja keine Listen ohne gemeinsames Element und genau das kam raus.

Oder habe ich die Frage falsch verstanden?

volkard

rapso schrieb:

vermutlich waere es schneller wenn du alle zahlen (sammt herkunft, ich meine sowas wie std::pair<int,CSourceList*> )in ein vector steckst, sortierst

Moment, ich probiers mal...

Ausgangsdaten:

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

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

und dann nur in der range von zahlen die sich gleichen

Jede Zahl wird links und rechts vorhanden sein.

die listen in einer matrix gegenseitig ausmaskierst (kannst dir den matrix-bitcount ja noch seperate speichern damit du spaeter die kandidaten fixer findest).

Die fülle ich zuerst mit 1

def
a111
b111
c111

und mache dann 0 überall, wo ein Paar aus den Zwischenlisten ist.

Die Paare:

ae af ce cf
bd be cd ce
ad
be bf
ad af bd bf cd cf

Nach dem Streichen:

def
a000
b000
c000

Aha. Nur noch Nullen.

Könnte glatt klappen.

Mal den Gewinn betrachten...

Ausgangsdaten:

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

//Einfaches Umschreiben. O(2*n*m)

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

und dann nur in der range von zahlen die sich gleichen

Jede Zahl wird links und rechts vorhanden sein.

die listen in einer matrix gegenseitig ausmaskierst (kannst dir den matrix-bitcount ja noch seperate speichern damit du spaeter die kandidaten fixer findest).

Die fülle ich zuerst mit 1
//Billig

def
a111
b111
c111

und mache dann 0 überall, wo ein Paar aus den Zwischenlisten ist.

//Ups, es gibt aber viele Paare. Mir scheint, das spart keine Arbeit,
//hat sie nur umgeschichtet.
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.

Wenn m größer wird, wächst meiner sublinear mit m (weil die Zahlen so dicht sind) und Deiner quadratisch mit der Anzahl verschiedener Zahlen und das sehr langsame Wachsen der Anzahl verschiedener Zahlen gleicht das wieder aus.

Ein Teufelskreis. Nette Idee.
Aber am Ausmaskieren der vielen Paare aus der Matrix hapert's. Ich sehe auch keinen kräftigen Schub durch bittwiddeling.