Algorithmus gesucht

Jester

life schrieb:

"Lokalisiere die Range an rechten Listen, die x_1 enthält => O(log n) binäre Suchschritte"
Wie soll das gehen?

Beispiel:
x_1 := 5, right_lists = [ [1,5,9], [2,6,9], [3,5,8] ]
Damit ist die "Range" an rechten Listen, die x_1 enthält:
[0,0] \cup [2,2]

Klingt für mich nicht sehr nach log(n) Aufwand, sondern eher nach O(n)..

wahh, stimmt. das funktioniert nur, wenn man ne identische Liste sucht. Für eine Subliste klappts nicht.

wer bringt mal bischen code an start?

no_code

also hier mal mein versuch

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

/////////////////////////////////////////////
//              rnd
/////////////////////////////////////////////

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

/////////////////////////////////////////////
//              Bitfield
/////////////////////////////////////////////

typedef struct _bitfield_t{
    char *data;
    size_t length;
}bitfield_t;

bitfield_t Bitfield(size_t length){
    bitfield_t x;

    x.data = calloc(length,sizeof(*x.data));
    x.length = x.data ? length : 0;

    return x;
}

void BitfieldMark(bitfield_t list,size_t index){
    list.data[index] = 1;
}

void BitfieldClear(bitfield_t list){
    size_t l = list.length;

    while(l--)
        list.data[l] = 0;
}

void BitfieldInvert(bitfield_t list){
    size_t l = list.length;

    while(l--)
        list.data[l] = !list.data[l];
}

void BitfieldPlot(bitfield_t list){
    size_t l = list.length;
    while(l--)
        printf("%d,%d\n",l,list.data[l]);
}

void BitfieldFree(bitfield_t list){
    free(list.data);
}

/////////////////////////////////////////////
//              List
/////////////////////////////////////////////

typedef struct _list_entry_t{
    int num;
    int list;
}list_entry_t;

typedef struct _list_t{
    list_entry_t *data;
    size_t length;
}list_t;

list_t List(size_t length){
    list_t x;

    x.data = calloc(length,sizeof(*x.data));
    x.length = x.data ? length : 0;

    return x;
}

void ListFill(list_t data){
    size_t l = data.length;
    int i = 0;
    while(l--){
        list_entry_t buffer = {
            .num = RandomRange(3,50)
            ,.list = (i++>3?i=0:i)
        };
        data.data[l] = buffer;
    }
}

void ListPlot(list_t data){
    size_t l = data.length;
    while(l--){
        list_entry_t buffer = data.data[l];
        printf("%d,%d\n",buffer.num,buffer.list);
    }
}

void ListFree(list_t list){
    free(list.data);
}

/////////////////////////////////////////////
//              Calc
/////////////////////////////////////////////

int CalcSort( const void * a, const void * b){
    return ((list_entry_t *)b)->num - ((list_entry_t *)a)->num;
}

void CalcData(list_t a,list_t b,bitfield_t c){
    size_t al = a.length-1;
    size_t bl = b.length-1;

    qsort(a.data,a.length,sizeof *a.data,CalcSort);
    qsort(b.data,b.length,sizeof *b.data,CalcSort);

    while(1){
        if(a.data[al].num < b.data[bl].num){
            if(al--)
                continue;
        }else if(a.data[al].num > b.data[bl].num){
            if(bl--)
                continue;
        }else{
            BitfieldMark(c,a.data[al].list);
            BitfieldMark(c,b.data[bl].list);

            while(al-- && a.data[al+1].num == a.data[al].num){
                BitfieldMark(c,a.data[al].list);
            }
            while(bl-- && b.data[bl+1].num == b.data[bl].num){
                BitfieldMark(c,b.data[bl].list);
            }

            if(al-->0 && bl-->0)
                continue;
        }
        break;
    }
}

/////////////////////////////////////////////
//              Mod
/////////////////////////////////////////////

void ModInit(){
    srand(time(0));
}

void ModExec(){
    list_t a = List(10);
    list_t b = List(10);
    bitfield_t c = Bitfield(10);
    ListFill(a);
    ListFill(b);
    CalcData(a,b,c);
    printf("=== a ===\n");
    ListPlot(a);
    printf("=== b ===\n");
    ListPlot(b);
    printf("=== c ===\n");
    BitfieldPlot(c);
    ListFree(a);
    ListFree(b);
    BitfieldFree(c);
}

