benczmark 00 implementacji tablicowej drzew czerwono czarnych - kod źródłowy


  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
#include "rb_tree.h"

#include <QStringList>
#include <QRegExp>
#include <QTextStream>
#include <set>
#include <QMap>

typedef int ityp;
typedef const ityp cityp;

typedef unsigned int utyp;
typedef const utyp cutyp;

typedef long long ltyp;
typedef const long long cltyp;

typedef unsigned long long ultyp;
typedef const unsigned long long cultyp;

class Empty {};

void testSet( cityp loop , cityp subloop , cityp size_i , cityp size_r , cityp size_f, cltyp range , cltyp seed ) {
    QTextStream out(stdout);
    std::mt19937_64 rnd(seed);
    ultyp sum = 1;
    ultyp m = 1;
    std::set<utyp> set;
    for( ityp i=0 ; i<loop ; i++ ) {
        for( ityp j=0 ; j<subloop ; j++ ) {
            for( ityp k=0 ; k<size_i ; k++ ) {
                set.insert(rnd() % range);
            }
            for( ityp k=0 ; k<size_r ; k++ ) {
                set.erase( rnd() % (range*32/31) );
            }
//            out << "size:" << set.size() << " " << i << " " << j << endl;
            sum += set.size();
            for( int k=0 ; k<size_f ; k++ ) {
                const auto node = set.find( rnd() % (range*32/31) );
                if( node != set.cend() ) {
                    sum += *node * m;
                    m += rnd() % 1024;
                }
            }
        }
        set.clear();
    }
    out << "sum:" << sum << endl;
}


void testMap( cityp loop , cityp subloop , cityp size_i , cityp size_r , cityp size_f, cltyp range , cltyp seed ) {
    QTextStream out(stdout);
    std::mt19937_64 rnd(seed);
    ultyp sum = 1;
    ultyp m = 1;
    QMap<utyp,Empty> map;
    for( ityp i=0 ; i<loop ; i++ ) {
        for( ityp j=0 ; j<subloop ; j++ ) {
            for( ityp k=0 ; k<size_i ; k++ ) {
                map.insert(rnd() % range,Empty());
            }
            for( ityp k=0 ; k<size_r ; k++ ) {
                map.remove( rnd() % (range*32/31) );
            }
//            out << "size:" << set.size() << " " << i << " " << j << endl;
            sum += map.size();
            for( int k=0 ; k<size_f ; k++ ) {
                const auto key = map.find( rnd() % (range*32/31) );
                if( key != map.cend() ) {
                    sum += key.key() * m;
                    m += rnd() % 1024;
                }
            }
        }
        map.clear();
    }
    out << "sum:" << sum << endl;
}


void testRB( cityp loop , cityp subloop , cityp size_i , cityp size_r , cityp size_f, cltyp range , cltyp seed ) {
    QTextStream out(stdout);
    std::mt19937_64 rnd(seed);
    ultyp sum = 1;
    ultyp m = 1;
    RBTree<utyp> rb;
    for( ityp i=0 ; i<loop ; i++ ) {
        for( ityp j=0 ; j<subloop ; j++ ) {
            for( ityp k=0 ; k<size_i ; k++ ) {
                rb.insert(rnd() % range);
            }
            for( ityp k=0 ; k<size_r ; k++ ) {
                const auto node = rb.search( rnd() % (range*32/31) );
                if( ! rb.isNull(node) )
                    rb.remove(node);
            }
//            out << "size:" << set.size() << " " << i << " " << j << endl;
            sum += rb.size();
            for( int k=0 ; k<size_f ; k++ ) {
                const auto node = rb.search( rnd() % (range*32/31) );
                if( ! rb.isNull(node) ) {
                    sum += rb.cData(node) * m;
                    m += rnd() % 1024;
                }
            }
        }
        rb.clear();
    }
    out << "sum:" << sum << endl;
}


void testRBSort( cityp loop , cityp subloop , cityp size_i , cityp size_r , cityp size_f, cltyp range , cltyp seed ) {
    QTextStream out(stdout);
    std::mt19937_64 rnd(seed);
    ultyp sum = 1;
    ultyp m = 1;
    RBTree<utyp> rb;
    for( ityp i=0 ; i<loop ; i++ ) {
        for( ityp j=0 ; j<subloop ; j++ ) {
            for( ityp k=0 ; k<size_i ; k++ ) {
                rb.insert(rnd() % range);
            }
            for( ityp k=0 ; k<size_r ; k++ ) {
                const auto node = rb.search( rnd() % (range*32/31) );
                if( ! rb.isNull(node) )
                    rb.remove(node);
            }
            rb.sort();
//            out << "size:" << set.size() << " " << i << " " << j << endl;
            sum += rb.size();
            for( int k=0 ; k<size_f ; k++ ) {
                const auto node = rb.sortSearch( rnd() % (range*32/31) );
                if( ! rb.isNull(node) ) {
                    sum += rb.cData(node) * m;
                    m += rnd() % 1024;
                }
            }
        }
        rb.clear();
    }
    out << "sum:" << sum << endl;
}


int main(int argc, char *argv[])
{
    QTextStream out(stdout);
    if( argc != 9 ) {
        out << "use\nrb00 test loop subloop size_i size_r size_f range seed" << endl;
        abort();
    }

    const QString test = argv[1];
    cityp loop         = QString(argv[2]).toInt();
    cityp subloop      = QString(argv[3]).toInt();
    cityp size_i       = QString(argv[4]).toInt();
    cityp size_r       = QString(argv[5]).toInt();
    cityp size_f       = QString(argv[6]).toInt();
    cltyp range        = QString(argv[7]).toLongLong();
    cltyp seed         = QString(argv[8]).toLongLong();

    if( test.toLower() == "testset" )
        testSet( loop , subloop , size_i , size_r , size_f , range , seed );
    else if( test.toLower() == "testmap" )
        testMap( loop , subloop , size_i , size_r , size_f , range , seed );
    else if( test.toLower() == "testrb" )
        testRB( loop , subloop , size_i , size_r , size_f , range , seed );
    else if( test.toLower() == "testrbsort" )
        testRBSort( loop , subloop , size_i , size_r , size_f , range , seed );
    else if( test.toLower() == "profile") {
        testSet( loop , subloop , size_i , size_r , size_f , range , seed );
        testMap( loop , subloop , size_i , size_r , size_f , range , seed );
        testRB( loop , subloop , size_i , size_r , size_f , range , seed );
        testRBSort( loop , subloop , size_i , size_r , size_f , range , seed );
    }

    return 0;
}

Komentarze

Popularne posty z tego bloga

benchmark 00 tablicowej implementacji drzew czerwono czarnych

metodyka testowania implementacji drzew czerwono czarnych na bazie tablicy