3. Algorithmus gesucht

Algorithmus gesucht

  • R

    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.

    0
  • V

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

    0
  • J

    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?

    0
  • Mod

    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?

    0
  • V

    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.

    0
  • ?

    volkard schrieb:

    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.

    #include <iostream>
#include <vector>
#include <map>
#include <set>

int main()
{
	std::vector<std::vector<int>> l;
    std::vector<int> l1;
	l1.push_back(28);
	l1.push_back(9);
	l1.push_back(210);
	l1.push_back(211);
	l.push_back(l1);
	l1.clear();
	l1.push_back(2);
	l1.push_back(8);
	l1.push_back(6);
	l1.push_back(16);
	l.push_back(l1);

	std::vector<std::vector<int>> r;
    std::vector<int> r1;
	r1.push_back(8);
	r1.push_back(18);
	r1.push_back(6);
	r1.push_back(16);
	r.push_back(r1);
	r1.clear();
	r1.push_back(9);
	r1.push_back(15);
	r1.push_back(6);
	r1.push_back(10);
	r.push_back(r1);

	std::multimap<int,int> m;
	for(size_t i=0;i<l.size();i++)
	{
		for(size_t j=0;j<l[i].size();j++)
		{
			m.insert(std::make_pair(l[i][j],i));
		}
	}

	for(size_t i=0;i<r.size();i++)
	{
		std::set<int> possible;
		for(size_t k=0;k<l.size();k++)
		{
			possible.insert(k);
		}
		for(size_t j=0;j<r[i].size();j++)
		{
			std::multimap<int,int>::iterator iter = m.find(r[i][j]);
			while( iter != m.end() && iter->first == r[i][j])
			{
				possible.erase(iter->second);
				++iter;
			}
			if(possible.size() == 0)
			{
				break;
			}
		}
		if(possible.size() != 0)
		{
			for(size_t j=0;j<r[i].size();j++)
			{
				std::cout<<"r"<<i<<":";
				std::cout<<r[i][j];
				for(std::set<int>::iterator iter = possible.begin();iter!=possible.end(); ++iter)
				{
					std::cout<<" l"<<*iter<<":";;
					std::cout<<l[*iter][j];
				}
				std::cout<<"\n";
			}
		}
	}

}

    Mach mal ein Beispiel was du meinst.

    0
  • V

    SeppJ schrieb:

    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?

    Hast die Frage richtig verstanden.

    Gegenbeispiel:

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

    Deine Zwischenliste:

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

    Auch keine.

    0
  • V

    Jester schrieb:

    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?

    Oh, das ist aber eine feine Idee.
    Leider sind die Zahlen auch groß bis viele Milliarden.

    0
  • V

    m2l schrieb:

    ...

    Dein Code klappt bei den ersten beiden per Hand eingetippten Beispielen. Ich versuche mal, zu verstehen, was er macht...

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

    Erster verschachtelte Schleife: Umschreiben von L.
    //billig mit 2*n*m

    L:
    1:ac
    2:ab
    3:c
    4:b
    6:abc

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

    0
  • K

    Keine Ahnung, ob das schon genannt wurde: Iteriere ueber alle Zahlen der "linken" Haelfte und speichere sie in einer Hashtabelle mit der Information, in welchen Listen diese Zahl vorkommt. Fuer die rechte Haelfte nimmst du dir jede Liste vor und schaust fuer jede enthaltene Zahl, in welcher Liste der "linken" Haelfte sie enthalten ist. Wenn fuer alles Hashtabellen verwendet werden, dann sollte diese Datenstruktur die Laufzeit auf O(z) druecken, wobei z die Anzahl der Zahlen ist.

    0
  • L

    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.

    Ups. Dann fällt mir aber leider auch spontan keine Möglichkeit ein, die Laufzeit unter O(n^2*m) zu drücken. 😞

    0
  • V

    life schrieb:

    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.

    Ups. Dann fällt mir aber leider auch spontan keine Möglichkeit ein, die Laufzeit unter O(n^2*m) zu drücken. 😞

    Smiley-Strichliste bisher (ohne Quotes und Sigs):
    😕 : I
    😞 : IIII
    😃 : I

    0
  • M

    volkard schrieb:

    Gegenbeispiel:

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

    Deine Zwischenliste:

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

    Auch keine.

    Ich weiß nicht, ob du oder ich SeppJ richtig verstanden hat. Ich verstehe ihn Folgendermaßen:

    a -> bcdef
b -> acdef
c -> abdef
d -> abcef
e -> abcdf
f -> abcde

1. acef streicht mögliche Kandidaten in den jeweiligen Listen:
a -> bd
b -> acdef
c -> bd
d -> abcef
e -> bd
f -> bd

2. abe:
a -> d
b -> cdf
c -> bd
d -> abcef
e -> d
f -> bd

3. cd:
a -> d
b -> cdf
c -> b
d -> abef
e -> d
f -> bd

4. bd:
a -> d
b -> cf
c -> b
d -> aef
e -> d
f -> bd

5. def:
a -> d
b -> cf
c -> b
d -> a
e -> 
f -> b

