Dynamisches mehrdimensionales Array!

[Woodstock]

Hi!

Hab mal wieder ein Problem. Die jenigen die hier regelmäßig lesen wissen ja was für ein Programm ich schreibe.

Ich suche auf meiner Festplaate alle Textdateien und schreibe in eine Datei (Index.idx) die Worte die ich finde, mit einer Zahl, die mir die Dateizeile angiebt, in der der Dateiname mit Pfad in einer weiteren Datei (Path.idx) steht.

So, klappt auch mittlerweile, ist nur sehr sehr langsam.

Darum soll ich jetzt nicht jedes Wort in die Datei schreiben, diese speichern und dann beim nächsten gefundenen Wort die komplette Index.idx durchsuchen ob das Wort eventuell schon einmal vorkam und die Zahl anhängen, sondern ich soll das ganze jetzt im Speicher lassen, also mit einem dynamischen mehrdimensionalen Array lösen.

Das Problem ist, ich weis absolut nicht wie ich das machen kann.

Es soll im Grunde so sein, das ich am Anfang nur ein Array XP [1][1] habe. Darin steht das erste Wort mit der ersten Zahl. Kommt jetzt in der gleichen Datei (also gleiche Zahl) ein weiteres Wort vor, so soll das Array erweitert werden auf XP [2][1], wobei ich jetzt XP [1][1] und XP [2][1] habe. Waren das für diese Datei alle Worte, ok. Nächste Datei: Ein weíteres Wort was noch nicht vorkam -> XP [3][1] mit XP [1][1], XP [2][1] und XP [3][1]. Und nun kommt in dieser zweiten (oder eben x-ten) Datei das Wort vor, welches auch schon in der ersten Datei vorkam. Jetzt soll das Array erweitert werden auf: XP [3][2] mit XP [1][1][1], XP [2][1] und XP [3][1]. Also wirklich nur da, wo es auch gebraucht wird. Wie kann ich das machen?

Bine

[Klotzkopp]

Ich würde vorschlagen, dass Du Dir selbst eine Klasse schreibst, die ein solches selbsterweiterndes Array simuliert, am besten mit Listen, die Listen von Listen enthalten. So wird nicht mehr Platz als nötig verbraucht.

[maxim_42]

Ein mehrdimensionales Array scheint mir ein grundsätzlich falscher Ansatz zu sein.

Denn, obwohl mehrdimensional, kannst du nur einen Datentyp darin unterbringen. Man kann also zum Beispiel mit einem char[100][100] einhundert Zeichenketten darstellen, man kann aber keine ints unterbringen (der typ der in den 100*100*sizeof(char) steht muss immer derselbe sein). Da ist der Ansatz mit verketteten Listen schon besser.

[Woodstock]

Das mit den Datentypen ist für mich kein Argument, da bei mir eh alles vom Typ char ist, was ich auch in die Index.idx schreibe. Aber gut, wenn ich nun in Eure Richtung gehe. Wie kann ich das realiesieren? Ich habe absolut keinen Plan.

Sabine

[Klotzkopp]

Ausgehen musst Du von einer Liste, die die gefundenen Worte enthält. Zusätzlich muss aber jedes Element dieser Liste wiederum eine Liste von Zahlen beinhalten, die die Dateien bezeichnen, in denen das Wort gefunden wurde. Wie das konkret aussieht, hängt davon ab, was für eine Art von Liste Du benutzt.

Willst Du die STL verwenden, eine verkettete Liste oder eine Wrapper-Klasse für einen selbsterweiternden Array? Oder was ganz anderes?

[Woodstock]

Sorry, aber ich verstehe nur Bahnhof.

Bine

[idefix]

Ich kenn zwar nicht die volle Aufgabenstellung, da ich heute das erste mal hier rein schaue. Mein Vorschlag wäre eine Mappe aus

der STL zu benutzen.

#include <map>

#include <string>

typedef stl::map<stl::string,int> INDEXMAP;

oder

typdef struct tagIndexInfo{

int count;

// ...

// what ever you need

// ...

}INDEXINFO;

typedef stl::map<stl::string,INDEXINFO> INDEXMAP;

Der Vorteil ist, das Du über den String an die dazu gehörenden

Daten kommst und nicht über den Index als Integer. Die Mappe

wächst autom. mit und du brauchst nicht viel programmieren.

Jedenfalls nicht das Handling deiner Daten.

[Woodstock]

Sorry, aber da steig ich immer noch nicht durch. Ich bin einfach noch nicht so weit, denke ich.

Also bitte einmal ganz von vorne.

Bine

[Klotzkopp]

Also:

Du brauchst eine Liste der Wörter im Speicher (anstelle der Datei Index.idx). Zu jedem Wort brauchst Du eine weitere Liste, in der die Zahlen gespeichert werden, die auf die Dateien verweisen, die in Path.idx stehen.

Wortliste--->    Hund       Katze         Maus


Dateilisten|       1           3            1

           |       2           4            2

           v       7           5            5

                               6            7

                               8

                               9

[/CODE]

