每周总结20130804

最近周末狂看房子,耽误了不少学习的时间

1 学习了两个stl函数partition 和nth_element。
1). 功能
前者把一堆数分成两组,第一组所有元素都小于第二组的元素,而返回的就是分开这两组的索引 see http://www.sgi.com/tech/stl/partition.html
后者类似于partition,但是他的第一组数的数目为n个

2).partition算法
参考http://www.cppblog.com/feng/archive/2008/11/06/66141.html
就是快速排序partition算法
主要就是将数组最后一个元素当成比较的值
遍历数组,将所有小于该比较值的数放到左边

3)nth_element algorithm
a). 在wiki上的selection算法
SelectSort是一个O(n^2)的算法?
It's called a selection algorithm and wikipedia has a decent page on it: http://en.wikipedia.org/wiki/Selection_algorithm

Also read about order statistics: http://en.wikipedia.org/wiki/Order_statistic

b). 某人写的“记一个高效、简单的nth_element算法”
http://www.felix021.com/blog/read.php?2122

2. fortran v.s. c++以及无用的几个modifier?


1). 语言 benchmark: http://stackoverflow.com/questions/13078736/fortran-vs-c-does-fortran-still-hold-any-advantage-in-numerical-analysis-thes
可以看到在数值计算上, fortran是最快的

2). 为啥fortran快呢?

俺搜了一下网上,主要观点就是 fortran不允许aliasing of memory pointers
而c99提供了restrict功能,理论上c也能达到同样的性能 (http://en.wikipedia.org/wiki/Restrict)

啥叫不允许aliasing of memory pointers, 或者说strict-aliasing?
 means that the programmer promises that pointers of different type will never overlap, for example a double* will not overlap with an int* (with the specific exception that char* and void* can overlap with anything)

再比如void transform (float *output, float const * input, float const * matrix, int *n)
fortran会认为两个指针output,matrix没有重叠,所以会load the matrix values once and store them in registers.

3). C99 standard 也允许 restrict keyword and strict-aliasing
这两个restrict, 和strict-aliasing 有啥不同??


4). vc的几个modifier有啥不同??
俺还是没有完全搞明白restrict和noalias的差别。。。

__restrict                针对variables, 表明该符号在当前scope内不会走样indicates that a symbol is not aliased in the current scope
                        编译器不会遗传变量的no-alias属性 the compiler will not propagate the no-alias property of a variable

__declspec(restrict)    针对function declarations and definitions

__declspec(noalias)    

例子: http://msdn.microsoft.com/en-us/library/k649tyc7%28v=vs.80%29.aspx
http://msdn.microsoft.com/en-us/library/5ft82fed%28v=vs.80%29.aspx


5). 有人试了几段代码,发现这个关键字在gcc上没啥效果。。
http://stackoverflow.com/questions/12634844/examples-of-strict-aliasing-of-pointers-in-gcc-c99-no-performance-differences

Powered by Jekyll and Theme by solid

本站总访问量