NRV（Named Return Value）是我阅读《Inside C++ Object》碰到的第一个感兴趣的东西，书上面有Lippman的测试数据和侯捷的测试数据。当然，对于VS的效率一直没有报太大希望，但是不至于这个Lippman所说的编译器的义不容辞的优化都不做吧。可能因为侯捷用的VC5.0实在太老了，于是我自己决定测试一下。
Have you seen it?红色部分，当我第一次看到989680h的时候，它的值已经是一千万了，说白了就是MS将原来的废循环中的唯一一条不废的语句抽出来，然后在编译期就算好了这条不废语句应该有的值，然后运行时仅仅进行了一条赋值操作。而且绝的是，编译期的这个值的计算是按NRV优化后的流程进行的，即gj为1千万。。。。。。优化成这样，我不知道该怎么说了。。。。。根本就不会有任何的构造函数和拷贝构造函数的调用。
还有一个例子，MFC自动生成的文件为了调试方便，所有的new在debug版本下都被宏替换成DEBUG_NEW，实际上被替换成了类似new(void *p,const char* filename,
int line)这样的形式，为的是跟踪每次的内存分配。这也是为什么MFC程序在出现内存泄露的时候你能在VS output中看到一大堆的memory leak。问题是，因为用了宏。。。带了了很大的副作用。我个人new的时候，有的时候喜欢用new(nothrow)的形式，为的是用老的new，然后判断返回的指针是否为空，这样可以避免使用异常处理,不是我不喜欢catch。。。。公司总监说一般不要用，老是容易出问题。另外，就<<inside C++ object>>中说，就算一个程序从来不抛出异常，加上一个catch语句都会有3%~5%的效率损失。。。。这也不算是小损失了。。。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <algorithm> 4 #include <iterator> 5 #include <iostream> 6 usingnamespace std; 7 8 int randInt(int i, int j) 9 { 10 if(i > j) 11 { 12 int temp = i; 13 i
= j; 14 j
= temp; 15 } 16 17 return rand() % (j-i) + i; 18 } 19 20 void randArr1(int arr[], int n) 21 { 22 for(int i=0; i<n; ++i) 23 { 24 while(true) 25 { 26 // some thing don't like py 27 // because my randInt is create number 28 // in [0,n) and py is [0,n] 29 int temp = randInt(0, n); 30 int j = 0; 31 while(j < i) 32 { 33 if(arr[j] == temp) 34 { 35 break; 36 } 37 ++j; 38 } 39 if(j == i) 40 { 41 arr[j]
= temp; 42 break; 43 } 44 } 45 } 46 } 47 48 void randArr2(int a[], int n) 49 { 50 bool *lpb = newbool[n]; 51 memset(lpb, 0, n); 52 53 for(int i=0; i<n; ++i) 54 { 55 while(true) 56 { 57 int temp = randInt(0, n); 58 if(!lpb[temp]) 59 { 60 a[i]
= temp; 61 lpb[temp]
= true; 62 break; 63 } 64 } 65 66 } 67 68 delete lpb; 69 lpb = NULL; 70 } 71 72 void swap(int& a, int&
b) 73 { 74 int temp = a; 75 a = b; 76 b = temp; 77 } 78 79 // just
for fun,but I like it. 80 // when py
could have range and bash could have seq 81 // why cpp
couldn't have a seq like this? lol 82 template<typename T> 83 class CFBSeq 84 { 85 public: 86 CFBSeq(const T& aValue) : mValue(aValue) {
} 87 88 T operator()() 89 { 90 return mValue++; 91 } 92 93 private: 94 T mValue; 95 }; 96 97 void randArr3(int a[], int n) 98 { 99 generate(a,
a+n, CFBSeq<int>(0)); 100 101 for(int i=1; i<n; ++i) 102 { 103 swap(a[i],
a[randInt(0,i)]); 104 } 105 106 } 107 108 109 110 111 112 int main(int argc, char*
argv[]) 113 { 114 constint TIMES=100; 115 srand(time(NULL)); 116 int a[TIMES],b[TIMES],c[TIMES]; 117 randArr1(a,TIMES); 118 copy(a, a+TIMES,
ostream_iterator<int>(cout," ")); 119 printf("/n"); 120 randArr2(b,TIMES); 121 copy(b, b+TIMES,
ostream_iterator<int>(cout," ")); 122 printf("/n"); 123 randArr3(c,
TIMES); 124 copy(c, c+TIMES,
ostream_iterator<int>(cout," ")); 125 126 127 128 exit(0); 129 } 130
LUA:
1 #!/usr/bin/env
lua 2 3 math.randomseed(os.time()) 4 5 function randArr1(a,
n) 6 for i=1,n do 7 whiletruedo 8 local temp = math.random(1, n) 9 10 local j = 1 11 while j < i do 12 if a[j] == temp then 13 break 14 end 15 -- Again damed that There is no ++ 16 -- and even no composite operator += ! 17 -- No one knows that is more concision 18 -- and more effective? 19 j
= j + 1 20 end 21 22 if j == i then 23 a[i]
= temp 24 break 25 end 26 27 end 28 end 29 end 30 31 32 function randArr2(a,
n) 33 -- use nil as false as a lua's special hack 34 local bt = {} 35 for i=1,n do 36 whiletruedo 37 local temp = math.random(1,n) 38 ifnot bt[temp] then 39 a[i]
= temp 40 bt[temp]
= true 41 break 42 end 43 end 44 end 45 end 46 47 function randArr3(a,
n) 48 for i=1,n do 49 a[i]
= i 50 end 51 52 for i=1,n do 53 local temp = math.random(1,n) 54 -- one of the most things i like in lua&py 55 a[i],a[temp]
= a[temp],a[i] 56 end 57 end 58 59 60 61 -- Test Code 62 63 times = 100 64 t = {} 65 randArr1(t, times) 66 for i,v inipairs(t) do 67 io.write(v .. "
") 68 end 69 70 71 t2 = {} 72 randArr2(t2, times) 73 for i,v inipairs(t2) do 74 io.write(v .. "
") 75 end 76 77 78 t3 = {} 79 randArr3(t3, times) 80 for i,v inipairs(t3) do 81 io.write(v .. "
") 82 end 83 84 85
PYTHON:
1 #!/usr/bin/env
python 2 from random import randint 3 4 defrandArr1(a,n): 5 for i in range(n): 6 while True: 7 temp
= randint(0, n-1) 8 9 for j in range(i): 10 if a[j] == temp: 11 break; 12 # another one of the things I like in py(for else) 13 else: 14 a.append(temp) 15 break; 16 17 defrandArr2(a,n): 18 #surely it is
not need be a dict but dict is faster then list 19 bd = {} 20 for i in range(n): 21 while True: 22 temp
= randint(0, n-1) 23 if temp notin tl: 24 a.append(temp) 25 tl[temp]
= True 26 break 27 28 defrandArr3(a,n): 29 a = range(n) 30 for i in range(n): 31
temp = randint(0, n-1) 32 # like in lua 33
a[i],a[temp] = a[temp],a[i] 34 35 deftest(): 36 times = 100 37 l = [] 38 randArr1(l,
times) 39 40 print l 41 l2 = [] 42 randArr1(l2,
times) 43 print l2 44 45 l2 = [] 46 randArr1(l2,
times) 47 print l2 48 49 50 51 if __name__ == '__main__': 52 test()
BASH:
1 #!/usr/bin/env
bash 2 3 4 #
just for a range rand....let me die.... 5 #
what I had said? bash is not a good 6 #
language for describing algorithms 7 randInt() 8 { 9 locala=$1 10 localb=$2 11 12 if(( a > b )) 13 then 14 local temp 15 (( temp =a)) 16 (( a =b)) 17 (( b =temp)) 18 fi 19 20 local mi 21 (( mi = b
- a + 1)) 22 localr=$((RANDOM%${mi}+${a})) 23 echo -n $r 24 } 25 26 randArr1() 27 { 28 # only one
argument because I hate the 29 # bash's
indirect reference 30 # you can
reference the (4) binarySearch to 31 # see what
I said 32 localn=$1 33 declare-aa 34 for(( i=1; i<=n; ++i )) 35 do 36 while true 37 do 38 temp=`randInt 1$n` 39 j=1 40 while (( j<i )) 41 do 42 if(( a[j]==temp)) 43 then 44 break 45 fi 46 (( ++j )) 47 done 48 if(( j ==i)) 49 then 50 (( a[j]=temp)) 51 break 52 fi 53 done 54 done 55 56 echo${a[*]} 57 } 58 59 randArr2() 60 { 61 localn=$1 62 declare-aa 63 # used for bool array 64 declare-ab 65 for(( i=1; i<=n; ++i )) 66 do 67 while true 68 do 69 localtemp=`randInt 1$n` 70 if[-z${b[temp]}] 71 then 72 (( a[i]=temp)) 73 (( b[temp]=true)) 74 break 75 fi 76 done 77 done 78 79 echo${a[*]} 80 } 81 82 randArr3() 83 { 84 localn=$1 85 for(( i=1; i<=n; ++i )) 86 do 87 (( a[i]= i )) 88 done 89 for(( i=1; i<=n; ++i )) 90 do 91 localtemp=`randInt 1$n` 92 (( t = a[i])) 93 (( a[i]= a[temp])) 94 (( a[temp]= t )) 95 done 96 97 echo${a[*]} 98 } 99 100 101 # so slow that
I can't bear it run 100 times 102 randArr1 10 103 randArr2 10 104 randArr3 10 105
--《数据结构与算法分析c++描述》 Mark Allen Weiss著人民邮电大学出版中文版第49面， 一随机数组的三种生成算法
由于偷懒我最近老是喜欢用bash从C语言（其实好像是csh)中引进的语法，所以感觉都不是那么纯粹的bash风格（但是其实bash的风格我本来就不喜欢），老是学了不用，有一天写bash都当C语言在写就完了。今天加班比较晚，就不搞什么新内容了，将2.8的bash实现翻译成了比较纯粹的bash 风格。。。。对于没有接触过Bash的人来说更加接近天书了，enjoy it......(I hope you can)
1 #!/usr/bin/env bash 2 3 # just for
a range rand....let me die.... 4 # what I had said? bash is not a
good 5 # language
for describing algorithms 6 randInt() 7 { 8 locala=$1 9 localb=$2 10 11 if["$a"-gt"$b"] 12 then 13 localtemp=$a 14 a=$b 15 b=$temp 16 fi 17 18 localmi=$(($b-$a+1)) 19 localr=$((RANDOM%${mi}+${a})) 20 echo -n $r 21 } 22 23 randArr1() 24 { 25 # only one
argument because I hate the 26 # bash's
indirect reference 27 # you can
reference the (4) binarySearch to 28 # see what I
said 29 localn=$1 30 for i in`seq $n` 31 do 32 while true 33 do 34 temp=`randInt 1$n` 35 j=1 36 while ["$j"-lt"$i"] 37 do 38 if[${a[j]}-eq"$temp"] 39 then 40 break 41 fi 42 j=$(($j+1)) 43 done 44 if["$j"-eq"$i"] 45 then 46 a[j]=$temp 47 break 48 fi 49 done 50 done 51 52 echo${a[*]} 53 } 54 55 randArr2() 56 { 57 localn=$1 58 # used for bool array 59 for i in`seq $n` 60 do 61 while true 62 do 63 localtemp=`randInt 1$n` 64 if[-z${b[temp]}] 65 then 66 a[i]=$temp 67 b[temp]=true 68 break 69 fi 70 done 71 done 72 73 echo${a[*]} 74 } 75 76 randArr3() 77 { 78 localn=$1 79 for i in`seq $n` 80 do 81 a[i]=$i 82 done 83 for i in`seq $n` 84 do 85 localtemp=`randInt 1$n` 86 t=${a[i]} 87 a[i]=${a[temp]} 88 a[temp]=$t 89 done 90 91 echo${a[*]} 92 } 93 94 # so slow that I
can't bear it run 100 times 95 randArr1 10 96 randArr2 10 97 randArr3 10 98
1 #include <stdio.h> 2 #include <stdlib.h> 3 4 long gcd(long m, long n) 5 { 6 if(m < n) 7 { 8 long temp = m; 9 m
= n; 10 n
= temp; 11 } 12 while( n != 0) 13 { 14 long rem = m % n; 15 m
= n; 16 n
= rem; 17 } 18 19 return m; 20 } 21 22 int main(int argc, char*
argv[]) 23 { 24 printf("gcd(1989,1590)=%ld/n",gcd(1989,1590)); 25 printf("gcd(1590,1989)=%ld/n",gcd(1590,1989)); 26 exit(0); 27 } 28
LUA:
1 #!/usr/bin/env
lua 2 3 4 function gcd(m,n) 5 if m < n then 6 m,n
= n,m 7 end 8 9 while n ~= 0do 10 rem
= m % n 11 m
= n 12 n
= rem 13 end 14 15 return m 16 end 17 18 -- Test code 19 print("gcd(1989,1590)=" .. gcd(1989,1590)) 20 print("gcd(1590,1989)=" .. gcd(1590,1989)) 21
PYTHON:
1 #!/usr/bin/env
python 2 3 4 defgcd(m,n): 5 if m < n: 6 m,n
= n,m 7 8 while n != 0: 9 rem
= m % n 10 m
= n 11 n
= rem 12 13 return m 14 15 deftest(): 16 print "gcd(1989,1590)=" +
str(gcd(1989,1590)) 17 print "gcd(1590,1989)=" +
str(gcd(1590,1989)) 18 19 if __name__ == '__main__': 20 test() 21
BASH:
1 #!/usr/bin/env
bash 2 3 4 gcd() 5 { 6 m=$1 7 n=$2 8 if(( m < n )) 9 then 10 (( temp =m)) 11 (( m =n)) 12 (( n =temp)) 13 fi 14 15 while (( n !=0)) 16 do 17 (( rem = m
% n )) 18 (( m = n )) 19 (( n = rem )) 20 done 21 22 return$m 23 } 24 25 26 # test code 27 echo -n "gcd(1989,1590)=" 28 gcd 19891590 29 echo$? 30 echo -n "gcd(1590,1989)=" 31 gcd 15901989 32 echo$? 33 34 35
1 #!/usr/bin/env
lua 2 3 4 function maxSubSum1(a) 5 assert(type(a) == "table", "Argument
a must be a number array.") 6 7 local maxSum = 0 8 9 for i=1,#a do 10 for j=i,#a do 11 local thisSum = 0 12 for k=i,j do 13 thisSum
= thisSum + a[k] 14 end 15 16 if thisSum > maxSum then 17 maxSum
= thisSum 18 end 19 end 20 end 21 22 return maxSum 23 end 24 25 function maxSubSum2(a) 26 assert(type(a) == "table", "Argument
a must be a number array.") 27 28 local maxSum = 0 29 30 for i=1,#a do 31 local thisSum = 0 32 33 for j=i,#a do 34 thisSum
= thisSum + a[j] 35 36 if(thisSum > maxSum) then 37 maxSum
= thisSum 38 end 39 end 40 end 41 return maxSum 42 end 43 44 function max3(n1,
n2, n3) 45 return (n1 > n2 and ((n1 > n3) and n1 or n3) or ((n2 > n3) and n2 or n3)) 46 end 47 48 -- require
math 49 50 function maxSumRec(a,
left, right) 51 assert(type(a) == "table", "Argument
a must be a number array.") 52 assert(type(left) == "number"andtype(right) == "number", 53 "Argument left&right must be number
arrays.") 54 55 if left == right then 56 if a[left] > 0then 57 return a[left] 58 else 59 return0 60 end 61 end 62 63 local center = math.floor((left
+ right) / 2) 64 local maxLeftSum = maxSumRec(a, left,
center) 65 local maxRightSum = maxSumRec(a, center+1, right) 66 67 local maxLeftBorderSum = 0 68 local leftBorderSum = 0 69 for i=center,left,-1do 70 leftBorderSum
= leftBorderSum + a[i] 71 if leftBorderSum > maxLeftBorderSum then 72 maxLeftBorderSum
= leftBorderSum 73 end 74 i
= i - 1 75 end 76 77 local maxRightBorderSum = 0 78 local rightBorderSum = 0 79 for j=center+1,right do 80 rightBorderSum
= rightBorderSum + a[j] 81 if rightBorderSum > maxRightBorderSum then 82 maxRightBorderSum
= rightBorderSum 83 end 84 end 85 86 return max3(maxLeftSum, maxRightSum,
maxLeftBorderSum + maxRightBorderSum) 87 end 88 89 function maxSubSum3(a) 90 assert(type(a) == "table", "Argument
a must be a number array.") 91 92 return maxSumRec(a, 1, 6) 93 94 end 95 96 function maxSubSum4(a) 97 assert(type(a) == "table", "Argument
a must be a number array.") 98 99 local maxSum = 0 100 local thisSum = 0 101 102 for i=1,#a do 103 thisSum
= thisSum + a[i] 104 105 if thisSum > maxSum then 106 maxSum
= thisSum 107 elseif thisSum < 0then 108 thisSum
= 0 109 end 110 111 end 112 113 return maxSum 114 115 end 116 117 -- Test Code 118 119 t = {-2, 11, -4, 13, -5, -2} 120 121 print("maxSubSum1(t):" .. maxSubSum1(t)) 122 print("maxSubSum2(t):" .. maxSubSum2(t)) 123 print("maxSubSum3(t):" .. maxSubSum3(t)) 124 print("maxSubSum4(t):" .. maxSubSum4(t)) 125 126 127
PYTHON:
1 #!/usr/bin/env
python 2 3 # How Short
and Clean it is I shocked as a CPP Programmer 4 defmaxSubSum1(a): 5 maxSum = 0 6 7 for i in a: 8 for j in a[i:]: 9 thisSum
= 0 10 11 for k in a[i:j]: 12 thisSum
+= k 13 14 if thisSum > maxSum: 15 maxSum
= thisSum 16 17 return maxSum 18 19 defmaxSubSum2(a): 20 maxSum = 0 21 22 for i in a: 23 thisSum
= 0 24 for j in a[i:]: 25 thisSum
+= j 26 27 if thisSum > maxSum: 28 maxSum
= thisSum 29 30 return maxSum 31 32 33 defmax3(n1,
n2, n3): 34 return ((n1 if n1
> n3 else n3) if n1 > n2 else (n2 if n2 > n3 else n3)) 35 36 defmaxSumRec(a,
left, right): 37 if left == right: 38 if a[left] > 0: 39 return a[left] 40 else: 41 return 0 42 43 center = (left +
right)//2 44 maxLeftSum =
maxSumRec(a, left, center) 45 maxRightSum =
maxSumRec(a, center+1, right) 46 47 maxLeftBorderSum
= 0 48 leftBorderSum = 0 49 for i in a[center:left:-1]: 50 leftBorderSum
+= i 51 if leftBorderSum > maxLeftBorderSum: 52 maxLeftBorderSum
= leftBorderSum 53 54 maxRightBorderSum
= 0 55 rightBorderSum =
0 56 for i in a[center+1:right]: 57 rightBorderSum
+= i 58 if rightBorderSum > maxRightBorderSum: 59 maxRightBorderSum
= rightBorderSum 60 61 return max3(maxLeftSum,
maxRightBorderSum, maxLeftBorderSum + maxRightBorderSum) 62 63 defmaxSubSum3(a): 64 return maxSumRec(a, 0,
len(a)-1 ) 65 66 defmaxSubSum4(a): 67 maxSum = 0 68 thisSum = 0 69 70 for i in a: 71 thisSum
+= i 72 73 if thisSum > maxSum: 74 maxSum
= thisSum 75 elif thisSum < 0: 76 thisSum
= 0 77 78 return maxSum 79 80 deftest(): 81 t = (-2, 11, -4,
13, -5, -2) 82 83 print "maxSubSum1:%d" %
maxSubSum1(t) 84 print "maxSubSum2:%d" %
maxSubSum2(t) 85 print "maxSubSum3:%d" %
maxSubSum3(t) 86 print "maxSubSum4:%d" %
maxSubSum4(t) 87 88 if __name__ == '__main__': 89 test()
