AISD: pracownia E

• Pracownia E.

• Testy E.

• testy są w /home/i221141/e na herze (testy-e.tar.bz2 zawiera wszystkie testy i odpowiedzi, można również uruchomić na rozpakowanych)

Czasy (na herze) dla struktur danych (wszystkie testy odpalone sprawdzarką dude'a):

Ja mam na RBT i działa szybko. Podejrzewam, że AVL działałyby podobnie szybko (AVL mają wysokość <1.44log(n) vs <2log(n) RBT; mają więc szybszy Upper i Lower, ale wolniejszy Insert i Delete) jeśli rozkład I+U jest podobny jak U+L, co zależy od testów.

Swoją drogą ciekawią mnie drzewa van Emde Boasa, które mają operacje słownikowe w O(log log n). Co prawda ilość elementów jest mała – maksymalnie 50000; log(50000) = 15.6, ale log(36) = 5.2, więc drzewa vEB mogą być nawet sześć razy szybsze. — drx 2010/05/23 18:16

Moje (dj3500) i Damiana czasy, testowane za pomocą:

time for i in `seq 1 10`; do ./program < test$i.in > test$i.tempout; done

Warto też może nadmienić, że treap ma 102 linijki, a cały program 3.5 kB kodu więc jeśli nie widać różnicy to po co przepłacać ;) dj3500

http://www.ii.uni.wroc.pl/~mbi/dyd/aisd_10s/wyniki_E.html - wyniki

0 oznacza brak poprawnej odpowiedzi na jakiś test

pierwsza kolumna to suma czasów

11304:  Mik Kali
13336:  Kon Wypy
13492:  Luk Syno
14248:  Luk Zapa
14272:  Pio Pole
14444:  Krz Kusi
14484:  Daw Jurc
14620:  Mar Ocze
14824:  Mic Karp
15028:  Wik Jana
15060:  Mag Sara
15128:  Kac Krol
15188:  And Kaje
15204:  Pio Bzow
15260:  Paw Muri
15460:  Dam Rusa
15500:  Krz Parj
15696:  Krz Ziel (test)
15716:  Kar Kona
15848:  Jak Tarn
15960:  Pio Posa
16008:  Mar Kola
16100:  Dam Stra
16160:  Pio Krze
16312:  Pio Ryba
16408:  Dan Blas
16828:  Krz Nowi
16884:  Krz Ziel
17036:  Iza Bicz
17440:  Mar Janu
17468:  Pio Rzep
17936:  Mic Mazu
18008:  Adr Dyli
18052:  Paw Kacp
18408:  Pio Gajo
18660:  Mic Roza
19072:  Pio Walk
19932:  Mac Maty
26812:  Mic Soko
0:  Ark Goch
0:  Raf Kowa
0:  Mic Kras
0:  Dam Piąt
0:  Mac Wiec
0:  Ada Kacz
0:  Ale Gali
0:  Bla Sala
0:  Dam Wiec
0:  Dom Brul
0:  Dom Rusa
0:  Fil Slom
0:  J L (test)
0:  Kam Miel
0:  Luc Fran
0:  Luk Toma
0:  Luk Wrza
0:  Mac Pacu
0:  Mar Janc
0:  Pat Urba
0:  Paw Kali
0:  Paw Kime
0:  Sla Step
0:  Szy Lasz
0:  Tom Luch
0:  Wal Augu (test)

#include <stdio.h>
 
#define SEARCH_BRAK (2LL<<60)
#define MAX_ELEMS 50010
#define LMAX 1000000000L
 
typedef signed long long T;
 
inline void putll (T & x) 
{
    signed long l = x / LMAX,
                r = x % LMAX;
 
    if (l != 0)
        printf("%ld%09ld\n", l,(r<0)?-r:r);
    else 
        printf("%ld\n", r);
}
 
typedef struct node
{
    T data;
    int prio;
    struct node *left, *right, *up;
} node;
 
node * root; 
 
 
/* Własny alokator pamięci. */
unsigned short nextFreeBlock[MAX_ELEMS]; // następna wolna komórka za bieżącą wolną (0 to kolejna)
node Block[MAX_ELEMS]; // pula pamięci
 
unsigned short firstFreeBlock = 1;	// bo zero to specjalna wartosc
unsigned int index;
 
#define allocate(X) X = &Block[firstFreeBlock]; \
                    if (nextFreeBlock[firstFreeBlock] == 0) \
                        firstFreeBlock++; \
                    else \
                        firstFreeBlock = nextFreeBlock[firstFreeBlock];
 
#define free(X) index = X - &Block[0]; \
                nextFreeBlock[index] = firstFreeBlock; \
                firstFreeBlock = index; 
