3. Algorithmus gesucht

Algorithmus gesucht

  • ?

    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.

    0
  • N

    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
    0
  • T

    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.

    0
  • N

    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 😕

    0
  • T

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

    0
  • V

    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;
}
    0
Anmelden zum Antworten