洗牌的技巧

蘇蓉蓉

參看：

如何用shell實現(xiàn)“洗牌”效果？
文本文件隨機取幾萬行怎么�。�

1. 
   
2. 
   
3. 
   
4.                                       洗牌的技巧
   
5. 
   
6. 
   
7. 
   
8. 
   
9. 
   
10. 
    
11. 
    
12.     洗牌問題：
    
13. 
    
14.     洗一副撲克，有什么好辦法？既能洗得均勻，又能洗得快？即相對于一個文件來說怎樣
    
15. 高效率的實現(xiàn)亂序排列？
    
16. 
    
17.     關(guān)于洗牌問題，其實已經(jīng)有了一個很好的shell解法，這里另外給三個基于AWK的方法，
    
18. 有錯誤之處還請不吝指出。
    
19. 
    
20. 
    
21. 
    
22. 方法一窮舉：
    
23.     類似于窮舉法，構(gòu)造一個散列來記錄已經(jīng)打印行出現(xiàn)行的次數(shù)，如果出現(xiàn)次數(shù)多于一
    
24. 次則不進行處理，這樣可以防止重復，但缺點是加大了系統(tǒng)的開銷。
    
25. 
    
26. 
    
27. 
    
28. awk -v N=`sed -n '$=' data` '
    
29. BEGIN{
    
30. FS="\n";
    
31. RS=""
    
32. }
    
33. {
    
34. srand();
    
35. while(t!=N){
    
36.   x=int(N*rand()+1);
    
37.   a[x]++;
    
38.   if(a[x]==1)
    
39.     {
    
40.         print $x;t++
    
41.     }
    
42.   }
    
43. }
    
44. ' data
    
45. 
    
46. 
    
47. 方法二變換：
    
48.     基于數(shù)組下標變換的辦法，即用數(shù)組儲存每行的內(nèi)容，通過數(shù)組下標的變換
    
49. 交換數(shù)組的內(nèi)容，效率好于方法一。
    
50. 
    
51. 
    
52. #! /usr/awk
    
53. 
    
54. BEGIN{
    
55. srand();
    
56. }
    
57. 
    
58. 
    
59. {
    
60. b[NR]=$0;
    
61. }
    
62. 
    
63. 
    
64. END{
    
65. 
    
66. C(b,NR);
    
67. for(x in b)
    
68.   {
    
69.     print b[x];
    
70.   }
    
71. 
    
72. }
    
73. 
    
74. 
    
75. function C(arr,len,i,j,t,x){
    
76. 
    
77. for(x in arr)
    
78.   {
    
79.       i=int(len*rand())+1;
    
80.       j=int(len*rand())+1;
    
81.       t=arr[i];
    
82.       arr[i]=arr[j];
    
83.       arr[j]=t;
    
84.   }
    
85. 
    
86. }
    
87. 
    
88. 
    
89. 
    
90. 
    
91. 方法三散列：
    
92. 
    
93.     三個方法中最好的。
    
94.     利用AWK中散列的特性(詳細請看：info gawk 中的7.x ),只要構(gòu)造一個
    
95. 隨機不重復的散列函數(shù)即可，因為一個文件每行的linenumber是獨一無二的，所
    
96. 以用：
    
97. 
    
98.     隨機數(shù)＋每行l(wèi)inenumber    ------對應------>    那一行的內(nèi)容
    
99. 
    
100. 即為所構(gòu)造的隨機函數(shù)。
     
101.     從而有：
     
102. 
     
103. 
     
104.     awk 'BEGIN{srand()}{b[rand()NR]=$0}END{for(x in b)print b[x]}' data
     
105. 
     
106. 
     
107. 
     
108. 
     
109. 
     
110. 
     
111. 
     
112.     其實大家擔心的使用內(nèi)存過大的問題不必太在意，可以做一個測試：
     
113. 
     
114. 測試環(huán)境：
     
115. PM 1.4GHz CPU,40G硬盤，內(nèi)存256M的LAPTOP
     
116. SUSE 9.3  GNU bash version 3.00.16 GNU Awk 3.1.4
     
117. 
     
118. 產(chǎn)生一個五十幾萬行的隨機文件,大約有38M：
     
