Hash table - running time > 600sec

flank

Hallo zusammen,

ich bin relativ neu im Programmieren mit C++. Für ein Assignement meiner Uni habe ich mich mit Hash tables auseinander gesetzt und ein funktionierendes Programm erstellen können. Das ganze Programm wird getestet mit g++ -o main.out -std=c++11 -O2 -Wall main.cpp. Insgesamt gibt es hundert Testfälle bspw:
For input Aasd Aasd Dasd Dasd Aasd Asd Asd Dsd Ad
Output shouldbe asd d
A kennzeichnet Insertion, D Deletion. Es handelt sich um eine Reihe von maximal 26 Wörtern.

Nun zu meinem Problem, wenn ich die Testfälle einzeln teste habe ich kein Problem, jedoch wenn das Programm die 100 Testfälle automatisch prüft komme ich auf über 600 Sekunden und der Testlauf wird abgebrochen. Dies ist eine Vorgabe der Uni und kann somit nicht verändert werden. Zudem sollten 100 Testfälle keine 600 Sekunden benötigen

Da das erst mein drittes Programm in C++ ist hänge ich den Code einmal an. Er ist mit Sicherheit etwas wild, aber das schiebe ich auf meine ausbaubaren C++ Kenntnissen. Evtl. hat jemand eine Idee, wo mein Fehler liegt.

#include <malloc.h>
#include <stdio.h>
#include <iostream>
using namespace std;

struct htable_item{
    string *key;
    int table_slot;
};

char hashValue(string str){
    return str[str.length()-1];
}

int search(string key,struct htable_item *table){
    char c=hashValue(key);
    int index=(int)c-97;
    int init=-1;
    struct htable_item *item;
    if(table[index].key->compare(key)==0){
        return index;
        //found
    }
    else{
        item=&table[index];
        if(item->table_slot==-1){
            return -1; // definitely not found .
        }
    else{
        while(init!=index){
                if((item->table_slot==1 && item->key->compare(key)!=0) || (item->table_slot==0) || item->table_slot==-1){
                    if(init==-1) init=index;
                        index=(index+1)%27;
                        item=&table[index];
                    }
                else if(item->key->compare(key)){
                    return index;
                }
            }   
        }
    }
    return -1;
}

void remove(string key,struct htable_item *table){
    int index=search(key,table);
    struct htable_item *item;
    if(index!=-1){
        item=&table[index];
        item->table_slot=0;
        item->key=new string("");
    }
}

void insert(string key,struct htable_item *table){
    int temp=-1;
    struct htable_item *item;
    int index=search(key,table);

    if(index==-1){
        index=(int)hashValue(key)-97;
        item=&table[index];
        if(item->table_slot!=1){
            item->key=new string(key);
            item->table_slot=1; //occupied 
        }
    	else{
	        while(item->table_slot==1 && temp!=index){
	            if(temp==-1) temp=index;
	            index=(index+1)%27;
	            item=&table[index];
	        }
	        item->key=new string(key);
	        item->table_slot=1;
        }
    }
    else{
        // do nothing
    }
}

int main(){
    struct htable_item *table;
    table=(struct htable_item*)malloc(sizeof(htable_item)*27);
    struct htable_item *item;
    // intialising 
    int i=0;
    while(i<27){
        item=&table[i];
        item->key=new string("");
        item->table_slot=-1; // -1 for never used
        i++;
    }
           
    string s;
    getline(cin,s);
    size_t pos = 0;
    string token;
    while((pos = s.find(" "))!=string::npos){
        token = s.substr(0, pos);
        if(token[0]=='A'){
            insert(token.substr(1,token.length()),table);
        }
        else if(token[0]=='D'){
            remove(token.substr(1,token.length()),table);
        }
    s.erase(0,pos+1);
    }
    token=s;
    if(token[0]=='A'){
        insert(token.substr(1,token.length()),table);
    }
    else if(token[0]=='D'){
        remove(token.substr(1,token.length()),table);
    }
    i=0;
    while(i<27){
        item=&table[i];
        if(item->table_slot==1){
            string *a=item->key;
            cout<<*a<<" ";
        }
        i++;
    }
    return 0;
}

Liebe Grüße

It0101

Ohne den Quellcode jetzt intensiv studiert zu haben fällt mir erstmal auf, dass du nie mit const-referenzen arbeitest.
Du kopierst ständig ganze Strings.

void remove(string key,struct htable_item *table)

Das ist aber gar nicht nötig, wenn du den "key" in der Funktion nicht verändern willst.
Das sollte dann so sein:

void remove(const string &key,struct htable_item *table)

Und schon sparst du jedes Mal das kopieren des Strings ein. Kannst du glaube bei allen Funktionen machen, denn nirgendwo änderst du den "key".

wob

Es fällt vor allem auf, dass dein Code eher nach C als nach C++ aussieht, wenn man von std::string und getline absieht. Hast du vorher C gelernt oder wurde dir diese Art Code zu schreiben als C++ beigebracht? Die Includes stdio.h und malloc.h weisen auf C, in C++ wird statt malloc new benutzt, aber new benutzt man nach Möglichkeit überhaupt nicht (stattdessen std::make_unique, wenn es Freispeicher sein soll). Und wenn du "struct X" hast, kannst du eine Variable danach einfach mit "X var;" deklarieren (ohne struct zu wiederholen). Die Funktionen search, insert und remove sollten meiner Meinung nach Memberfunktionen sein.

Wichtige Frage: Was erwartet deine "search"-Funktion als Input-Parameter? Und was gibt sie zurück? Schau insbesondere auch auf den 2. Parameter. Woher weißt du, dass du in Zeile 20 auf table[index] zugreifen darfst?

Weitere Fragen (unsortiert)

Was mach das c-97?
Warum gibt die hashValue nur ein char zurück?
Hash value ist Stringlänge? Das geht besser!
Warum findet sich die Zahl 27 so oft in deinem Programm?
Warum benutzt du string::compare, wenn du nur auf Gleichheit testen willst? (einfach == benutzen!)
Warum gibt es keine Kommentare? Es wäre hilfreich, wenn dokumentiert wäre, wie du deine Hashtable überhaupt implementiert hast, was du bei Kollisionen machst etc.
Du hast Speicherlecks (new aber kein delete, malloc aber kein free). Warum überhaupt diese Pointer?

flank

Vielen Dank für die Denkanstöße. Tatsächlich programmiere ich in C++ seit 5 Wochen Ich bin in R, Matlab und Python evtl. noch Java beheimatet und nicht wirklich ein Programmierer. Das Wissen habe ich von den wenigen Infos von unserem Professor und aus dem Internet. Aber ich die aufgeführten Fragen haben mir ein paar Dinge aufgezeigt, worüber ich mir wirklich Gedanken machen sollte.

Danke dafür