Algorithmus gesucht

[volkard]

hustbaer schrieb:

Jetzt wäre ein Algorithmus gefragt, der schnell die Index-Union (Set-Union) von 100 Indexen (Sets) errechnen kann.

Als Bitfelder wären die Sets sie mehrer tausend Bits lang. Das macht keinen Spaß, fürchte ich. Eine Idee war, statt schlichter Bitfelder stattdessen Bloom-Filter u nehmen. Es stört den Algo ja nicht, wenn gelegentlich ein ganz selten false positive gefunden wird. Alle positives würden einfach langsam nochmal nachgestet, was durchschnittlich fast nichts kostet, weil sehr wenige positives zu erwarten sind. Aber Bloom-Filter gefallen mir nicht genug.
Ich lese gerade alle in Wikipedia gelisteten Datenstrukturen durch. Fastinierend, was sich in den letzten Jahren getan hat.

[hustbaer]

Ich hätte die Sets mal ganz naiv als sortierte Liste implementiert.
Bitfelder sind da sicher überhaupt nicht optimal, da sie immer gleich gross sind, egal wie viele Bits "gesetzt" sind.

[no_c0de]

hustbaer schrieb:

Ich hätte die Sets mal ganz naiv als sortierte Liste implementiert.
Bitfelder sind da sicher überhaupt nicht optimal, da sie immer gleich gross sind, egal wie viele Bits "gesetzt" sind.

dafür kann man die schön invertieren

[volkard]

Ich habe gleich Beispieldaten.
Format ist

maxlnu maxz
lnu lanz z z z z z...
lnu lanz z z z z z...
lnu lanz z z z z z...
...

lnu: Listennummer. Der Name der Liste.
lanz: Anzahl der Zahlen in dieser Liste
z: Eine Zahl in einer Liste
maxz: Größte vorkommende Zahl + 1
maxlnu: Größe Listennummer + 1
Es kommen alle Listennummern im spezifizierten Bereich vor.
Es kommen (höchst wahrscheinlich) alle Zahlen im spezifizierten Bereich vor.
Die Zahlen in jeder Liste sind aufsteigend sortiert.
Das sieht dann aus wie http://pastebin.com/xvzdY0th
Nur hab ich keinen Webspace. Mal schauen, wo man sowas uploaden kann. Wird groß, ich mache bis maxlnu=1Mio. Eigentlich sollten hoffentlich nur sehr sehr wenige disjunkte Listen-Paare vorkommen.

[volkard]

hustbaer schrieb:

Ich hätte die Sets mal ganz naiv als sortierte Liste implementiert.
Bitfelder sind da sicher überhaupt nicht optimal, da sie immer gleich gross sind, egal wie viele Bits "gesetzt" sind.

Kombiniert könnte ganz nett sein.
Die Sets brav als Listen. Aber das Merge-Ergebnis als Bitfeld.

[volkard]

hustbaer schrieb:

Das hat mich auf eine Idee gebracht...

Links
a[1,2,6]
b[2,4,6]
c[1,3,5]
d[1,7]

Rechts
e[3,4,5]
f[1,2,5]
g[1,5,6]
h[1,8]

Erstelle einen Index für jede Zahl, in der du die IDs der/Zeiger auf die rechten Listen ablegst, in der die Zahl vorkommt:

Ja, das ist erstmal billig.

hustbaer schrieb:

I1 = [f,g,h]
I2 = [f]
I3 = [e]
I4 = [e]
I5 = [e,f,g]
I6 = [g]
I7 = []
I8 = [h]

Das wären v Listen zu je n*m/v Elementen.

hustbaer schrieb:

Wenn du jetzt für die linke Liste a[1,2,6] suchen willst, kannst du die Index-Union (I1, I2, I6) machen. Wenn die Union nicht alle Listen enthält, sind die die fehlen die Treffer.
Union([f,g,h], [f], [g]) = [f,g,h] -> e fehlt -> Treffer

Also Index-Union von m Idizes.
Zu jedem Index gehörten nm/v Elemete.
Macht nm^2/v Operationen, um eine linke Liste gegen alle rechten Listen zu testen.
Und das muß man n mal machen.
Wäre n^2*m2/v.

Das Wichtigste ist, n^2 loszuwerden. Mit n^2 sieht man gar keine Sonne beim Versuch, die fette Datei zu checken.

[size > 1gb ? ram _ dis]

ist schon klar wiegroß die datei wird? scheint mir so als würd die größer als ein gig und damit nichtmehr in meinen ram passen

