Algorithmus gesucht

[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;
}