Algorithmus gesucht

volkard

Optimiza schrieb:

Du kannst nicht vielleicht so nett sein zu diesem Wettbewerb ein Beispielsatz an Datan hochzuladen und vielleicht welche Zeit deine CPU gebraucht hat?
Eine Referenzimplementation wäre natürlich , um Zeiten vergleichen zu können.

Leider nicht. Das Programm mag ich erst bauen, wenn ich in eine andere Komplexitätsklasse komme.

volkard schrieb:

Das Programm mag ich erst bauen, wenn ich in eine andere Komplexitätsklasse komme.

Geht das überhaupt? Muss man nicht im Worst Case immer alle Elemente mit allen vergleichen, um dann genau beim letzten festzustellen, dass es keine unterschiedlichen gibt?

volkard

m2l schrieb:

volkard schrieb:

Das Programm mag ich erst bauen, wenn ich in eine andere Komplexitätsklasse komme.

Geht das überhaupt? Muss man nicht im Worst Case immer alle Elemente mit allen vergleichen, um dann genau beim letzten festzustellen, dass es keine unterschiedlichen gibt?

Würde man zwei Gleiche suchen oder zwei Ungleiche, wäre es, glaube ich, sauschnell und sogar einfach. Oder zwei, die mindestens ein gemeinsames Element haben. Aber zwei, die kein gemeinsames Element haben, das fuckt mich total ab.

Vielleicht gabs den Vorschlag schon, ich versuche es mal:

Beispiel:

links           rechts
a [1 2 3]       x [1 4 5]
b [1 3 5]       y [2 3 5]
c [2 4 6]       z [1 3 5]

Hash table aufbauen für rechts (einmal jedes Element anfassen O(n*m))

h(1)    a b
h(2)    a c
h(3)    a b
h(4)    c
h(5)    b
h(6)    c

Hashoperationen schätze ich mit O(1) ab.

Jetzt die rechten Listen durchgehen und jeweils in die Tabelle gucken, mit welchen linken Listen es überdeckungen gibt:

x: h(1): a b   h(4): c  [ eigentlich hier schon fertig ]  h(5) b  --> keine disjunkte Menge
y: h(2): a c   h(3): a b [ eigentlich hier schon fertig ]  h(5) b  --> keine disjunkte Menge
y: h(1): a b   h(3): a b  h(5) b  --> y und c sind disjunkt

Hierfür müssen wir O(n*m) mal in die Tabelle gucken. Wie voll wird denn ein bucket? Wenn es weniger als O(n) ist, dann ist das gut. Wenn da O(n) oder mehr Elemente drin sind, bringt es nix.

knivil

Ja, den Vorschlag gab es auch schon.

Jester

Okay, neue Idee. Ich löse jetzt erst ein anderes Problem, dann löse ich mit dessen Hilfe das urpsrüngliche Problem ganz ineffizient und beschleunige es anschließend im letzten Schritt. (Wenn alles gut geht. ;))

Schritt 1:

Neues Problem FINDSUBLIST: Gesucht wird eine linke Liste, die vollständig in einer rechten Liste enthalten ist.

- Sortiere die linken und rechten Listen. => O(n*m*log(m)) Zeit.
- Sortiere die rechten Listen lexikographisch. => O(m*n*log(n)) Zeit.
- Führe für jede linke List (x_1,...,x_m) folgendes aus:
- Lokalisiere die Range an rechten Listen, die x_1 enthält => O(log n) binäre Suchschritte
- Lokalisiere in dieser Range die rechten Listen, die auch x_2 enthalten => O(log n) binäre Suchschritte
- usw. bis x_m

Ist die Endrange nicht leer, dann enthält sie gerade alle gültigen Listen. Die Laufzeit für den letzten Schritt ergibt sich wie folgt. Jeder binäre Suchschritt dürfte sich in O(log m) Zeit implementieren lassen. Damit ergibt sich für jedes x_i eine Laufzeit von O(log n* log m) und da wir das für jedes x_i jeder Liste einmal machen müssen insgesamt O(n*m*log n * log m) Zeit.

Soweit so gut, der theoretische Informatiker ist also angekommen, hat sich ein neues Problem definiert und es gelöst.

Schritt 2: Reduziere das ursprüngliche Problem FINDDISJOINTLIST auf FINDSUBLIST.

Das ist einfach. Wir tauschen einfach die rechten Listen gegen ihre Komplementlisten aus. Wirf den Algo aus Schritt 1 an und gib das Ergebnis zurück.

Laufzeit: oh weia, das taugt wirklich nur als theoretische Lösung. Da die Zahlen leider groß sind, sind die neuen rechten Listen riesig!

Schritt 3: (klappt das hier alles so?)

Implementiere die Invertierung der rechten Listen nur implizit durch Verwendung eines geeigneten Vergleichsoperators beim Sortieren und bei der binären Suche. Da Nachschauen ob ein Wert vorhanden oder nicht vorhanden ist beides in O(log m) Zeit geht, dürfte sich an der Laufzeitanalyse aus Schritt 1 nichts ändern.

Damit komme ich auf eine Gesamtlaufzeit von O(n*m*log(n)*log(m)) Zeit.

edit: evtl. kann man mit hashen sogar noch die log(m) wegsparen oder so.

knivil schrieb:

Ja, den Vorschlag gab es auch schon.

Und wo war das Problem?

SeppJ

Mups schrieb:

knivil schrieb:

Ja, den Vorschlag gab es auch schon.

Und wo war das Problem?

Gleiche Laufzeitklasse, wenn man genauer drüber nachdenkt.

life

"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)..

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.