【程设大作业】mydeque

2019-07-19 project 程设 0 Comments

记录下，那段，与 STL 斗智斗勇的岁月~

Task

一句话，实现 deque<int> 及相应的 iterator。

具体来说，你需要实现 mydeque、myIterator、myrIterator 三个类（不允许使用 STL），需要完成的功能如下：

class mydeque {
	public:
		mydeque();
		~mydeque();
		// Add element at the end
		void push_back(int num);
		// Add element at the front
		void push_front(int num);
		// Insert elements at pos
		void insert(myIterator& pos, int num);
		// Erase elements
		void earse(myIterator& pos);
		// Clear content
		void clear();
		// Access element
		int& operator[](int pos);
		// Access first element
		int& front();
		// Access last element
		int& back();
		// Return size
		int size();
		// Return iterator to beginning
		myIterator begin();
		// Return iterator to end
		myIterator end();
		// Return reverse iterator to reverse beginning
		myrIterator rbegin();
		// Return reverse iterator to reverse end
		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 {
	//与 myIterator 同理
};

可自行增加需要的函数、变量。

使用 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 效率如下：

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 得高分，就必须使尽浑身解数，斗智斗勇。

$\\$

首先简化一下我需要记录的东西：

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。

有趣的故事

我的队友老哥，想写平衡树艹它，于是写了个无旋 treap。
一开始的时候，main.cpp 里的那些关于暂停的注释是没有的，也就是说，构造 deque 是不计时间的。
这位老哥的 treap 很优秀，各操作时间很平衡，于是艹爆了 STL 的 $O(n)$ 操作。但是他复制这个 treap 的时间有点慢。
万万没想到让这个 benchmark 的测评方法给栽跟头了。由于他跑太快了，于是他要跑很多次，跑很多次的话，他的复制的时间就爆掉了。
于是就出现了“我跑得太快了，所以我超时了”。

后来可怜的助教就把注释加上了，构造 deque 也计时间，于是他的平衡树就被打爆了，不得不写标准版。

代码

// main.cpp
// 这是下发的不可修改的文件
// 程序最后可看到 18 个测试项，括号里的数字代表数据规模

#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;
    // state.PauseTiming();
    deq = constructRandomDeque(state.range(0));
    // state.ResumeTiming();
    for (auto it = deq.begin(); it != deq.end(); it++) {}
  }
}

static void BM_deqRtraverse(benchmark::State& state) {
  for (auto _ : state) {
    mydeque deq;
    // state.PauseTiming();
    deq = constructRandomDeque(state.range(0));
    // state.ResumeTiming();
    for (auto it = deq.rbegin(); it != deq.rend(); it++) {}
  }
}

static void BM_deqInsert(benchmark::State& state) {
  for (auto _ : state) {
    mydeque deq;
    // state.PauseTiming();
    deq = constructRandomDeque(state.range(0));
    // state.ResumeTiming();
    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;
    // state.PauseTiming();
    deq = constructRandomDeque(state.range(0));
    // state.ResumeTiming();
    for (long j = 0; j < state.range(1); ++j)
      deq[getRandom(0, state.range(0)-1)];
  }
}

// static void BM_deqSort(benchmark::State& state) {
//   mydeque deq;
//   for (auto _ : state) {
//     state.PauseTiming();
//     deq = constructRandomDeque(state.range(0));
//     state.ResumeTiming();
//     std::sort(deq.begin(),deq.end());
//   }
// }

// static void BM_deqShuffle(benchmark::State& state) {
//   mydeque deq;
//   for (auto _ : state) {
//     state.PauseTiming();
//     deq = constructRandomDeque(state.range(0));
//     state.ResumeTiming();
//     std::random_shuffle(deq.begin(),deq.end());
//   }
// }


// Register the function as a benchmark
BENCHMARK(BM_deqempty);
BENCHMARK(BM_deqPushBack)->Arg(32)->Arg(65536)->Arg(1L<<22);
//BENCHMARK(BM_deqPushfront)->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(BM_deqPushfront)->RangeMultiplier(32)->Range(8L, 8L<<20);
// BENCHMARK(BM_deqTraverse)->RangeMultiplier(32)->Range(8L, 8L<<20);
// BENCHMARK(BM_deqRtraverse)->RangeMultiplier(32)->Range(8L, 8L<<20);
// BENCHMARK(BM_deqInsert)->Ranges({{32L, 8L<<22}, {128, 512}});
// BENCHMARK(BM_deqErase)->Ranges({{32L, 8L<<22}, {128, 512}});
// BENCHMARK(BM_deqAt)->Ranges({{32L, 8L<<22}, {128, 512}});
// BENCHMARK(BM_deqSort)->RangeMultiplier(32)->Range(8L, 8L<<20);
// BENCHMARK(BM_deqShuffle)->RangeMultiplier(32)->Range(8L, 8L<<22);

BENCHMARK_MAIN();

// mydeque.hpp

#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

#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

#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

#include"myIterator.hpp"

//myIterator

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);
}

//myrIterator

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);
}

本文链接： http://kqp.world/programming_mydeque/
版权声明： 本博客所有文章除特别声明外，均采用 CC BY 4.0 CN协议许可协议。转载请注明出处！

kqpOIACMer / HKU_CS / LLer / TCS

糖少许，盐少许