119. 
     
120. od /dev/urandom |dd  count=75000 >data
     
121. 
     
122. 
     
123. 
     
124. 拿效率較低的方法一來說:
     
125. 
     
126. 洗牌一次所用時間:
     
127. 
     
128. time awk -v N=`sed -n '$=' data` '
     
129. BEGIN{
     
130. FS="\n";
     
131. RS=""
     
132. }
     
133. {
     
134. srand();
     
135. while(t!=N){
     
136.   x=int(N*rand()+1);
     
137.   a[x]++;
     
138.   if(a[x]==1)
     
139.     {
     
140.         print $x;t++
     
141.     }
     
142.   }
     
143. }
     
144. ' data
     
145. 
     
146. 結(jié)果（文件內(nèi)容省略）：
     
147. 
     
148. 
     
149. real    3m41.864s
     
150. user    0m34.224s
     
151. sys     0m2.102s
     
152. 
     
153. 
     
154. 所以效率還是勉強可以接受的。
     
155. 
     
156. 方法二的測試:
     
157. 
     
158. time awk -f awkfile datafile
     
159. 
     
160. 結(jié)果（文件內(nèi)容省略）：
     
161. 
     
162. real    2m26.487s
     
163. user    0m7.044s
     
164. sys     0m1.371s
     
165. 
     
166. 效率明顯好于第一個。
     
167. 
     
168. 
     
169. 接著考察一下方法三的效率：
     
170. 
     
171. time awk 'BEGIN{srand()}{b[rand()NR]=$0}END{for(x in b)print b[x]}' data
     
172. 
     
173. 結(jié)果（文件內(nèi)容省略）：
     
174. 
     
175. real    0m49.195s
     
176. user    0m5.318s
     
177. sys     0m1.301s
     
178. 
     
179. 
     
180. 對于一個38M的文件來說已經(jīng)相當不錯了。
     
181. 玩的愉快！
     

復制代碼

寂寞烈火

樓主莫非是dbcat的馬甲？

waker

dbcat是樓主的馬甲

寂寞烈火

原帖由 waker 于 2006-7-31 10:57 發(fā)表
dbcat是樓主的馬甲

很像很像，dbcatMM很久沒露面了，~

waker

隨機不重復的散列函數(shù)即可，因為一個文件每行的linenumber是獨一無二的，所
以用：

    隨機數(shù)＋每行l(wèi)inenumber    ------對應------>    那一行的內(nèi)容

即為所構(gòu)造的隨機函數(shù)。

b[rand()NR]
機率非常小，但不能排除重復可能
用 b[rand()" "NR]如何?

r2007

原帖由 waker 于 2006-7-31 11:02 發(fā)表
隨機不重復的散列函數(shù)即可，因為一個文件每行的linenumber是獨一無二的，所
以用：

    隨機數(shù)＋每行l(wèi)inenumber    ------對應------>    那一行的內(nèi)容

即為所構(gòu)造的隨機函數(shù)。

b[rand()NR]
機率非 ...

同樓上觀點一樣
也可用逗號b[rand(),NR]，默認是\034字符
散列的思路真棒，贊！

蘇蓉蓉

原帖由 waker 于 2006-7-31 11:02 發(fā)表
隨機不重復的散列函數(shù)即可，因為一個文件每行的linenumber是獨一無二的，所
以用：

    隨機數(shù)＋每行l(wèi)inenumber    ------對應------>    那一行的內(nèi)容

即為所構(gòu)造的隨機函數(shù)。

b[rand()NR]
機率非 ...

問世間此山是否最高？天若有情天亦老，愛你愛到忘不了

寂寞烈火

原帖由 蘇蓉蓉 于 2006-7-31 11:10 發(fā)表


問世間此山是否最高？天若有情天亦老，愛你愛到忘不了

暈~，waker好福氣~  

r2007

原帖由 寂寞烈火 于 2006-7-31 11:23 發(fā)表

暈~，waker好福氣~  

曾子曰：機率非常小，但不能排除重復可能
我就是那個重復的
強烈申請和waker同等待遇

phpman

干嘛呢？ 干嘛呢~
打情罵翹�。