3
Also dachte ich mir, ich hätte eine funktionierende Skip-Liste erstellt und dachte mir, ich sollte meine Arbeit überprüfen und die Zeitmessung der Suchfunktion untersuchen. Ich fand ein Tutorial, wie clock() zu verwenden und implementiert es wie folgt aus:Sucht meine Skip-Liste wirklich in N und nicht in Log (N)?
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "skiplist.h"
int main() {
// initialize
SkipList *list = initSkipList();
// numbers to search for, array to store time
int n[] = {1, 10, 50, 100, 1000, 5000, 10000, 25000, 50000, 100000, 200000};
double time[11];
// insert
for (int i = 1; i <= 200000; i++)
insertElement(list, i);
// search, time, print
for (int i = 0; i < 11; i++) {
clock_t t;
t = clock();
findElement(list, n[i]);
t = clock() - t;
double time_taken = ((double)t)/CLOCKS_PER_SEC; // in seconds
ti[i] = time_taken;
printf("fun() took %f seconds to execute \n", time_taken);
}
return 0;
}
Ich dachte, indem Sie diese und Plotten N gegen die Zeit würde ich einen Graphen erhalten, die logarithmische aussieht, sondern mein Diagramm sieht linear:
Muß ich ein Missverständnis darüber, wie ich meine Skip-Liste Suche gehen sollte meine Funktionen über Timing, um zu versuchen und die Testzeit-Komplexität oder ist einfach nicht wie es sein sollte? Hier ist meine ganze Skip-Liste Implementierung für alle Fälle, aber die Suchfunktion findElement() genannt:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <math.h>
#ifndef SKIPLIST_H_
#define SKIPLIST_H_
// number of lists
#define MAXLEVEL 5
// node with pointers
typedef struct Node {
int data;
struct Node *next[1]; // or C99 using flexible array members: *next[]
} Node;
// skiplist
typedef struct SkipList {
Node *header;
int level;
int count;
} SkipList;
// initialize skip list
SkipList* initSkipList() {
int i;
SkipList *list = calloc(1, sizeof(SkipList));
if (!list) {
printf("Memory Error\n");
exit(1);
}
//list->level = 0;
if ((list->header = calloc(1, sizeof(Node) + MAXLEVEL*sizeof(Node*))) == 0) {
printf("Memory Error\n");
exit(1);
}
for (i = 0; i <= MAXLEVEL; i++)
list->header->next[i] = list->header; // or = list->header?
printf("Skip list initialized.\n");
//srand(time(NULL));
return list;
}
// insert into skip list, return pointer to node
Node* insertElement(SkipList *list,int data) {
int i, newLevel;
Node* temp = list->header;
Node *update[MAXLEVEL+1];
// find where data belongs
for (i = list->level; i >= 0; i--) {
while(temp->next[i] != list->header && temp->next[i]->data < data)
temp = temp->next[i];
update[i] = temp;
}
temp = temp->next[0];
// if element already exists, just return it (no duplicates)
if (temp != list->header && temp->data == data)
return temp;
// determine level (coin flips till failure or max level reached)
for (newLevel = 0; (rand() < RAND_MAX/2) && (newLevel < MAXLEVEL); newLevel++); // Pr(4) == Pr(5)??
if (newLevel > list->level) {
for (i = list->level + 1; i <= newLevel; i++)
update[i] = list->header;
list->level = newLevel;
}
// make new node
if ((temp = calloc(1, sizeof(Node) + newLevel*sizeof(Node*))) == 0) {
printf("Memory Error\n");
exit(1);
}
temp->data = data;
list->count++;
// update next links
for (i = 0; i <= newLevel; i++) {
temp->next[i] = update[i]->next[i];
update[i]->next[i] = temp;
}
//printf("Element %d inserted into list. (level %d)\n", data, newLevel);
return temp;
}
// delete node containing data
void deleteElement(SkipList *list, int data) {
int i;
Node *update[MAXLEVEL+1], *temp;
temp = list->header;
for (i = list->level; i >= 0; i--) {
while (temp->next[i] != list->header && temp->next[i]->data < data)
temp = temp->next[i];
update[i] = temp;
}
// move to (possible) node to delete
temp = temp->next[0];
// if doesn't exist
if (temp == list->header || temp->data != data) {
printf("Element %d doesn't exist.\n", data);
return;
}
// adjust next pointers
for (i = 0; i <= list->level; i++) {
if (update[i]->next[i] != temp) break;
update[i]->next[i] = temp->next[i];
}
free (temp);
printf("Element %d deleted from list.\n", data);
list->count--;
// adjust header level
while ((list->level > 0) && (list->header->next[list->level] == list->header)) // double check
list->level--;
}
// find node containing data
Node* findElement(SkipList *list, int data){
int i;
Node *temp = list->header;
for (i = list->level; i >= 0; i--) {
while (temp->next[i] != list->header && temp->next[i]->data < data)
temp = temp->next[i];
}
temp = temp->next[0];
if (temp != list->header && temp->data == data) {
printf("Element %d found and returned.\n", data);
return (temp);
}
printf("Element %d not found.\n", data);
return 0;
}
/* Dynamic array for use in printSkipList() function */
typedef struct {
int *array;
size_t used;
size_t size;
} Array;
void initArray(Array *a, size_t initialSize) {
a->array = malloc(initialSize * sizeof(int));
a->used = 0;
a->size = initialSize;
}
void insertArray(Array *a, int element) {
if (a->used == a->size) {
a->size *= 2;
a->array = realloc(a->array, a->size * sizeof(int));
}
a->array[a->used++] = element;
}
void freeArray(Array *a) {
free(a->array);
a->array = NULL;
a->used = a->size = 0;
}
// print skip-list info and representational figure
void printSkipList(SkipList *list) {
int i, j, k, pos = 0, prevPos = 0, diff, numDigits;
Node* temp = list->header;
Array a;
// fill dynamic array with level 0 elements
initArray(&a, 10);
while (temp->next[0] != list->header) {
temp = temp->next[0];
insertArray(&a, temp->data);
}
temp = list->header;
// print number of levels
printf("\nNumber of levels in skip-list: %d\n", list->level + 1);
printf("Number of elements in skip-list: %d\n", list->count);
printf("Skip-list figure: \n");
// print data
for (i = list->level; i >= 0; i--) {
pos = 0, prevPos = 0;
while (temp->next[i] != list->header) {
numDigits = 0;
temp = temp->next[i];
while (temp->data != a.array[pos]) {
numDigits += floor (log10 (abs (a.array[pos]))) + 1;
pos++;
}
pos++;
diff = (pos - prevPos) - 1;
if (diff >= 1) {
for (j = 0; j < (4*diff)+numDigits; j++)
printf(" ");
}
printf("%d -> ", temp->data);
prevPos = pos;
}
temp = list->header;
printf("\n");
}
printf("\n\n");
}
#endif // SKIPLIST_H_
Jede Beratung wird sehr geschätzt, danke.
Ich denke, es könnte mit mir zu tun haben, die 'MAXLEVEL' auf 5 gesetzt, aber sollte dies eine Zahl sein, die ich auswähle oder etwas, das sich aufgrund der Größe der Überspringungsliste ändern sollte? Die anderen Implementierungen, die ich finde, scheinen keine Änderung der maximalen Level-Größe zu haben, aber ich dachte, die optimale Anzahl würde von der Liste abhängen. – Austin
Anstatt uns zu fragen, warum verbinden Sie nicht Ihren Debugger und sehen Sie, ob Ihre Suchmethode die höherrangigen Links erreicht? Oder fügen Sie einen Debug-Code ein, der jeden Link zusammen mit dem Link-Level ausgibt, während er verfolgt wird. –
Nun zuerst wollte ich wissen, ob die Art und Weise, wie ich die Zeiten erreicht habe, sogar Sinn ergab oder ob es einen Aspekt gab, an den ich nicht gedacht hatte. Ich habe einige print-Anweisungen zum Debuggen auf einer kleineren Liste versucht, und es scheint, dass es dem Pfad folgt, den ich erwartet habe, ob das ist, wie es eigentlich funktionieren soll, ist eine andere Geschichte. Ich werde immer wieder darüber nachdenken, wie man debuggt, aber wenn ich die Anzahl der Elemente so weit vergröβere, dass man signifikante Zeitmessungen zum Plotten bekommt, wird es für mich schwieriger zu versuchen und zu folgen. – Austin