Suchalgorithmen

Kamikatze · 17. Dezember 2004

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:

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));
}

Kamikatze · 18. Dezember 2004

Könnte es vielleicht auch am Compiler bzw. Betriebssystem liegen? Vielleicht liegt es gar nicht am Programm.
Es kann doch nicht sein, dass das Programm eine 350 MB große Datei in 1/2 Sekunde komplett durchsucht (und gelesen) hat.

ag3nt · 18. Dezember 2004

hmm hab das Programm jetzt nur überflogen aber du vergleichst bei denen "Elementen" nur den Wert für key (~1/9 Anteil) der macht etwa 40MB von deinen 350MB Dateien aus und das sollte auf aktueller Hardware doch recht flott gehen.

p.s.: nicht schlagen wenn ich hier Müll gelabert hab

Kamikatze · 19. Dezember 2004

Es wird zwar nur key verglichen, aber trotzdem immer der ganze Datensatz gelesen. Der dummy-String ist nur da, damit ein Datensatz größer wird (da beim Lesen von der Festplatte tatsächlich mehr auf einmal gelesen und im RAM gepuffer wird. So wird verhindert, dass tatsächlich zu viele Datensätze auf einmal gelesen werden).

Ich habe auch schon einmal versucht nur die Datei zu erstellen, danach das OS neu zu starten und dann erst zu suchen - trotzdem das gleiche Ergebnis. Außerdem habe ich eine langsame Festplatte. Wie kann das Programm einfach so, ohne wirklich viel von der Festplatte zu lesen, einen DS am Ende der Datei finden, wobei dann auch noch das Ergebnis stimmt? *verzweifelntu*

Suche

Suchalgorithmen

Kamikatze

Captain

Kamikatze

Captain

ag3nt

Lieutenant

Kamikatze

Captain

Ähnliche Themen