/****/
 
inline void rotate_left (node * n)
{
    node *x = n->right;
 
    x->up = n->up;
    if (x->up != NULL)
    {
        if (x->up->left == n)
            x->up->left = x;
        else
            x->up->right = x;
    }
 
    n->right = x->left;
    if (n->right != NULL)
        n->right->up = n;
 
    n->up = x;
    x->left = n;
}
 
inline void rotate_right (node * n)
{
    node *x = n->left;
 
    x->up = n->up;
    if (x->up != NULL)
    {
        if (x->up->left == n)
            x->up->left = x;
        else
            x->up->right = x;
    }
 
    n->left = x->right;
 
    if (n->left != NULL)
        n->left->up = n;
 
    n->up = x;
    x->right = n;
}
 
void ins (T & e)
{
    T ret = 0;
    node *n = root,
         *p = NULL;
 
    static int next = 1;  
 
    // p - ojciec e
    while (n != NULL)
    {
        p = n;
        ret = e - (n->data);
 
        if (ret < 0)
            n = n->left;
        else if (ret > 0)
            n = n->right;
        else
            return;	// duplikat
    }
 
    allocate(n);
 
    n->left = n->right = NULL;
    n->up = p;
    n->data = e;
 
    if (p == NULL)
        root = n;
    else if (ret < 0)
        p->left = n;
    else
        p->right = n;
 
    next = next * 1103515245 + 12345;
    n->prio = (unsigned)(next/65536) % 32768;
 
    // rebalance 
    while (n->up != NULL && 
          (n->up->prio) > (n->prio))
 
        if (n->up->right == n)
            rotate_left (n->up);
        else
            rotate_right (n->up);
 
    if (n->up == NULL)
        root = n;
 
}
 
void del (T & e)
{
    node *n = NULL,
         *m = root;
 
    // znajdź poprzednika e - n.
    while (m != NULL)
        if (e < m->data)
            m = m->left;
        else
        {
            n = m;
            m = m ->right;
        }
 
 
    if ((n == NULL) || (n->data != e))
    {
        fputs_unlocked ("BRAK\n", stdout);
        return;
    }
 
    /* rotuj do liścia */
    while (n->left != NULL || n->right != NULL)
    {
        if (n->left != NULL)
        {
            if (n->right == NULL || n->left->prio < n->right->prio)
                rotate_right (n);
            else
                rotate_left (n);
        }
        else
            rotate_left (n);
 
        if (root == n)
            root = n->up;
    }
 
    if (n->up == NULL)
        root = NULL;
    else
        if (n->up->left == n)
            n->up->left = NULL;
        else
            n->up->right = NULL;
 
    free(n);
 
    fputs_unlocked ("OK\n", stdout);
}
 
inline void lower (node * t, T & k)
{
    T ret = SEARCH_BRAK;
 
    while (t != NULL)
    {
        if (t->data == k) {
            putll (k);
            return; 
        }
 
        if (k < t->data)
            t = t->left;
        else
        {
            ret = t->data;
            t   = t->right;
        }
    }
 
    if (ret == SEARCH_BRAK)
        fputs_unlocked ("BRAK\n", stdout);
    else
        putll ( ret);
 
}
 
inline void upper (node * t, T & k)
{
    T ret = SEARCH_BRAK;
 
    while (t != NULL)
    {
        if (t->data == k) 
        {
            putll ( k);
            return;
        }
 
        if (k < t->data)
        {
            ret = t->data;
            t = t->left;
        }
        else
            t = t->right;
    }
 
    if (ret == SEARCH_BRAK)
        fputs_unlocked ("BRAK\n", stdout);
    else
        putll ( ret);
}
 
 
int main (void)
{
    setvbuf (stdout, NULL, _IOFBF, 2 << 10);
 
    T sign, n;
    char op, ch;
    int oper;
 
    root = NULL;
 
    oper = getchar_unlocked() - '0';  
    while ((ch = getchar_unlocked ()) >= '0')
        oper = oper * 10 + (ch - '0');
 
    while (oper --> 0)
    {
        sign = 1;
        n = 0;
 
        op = getchar_unlocked ();	// operacja
        getchar_unlocked ();	    // spacja
 
        ch = getchar_unlocked ();
        if (ch == '-')
            sign = -1;
        else
            n = ch - '0';
 
        while ((ch = getchar_unlocked ()) >= '0')
            n = n * 10 + (ch - '0');
 
        n *= sign; 
 
        switch (op)
        {
            case 'I': ins (n);         break;
            case 'D': del (n);         break;
            case 'L': lower (root, n); break;
            default:  upper (root, n);
        }
    }
 
    return 0;
}