Kamikatze
Captain
- Registriert
- Okt. 2004
- Beiträge
- 3.703
Ich besuche derzeit die 3. Klasse der HTBL. Da habe ich im Rahmen des Unterrichts folgende Aufgabe gestellt bekommen:
Ich soll Suchalgorithmen testen und die benötigte Zeit zum Auffinden eines Elements soll ausgegeben werden. Es soll für mehrere Feldgrößen getestet werden, außerdem für verschiedene Bereiche im Feld. Zu suchen ist auf einem externen Datenträger.
Mein Problem ist nun, dass selbst beim seriellen Durchsuchen einer ca. 350 MB großen Datei (10 Mio. DS) für z.B. ein Element, das nicht existiert nur ca. 1 Sekunde brauche (obwohl jeder Datensatz einzeln gelesen wird). Das ist theoretisch unmöglich. Was ist die Ursache?
Es sind 2 eigenständige Programme vorhanden:
Suchalgorithmen - zum Testen der Algorithmen und
Ausgabe - zur Interpretation der Messergebnisse
Die Ausgabe müsste eigentlich funktionieren, man merkt schon beim Debuggen, wie kurz die Funktionen zum Auffinden eines Elements benötigen.
Suchalgorithmen:
Ich soll Suchalgorithmen testen und die benötigte Zeit zum Auffinden eines Elements soll ausgegeben werden. Es soll für mehrere Feldgrößen getestet werden, außerdem für verschiedene Bereiche im Feld. Zu suchen ist auf einem externen Datenträger.
Mein Problem ist nun, dass selbst beim seriellen Durchsuchen einer ca. 350 MB großen Datei (10 Mio. DS) für z.B. ein Element, das nicht existiert nur ca. 1 Sekunde brauche (obwohl jeder Datensatz einzeln gelesen wird). Das ist theoretisch unmöglich. Was ist die Ursache?
Es sind 2 eigenständige Programme vorhanden:
Suchalgorithmen - zum Testen der Algorithmen und
Ausgabe - zur Interpretation der Messergebnisse
Die Ausgabe müsste eigentlich funktionieren, man merkt schon beim Debuggen, wie kurz die Funktionen zum Auffinden eines Elements benötigen.
Suchalgorithmen:
Code:
#include "stdafx.h"
#include <wtypes.h>
#include <conio.h>
#define FELDPATH "C:\\windows\\temp\\feld.dat"
#define INFPATH "C:\\windows\\temp\\inf.dat"
#define BASEPATH "C:\\windows\\temp\\base.dat"
struct Element
{
char dummy[32];
int key;
};
// Messergebnisse
struct Inf
{
int idx_n;
int idx_teile;
int idx_such;
int time;
};
void Init(Element vekt[], int n);
void Eingabe(int n[], int *teile);
long ActTime();
void SaveInFile(Element feld[], int n);
int SequSearch(FILE *fp, int key, int count);
int mWegeSearch(FILE *fp, int key, int li, int re);
int BinSearch(FILE *fp, int k, int li, int re);
int SearchedEl(Inf &inf, int n[], int teile, FILE *fp);
int Biggest(int vek[], int n);
void SaveBaseInf(int teile, int n[]);
int main(int argc, _TCHAR* argv[])
{
int n[8] = {0}, m = 0; // Feldgrößen
int teile = 0; // Anzahl der Teile, in die das Feld geteilt wird, um zu suchen
Element *feld = NULL;
Inf inf = {0}; // Messergebnisse
int srch = 0; // zu suchendes Element
FILE *inffp = NULL, *feldfp = NULL;
int idx = 0; // Ergebnis des Suchalgorithmuses
Eingabe(n, &teile); // n und teile initialisieren
m = Biggest(n, 8); // Größtes n wird gesucht
SaveBaseInf(teile, n);
feld = new Element[m];
Init(feld, m); // keys der Elemente initialisieren
SaveInFile(feld, m); // Feld in Datei schreiben
delete[] feld; // Feld löschen
inffp = fopen(INFPATH, "wb"); // Datei für Messergebnisse öffnen
feldfp = fopen(FELDPATH, "rb"); // Datei mit den Feld-Daten öffnen
// Schleife 1: Feldgrößen
for(inf.idx_n = 0; n[inf.idx_n]; inf.idx_n++)
{
// Schleife 2: Teilbereiche des Feldes
for(inf.idx_teile = 0; inf.idx_teile <= teile; inf.idx_teile++)
{
// Schleife 3: Suchalgorithmen
for(inf.idx_such = 0; inf.idx_such < 3; inf.idx_such++)
{
srch = SearchedEl(inf, n, teile, feldfp); // Zu suchendes Element wird ermittelt
// Im letzten Durchgang wird nach einem Element gesucht, das nicht existiert
if (inf.idx_teile == teile)
{
inf.idx_teile--;
srch = SearchedEl(inf, n, teile, feldfp) + 1;
inf.idx_teile++;
}
inf.time = ActTime();
switch(inf.idx_such)
{
case 0: idx = SequSearch(feldfp, srch, n[inf.idx_n]); break;
case 1: idx = BinSearch(feldfp, srch, 0, n[inf.idx_n]-1); break;
case 2: idx = mWegeSearch(feldfp, srch, 0, n[inf.idx_n]-1); break;
}
inf.time = (inf.time - ActTime())* -1; // Zeit vorher minus Zeit nachher ergibt negativ --> umkehren
fwrite(&inf, sizeof(Inf), 1, inffp); // Speichert Messergebnis in Datei
}
}
}
fclose(inffp);
fclose(feldfp);
unlink(FELDPATH); // Datei wird wieder gelöscht
return 0;
}
// Speichert Informationen, die für Ausgabe benötigt werden
void SaveBaseInf(int teile, int n[])
{
FILE *fp = NULL;
int i = 0;
fp = fopen(BASEPATH, "wb");
fwrite(&teile, sizeof(int), 1, fp);
while (n[i])
{
fwrite(n+i, sizeof(int), 1, fp);
i++;
}
fclose(fp);
}
// Gibt größtes Element eines Feldes zurück (nicht Index!)
int Biggest(int vek[], int n)
{
int i = 1;
int biggest = vek[0];
while (vek[i] && i < n)
{
if (vek[i] > biggest)
biggest = vek[i];
i++;
}
return biggest;
}
// Ermittelt das zu suchende Element
int SearchedEl(Inf &inf, int n[], int teile, FILE *fp)
{
Element e = {0};
int idx = (((n[inf.idx_n]/teile)*(2*inf.idx_teile + 1) - 1) / 2);
fseek(fp, idx*sizeof(Element), SEEK_SET);
fread(&e, sizeof(Element), 1, fp);
return e.key;
}
// Festlegung der Feldgröße und Anzahl der Teile des Feldes
void Eingabe(int n[], int *teile)
{
int i = 0;
printf("Bitte Feldgroessen eingeben (aufsteigend sortiert - Beenden mit 0):\n");
do
{
scanf("%d", n+i);
i++;
}
while(n[i-1] != 0);
printf("\nAnzahl der Teile eingeben: ");
scanf("%d", teile);
}
// Initialisiert Feld - Schlüssel sind nach Ende aufsteigend sortiert
void Init(Element vekt[], int n)
{
int i=1;
vekt[0].key = rand()%5;
while (i < n)
{
// Element = vorhergehendes Element + Zufallszahl zwischen 2 und 5
vekt[i].key = vekt[i-1].key + 2+rand()%4;
i++;
}
}
// BinSearch (iterativ)
int BinSearch(FILE *fp, int k, int li, int re)
{
int mi = 0;
Element e = {0};
while(li <= re)
{
mi=(li + re)/2;
fseek(fp, mi * sizeof(Element), SEEK_SET);
fread(&e, sizeof(Element), 1, fp);
if(e.key == k) // Element gefunden
return mi;
if(e.key < k)
li = mi + 1;
else
re = mi - 1;
}
return -1; // Element nicht vorhanden
}
// M-Wege Suchen (rekursiv)
int mWegeSearch(FILE *fp, int key, int li, int re)
{
int schrw = 1; // Schrittweite
int anz = re-li; // Anzahl der Elemente
int lauf = li;
int lauf_old = 0;
Element e = {0};
if (anz >= 100)
schrw = anz/100;
do
{
lauf_old = lauf;
lauf += schrw;
if (lauf > re)
lauf = re;
fseek(fp, lauf * sizeof(Element), SEEK_SET);
fread(&e, sizeof(Element), 1, fp);
if (e.key == key)
return lauf;
if (e.key < key && lauf == re) // Obwohl am Ende des Feldes und Element trotzdem nicht gefunden --> Element nicht vorhanden
return -1;
}
while (e.key < key);
return mWegeSearch(fp, key, lauf_old, lauf-1);
}
// Sequentielle Suche
int SequSearch(FILE *fp, int key, int n)
{
Element e = {0};
int count = -1; // Zähler, return-Wert
fseek(fp, 0, SEEK_SET);
do
{
count++; // Beim 1. Durchlauf auf 0 gesetzt
fread(&e, sizeof(Element), 1, fp);
}
while(e.key != key && count < n-1); // Abbruch wenn gefunden oder Dateiende erreicht (0 bedeutet 0 DS erfolgreich gelesen)
if(count <= n-1) // Element gefunden
return count;
else // Dateiende, Element nicht vorhanden
return -1;
}
// speichert Feld sequentiell in Datei
void SaveInFile(Element feld[], int n)
{
int i=0;
FILE *fp = fopen(FELDPATH, "wb");
fwrite(feld, sizeof(Element), n, fp);
fclose(fp);
}
// liefert verstrichene Zeit seit Tagesbeginn in Millisekunden
long ActTime()
{
SYSTEMTIME tm;
GetLocalTime(&tm);
return ((tm.wHour * 60 + tm.wMinute) * 60 + tm.wSecond) * 1000 + tm.wMilliseconds;
}
Ausgabe:
_________________________________________________________________
#include "stdafx.h"
#include <io.h>
#define INFPATH "C:\\windows\\temp\\inf.dat"
#define BASEPATH "C:\\windows\\temp\\base.dat"
#define ZLEN 79
// Messergebnisse
struct Inf
{
int idx_n;
int idx_teile;
int idx_such;
int time;
};
void GetBaseInf(int *teile, int n[]);
long GetTime(Inf inf[], int idx_n, int idx_teil, int idx_such);
int GetAnzN(int n[]);
// Ausgabe der Messergebnisse
int _tmain(int argc, _TCHAR* argv[])
{
FILE *fp = NULL;
Inf *inf = NULL;
int anz = 0;
int teile = 0;
int n[8] = {0}; // Feldgrößen
int idx_n = 0, idx_teil = 0, idx_such = 0;
int ausw = 0;
int anz_n = 0;
char cmd[16] = {0}, ausg[32] = {0};
fp = fopen(INFPATH, "rb");
anz = filelength(fileno(fp)) / sizeof(Inf);
inf = new Inf[anz];
fread(inf, sizeof(Inf), anz, fp);
fclose(fp);
GetBaseInf(&teile, n);
anz_n = GetAnzN(n);
do
{
printf("\n\nAusgabemoeglichkeiten:\n");
printf(" 1.) x = Suchalgorithmus / y = Teilbereich / z = Feldgroesse\n");
printf(" 2.) x = Suchalgorithmus / y = Feldgroesse / z = Teilbereich\n");
printf(" 3.) x = Teilbereich / y = Suchalgorithmus / z = Feldgroesse\n");
printf(" 4.) x = Teilbereich / y = Feldgroesse / z = Suchalgorithmus\n");
printf(" 5.) x = Feldgroesse / y = Suchalgorithmus / z = Teilbereich\n");
printf(" 6.) x = Feldgroesse / y = Teilbereich / z = Suchalgorithmus\n");
printf(" Ungueltig: Beenden\n");
printf("\nAusgabeprinzip: ");
scanf("%d", &ausw);
switch(ausw)
{
case 1:
// x = Suchalgorithmus / y = Teilbereich / z = Feldgroesse
for (idx_n = 0; idx_n < anz_n; idx_n++)
{
printf("n = %d\n", n[idx_n]);
for (idx_teil = -1; idx_teil <= teile; idx_teil++)
{
for (idx_such = -1; idx_such < 3; idx_such++)
{
if (idx_teil == -1 && idx_such == -1)
printf("%19s", " ");
else if (idx_teil == -1)
{
switch(idx_such)
{
case 0: printf("%19s", "Lineares Suchen"); break;
case 1: printf("%19s", "Binaeres Suchen"); break;
case 2: printf("%19s", "m-Wege-Suchen"); break;
}
}
else if (idx_such == -1)
{
if (idx_teil == teile)
printf("%19s", "nicht vorhanden");
else
printf("%11d. Teilb.", idx_teil+1);
}
else
printf("%19.3f", GetTime(inf, idx_n, idx_teil, idx_such)/1000.0);
}
printf("\n");
}
printf("\n\n");
}
break;
case 2:
// x = Suchalgorithmus / y = Feldgroesse / z = Teilbereich
for (idx_teil = 0; idx_teil <= teile; idx_teil++)
{
if (idx_teil == teile)
printf("nicht vorhanden\n");
else
printf("%d. Teilbereich\n", idx_teil+1);
for (idx_n = -1; idx_n < anz_n; idx_n++)
{
for (idx_such = -1; idx_such < 3; idx_such++)
{
if (idx_n == -1 && idx_such == -1)
printf("%19s", " ");
else if (idx_n == -1)
{
switch(idx_such)
{
case 0: printf("%19s", "Lineares Suchen"); break;
case 1: printf("%19s", "Binaeres Suchen"); break;
case 2: printf("%19s", "m-Wege-Suchen"); break;
}
}
else if (idx_such == -1)
{
sprintf(ausg, "n = %-d", n[idx_n]);
printf("%19s", ausg);
}
else
printf("%19.3f", GetTime(inf, idx_n, idx_teil, idx_such)/1000.0);
}
printf("\n");
}
printf("\n\n");
}
break;
case 3:
// x = Teilbereich / y = Suchalgorithmus / z = Feldgroesse
for (idx_n = 0; idx_n < anz_n; idx_n++)
{
printf("n = %d\n", n[idx_n]);
for (idx_such = -1; idx_such < 3; idx_such++)
{
for (idx_teil = -1; idx_teil <= teile; idx_teil++)
{
if (idx_teil == -1 && idx_such == -1)
{
sprintf(cmd, "%%%ds", ZLEN/(teile+2));
printf(cmd, " ");
}
else if (idx_such == -1)
{
if (idx_teil == teile)
{
sprintf(cmd, "%%%ds", ZLEN/(teile+2));
printf(cmd, "n. vorh.");
}
else
{
sprintf(cmd, "%%%dd. Teilb.", ZLEN/(teile+2)-8);
printf(cmd, idx_teil+1);
}
}
else if (idx_teil == -1)
{
sprintf(cmd, "%%%ds", ZLEN/(teile+2));
switch(idx_such)
{
case 0: printf(cmd, "Lin. S."); break;
case 1: printf(cmd, "Bin. S."); break;
case 2: printf(cmd, "m-Wege-S."); break;
}
}
else
{
sprintf(cmd, "%%%d.3f", ZLEN/(teile+2));
printf(cmd, GetTime(inf, idx_n, idx_teil, idx_such)/1000.0);
}
}
printf("\n");
}
printf("\n\n");
}
break;
case 4:
// x = Teilbereich / y = Feldgroesse / z = Suchalgorithmus
for (idx_such = 0; idx_such < 3; idx_such++)
{
switch(idx_such)
{
case 0: printf("Lineares Suchen\n"); break;
case 1: printf("Binaeres Suchen\n"); break;
case 2: printf("m-Wege-Suchen\n"); break;
}
for (idx_n = -1; idx_n < anz_n; idx_n++)
{
for (idx_teil = -1; idx_teil <= teile; idx_teil++)
{
if (idx_n == -1 && idx_teil == -1)
{
sprintf(cmd, "%%%ds", ZLEN/(teile+2));
printf(cmd, " ");
}
else if (idx_n == -1)
{
if (idx_teil == teile)
{
sprintf(cmd, "%%%ds", ZLEN/(teile+2));
printf(cmd, "n. vorh.");
}
else
{
sprintf(cmd, "%%%dd. Teilb.", ZLEN/(teile+2)-8);
printf(cmd, idx_teil+1);
}
}
else if (idx_teil == -1)
{
sprintf(ausg, "n = %-d", n[idx_n]);
sprintf(cmd, "%%%ds", ZLEN/(teile+2));
printf(cmd, ausg);
}
else
{
sprintf(cmd, "%%%d.3f", ZLEN/(teile+2));
printf(cmd, GetTime(inf, idx_n, idx_teil, idx_such)/1000.0);
}
}
printf("\n");
}
printf("\n\n");
}
break;
case 5:
// x = Feldgroesse / y = Suchalgorithmus / z = Teilbereich
for (idx_teil = 0; idx_teil <= teile; idx_teil++)
{
if (idx_teil == teile)
printf("nicht vorhanden\n");
else
printf("%d. Teilbereich\n", idx_teil+1);
for (idx_such = -1; idx_such < 3; idx_such++)
{
for (idx_n = -1; idx_n < anz_n; idx_n++)
{
if (idx_n == -1 && idx_such == -1)
{
sprintf(cmd, "%%%ds", ZLEN/(anz_n+1));
printf(cmd, " ");
}
else if (idx_such == -1)
{
sprintf(ausg, "n = %-d", n[idx_n]);
sprintf(cmd, "%%%ds", ZLEN/(anz_n+1));
printf(cmd, ausg);
}
else if (idx_n == -1)
{
sprintf(cmd, "%%%ds", ZLEN/(anz_n+1));
switch(idx_such)
{
case 0: printf(cmd, "Lin. S."); break;
case 1: printf(cmd, "Bin. S."); break;
case 2: printf(cmd, "m-Wege-S."); break;
}
}
else
{
sprintf(cmd, "%%%d.3f", ZLEN/(anz_n+1));
printf(cmd, GetTime(inf, idx_n, idx_teil, idx_such)/1000.0);
}
}
printf("\n");
}
printf("\n\n");
}
break;
case 6:
// x = Feldgroesse / y = Teilbereich / z = Suchalgorithmus
for (idx_such = 0; idx_such < 3; idx_such++)
{
switch(idx_such)
{
case 0: printf("Lineares Suchen\n"); break;
case 1: printf("Binaeres Suchen\n"); break;
case 2: printf("m-Wege-Suchen\n"); break;
}
for (idx_teil = -1; idx_teil <= teile; idx_teil++)
{
for (idx_n = -1; idx_n < anz_n; idx_n++)
{
if (idx_n == -1 && idx_teil == -1)
{
sprintf(cmd, "%%%ds", ZLEN/(anz_n+1));
printf(cmd, " ");
}
else if (idx_teil == -1)
{
sprintf(ausg, "n = %-d", n[idx_n]);
sprintf(cmd, "%%%ds", ZLEN/(anz_n+1));
printf(cmd, ausg);
}
else if (idx_n == -1)
{
if (idx_teil == teile)
{
sprintf(cmd, "%%%ds", ZLEN/(anz_n+1));
printf(cmd, "nicht vorhanden");
}
else
{
sprintf(cmd, "%%%dd. Teilb.", ZLEN/(anz_n+1)-8);
printf(cmd, idx_teil+1);
}
}
else
{
sprintf(cmd, "%%%d.3f", ZLEN/(anz_n+1));
printf(cmd, GetTime(inf, idx_n, idx_teil, idx_such)/1000.0);
}
}
printf("\n");
}
printf("\n\n");
}
break;
default:
return 0;
}
}
while (1);
return 0;
}
// Liefert die Anzahl der unterschiedlichen Feldgrößen zurück
int GetAnzN(int n[])
{
int i = 0;
while (n[i])
i++;
return i;
}
// Liefert Zeit für bestimmtes Messergebnis zurück
long GetTime(Inf inf[], int idx_n, int idx_teil, int idx_such)
{
int i = 0;
while (inf[i].idx_n != idx_n || inf[i].idx_such != idx_such || inf[i].idx_teile != idx_teil)
i++;
return inf[i].time;
}
// Liefert Informationen, die für Ausgabe benötigt werden
void GetBaseInf(int *teile, int n[])
{
FILE *fp = NULL;
int i = 0;
fp = fopen(BASEPATH, "rb");
fread(teile, sizeof(int), 1, fp);
// Feldgrößen einlesen
while (fread(n + i++, sizeof(int), 1, fp));
}
Zuletzt bearbeitet:
(Kleiner Bug in SequSearch, was aber nicht das Problem war)