それで、私は最終的に機能するスキップリストの作成を完了したと思い、自分の作業をチェックして検索機能のタイミングを調べる必要があると考えました. 使い方のチュートリアルを見つけて、次のclock()ように実装しました。
#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;
}
これを行って N 対時間をプロットすると、対数的に見えるグラフが得られると思いましたが、代わりに私のグラフは線形に見えます。
時間の複雑さを試してテストするために関数のタイミングを調整する方法について誤解がありますか、それともスキップリストが本来あるべき検索をしていないだけですか? 念のため、スキップリストの実装全体を次に示しますが、検索関数は次のように呼び出されfindElement()ます。
#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_
どんなアドバイスでも大歓迎です、ありがとう。