skiplists

[alexjj]

in struct nod {} , in loc de nod * link n-ar trebui sa fie nod ** link ?
avem nevoie de mai multi pointeri din fiecare nod ...

[•fluffy]

Da, asa este, e nevoie de nod** link, am modificat.
Codul asta oricum nu compileaza in C pur, acolo trebuie ceva de genul:

typedef struct _node_ node;
struct _node_
{
    // whatever
}

Pasajele cu cod sursa din articole sunt prezentate orientativ, nu va asteptati sa fie 100% corect, nici macar sa compileze.

Oricum, multumesc de comentariu, orice fel de feed-back cu privire la articole e bine venit.

[alexjj]

ma bucur ca am putut ajuta   .
am incercat sa implementez shi am intampinat probleme.

am facut ceva de genu

Cod:

struct nod {int key; nod ** next;};

shi alocarea x->next= new nod* [nr_de_pointeri_necesari].
algoritmul e bun (am mai cautat pa net shi am gasit documente mult mai detaliate.) dar din motive necunoscute (l-am rulat shi lam depanat in draci) nu functioneaza totdeauna k lumea.

(other) ideas/help for implementation ?  

[•skipy]

Mi se parea destul de important sa se explice si adaugarea efectiva, dar ma rog e inuitiv. Ceea ce nu inteleg este nod** link. Poate cineva sa-mi explice adaugarea / sami trimita o sursa care merge pe mail. Daca aveti, va rog datimi shi mie pe [email protected]

[•domino]