void ModExit(){

}

/////////////////////////////////////////////
//              Main
/////////////////////////////////////////////

int main(){
    ModInit();
    ModExec();
    ModExit();
    return 0;
}

buggy ungetestet und was weiß ich sonst noch für fehler drin, besonders die array grenzen sind sicher das ein oder andere mal überlaufen

|edit: bischen eben

Jester

Man kann zumindest die Zahlen normalisieren, d.h., man sortiert die vorkommenden zahlen und zählt wieviele verschiedene es gibt (nenne diese Zahl K), dann kann man leicht die Zahlen remappen auf den Bereich 0...K-1. Dabei gilt natürlich K<=n*m. Das funktioniert in O(n*m*log(n)*log(m)) Zeit. Danach funktioniert der Invertierungstrick und wir können also auch FINDSUBLIST lösen statt FINDDISJOINTLIST.

Mal weiter nachdenken, ob uns das irgendwie hilft. Vielleicht kann man mehrere Einträge zusammenkomprimieren oder ähnliches?

volkard

Jester schrieb:

Man kann zumindest die Zahlen normalisieren, d.h., man sortiert die vorkommenden zahlen und zählt wieviele verschiedene es gibt (nenne diese Zahl K), dann kann man leicht die Zahlen remappen auf den Bereich 0...K-1. Dabei gilt natürlich K<=n*m. Das funktioniert in O(n*m*log(n)*log(m)) Zeit.

Zufällig hier sogar kostenlos. Alle verschiedenen Zahlen (die Chancen stehen gut, daß es wenige tausend bleiben) stehen von Anfang an in einem Array, und daraus werden die Listen gebastelt. Ob ich Zahlen oder Arrayindizes speichere, ist egal.

Danach funktioniert der Invertierungstrick und wir können also auch FINDSUBLIST lösen statt FINDDISJOINTLIST.

Könntest Du mir das näher erläutern?

volkard

Ich glaube fast, ich habe den Invertierungstrick verstanden:

Ausgangslage:

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]

Die rechte Seite invertieren.
Zeit: O(n*m)

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

Die linke Seite sotieren.
Zeit: O(n*log(n)*m)

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

Jetzt die rechten nacheinander mit binärer Suche suchen.

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

Suchstring
e[1,2,6,7,8]

Fund bei a

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

Suchstring
f[3,4,6,7,8] 

Kein Fund

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

Suchstring
g[2,3,4,7,8] 

Kein Fund

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

Suchstring
h[2,3,4,5,6,7] 

Kein Fund

Zeit: O(n*log(n)*m)

Gesamtzeit: O(n*log(n)*m)

Klappt das denn wirklich?
Es basiert auf der Annahme, daß die Aussagen
"l1 und l2 haben kein gemeinsames Element"
und
"l1 ist vollständig in invert(l2) enthalten"
gleich sind.
Ja, das glaube ich mal.

Und auf der Annahme, daß ich vollständiges Enthaltensein
mit dieser binären Suche testen kann.
Nein, das glaube ich mal nicht.

Aber vielleicht hilft der Ansatz ja weiter.

edit:
Geht nicht einfach mit binärer Suche.

Nach dem Sortieren und Invertieren

Links:
a[1,2,6]
c[1,3,5]
d[1,7]
f[2,3,4,7]
g[2,3,4,5]
h[4,8]

Rechts:
e[2,3,4,6,8]

Jetzt finde ich nicht, daß h ganz in e enthalten ist.

hustbaer

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:

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

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

Worst-Case bringt das vermutlich nix, aber Average-Case könnte das vielleicht schon ganz OK sein.

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

Alternativ könnte man die Intersection der Invertierten Indexe/Sets berechnen. Idealerweise ohne die Indexe/Sets wirklich invertieren zu müssen, denn die invertierten Indexe/Sets wären ziemlich gross - was das Berechnen der Intersection vermutlich nicht gerade beschleunigen wird

Vielleicht bringt das ja irgend jemand auf Ideen.

p.S.: bitte nicht hauen falls dieser oder ein ähnlicher Vorschlag schon gekommen ist, oder es sich herausstellen sollte dass es doch nicht schneller ist als die Brute-Force Variante

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.

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.

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

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.