Letztendlich geht es nur darum, die Daten, die in Index.idx abgelegt würden, im Speicher zu halten.

So weit klar?

[Woodstock]

Ja, das ist verständlich.

Bine

[idefix]

Also, wenn ich das richtig verstehe ist das Problem die Anzahl der Strings, die in Dateien gefunden worden zu ermitteln. Ein normales Array hat einen ganzzahligen Index. Dieser ist aber ungeeignet da du ja ein String findest. Normalerweise mußstest Du jetzt in deinem Array immer suchen, ob und wo sich der gefunde String befindet. Kann man machen, vieleicht als ersten Schritt. Steigt allerdings die Anzahl der gefunden Strings wird die Sucherei lästig und zeitraubend. Kannst ja mal ausprobieren. So, nun zu der Mappe, eine Mappe kombiniert die Eigenschaften eines

Arrays und einer Liste.

Vieleicht noch ein Wort zur STL (Standard template library) hier versammeln sich Standard Container (Listen, Arrays, sets, Maps usw.) die von Programmierern oft benutzt werden ...

.. ich schreib gleich weiter

ciao

[Klotzkopp]

So, es gibt jetzt mehrere Möglichkeiten, in C++ so eine Liste zu implementieren. In der Standard Template Library (STL) gibt es mehrere Klassen, die genau das können. Es handelt sich dabei um Template-Klassen, d.h. es sind Schablonen, bei denen Du noch angeben musst, was die einzelnen Objekte der Liste sind.

Ich würde std::vector empfehlen:

#include <vector>

std::vector< int > meinIntVector;

deklariert einen "vector" von ints. So etwas könntest Du verwenden, um die Zahlen zu jedem Wort zu speichern. Du kannst mit meinIntVector.push_back( Zahl ) neue Zahlen zum vector hinzufügen.

Für die Wortliste kannst Du auch einen vector verwenden, allerdings muss jeder Eintrag nicht nur das Wort selbst enthalten, sondern auch die Liste mit den Zahlen:

typedef struct {

char szWort[200];

std::vector< int > DateiListe;

} WortListenEintrag;

std::vector< WortListenEintrag > meineWortListe;

[Woodstock]

Hmm, verstehe ich nicht wirklich (ich bin heute scheinbar total von der Rolle). Sorry, ich habe gerade erst mit der Objektorientierung angefangen.

Also, in der Header Datei 'vector' gibt es eine Klasse Vector, sehe ich das richtig?

Und wie genau weise ich das jetzt wem was zu? Hiiiiiiiiiiiiilfe!

Bine

[idefix]

Gut, ich glaube ich habe so langsam die Dimension der Aufgabenstellung begriffen. Möchte mich für meinen Schnellschuß entschuldigen. Ich würde mich gern an den Vorschlag von klotzkopp halten. Wobei ich noch nicht ganz verstanden habe wie das nun wircklich vor sich gehen soll.

int CScanner::HowManyWords(const char* pszWord,const char* pszFileName)

{

int i;

int iAnzahl=0;

for (i=0;i<meineWortListe.size();i++){

if(!strcmp(meineWortListe.szWort,pszWord)){

// und nun?

// woher weiß ich jetzt wie oft dieses Wort in welcher

// Datei vorkammen?

}

}

return iAnzahl;

};

Aber vieleicht bin ich ein wenig auf dem Holzweg und diese Frage ergibt sich gar nicht.

[idefix]

Gut, mal zur Probe

#include <string>

#include <vector>

class CWordList

{

public:

typedef struct tagFILEPARAM

stl::string sName;

stl::string sPath;

}FILEPARAM;

typdef struct tagWORDPARAM

{

int nFileIndex;

int nCount;

}WORDPARAM;

typdef stl::vector<int,FILEPARAM> FILEVEC;

typdef stl::vector<int,WORDPARAM> WORDVEC;

typdef struct tagWORDSCAN

{

stl:string sWord;

WORDVEC WordVec;

}WORDSCAN;

typedef stl::vector<int,WORDSCAN> SCANVEC;

private:

FILEVEC a_FileVec;

SCANVEC a_ScanVec;

public:

int AddFile(const char*pszFilePath)

{

for(int i=0;i< a_FileVec.size();i++){

if(!a_FileVec.sPath.compare(pszFilePath)){

return i;

}

}

FILEPARAM fp;

fp.sName=//split filename jetzt nicht wichtig

fp.sPath=pszFilePath;

a_FileVec.push_back(fp);

return a_FileVec.size()-1;

}

void AddWord(const char*pszFilePath,const char*pszWord)

{

WORDPARAM wp;

wp.iFileIndex=iFileIndex;

wp.nCount=1;

int iFileIndex=AddFile(pszFilePath);

for(int i=0;i< a_ScanVec.size();i++){

if(!a_ScanVec.sWord.compare(pszWord)){

for(int j=0;a_ScanVec.WordVec.size();j++){

if(a_ScanVec.WordVec[j].iFileIndex

==iFileIndex){

a_ScanVec.WordVec[j].nCount++;

return;

}

a_ScanVec.WordVec.push_back(wp);

return;

}

}

}

WORDSCAN ws;

ws.WordVec.push_back(wp);

ws.sWord=pszWord;

a_ScanVec.push_back(ws);

}

};

