Pagini: [1]   În jos
  Imprimă  
Ajutor Subiect: skiplists  (Citit de 4026 ori)
0 Utilizatori şi 1 Vizitator pe acest subiect.
alexjj
Vizitator
« : Februarie 08, 2005, 09:58:00 »

in struct nod {} , in loc de nod * link n-ar trebui sa fie nod ** link ?
avem nevoie de mai multi pointeri din fiecare nod ...
Memorat
fluffy
Echipa infoarena
De-al casei
*****

Karma: 71
Deconectat Deconectat

Mesaje: 146



Vezi Profilul
« Răspunde #1 : Februarie 08, 2005, 15:21:46 »

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.
Memorat
alexjj
Vizitator
« Răspunde #2 : Februarie 10, 2005, 20:11:42 »

ma bucur ca am putut ajuta  Very Happy .
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 ?  Sad
Memorat
skipy
Strain
*

Karma: 8
Deconectat Deconectat

Mesaje: 46



Vezi Profilul
« Răspunde #3 : Februarie 21, 2005, 13:06:04 »

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]
Memorat

Cheap VR WoW could destroy modern society...
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #4 : Februarie 21, 2005, 20:44:36 »

Citat din mesajul lui: wickedman
hei... sa bage careva sursa aia jmenoasa a lu` Berinde cu skiplists. Cool
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  wink .. 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.  Very Happy

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;
}
Memorat
wickedman
Echipa infoarena
Nu mai tace
*****

Karma: 227
Deconectat Deconectat

Mesaje: 670



Vezi Profilul WWW
« Răspunde #5 : Februarie 21, 2005, 20:50:57 »

lol
agitate vremuri ...
Memorat
domino
Echipa infoarena
Nu mai tace
*****

Karma: 281
Deconectat Deconectat

Mesaje: 1.340



Vezi Profilul WWW
« Răspunde #6 : Februarie 21, 2005, 20:51:08 »

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;
}
Memorat
stef2n
Nu mai tace
*****

Karma: 218
Deconectat Deconectat

Mesaje: 641



Vezi Profilul
« Răspunde #7 : Februarie 20, 2009, 02:35:59 »

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

Exista 10 categorii de oameni: cei care inteleg sistemul binar si cei care nu il inteleg.
Pagini: [1]   În sus
  Imprimă  
 
Schimbă forumul:  

Powered by SMF 1.1.19 | SMF © 2006-2013, Simple Machines