每周总结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

Published on Aug 04, 2013 in categories links