[volkard]

size > 1gb ? ram _ dis schrieb:

ist schon klar wiegroß die datei wird? scheint mir so als würd die größer als ein gig und damit nichtmehr in meinen ram passen

Supi. Die Datei hat nur 869M.

[hustbaer]

Hm. Also hast du n >> v > m?

Das ändert dann natürlich einiges.

Ich war davon ausgegangen dass v > n > m, glaube du hast irgendwas von n=4096, m=100 und v~~20000 geschrieben.

[volkard]

hustbaer schrieb:

Hm. Also hast du n >> v > m?
Das ändert dann natürlich einiges.
Ich war davon ausgegangen dass v > n > m, glaube du hast irgendwas von n=4096, m=100 und v~~20000 geschrieben.

Ja, tut mir leid. Die Zahlen haben sich geändert, weil ich Anfangs noch nicht die Übersicht hatte.
Solange es sicher erschien, daß es O(n^2*...) ist, war zum Untersuchen der großen Datei völlig unerheblich, wie groß n gewählt wird. Das Zerhacken in kleine 4096x4096-Fensterchen bringt da fast keinen Zeitverlust. Je größer n, desto seltener mußten Sachen wie Listen-Laden gemacht werden. 4096^2 schien so unglaublich groß, daß Laden oder Sortieren vernachlässigbar sind.
Wenn aber das böse n^2 fällt, drängt sich sofort auf, die Fenster so groß zu ziehen, wie der Speicher das erlaubt.
v ist in den Dateien nur 3635 und wird hoffentlich 10000 nie überschreiten. Das stimmt noch. m ist bei 200 und scheint ähnlich stabil wie v zu sein.

[volkard]

Die Dateien sind da.
http://rapidshare.com/files/411102117/10000a.rar.html
http://rapidshare.com/files/411104549/100000a.rar.html
http://rapidshare.com/files/411126077/1000000a.rar.html

[no_c0de]

volkard schrieb:

Die große kommt nach.

was hälts von sowas? da es ja eh nur "fake" listen sind um die performance des jeweiligen algos zu testen kann die sich ja jeder selbst generieren... mit den selben seeds bekommt auch jeder die gleiche liste raus

#include <stdio.h>
#include <stdlib.h>

#define CFG_FILE_NAME		"xxx"
#define CFG_FILE_EXT		".txt"

#define CFG_SEED_X			123456789
#define CFG_SEED_Y			362436069
#define CFG_SEED_Z			521288629
#define CFG_SEED_W			88675123

#define CFG_MAX_LNU			1000000

#define CFG_MIN_LANZ		1
#define CFG_MAX_LANZ		500

#define CFG_MIN_Z			1
#define CFG_MAX_Z			10000

int Random(void){
	static int x = CFG_SEED_X;
	static int y = CFG_SEED_Y;
	static int z = CFG_SEED_Z;
	static int w = CFG_SEED_W;
	int t;

	t = x ^ (x << 11);
	x = y; y = z; z = w;
	return w = w ^ (w >> 19) ^ t ^ (t >> 8);
}

int RandomRange(int start,int stop){
    return start+(Random()%(stop+1-start));
}

int FileGenerator(FILE *file){
	size_t lnu = 1;
	size_t lanz = 0;

	if(fprintf(file,"%d %d\n",CFG_MAX_LNU+1,CFG_MAX_Z+1)<0)
		return 1;

	for(;lnu<=CFG_MAX_LNU;lnu++){
		if(fprintf(file,"%d %d"
			,lnu
			,lanz = RandomRange(CFG_MIN_LANZ,CFG_MAX_LANZ)
		)<0){
			return 1;
		}
		while(lanz--){
			if(fprintf(file," %d",RandomRange(CFG_MIN_Z,CFG_MAX_Z))<0){
				return 1;
			}
		}
		if(fprintf(file,"\n")<0){
			return 1;
		}
	}

	return 0;
}

int main(void){
	char buffer[1024]={};
	int fileNumber = 0;
	FILE *file;

	while(1){
		if(fileNumber)
			sprintf(buffer,"%s_%d%s",CFG_FILE_NAME,fileNumber,CFG_FILE_EXT);
		else
			sprintf(buffer,"%s%s",CFG_FILE_NAME,CFG_FILE_EXT);

		file = fopen(buffer,"r");
		if(file){
			fclose(file);
			fileNumber++;
			if(fileNumber>999)
				return 1;
		}else
			break;
	}

	file = fopen(buffer,"wb");
	if(file){
		FileGenerator(file);
		fclose(file);
		return 0;
	}
	return 1;
}

