language: C++11 (gcc-4.7.2)
date: 496 days 19 hours ago
link:
visibility: private 
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

#include <algorithm>
#include <iterator>
#include <vector>
 
template<class iterator> auto structure_dereference_operator(const iterator& r) -> typename std::iterator_traits<iterator>::pointer {return r.operator->();}
template<class type> typename std::iterator_traits<type*>::pointer structure_dereference_operator(const type*& r) {return r;}
 
template <class key_, 
          class mapped_, 
          class traits_ = std::less<key_>,
                  class undertype_ = std::vector<std::pair<key_,mapped_> >
         >
class associative
{
public:
        typedef traits_ key_compare;
        typedef key_ key_type;
        typedef mapped_ mapped_type;
        typedef std::pair<const key_type, mapped_type> value_type;
        typedef typename undertype_::allocator_type allocator_type;
        typedef typename allocator_type::template rebind<value_type>::other value_allocator_type;
        typedef typename undertype_::const_iterator const_iterator;
 
        class value_compare {
                key_compare pred_;
        public:
                inline value_compare(key_compare pred=key_compare()) : pred_(pred) {}
                inline bool operator()(const value_type& left, const value_type& right) const {return pred_(left.first,right.first);}
                inline bool operator()(const value_type& left, const key_type& right) const {return pred_(left.first,right);}
                inline bool operator()(const key_type& left, const value_type& right) const {return pred_(left,right.first);}
                inline bool operator()(const key_type& left, const key_type& right) const {return pred_(left,right);}
                inline key_compare key_comp( ) const {return pred_;}
        };
        class iterator  {
        public:       
                typedef typename value_allocator_type::difference_type difference_type;
                typedef typename value_allocator_type::value_type value_type;
                typedef typename value_allocator_type::reference reference;
                typedef typename value_allocator_type::pointer pointer;
                typedef std::bidirectional_iterator_tag iterator_category;
                inline iterator(const typename undertype_::iterator& rhs) : data(rhs) {}
                inline pointer operator->() const {return reinterpret_cast<pointer>(structure_dereference_operator(data));}
                operator const_iterator&() const {return data;}
        protected:
                typename undertype_::iterator data;
        };
 
    template<class input_iterator>
    inline associative(input_iterator first, input_iterator last) : internal_(first, last), comp_() 
        {if (std::is_sorted(internal_.begin(), internal_.end())==false) std::sort(internal_.begin(), internal_.end(), comp_);}
 
        inline iterator find(const key_type& key) {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
    inline const_iterator find(const key_type& key) const {return std::lower_bound(internal_.begin(), internal_.end(), key, comp_);}
 
protected:
        undertype_ internal_;
        value_compare comp_;
};
 
#include <cstdlib>
#include <ctime>
#include <fstream>
#include <iomanip>
#include <iostream>
#include <map>
 
#ifdef _DEBUG
#define WARMUP_TIME_MILLISECONDS 1
#define TEST_TIME_MILLISECONDS 9
#else
#define WARMUP_TIME_MILLISECONDS 10
#define TEST_TIME_MILLISECONDS 400
#endif
 
template<unsigned int size>
struct payload {
        int data[size/4];
        payload() {data[0]=rand()*RAND_MAX+rand();}
        bool operator==(const payload& rhs) const {return data[0]==rhs.data[0];}
        bool operator<(const payload& rhs) const {return data[0]<rhs.data[0];}
};
 
template<class load, class container>
void test_internal(const std::vector<std::pair<load, load>>& data, const char* classname, const char* payloadname) {
        clock_t beg,end,elapsed,freq;
        unsigned int count=0;
        bool timed=false;
        freq = CLOCKS_PER_SEC;
 
        std::vector<std::pair<load, load>> shuffled(data.begin(), data.end());
        std::random_shuffle(shuffled.begin(), shuffled.end());
        std::vector<std::pair<load, load>> sorted(data.begin(), data.end());
        std::sort(sorted.begin(), sorted.end());
        
        std::cout << payloadname << ' ' << std::setw(4) << data.size() << ' ' << classname << ' ';
        timed = false;
        elapsed = 0;
        {
            container a(data.begin(), data.end());
                do {
                        beg = clock();
                        auto i=a.find(shuffled[count%data.size()].first);
                        end = clock();
                        elapsed += end-beg;
                        if (elapsed>WARMUP_TIME_MILLISECONDS && !timed) {
                                elapsed =0;
                                count=0;
                                timed = true;
                        }
                        ++count;
                } while(elapsed<TEST_TIME_MILLISECONDS);
        }
        std::cout << std::setw(9) << count << '\n';
}
 
template<class load>
void test(const std::vector<std::pair<load, load>> &data, const char* payload_name) {
        std::vector<std::pair<load, load>> use(data.begin(), data.begin()+8);
        for( ; ; ) {
                test_internal<load, std::map   <load,load>>(use, "std::map", payload_name);
                test_internal<load, associative<load,load,std::less<load>,std::vector<std::pair<load,load>>>>(use, "astv/vec", payload_name);
                if (use.size()<1024)
                        use.insert(use.end(), data.begin()+use.size()*1ull, data.begin()+use.size()*2ull);
                else if (use.size() != data.size())
                        use.insert(use.end(), data.begin()+use.size(), data.end());
                else break;
        }
}
 
int main() {
        test(std::vector<std::pair<payload<  4>,payload<  4>>>(2000), "payload<  4>");
        test(std::vector<std::pair<payload<  8>,payload<  8>>>(2000), "payload<  8>");
        test(std::vector<std::pair<payload< 16>,payload< 16>>>(2000), "payload< 16>");
        test(std::vector<std::pair<payload< 32>,payload< 32>>>(2000), "payload< 32>");
        test(std::vector<std::pair<payload< 64>,payload< 64>>>(2000), "payload< 64>");
        test(std::vector<std::pair<payload<128>,payload<128>>>(2000), "payload<128>");
 
        return 0;
}
 