6. abcf:
a -> d
b -> 
c -> 
d -> a
e -> 
f ->

    Also sind a und d disjunkt.

    0
  • V

    knivil schrieb:

    Keine Ahnung, ob das schon genannt wurde: Iteriere ueber alle Zahlen der "linken" Haelfte und speichere sie in einer Hashtabelle mit der Information, in welchen Listen diese Zahl vorkommt. Fuer die rechte Haelfte nimmst du dir jede Liste vor und schaust fuer jede enthaltene Zahl, in welcher Liste der "linken" Haelfte sie enthalten ist. Wenn fuer alles Hashtabellen verwendet werden, dann sollte diese Datenstruktur die Laufzeit auf O(z) druecken, wobei z die Anzahl der Zahlen ist.

    Ist wohl das von 02 Aug 2010 12:25?
    Das wäre dann meiner (hoffentlich richtigen) Abschätzung nach O(n^2*m).

    0
  • Mod

    volkard schrieb:

    SeppJ schrieb:

    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?

    Hast die Frage richtig verstanden.

    Gegenbeispiel:

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

    Deine Zwischenliste:

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

    Auch keine.

    Ok, das kann ich korrigieren:
    Man suche die Listen die niemals mit einer Liste aus der anderen Hälfte zusammen auftauchen.

    Mögliche Kombinationen bei diesem Beispiel: (a,d), (a,e), (a,f), (b,d), (b,e), (b,f), (c,d), (c,e), (c,f).
    Nach 1 bleiben: (a,d), (b,d), (b,e), (b,f), (c,d)
    Nach 2 bleiben: (a,d), (b,d), (b,f), (c,d)
    Nach 3 bleiben: (a,d), (b,d), (b,f)
    Nach 4 bleiben: (a,d), (b,f)
    Nach 5 bleiben: (a,d), (b,f)
    Nach 6 bleiben: (a,d)

    Jedoch wird es schon komplizierter, alle Tupel statt aller Einzellisten durchzugehen. Das gibt uns nämlich einen weiteren Faktor n, womit wir wieder bei O(n^2*m) sind 😞 . Außerdem ist es so nur eine andere Formulierung von m2ls Vorschlag (wenn ich diesen richtig verstanden habe).

    0
  • K

    Bei der jetzigen Darstellung wirst du wohl jede Liste mit jeder anderen vergleichen muessen. 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 .

    0
  • ?

    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.

    0
  • V

    Michael E. schrieb:

    Ich weiß nicht, ob du oder ich SeppJ richtig verstanden hat. Ich verstehe ihn Folgendermaßen:

    a -> bcdef
b -> acdef
c -> abdef
d -> abcef
e -> abcdf
f -> abcde

1. acef streicht mögliche Kandidaten in den jeweiligen Listen:
a -> bd
b -> acdef
c -> bd
d -> abcef
e -> bd
f -> bd

2. abe:
a -> d
b -> cdf
c -> bd
d -> abcef
e -> d
f -> bd

3. cd:
a -> d
b -> cdf
c -> b
d -> abef
e -> d
f -> bd

4. bd:
a -> d
b -> cf
c -> b
d -> aef
e -> d
f -> bd

5. def:
a -> d
b -> cf
c -> b
d -> a
e -> 
f -> b

6. abcf:
a -> d
b -> 
c -> 
d -> a
e -> 
f ->

    Also sind a und d disjunkt.

    Dann vestehst Du ihn richtig. Den Plan verstehe ich. Überzeugend einfach.

    Läßt sich sogar ein klein wenig tunen, wenn man statt

    a -> bcdef
b -> acdef
c -> abdef
d -> abcef
e -> abcdf
f -> abcde

    nur

    a -> def
b -> def
c -> def
d -> abc
e -> abc
f -> abc

    speichert.

    Oder gar nur

    def
a111
b111
c111

    1. acef streicht mögliche Kandidaten in den jeweiligen Listen:

    Also a streicht cef, c streicht aef, e streicht acf, f streicht ace. Hier ist ein O(n^2) drin. Und das pro vorkommender Zahl.

    Damit sind wir bei 02 Aug 2010 11:59

    Nochmal mir ein wenig Klarheit über die Zeit machen...

Ausgangslage:
a[1,2,6]   d[3,4,5] 
b[2,4,6]   e[1,2,5] 
c[1,3,6]   f[1,5,6] 
Hier stehen 2*n*m Zahlen. 

Umschichten

Zwischenlisten:
1:ac ef
2:ab e
3:c d
4:b d
5:d ef
6:abc f 
Hier stehen jetzt 2*n*m Buchstaben. Sie v die Anzahl der vorkommenden Zahlen. 
Dann stehen in jeder Zeile 2*n*m/v Zahlen. 
Davon links n*m/v und rechts n*m/v

Tabelle:
 def
a111
b111
c111

1. ac ef streicht mögliche Kandidaten in den jeweiligen Listen:
(n*m/v)*(n*m/v) Streichungen
a -> bd
b -> acdef
c -> bd
d -> abcef
e -> bd
f -> bd

2. usw.

Macht 
v*(n*m/v)*(n*m/v) Streichungen
=
n^2*m^2/v
=
n^2*m * m/v

Und ich hatte 
n^2*m

Ich fürchte, m wächst schneller als v. Die Version ist wohl sogar für kleine Listen schneller, 
wird aber später langsamer. :(
    0
  • V

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

    0
  • V

    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.

    0
Anmelden zum Antworten