dauert ca. einen kaffee bis es fertig ist 1.2 GB (1235615944 bytes)

[volkard]

no_c0de schrieb:

was hälts von sowas?

Das ist an sich eine prima Idee. Aber ich fürchte, meine Daten haben immer die Eigenschaften, die einen ärgern. Also bisher haben sie mich oft geärgert. Beim Überfliegen schien mir gerade, daß die in den Listen weiter hinten stehenden Zahlen wichtiger sind als die vorne. Das macht dann so Annahmen wie "Der Vergleich bricht bestimmt recht früh ab" vielleicht kaputt.

no_c0de schrieb:

da es ja eh nur "fake" listen sind um die performance des jeweiligen algos zu testen kann die sich ja jeder selbst generieren...

Ich habe keine fake-Listen hochgeladen. Es sind die echten. Aber auf nur 1Mio beschränkt, mehr habe ich nämlich noch gar nicht. Und die Listen sind auch noch unfertig, das heißt, es gibt noch disjunkte Listen, aber gar nicht viele. Das soll ja sein, damit man auch was zum Finden hat. Wenn ich zufällig alles richtig gemacht habe, sollten die beiden kleinen Dateien keine Disjunkten Listen aufweisen. Will man da was zum Finden haben, muß man sich in der Datei ein Paar per Hand disjuktivieren.

[??? ist leider bereits be]

volkard schrieb:

Die kleinen Dateien sind da.
http://rapidshare.com/files/411102117/10000a.rar.html
http://rapidshare.com/files/411102298/100000a.rar.html
Die große kommt nach.

Was ist das für ne Formatierung? Wo fängt was an?

[bitte danke]

volkard schrieb:

Ich habe gleich Beispieldaten.
Format ist

maxlnu maxz
lnu lanz z z z z z...
lnu lanz z z z z z...
lnu lanz z z z z z...
...

lnu: Listennummer. Der Name der Liste.
lanz: Anzahl der Zahlen in dieser Liste
z: Eine Zahl in einer Liste
maxz: Größte vorkommende Zahl + 1
maxlnu: Größe Listennummer + 1
Es kommen alle Listennummern im spezifizierten Bereich vor.
Es kommen (höchst wahrscheinlich) alle Zahlen im spezifizierten Bereich vor.
Die Zahlen in jeder Liste sind aufsteigend sortiert.
Das sieht dann aus wie http://pastebin.com/xvzdY0th
Nur hab ich keinen Webspace. Mal schauen, wo man sowas uploaden kann. Wird groß, ich mache bis maxlnu=1Mio. Eigentlich sollten hoffentlich nur sehr sehr wenige disjunkte Listen-Paare vorkommen.

[no_code]

aufgehts zu runde 2

== lol ==

#include <stdio.h>
#include <stdlib.h>

int main(int argc, char **argv){
	if(argc > 1){
		switch(argv[1][0]){
			case 't':
			case 'T':{
				int maxlnu;
				int maxz;
				int lnu;
				int lanz;
				int z;

				scanf("%d %d\n",&maxlnu,&maxz);

				while(maxlnu-->0){
					scanf("%d %d",&lnu,&lanz);
					while(lanz-->0){
						scanf(" %d",&z);
						printf("%d %d\n",z,lnu);
					}
					scanf("\n");
				}
			}break;
			case 'a':
			case 'A':{
				int a_num;
				int a_list;

				int b_num;
				int b_list;

				int ret;

				if(2!=scanf("%d %d\n",&a_num,&a_list))
					return 0;

				while(2==(ret=scanf("%d %d\n",&b_num,&b_list))){
					if(a_num == b_num){
						printf("%d\n%d\n",a_list,b_list);
						while(2==(ret=scanf("%d %d\n",&b_num,&b_list))){
							if(a_num == b_num){
								printf("%d\n",b_list);
							}else{
								a_num = b_num;
								a_list = b_list;
								break;
							}
						}
					}else{
						a_num = b_num;
						a_list = b_list;
					}
				}
			}break;
			case 'i':
			case 'I':if(argc > 2){
				int list;
				int llen;
				int l=0;
				FILE *fp = fopen(argv[2],"rb");
				if(fp){
					fscanf(fp,"%d",&llen);
					fclose(fp);
					scanf("%d\n",&list);
					for(;l<llen;l++){
						if(l == list)
							scanf("%d\n",&list);
						else
							printf("%d\n",l);
					}
				}
			}break;
		}
	}
	return EXIT_SUCCESS;
}