hei... sa bage careva sursa aia jmenoasa a lu` Berinde cu skiplists.
eu nu o am la indemana.

Nu cred ca exista asa ceva, din cate stiu eu Berinde n-a facut niciodata skiplisturi ... cred ca era vorba de sursa ta   .. ma rog, eu am o sursa de a ta, modifica un pic de Silviu cred, o atasez mai jos pentru toti, sper sa fie 100% corecta. Daca are o varianta mai recenta il rog pe Silviu sa o puna aici.  

Cod:

/*
Skip List
    inserare, stergere, cautare: O(lgN)

    >> sursa facuta cu tab-size 4 <<


    * inserarea si cautarea merg de minune insa *stergerea* merge greu
atunci
    cand te apuci sa stergi elementele in ordine, altfel, pe cazuri
random,
    merge bine. totusi am vazut niste grafice cu timpi de executie
    skip lists VS AVL (de mai multe feluri) si skip list-urile mergeau
mai
    bine la toate operatiile (inclusiv stergere).

    * pentru cazuri in care nu ai nevoie de stergeri sunt super
bestiale
    skip list-urile: usor de implementat (rapid si greu de gresit), mai
    rapide si mai putina memorie
    * pentru cazuri in care ai nevoie de stergere, risti cu o constanta
mare
    cand se intampla sa stergi multe in ordine
*/

    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>

    #include <time.h>
    #include <assert.h>

    /* o chestie de probabilistica. merge bine 2, 4 */
#define L_P 2
    /* nr. maxim de nivele. in general trebuie luat log(L_P,
MAX_ELEMENTE) */
    #define L_MAXL  16
    /* valoare mai mare decat orice cheie din lista */
    #define L_INF 10000000

struct elem {
    int key;
    struct elem *fw[1];
};
typedef struct elem elem;

elem *H, *NIL, *aux[L_MAXL];

/* in ll se retine nivelul curent al listei. teoretic nu avem nevoie de
ll
intrucat putem considera nivelul listei ca fiind L_MAXL. insa cu
ajutorul
lui ll se pot face niste optimizari sesizabile (constante) */
int ll;

/* pentru teste */
    #define MAXT 1000013
char T[MAXT];
    /* /pentru teste */

void linit() {
    int i;

    /* aici se mai poate simplifica dar fac asa ca sa KISS */
    NIL=(elem *)malloc(sizeof(elem)+sizeof(elem *)*L_MAXL);
H=(elem *)malloc(sizeof(elem)+sizeof(elem *)*L_MAXL);
    H->key=NIL->key=L_INF;
    for (ll=i=0; i<L_MAXL; i++) H->fw[i]=NIL->fw[i]=NIL;
}

elem *lsearch(int key) {
elem *e;
    int i;

    for (i=ll-1, e=H; i>=0; i--)
    for (; e->fw[i]->key<key; e=e->fw[i]);

return (e->fw[0]->key==key?e->fw[0]:NULL);
}

elem *ladd(int key) {
elem *e;
    int i, nl;

    /* determina locatie */
    for (i=ll-1, e=H; i>=0; aux[i--]=e)
    for (; e->fw[i]->key<key; e=e->fw[i]);
if (e->fw[0]->key==key) return e->fw[0];
   
    /* nod nou */
    for (nl=1; rand()<RAND_MAX/L_P && nl<L_MAXL; nl++);
    e=(elem *)malloc(sizeof(elem)+sizeof(elem *)*nl);
    assert(e);
    e->key=key;
    for (i=0; i<nl; i++) {
    if (i<ll) e->fw[i]=aux[i]->fw[i], aux[i]->fw[i]=e;
        else H->fw[i]=e, e->fw[i]=NIL;
}
    if (nl>ll) ll=nl;
    return e;
}

char ldel(int key) {
int i;
    elem *e;

    /* determina locatie */
    for (i=ll-1, e=H; i>=0; aux[i--]=e)
    for (; e->fw[i]->key<key; e=e->fw[i]);
    e=e->fw[0];
if (e->key!=key) return 0;

/* repara pointeri */
    for (i=0; i<ll && aux[i]->fw[i]==e; aux[i]->fw[i]=e->fw[i++]);

    free(e);

    /* repara ll */
    for (; ll && H->fw[ll-1]==NIL; ll--);
   
    return 1;
}

int main(void)
{
    FILE *fin, *fout;
    char c; int x;
    elem *e;

    fin = fopen("in.txt", "r");
    fout = fopen("out.txt", "w");

    linit();
    while (!feof(fin))
    {
        fscanf(fin, "%c %d\n", &c, &x);
        if (c == 'I')
           ladd(x);
        else
        if (c == 'S')
           fprintf(fout, "search for %d: %d\n", x, lsearch(x) != NULL);
        else
        if (c == 'E')
           ldel(x);
    }
   
    fclose(fin), fclose(fout);
   
    return 0;
}

[•wickedman]

lol
agitate vremuri ...

[•domino]

Am mai gasit o sursa de skiplist, ceva mai "didactic" scrisa.. Here it is:

Cod:

/* skip list */

#include <stdio.h>
#include <stdlib.h>

/* implementation dependend declarations */
typedef enum {
    STATUS_OK,
    STATUS_MEM_EXHAUSTED,
    STATUS_DUPLICATE_KEY,
    STATUS_KEY_NOT_FOUND
} statusEnum;

typedef int keyType; /* type of key */

/* user data stored in tree */
typedef struct {
    int stuff;  /* optional related data */
} recType;

#define compLT(a,b) (a < b)
#define compEQ(a,b) (a == b)

/* levels range from (0 .. MAXLEVEL) */
#define MAXLEVEL 15

typedef struct nodeTag {
    keyType key;  /* key used for searching */
    recType rec;   /* user data */
    struct nodeTag *forward[1];
    /* skip list forward pointer */
} nodeType;

/* implementation independent declarations */
typedef struct {
    nodeType *hdr; /* list Header */
    int listLevel;      /* current level of list */
} SkipList;

SkipList list;  /* skip list information */

#define NIL list.hdr

statusEnum insert(keyType key, recType *rec) {
    int i, newLevel;
    nodeType *update[MAXLEVEL+1];
    nodeType *x;

   /***********************************************
    *  allocate node for data and insert in list  *
    ***********************************************/

    /* find where key belongs */
    x = list.hdr;
    for (i = list.listLevel; i >= 0; i--) {
        while (x->forward[i] != NIL
          && compLT(x->forward[i]->key, key))
            x = x->forward[i];
        update[i] = x;
    }
    x = x->forward[0];
    if (x != NIL && compEQ(x->key, key))
        return STATUS_DUPLICATE_KEY;

    /* determine level */
    for (
      newLevel = 0;
      rand() < RAND_MAX/2 && newLevel < MAXLEVEL;
      newLevel++);

    if (newLevel > list.listLevel) {
        for (i = list.listLevel+1; i<=newLevel; i++)
            update[i] = NIL;
        list.listLevel = newLevel;
    }

    /* make new node */
    if ((x = malloc(sizeof(nodeType) + newLevel
         *sizeof(nodeType *))) == 0)
        return STATUS_MEM_EXHAUSTED;
    x->key = key;
    x->rec = *rec;

    /* update forward links */
    for (i = 0; i <= newLevel; i++) {
        x->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = x;
    }
    return STATUS_OK;
}

statusEnum delete(keyType key) {
    int i;
    nodeType *update[MAXLEVEL+1], *x;

   /*******************************************
    *  delete node containing data from list  *
    *******************************************/

    /* find where data belongs */
    x = list.hdr;
    for (i = list.listLevel; i >= 0; i--) {
        while (x->forward[i] != NIL
          && compLT(x->forward[i]->key, key))
            x = x->forward[i];
        update[i] = x;
    }
    x = x->forward[0];
    if (x == NIL || !compEQ(x->key, key)) return
       STATUS_KEY_NOT_FOUND;

    /* adjust forward pointers */
    for (i = 0; i <= list.listLevel; i++) {
        if (update[i]->forward[i] != x) break;
        update[i]->forward[i] = x->forward[i];
    }

    free (x);

    /* adjust header level */
    while ((list.listLevel > 0)
    && (list.hdr->forward[list.listLevel] == NIL))
        list.listLevel--;

    return STATUS_OK;
}

statusEnum find(keyType key, recType *rec) {
    int i;
    nodeType *x = list.hdr;

   /*******************************
    *  find node containing data  *
    *******************************/

    for (i = list.listLevel; i >= 0; i--) {
        while (x->forward[i] != NIL
          && compLT(x->forward[i]->key, key))
            x = x->forward[i];
    }
    x = x->forward[0];
    if (x != NIL && compEQ(x->key, key)) {
        *rec = x->rec;
        return STATUS_OK;
    }
    return STATUS_KEY_NOT_FOUND;
}

void initList() {
    int i;

   /**************************
    *  initialize skip list  *
    **************************/

    if ((list.hdr = malloc(
            sizeof(nodeType) + MAXLEVEL*
            sizeof(nodeType *))) == 0) {
        printf ("insufficient memory (initList)\n");
        exit(1);
    }
    for (i = 0; i <= MAXLEVEL; i++)
        list.hdr->forward[i] = NIL;
    list.listLevel = 0;
}

int main(int argc, char **argv) {
    int i, maxnum, random;
    recType *rec;
    keyType *key;
    statusEnum status;


    /* command-line:
     *
     *   skl maxnum [random]
     *
     *   skl 2000
     *       process 2000 sequential records
     *   skl 4000 r
     *       process 4000 random records
     *
     */

    maxnum = atoi(argv[1]);
    random = argc > 2;

    initList();

    if ((rec = malloc(maxnum *
         sizeof(recType))) == 0) {
        fprintf (stderr, "insufficient memory (rec)\n");
        exit(1);
    }
    if ((key = malloc(maxnum *
         sizeof(keyType))) == 0) {
        fprintf (stderr, "insufficient memory (key)\n");
        exit(1);
    }

    if (random) {
        /* fill "a" with unique random numbers */
        for (i = 0; i < maxnum; i++) key[i] = rand();
        printf ("ran, %d items\n", maxnum);
    } else {
        for (i = 0; i < maxnum; i++) key[i] = i;
        printf ("seq, %d items\n", maxnum);
    }

    for (i = 0; i < maxnum; i++) {
        status = insert(key[i], &rec[i]);
        if (status)
           printf("pt1: error = %d\n", status);
    }

    for (i = maxnum-1; i >= 0; i--) {
        status = find(key[i], &rec[i]);
        if (status)
           printf("pt2: error = %d\n", status);
    }

    for (i = maxnum-1; i >= 0; i--) {
        status = delete(key[i]);
        if (status)
           printf("pt3: error = %d\n", status);
    }
    return 0;
}

[•stef2n]

Discutia poate continua in topicul destinat acestui articol: http://infoarena.ro/forum/index.php?topic=3688.0