首页 > 代码库 > C++ 之 over-eager evaluation 超前评估

C++ 之 over-eager evaluation 超前评估

C++之超急评估

over-eager evaluation vs.eager evaluation vs. lazy evaluation

在前面已经提到了C++地懒惰求值:不要为你程序功能之外的任何事情付出任何代价。在你总是需要执行某种计算,但是该计算地结果并不总是被用到地时候,lazy evaluation 绝对可以提高你的程序的性能。但是当计算的结果总是被需要的时候,我们的 “未雨绸缪”却可以给程序的性能带来极大的提升。

PS: 至于eager evaluation便是 “走一步看一步”,如果当前需要这个结果,那么计算处该结果。无论后面是否会被用到。

over-eager evaluation

关于over-eager evaluation的用法,下面的几个简单并且常见的例子便是很好的解释:

STL 之 vector的增长方式

在STL中,vector的空间的增长方式是 eager evaluation的最好的例子,在当前空间的capacity满时,再添加元素时,我们分配的内存时当前内存的两倍,并不仅仅只是用来刚好装下当前的新元素。关于STL的vector的insert的源代码,便可以说明:

PS: 下述代码截自: http://blog.csdn.net/shoulinjun/article/details/23450597

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
template<class T>
void MyVector<T>::insert(iterator position, size_type n, const T& value)
{
if(n <= end_of_storage - finish)
{/* enough memory */
if(n <= finish - position)
{
std::uninitialized_copy(finish-n, finish, finish);
std::copy(position, finish-n, position+n);
std::fill_n(position, n, value);
}
else
{
std::uninitialized_fill_n(finish, n - (finish - position), value);
std::uninitialized_copy(position, finish, position + n);
std::fill(position, finish, value);
}
finish += n;
}
else
{/* reallocate */
pointer new_start(NULL), new_finish(NULL);
size_type old_type = end_of_storage - start;
size_type new_size = old_type + std::max(old_type, n);
new_start = alloc.allocate(new_size);
// copy old vector to new vector
new_finish = std::uninitialized_copy(start, position, new_start);
std::uninitialized_fill_n(new_finish, n, value);
new_finish += n;
new_finish = std::uninitialized_copy(position, finish, new_finish);
alloc.deallocate(start, end_of_storage - start);
start = new_start;
finish = new_finish;
end_of_storage = new_start + new_size;
}
}

Caching 技术

在读取磁盘上的文件时,我们可以预先读取一些放在内存,降低下一次读取到该区域的开销,根据程序执行的 “局部性原理”。

分期摊还,就是降低单次操作的时间复杂度。

维护流式数据的 min max avg 值

维护一个数据结构保存当前已有数据的最大值或最小值或平均值,降低单次操作的时间复杂度(严格的讲,这里的时间复杂度指的是平均时间复杂度)。

以时间换空间的例子。

比如,要求维护一个返回最小值的栈,这就是典型的使用额外的数据结构来维护最小值,使得返回最小值的时间复杂度为O(1)。代码为 :

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
class Stack{
private:
stack<int> elemStack;
stack<int> minStack;
int minElem;
public:
Stack(){minElem=INT_MAX;}
int getMin();
void Push(int val);
void Pop();
};
int Stack::getMin()
{
if (minStack.empty())
{
cout << "Stack is empty..." << endl;
return INT_MIN;
}
else
{
return minStack.top();
}
}
void Stack::Push(int val)
{
if (elemStack.empty())
{
elemStack.push(val);
minStack.push(val);
}
else
{
elemStack.push(val);
if (val < minStack.top())
{
minStack.push(val);
}
else
{
minStack.push(minStack.top());
}
}
}
void Stack::Pop()
{
if (elemStack.empty())
{
cout << "Stack is empty..." << endl;
return;
}
elemStack.pop();
minStack.pop();
}

Final words:

  1. 如果你预期程序常常需要某个运算,那么你可以“未雨绸缪”,使用数据结构(如上面的Cache以及min stack)降低该操作的单次时间复杂度。从而提高整个程序的运行效率。
  2. 这里的over-eager evaluation与lazy evaluation并不矛盾,前者是为某些一定会做的操作未雨绸缪;后者时绝不为不必要的操作付出额外的代价。

C++ 之 over-eager evaluation 超前评估