== ll ==

#!/bin/sh
cat $1 | ./lol t | sort -n | uniq | ./lol a | sort -n | uniq | ./lol i $1 > $2

== 10000a.txt ==

4 4
0 5 0 0 0 0 0
1 5 1 1 1 1 1
2 5 2 0 2 2 2
3 5 3 0 3 3 3

./ll 10000a.txt xy.txt

== xy.txt ==

1

[Tachyon]

Hmm, könnte man nicht alle Listen in einen Radix-Tree packen? Jeder Zweig der nur aus Knoten mit nur einem Kind besteht, würde dann eine einzigartige Liste darstellen. Das sollte dann O(m*n) → O(n) geben.

[no_code]

Tachyon schrieb:

Hmm, könnte man nicht alle Listen in einen Radix-Tree packen? Jeder Zweig der nur aus Knoten mit nur einem Kind besteht, würde dann eine einzigartige Liste darstellen. Das sollte dann O(m*n) → O(n) geben.

zeig doch mal code statt hier iwelche vermutungen aufzustellen...

@edit btw. dir ist schon klar das die mit abstand langsamste operation in meinem code der sort ist oder

[Tachyon]

no_code schrieb:

Tachyon schrieb:

Hmm, könnte man nicht alle Listen in einen Radix-Tree packen? Jeder Zweig der nur aus Knoten mit nur einem Kind besteht, würde dann eine einzigartige Liste darstellen. Das sollte dann O(m*n) → O(n) geben.

zeig doch mal code statt hier iwelche vermutungen aufzustellen...

@edit btw. dir ist schon klar das die mit abstand langsamste operation in meinem code der sort ist oder

Nichts für ungut, aber was isn das für ein Ton, hier?
Ich habe nur eine Idee gehabt. Um hier zu codieren, habe ich ehrlich gesagt nicht die Zeit. Außerdem traue ich Volkard durchaus zu, zu durchdringen, was ich im Groben meine.

PS: Außerdem funktioniert es so auch nicht.

[volkard]

Ich habe das ursprüngliche Verfahren eingetippt.

#include <iostream>
#include <fstream>
#include <vector>
#include <ctime>
using namespace std;

vector<vector<int>> liesListen(int minlnu,int maxlnu) {
	ifstream in("1000000a.txt");
	int dummy;
	in>>dummy>>dummy;
	vector<vector<int>> listen(maxlnu-minlnu);
	int lnu,lanz;
	while (in>>lnu>>lanz) {
		if (lnu>=maxlnu)
			break;
		if (lnu%1024==0) cout<<lnu<<'\r';
		for (int i=0;i<lanz;++i) {
			int z;
			in>>z;
			if (lnu>=minlnu)
				listen[lnu-minlnu].push_back(z);
		}
	}
	cout<<"          \r";
	return listen;
}

bool istDisjunkt(vector<int>& va,vector<int>& vb) {
	vector<int>::iterator ia=va.begin();
	vector<int>::iterator ib=vb.begin();
	while (ia!=va.end() && ib!=vb.end()) {
		if (*ia==*ib)
			return false;
		if (*ia<*ib)
			++ia;
		else
			++ib;
	}
	return true;
}

bool f(vector<vector<int>>& links,vector<vector<int>>& rechts) {
	for (size_t a=0;a<links.size();++a) {
		cout<<a<<'\r';
		for (size_t b=0;b<rechts.size();++b) {
			if (istDisjunkt(links[a],rechts[b])) {
				cout<<"Fund bei "<<a<<','<<b<<'\n';
				return true;
			}
		}
	}
	cout<<"          \r";
	return false;
}

//#define SOLLFINDEN

int main() {
#ifdef SOLLFINDEN
	cout<<"Lese linke Listen\n";
	vector<vector<int>> links=liesListen(860000,870000);
	cout<<"Lese rechte Listen\n";
	vector<vector<int>> rechts=liesListen(730000,740000);
#else
	cout<<"Lese linke Listen\n";
	vector<vector<int>> links=liesListen(0,10000);
	cout<<"Lese rechte Listen\n";
	vector<vector<int>> rechts=liesListen(0,10000);
#endif
	cout<<"Vergleiche Listen\n";
	clock_t start=clock();
	bool fund=f(links,rechts);
	clock_t end=clock();
	cout<<"Zeit: "<<(end-start)/double(CLOCKS_PER_SEC)<<'\n';
	cout<<"Ergebnis: "<<fund<<'\n';
	return 0;
}