记录下,那段,与 STL 斗智斗勇的岁月~
Task
一句话,实现 deque<int>
及相应的 iterator
。
具体来说,你需要实现 mydeque
、myIterator
、myrIterator
三个类(不允许使用 STL),需要完成的功能如下:
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
| class mydeque { public: mydeque(); ~mydeque(); void push_back(int num); void push_front(int num); void insert(myIterator& pos, int num); void earse(myIterator& pos); void clear(); int& operator[](int pos); int& front(); int& back(); int size(); myIterator begin(); myIterator end(); myrIterator rbegin(); myrIterator rend(); }; class myIterator { public: myIterator& operator= (const myIterator &iter); bool operator!= (const myIterator &iter); bool operator== (const myIterator &iter); myIterator& operator++ (); myIterator operator++ (int); myIterator operator+ (int num); }; class myrIterator { };
|
可自行增加需要的函数、变量。
使用 Linux 下的 benchmark 评分。评分标准为跟 STL 比速度,共 18 个测试项(具体看后面的 main.cpp),每个测试项满分为 6 分,总分最终不超过 100 分。(基准实验指 class mydeque : public stl::deque<int> {}
)
- 程序正确运行,没有崩溃,内存泄露等错误(3.6分)
- 程序运行效率达到基准实验的60%(4.2分)
- 程序运行效率达到基准实验的70%(6.8分)
- 程序运行效率达到基准实验的80%(5.4分)
- 程序运行效率达到基准实验的100%(6分)
STL 效率如下:
![](/images/mydeque1.png)
Iteration 我猜是一个自适应的迭代次数,就是如果你跑得快,就可以多跑一些,跑得慢就会少跑一些,最终用自己的 Iteration 除以 STL 的 Iteration 就可以直到效率比了。
Sol
deque 的特性是,$O(1)$ 前端后端插入、随机访问,$O(n)$ 中间插入、删除。要做到这样,最方便的是使用一个长长的一维数组,但是这样的话迁移的效率又不是很高,而且对内存要求苛刻,因此折中一下使用块状链表,有一个大数组 map
,里面的每一个元素都指向一个小数组,即双层数组结构。
然后它的 iterator 比较复杂,要记录两层数组的下标、所在第二层数组的开头、结尾,具体参考《STL源码剖析》。
然而,要深知,照着 STL 的写法来写一遍,是会有 debuff 的,是永远也别想跟它比效率的。
比如,就 for (auto it = deq.begin(); it != deq.end(); it++) {}
这句话,如果在 it++
里执行了大于等于两个操作,你甚至可能要跑 STL 的几倍到十几倍时间。。。
要想艹 STL 得高分,就必须使尽浑身解数,斗智斗勇。
首先简化一下我需要记录的东西:
1 2 3 4
| struct MapType { int *a,num; } *map; int head,tail,l,r,maxsize,totsize;
|
map[i].a[j]
就是一个双层数组结构,用于存放东西,用一个常数 alen
表示每个 map.a[]
的定长,maxsize
表示第一层也就是 map[]
的长度(这个是要不断倍长、迁移的)。STL 的写法中记录了一头一尾两个 iterator,在这里我用 head
和 l
表示头的两个下标,tail
和 r
表示尾的两个下标。
做法很简单,push_back()
和 push_front()
就直接往两边放,第二层不够了就新开第二层,第一层不够了就整体倍长迁移(像 vector 那样)。insert()
就直接找到那个位置,然后把它右边的元素全部往后推一位,erase()
同理。由于第二层数组是定长的,因此简单算个数就能使用 []
访问了。
一些优化:
比如说,myIterator 里就只放一个下标,表示它是从左往右数第几个数。毕竟测试项里没有通过 iterator 访问元素这一项,那我就牺牲这个的复杂度(把它转成通过 []
来访问),换取一个飞快的 for (auto it = deq.begin(); it != deq.end(); it++) {}
。
insert()
和 erase()
在 STL 里都用 iterator 来写,那么我就直接 for 循环,避免过多的调用。
能用 memcpy
就不要用 for 循环,要始终坚信它写的东西就是比你的快。
一个重要的优化是,insert()
不要鲁莽地全部往右推,判断一下它是在整个结构的左半边还是右半边,如果在左半边就左边的往左推,如果在右半边就往右推。简单分析一下效率,如果一味往右推,单次操作期望次数 $\frac{n^2}{2}$,优化以后单次操作期望次数 $2\times\frac{(\frac n2)^2}{2}=\frac{n^2}{4}$,能优化掉一半的时间。erase()
同理。
块大小 alen
可以调调参,理论上当它取 $\sqrt n$ 的时候效率是最优的(学分块学疯了),但是 $n$ 在实际中是未知的,而且恰好取到 $\sqrt n$ 的时候其实挺慢的,STL 其实也取得很小。
写时复制。这个我没加,但是对于这个题来说(详见 main.cpp,构造了一个 deque 之后传来传去的)显然是一个十分有用的优化。写了的人说十分有用。
自己写内存分配,不要用 new
和 free
。这两个贼慢,详见 舍友的博客。
放一波效率图,可以看到效率其实还是很烂,毕竟 STL 自带了很多 buff。
![](/images/mydeque2.png)
有趣的故事
我的队友老哥,想写平衡树艹它,于是写了个无旋 treap。
一开始的时候,main.cpp 里的那些关于暂停的注释是没有的,也就是说,构造 deque 是不计时间的。
这位老哥的 treap 很优秀,各操作时间很平衡,于是艹爆了 STL 的 $O(n)$ 操作。但是他复制这个 treap 的时间有点慢。
万万没想到让这个 benchmark 的测评方法给栽跟头了。由于他跑太快了,于是他要跑很多次,跑很多次的话,他的复制的时间就爆掉了。
于是就出现了“我跑得太快了,所以我超时了”。
后来可怜的助教就把注释加上了,构造 deque 也计时间,于是他的平衡树就被打爆了,不得不写标准版。
代码
// main.cpp
// 这是下发的不可修改的文件
// 程序最后可看到 18 个测试项,括号里的数字代表数据规模
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
| #include <benchmark/benchmark.h> #include <algorithm> #include <random>
#include "mydeque.hpp"
long getRandom(long from=0, long to=65536) { return (rand() % (to-from+1)) + from; }
mydeque constructRandomDeque(long num) { mydeque deq; for (long i = 0; i < num; i++) { deq.push_back(i); } return deq; }
static void BM_deqempty(benchmark::State& state) { for (auto _ : state) { mydeque deq; } }
static void BM_deqPushBack(benchmark::State& state) { for (auto _ : state) { mydeque deq; for (long i = 0; i < state.range(0); i++) { deq.push_back(i); } } }
static void BM_deqPushfront(benchmark::State& state) { for (auto _ : state) { mydeque deq; for (long i = 0; i < state.range(0); i++) { deq.push_front(i); } } }
static void BM_deqTraverse(benchmark::State& state) { for (auto _ : state) { mydeque deq; deq = constructRandomDeque(state.range(0)); for (auto it = deq.begin(); it != deq.end(); it++) {} } }
static void BM_deqRtraverse(benchmark::State& state) { for (auto _ : state) { mydeque deq; deq = constructRandomDeque(state.range(0)); for (auto it = deq.rbegin(); it != deq.rend(); it++) {} } }
static void BM_deqInsert(benchmark::State& state) { for (auto _ : state) { mydeque deq; deq = constructRandomDeque(state.range(0)); for (int j = 0; j < state.range(1); ++j) deq.insert(deq.begin()+getRandom(0, deq.size()-1), getRandom()); } }
static void BM_deqErase(benchmark::State& state) { for (auto _ : state) { mydeque deq; state.PauseTiming(); deq = constructRandomDeque(state.range(0)); int max = state.range(0) > state.range(1) ? state.range(0) : state.range(1); state.ResumeTiming(); for (long j = 0; j < state.range(1); ++j) { if (deq.size()==0) break; deq.erase(deq.begin()+getRandom(0, max-1-j)); } } }
static void BM_deqAt(benchmark::State& state) { for (auto _ : state) { mydeque deq; deq = constructRandomDeque(state.range(0)); for (long j = 0; j < state.range(1); ++j) deq[getRandom(0, state.range(0)-1)]; } }
BENCHMARK(BM_deqempty); BENCHMARK(BM_deqPushBack)->Arg(32)->Arg(65536)->Arg(1L<<22);
BENCHMARK(BM_deqTraverse)->Arg(32)->Arg(65536)->Arg(1L<<22); BENCHMARK(BM_deqRtraverse)->Arg(32)->Arg(65536)->Arg(1L<<22); BENCHMARK(BM_deqInsert)->Args({32, 512})->Args({65536, 512})->Args({1L<<22, 512}); BENCHMARK(BM_deqErase)->Args({512, 512})->Args({65536, 512})->Args({1L<<22, 512}); BENCHMARK(BM_deqAt)->Args({32, 128})->Args({65536, 128});
BENCHMARK_MAIN();
|
// mydeque.hpp
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
| #ifndef MYDEQUE_HPP #define MYDEQUE_HPP
#include"myIterator.hpp"
class mydeque { public: struct MapType { int *a,num; } *map; int head,tail,l,r,maxsize,totsize; void NewMapType(MapType &x); void ChangeMap(); inline void Release(); inline void init(); mydeque(); ~mydeque(); mydeque& operator = (const mydeque &deq); void push_back(const int &val); void push_front(const int &val); void insert(myIterator pos,int val); void erase(const myIterator &pos); void clear(); int& operator [] (int i); int& front(); int& back(); int size(); myIterator begin(); myIterator end(); myrIterator rbegin(); myrIterator rend(); };
#endif
|
// myIterator.hpp
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
| #ifndef MYITERATOR_HPP #define MYITERATOR_HPP
const int alen=130;
class myIterator { public: int pos; myIterator(int x=0); bool operator != (const myIterator &iter); bool operator == (const myIterator &iter); myIterator& operator ++ (); myIterator& operator -- (); myIterator operator ++ (int); myIterator operator + (int num); };
class myrIterator { public: int pos; myrIterator(int x=0); bool operator != (const myrIterator &iter); bool operator == (const myrIterator &iter); myrIterator& operator ++ (); myrIterator& operator -- (); myrIterator operator ++ (int); myrIterator operator + (int num); };
#endif
|
// mydeque.cpp
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 182 183
| #include<cstring> #include"mydeque.hpp" #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std;
inline void mydeque::NewMapType(mydeque::MapType &x) { x.a=new int[alen+2]; x.num=0; }
void mydeque::ChangeMap() { int len=maxsize, half=len>>1; maxsize<<=1; MapType *newmap=new MapType[maxsize+2]; memcpy(newmap+half,map,len*sizeof(MapType)); delete[] map; map=newmap; head+=half, tail+=half; }
inline void mydeque::Release() { fo(i,head,tail) delete[] map[i].a; delete[] map; }
inline void mydeque::init() { maxsize=2; map=new MapType[maxsize+2]; NewMapType(map[1]); head=tail=1; l=1, r=0; totsize=0; }
mydeque::mydeque() { init(); }
mydeque::~mydeque() { Release(); }
mydeque& mydeque::operator = (const mydeque &deq) { Release(); maxsize=deq.maxsize; head=deq.head, tail=deq.tail; l=deq.l, r=deq.r; totsize=deq.totsize; map=new MapType[maxsize+2]; fo(i,head,tail) { map[i].num=deq.map[i].num; map[i].a=new int[alen+2]; memcpy(map[i].a,deq.map[i].a,sizeof(map[i].a)); } }
void mydeque::push_back(const int &val) { if (r==alen) { if (tail==maxsize-1) ChangeMap(); NewMapType(map[++tail]); r=0; } map[tail].num++; map[tail].a[++r]=val; totsize++; }
void mydeque::push_front(const int &val) { if (l==1) { if (head==0) ChangeMap(); NewMapType(map[--head]); l=alen+1; } map[head].num++; map[head].a[--l]=val; totsize++; }
void mydeque::insert(myIterator pos,int val) { if (pos.pos>=(totsize>>1)) { push_back(0); for(int i=tail, cnt=totsize-1; cnt!=pos.pos; --i) for(int j=(i==tail ?r :alen); j>=1 && cnt!=pos.pos; --j, --cnt) map[i].a[j]=(j==1) ?map[i-1].a[alen] :map[i].a[j-1] ; } else { push_front(0); for(int i=head, cnt=0; cnt!=pos.pos; ++i) for(int j=(i==head ?l :1); j<=alen && cnt!=pos.pos; ++j, ++cnt) map[i].a[j]=(j==alen) ?map[i+1].a[1] :map[i].a[j+1] ; } (*this)[pos.pos]=val; }
void mydeque::erase(const myIterator &pos) { if (pos.pos>=(totsize>>1)) { for(int i=tail, cnt=totsize-1, last=map[i].a[(i==tail ?r :alen)], t, *p; cnt!=pos.pos; --i) for(int j=(i==tail ?r :alen); j>=1 && cnt!=pos.pos; --j, --cnt) { p=(j==1) ?&(map[i-1].a[alen]) :&(map[i].a[j-1]) ; t=*p, *p=last, last=t; } map[tail].num--; if (--r==0) {delete[] map[tail--].a; r=alen;} } else { for(int i=head, cnt=0, last=map[i].a[(i==head ?l :1)], t, *p; cnt!=pos.pos; ++i) for(int j=(i==head ?l :1); j<=alen && cnt!=pos.pos; ++j, ++cnt) { p=(j==alen) ?&(map[i+1].a[1]) :&(map[i].a[j+1]) ; t=*p, *p=last, last=t; } map[head].num--; if (++l>alen) {delete[] map[head++].a; l=1;} } totsize--; }
void mydeque::clear() { Release(); init(); }
int& mydeque::operator [] (int i) { if (i<map[head].num) return map[head].a[l+i]; i-=map[head].num; int index=i/alen; return map[head+index+1].a[i-index*alen+1]; }
int& mydeque::front() { return map[head].a[l]; }
int& mydeque::back() { return map[tail].a[r]; }
int mydeque::size() { return totsize; }
myIterator mydeque::begin() { return myIterator(0); }
myIterator mydeque::end() { return myIterator(totsize); }
myrIterator mydeque::rbegin() { return myrIterator(totsize-1); }
myrIterator mydeque::rend() { return myrIterator(-1); }
|
// myIterator.cpp
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
| #include"myIterator.hpp"
bool myIterator::operator != (const myIterator &iter) { return (this->pos!=iter.pos); }
bool myIterator::operator == (const myIterator &iter) { return (this->pos==iter.pos); }
myIterator::myIterator(int x) { pos=x; }
myIterator& myIterator::operator ++ () { ++pos; return *this; }
myIterator& myIterator::operator -- () { --pos; return *this; }
myIterator myIterator::operator ++ (int) { myIterator re=*this; ++pos; return re; }
myIterator myIterator::operator + (int num) { return myIterator(this->pos+num); }
bool myrIterator::operator != (const myrIterator &iter) { return (this->pos!=iter.pos); }
bool myrIterator::operator == (const myrIterator &iter) { return (this->pos==iter.pos); }
myrIterator::myrIterator(int x) { pos=x; }
myrIterator& myrIterator::operator ++ () { --pos; return *this; }
myrIterator& myrIterator::operator -- () { ++pos; return *this; }
myrIterator myrIterator::operator ++ (int) { myrIterator re=*this; --pos; return re; }
myrIterator myrIterator::operator + (int num) { return myrIterator(this->pos-num); }
|