  • upload with new input
  • # 1:   hide   clone   input   496 days 19 hours ago

    result: Success     time: 4.47s    memory: 3548 kB     returned value: 0 

    payload<  4>    8 std::map     33599
payload<  4>    8 astv/vec     18834
payload<  4>   16 std::map     22176
payload<  4>   16 astv/vec     32884
payload<  4>   32 std::map     60337
payload<  4>   32 astv/vec      2994
payload<  4>   64 std::map     18328
payload<  4>   64 astv/vec     56509
payload<  4>  128 std::map     40379
payload<  4>  128 astv/vec     39685
payload<  4>  256 std::map     19003
payload<  4>  256 astv/vec     13880
payload<  4>  512 std::map     36029
payload<  4>  512 astv/vec     72882
payload<  4> 1024 std::map     38000
payload<  4> 1024 astv/vec     21224
payload<  4> 2000 std::map     20498
payload<  4> 2000 astv/vec     43237
payload<  8>    8 std::map     50547
payload<  8>    8 astv/vec     16165
payload<  8>   16 std::map     51889
payload<  8>   16 astv/vec     39787
payload<  8>   32 std::map     17533
payload<  8>   32 astv/vec      5623
payload<  8>   64 std::map     17828
payload<  8>   64 astv/vec      1460
payload<  8>  128 std::map     17643
payload<  8>  128 astv/vec     39168
payload<  8>  256 std::map     23735
payload<  8>  256 astv/vec     12991
payload<  8>  512 std::map     51787
payload<  8>  512 astv/vec      7220
payload<  8> 1024 std::map     38081
payload<  8> 1024 astv/vec      7759
payload<  8> 2000 std::map     35414
payload<  8> 2000 astv/vec     37628
payload< 16>    8 std::map     16674
payload< 16>    8 astv/vec     14736
payload< 16>   16 std::map     54363
payload< 16>   16 astv/vec     17580
payload< 16>   32 std::map     57727
payload< 16>   32 astv/vec     21364
payload< 16>   64 std::map     21711
payload< 16>   64 astv/vec      3590
payload< 16>  128 std::map     21913
payload< 16>  128 astv/vec     44745
payload< 16>  256 std::map     14510
payload< 16>  256 astv/vec     28358
payload< 16>  512 std::map     38299
payload< 16>  512 astv/vec     11352
payload< 16> 1024 std::map     58018
payload< 16> 1024 astv/vec     29524
payload< 16> 2000 std::map     34784
payload< 16> 2000 astv/vec     15695
payload< 32>    8 std::map     40986
payload< 32>    8 astv/vec     18771
payload< 32>   16 std::map     16305
payload< 32>   16 astv/vec     24076
payload< 32>   32 std::map     16483
payload< 32>   32 astv/vec      3688
payload< 32>   64 std::map     56859
payload< 32>   64 astv/vec     33015
payload< 32>  128 std::map     25408
payload< 32>  128 astv/vec     11563
payload< 32>  256 std::map     55746
payload< 32>  256 astv/vec     20071
payload< 32>  512 std::map     35143
payload< 32>  512 astv/vec     41944
payload< 32> 1024 std::map     28021
payload< 32> 1024 astv/vec     54433
payload< 32> 2000 std::map     35346
payload< 32> 2000 astv/vec     24254
payload< 64>    8 std::map     15495
payload< 64>    8 astv/vec     18337
payload< 64>   16 std::map     10669
payload< 64>   16 astv/vec     17765
payload< 64>   32 std::map     16545
payload< 64>   32 astv/vec     13361
payload< 64>   64 std::map     20873
payload< 64>   64 astv/vec      2897
payload< 64>  128 std::map     51171
payload< 64>  128 astv/vec     38736
payload< 64>  256 std::map     33707
payload< 64>  256 astv/vec     74476
payload< 64>  512 std::map     17517
payload< 64>  512 astv/vec     71373
payload< 64> 1024 std::map      2956
payload< 64> 1024 astv/vec     35336
payload< 64> 2000 std::map     18962
payload< 64> 2000 astv/vec     67859
payload<128>    8 std::map      1991
payload<128>    8 astv/vec     18178
payload<128>   16 std::map      6908
payload<128>   16 astv/vec     62143
payload<128>   32 std::map     14767
payload<128>   32 astv/vec      7237
payload<128>   64 std::map      1469
payload<128>   64 astv/vec     33151
payload<128>  128 std::map     19062
payload<128>  128 astv/vec     18513
payload<128>  256 std::map      4838
payload<128>  256 astv/vec     16624
payload<128>  512 std::map     22279
payload<128>  512 astv/vec     18993
payload<128> 1024 std::map     16973
payload<128> 1024 astv/vec     14686
payload<128> 2000 std::map     50912
payload<128> 2000 astv/vec     21192