So, ich habe das nicht compiliert, sollte aber laufen.

Jetzt würde HowManyWords eigentlich laufen

in der MSDN werden die meisten funktionen beschrieben, aber leider nur wenig über die Zusammenhänge. Es gibt von Ulrich Breymann Die C++ Standard Template Library. Tja, wirkt irgendwie kompliziert aber ist ja auch nicht ganz einfach. Ich hoffe du hast jetzt einen kleinen Ansatz. Ein Vector ist nichts anders als eine Klasse die eine dynamisches Array birgt. Da dies sehr oft gebraucht wird und das Handling von dyn. Arrays, zwar einfach aber man auch schnell Fehler machen kann und der Ablauf immer der Gleiche nur die Datentypen anders sind ist ein Template genau die richtige Antwort

[Poldi]

schau dir doch mal die split funktion an, die ich -= *["]Mr.Coffee["]* =- gepostet hab.

vektoren sind so ähnlich wie arrays, allerdings sehr einfach dynamisch zu handhaben.

vector<string> beispielVektor kann zum Beispiel Strings speichern:

beispielVektor[0]="Das ist ein String";

mit push_back hängst du elemente an diesen vektor an:

beispielVektor.push_back("Noch ein String");

hat den vorteil, daß der vektor automatisch größer wird, und zwar genau so groß, wie er sein muß.

beispielVektor[0]="Das ist ein String";

beispielVektor[1]="Noch ein String";

Das gleiche geht auch mehrdimensional:

vektor< vektor<string> > bigTestVec;

bigTestVec[0] = ein Vektor vom Typen String

Beispiel:

bigTestVec.push_back(beispielVektor);

....

Alles klar?

...

Ich würde dir auch die Kombination Verkettete Liste (-> Strukturen, also struct) und Vektoren zum Speichern der Indiezes empfehlen ...

[Crush]

Wenn es aber darum geht, daß nur die neuen Worte aufgelistet werden sollen und Alte nur einmal gemerkt werden, dann ist das Set (hab ich auch schon als Menge-Klasse gesehen) die bessere Lösung, weil das dort automatisch gemacht wird, solange man nicht aufs Multiset ausweicht, wo Inhalte mehrfach auftreten dürfen.

[maxim_42]

@Poldi

hat den vorteil, daß der std::vektor automatisch größer wird, und zwar genau so groß, wie er sein muß.

Soweit ich weiß, wird ein Vektor zwar automatisch größer, wenn der Platz nicht mehr ausreicht um weitere Elemente aufzunehmen, er hat aber nach der Vergrößerung nicht die genau passende Größe. Wär ja auch ziemlich uneffektiv wenn für jedes Einfügen eines Elements, der Vektor neu dimensioniert werden müsste.

Soweit ich weiß, verdoppelt der Vektor in den meisten Implementierungen die Größe.

Das ist einer der Gründe, der manchmal gegen die Verwendung von std::vector sprich.

Ein klasse Artikel dazu hier

[gajUli]

Guter Link!

Ich wusste gar nicht, dass diese vector-Templates im Grunde so grottenschlecht sind (exponentielles Wachstum, kein shrinking...)

Vielleicht sollte mal die Praxis ueberdacht werden, sie so dringend zu empfehlen, wir es hier oft passiert ist.

[Poldi]

da steht aber drin, daß er den doppelten speicher nur für eine kurze zeit reserviert, also ist der vektor nicht die ganze zeit über doppelt so groß.

ich persönlich kann das nicht so ganz glauben, was der typ da erzählt, da ich ein programm von dynamischen arrays und verketteten listen auf geschachtelte vektoren umgestellt habe. mit vektoren ist das programm nicht nur schneller, sondern kommt auch mit deutlich weniger arbeitsspeicher aus ... !!

[gajUli]

Wie wuerdest Du denn dies

" "Imperialistic" memory allocation strategy. Standard vectors never shrink; they only grow. If you collected three million data samples and you decide to keep one million samples after some interpolation, you'll have slack space worth two million objects. "

uebersetzen?

[Crush]

Schreibt Euch doch einfach einen eigenen Allocator für eine abgeleitete Vector-Klasse. Wenn der im Standard nicht schrumpfen darf, dann macht ihn sich halt schrumpfbar. Beim Schrumpfen steigt jedoch der Speicherbedarf im Normalfall an - und wenn man das verhindern will, muß man versuchen die allokierten Template-Fragmente zu traversieren und mit dem geschrumpften Inhalt zu füllen - ist also auch nicht unmöglich. Im C++ Programmiersprache-Buch vom Stroutrup ist ein Beispiel eines eigenen Allokators (Beispiel Pool). Es ist eigentlich gar nicht so kompliziert das ganze auf einen Release() umzuschreiben. Wenn man den Vector mit Zeiger auf Objekte belegt ist das eigentlich kein Hexenwerk mehr.