fork download
copy 
  1. # 多数の浮動小数点の列の中央値
  2. ## http://d...content-available-to-author-only...o.jp/qa/question_detail/q13155828638;_ylt=A2RAqR66_L9WaF4AHzXl_PN7
  3. # encodeing: utf-8
  4. DataCount = 40000
  5. MaxCapacity = Math.sqrt(DataCount).to_i
  6. samplingCount = Math.sqrt(MaxCapacity).to_i
  7.  
  8. class FrequencyElement
  9.   attr_accessor :key,:freqCount,:acumulate
  10.   def initialize(k,c,a)
  11.     @key = k
  12.     @freqCount = c
  13.     @acumulate = a
  14.   end
  15.   def <=> (o) 
  16.     return self.key <=> o.key
  17.   end
  18. end
  19. class Frequency
  20.   def initialize()
  21.     @f = []
  22.     @lowerLimit = 0 - 1/ 0.0
  23.     @upperLimit = 1 / 0.0
  24.   end
  25.   def calcTotal()
  26.     totalCount=0
  27.     @f.each {|x| x.acumulate = (totalCount += x.freqCount)}
  28.     return totalCount
  29.   end
  30.   def calcCenter()
  31.     totalCount=calcTotal()
  32.     centerCount2 = (totalCount + 2) / 2
  33.     centerIndex2= @f.each_with_index.detect {|x,i| x.acumulate >= centerCount2}[1]
  34.     if ( centerCount1 = (totalCount + 1) / 2) < centerCount2
  35.       centerIndex1 = centerIndex2 -1
  36.       if @f[centerIndex1].acumulate <= centerCount1
  37.           return [centerIndex1 ,centerIndex2]
  38.       end   
  39.     end
  40.     return [centerIndex2]
  41.   end
  42.   def ajustLimit()
  43.     if @f.length >= 2
  44.       @lowerLimit = @f[0].key
  45.       @upperLimit = @f[@f.length() -1].key
  46.     end
  47.     puts " ajusted range=" + [@lowerLimit, @upperLimit].to_s
  48.   end  
  49.   def deleteFence() ## ふちを削除
  50.     if @f.length >= MaxCapacity
  51.       centerIndex = calcCenter()
  52.       if (centerIndex[0] < (@f.length - centerIndex[0]))
  53.         removeValue = @f.pop
  54.         @f[@f.length() -1].freqCount += removeValue.freqCount
  55.       else
  56.         removeValue = @f.shift
  57.         @f[0].freqCount += removeValue.freqCount
  58.         @f[0].acumulate += removeValue.acumulate
  59.       end
  60.     end
  61.   end
  62.   def add(k)
  63.     newValue = FrequencyElement.new(k,1,0)
  64.     if (@f.length <=0)
  65.       @f.push(newValue)
  66.     elsif newValue.key <= @lowerLimit
  67. 	       @f[0].freqCount += 1
  68.     elsif @upperLimit < newValue.key
  69. 	       @f[@f.length() - 1].freqCount += 1
  70.     elsif newValue.key < @f[0].key
  71.       @f.unshift(newValue) ## 前方に追加
  72.       deleteFence()
  73.     elsif @f[@f.length() - 1].key < newValue.key
  74.       deleteFence()
  75.       @f.push(newValue) ## 後方に追加
  76.     else
  77.       # p "k=" + k.to_s
  78.       insertAt = @f.each_with_index.find {|x,i| newValue.key <= x.key}[1]
  79.       # p insertAt
  80.       if (newValue.key < @f[insertAt].key)
  81. 	       @f.insert(insertAt,newValue)
  82.          deleteFence()
  83.       else
  84. 	       @f[insertAt].freqCount += 1
  85.       end
  86.       # p @f 
  87.     end
  88.   end
  89.   def show()
  90.     totalCount= calcTotal()
  91.     puts "length =" + @f.length.to_s + ",\t total Count=" + totalCount.to_s
  92.     @f.sort.each_with_index {|x,i| puts (i+1).to_s + ":\t" + x.key.to_s + ",\t" + x.freqCount.to_s + ",\t" +x.acumulate.to_s}
  93.   end  
  94.   def getMedian()
  95.     centerIndex = calcCenter()
  96.     p centerIndex
  97.     if centerIndex.length > 1
  98.       puts " center  range=" + [@f[centerIndex[0]].key , @f[centerIndex[1]].key].to_s
  99.       return (@f[centerIndex[0]].key + @f[centerIndex[1]].key) / 2.0
  100.     else
  101.       puts " center  range=" + [@f[centerIndex[0]].key].to_s
  102.       return @f[centerIndex[0]].key
  103.     end
  104.   end
  105.   def resetData()
  106.     ## 2pass目向け計算
  107.     centerIndex = calcCenter()
  108.     nearCenter0 = @f[(centerIndex[0] >0) ? centerIndex[0]-1 : 0 ].key       
  109.     nearCenter1 = @f[centerIndex[0]].key       
  110.     nearCenter2 = @f[centerIndex[centerIndex.length() - 1]].key       
  111.     maxValue = @f[@f.length() -1].key
  112.     @f = []
  113.     [nearCenter0,nearCenter1,nearCenter2,maxValue].uniq.each {|k|
  114.       @f.push(FrequencyElement.new(k,0,0))
  115.     }
  116.     @lowerLimit = @f[0].key
  117.     @upperLimit = @f[@f.length() -2].key
  118.   end
  119. end
  120. def simpleMedian(array)
  121.   sorted = array.sort
  122.   len = sorted.length
  123.   p [(len - 1) / 2 , len / 2]
  124.   p [sorted[(len - 1) / 2 ] , sorted[len / 2]]
  125.   (sorted[(len - 1) / 2 ] + sorted[len / 2]) / 2.0
  126. end
  127. ## 個別データ向け処理
  128. puts "data count =" + DataCount.to_s
  129. puts "frequency Data Capacity=" + MaxCapacity.to_s
  130. puts "sampling data count =" + samplingCount.to_s
  131.  
  132. frequencyData = Frequency.new()
  133.  
  134. randValue = Random.new(1000)
  135. v =[]
  136. samplingCount.times {
  137.   x= randValue.rand(1.0)
  138.   v << x
  139.   frequencyData.add(x)
  140. }
  141. # #  集積した値中の最小最大に合わせる
  142. frequencyData.ajustLimit()
  143. # #  データ読み込み再開
  144. (DataCount-samplingCount).times {
  145.   x= randValue.rand(1.0)
  146.   v << x
  147.   # p x
  148.   frequencyData.add(x)
  149. }
  150. # p v.sort
  151. p simpleMedian(v)
  152. frequencyData.show()
  153. puts "1St medin=" + frequencyData.getMedian().to_s
  154. # データの再読み込み
  155. frequencyData.resetData()
  156. randValue = Random.new(1000)
  157. (DataCount).times {
  158.   x= randValue.rand(1.0)
  159.   frequencyData.add(x)
  160. }
  161. frequencyData.show()
  162. puts "2St medin=" + frequencyData.getMedian().to_s
  163.  
Success #stdin #stdout 4.76s 11816KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
data count =40000
frequency Data Capacity=200
sampling data count =14
 ajusted range=[0.040709624769089126, 0.9502828643490245]
[19999, 20000]
[0.49751539351651397, 0.49753613049297263]
0.4975257620047433
length =200,	 total Count=40000
1:	0.20621368169065968,	2,	2
2:	0.45233000685728053,	603,	605
3:	0.4525398678753172,	1,	606
4:	0.45377872425038834,	1,	607
5:	0.4556072111833458,	1,	608
6:	0.4562097510086687,	1,	609
7:	0.4580716255687366,	1,	610
8:	0.4580874804113241,	1,	611
9:	0.45941845758782385,	1,	612
10:	0.4602633274697989,	1,	613
11:	0.4613548435357102,	1,	614
12:	0.46308476473880833,	3,	617
13:	0.4632297614638473,	1,	618
14:	0.46338601755869835,	1,	619
15:	0.46348027766730715,	1,	620
16:	0.4676173981131838,	1,	621
17:	0.4681257008090963,	1,	622
18:	0.4689796617958082,	1,	623
19:	0.4703097171007967,	1,	624
20:	0.4715594110151966,	1,	625
21:	0.4727308299229104,	1,	626
22:	0.47329600224809565,	1,	627
23:	0.47866217818574097,	1,	628
24:	0.47946297192904064,	1,	629
25:	0.479554864610371,	1,	630
26:	0.4797953837003682,	1,	631
27:	0.48040323508171523,	8,	639
28:	0.4805622466346482,	1,	640
29:	0.4829560322207016,	1,	641
30:	0.48668636005682,	1,	642
31:	0.4868815338024707,	1,	643
32:	0.4901219170172145,	1,	644
33:	0.4902382032272934,	1,	645
34:	0.4916180883515756,	1,	646
35:	0.4939372824517806,	1,	647
36:	0.49510854937237103,	1,	648
37:	0.49607697905306336,	19288,	19936
38:	0.496115956026813,	1,	19937
39:	0.4961503642780807,	1,	19938
40:	0.4961675023659591,	1,	19939
41:	0.4961684454606836,	1,	19940
42:	0.4961792435847401,	1,	19941
43:	0.4961808381230134,	1,	19942
44:	0.4961911838752562,	1,	19943
45:	0.49620572033752386,	1,	19944
46:	0.4962115975849144,	1,	19945
47:	0.49621413407804593,	1,	19946
48:	0.4962197048501218,	1,	19947
49:	0.4962226799671462,	1,	19948
50:	0.49623394047289615,	1,	19949
51:	0.49625571373895483,	1,	19950
52:	0.49626324343927375,	1,	19951
53:	0.4962910892964295,	1,	19952
54:	0.49631292483399825,	1,	19953
55:	0.49632433373168017,	1,	19954
56:	0.4963900202906355,	1,	19955
57:	0.49642795173061927,	1,	19956
58:	0.49644472568095255,	1,	19957
59:	0.4964470531512638,	1,	19958
60:	0.4965273358219787,	1,	19959
61:	0.49658220580197354,	1,	19960
62:	0.49666782087396755,	1,	19961
63:	0.49667109205224036,	1,	19962
64:	0.4966712547733787,	1,	19963
65:	0.49668227633625506,	1,	19964
66:	0.49669706828084303,	1,	19965
67:	0.49673656229890184,	1,	19966
68:	0.4967868399835552,	1,	19967
69:	0.49679781352707875,	1,	19968
70:	0.49686008783177504,	1,	19969
71:	0.4968669364124292,	1,	19970
72:	0.4968816818609235,	1,	19971
73:	0.49690076682126694,	1,	19972
74:	0.49691402174487476,	1,	19973
75:	0.49691627105007175,	1,	19974
76:	0.4969328793653892,	1,	19975
77:	0.4969425896013647,	1,	19976
78:	0.49694991990002,	1,	19977
79:	0.496973000993455,	1,	19978
80:	0.49699861263047895,	1,	19979
81:	0.49702182260571015,	1,	19980
82:	0.4970426729418581,	1,	19981
83:	0.4970485759961444,	1,	19982
84:	0.4970494430880541,	1,	19983
85:	0.497050950620321,	1,	19984
86:	0.4970823688740752,	1,	19985
87:	0.49710807862637063,	1,	19986
88:	0.4971376590979655,	1,	19987
89:	0.49714373879231877,	1,	19988
90:	0.4971556480337397,	1,	19989
91:	0.4971587230638954,	1,	19990
92:	0.497240007532056,	1,	19991
93:	0.4972799414434751,	1,	19992
94:	0.4973170123773284,	1,	19993
95:	0.49736701192901356,	1,	19994
96:	0.49742555658329757,	1,	19995
97:	0.4974263438536566,	1,	19996
98:	0.49743530106800615,	1,	19997
99:	0.4974446434983617,	1,	19998
100:	0.49745262984426786,	1,	19999
101:	0.49751539351651397,	1,	20000
102:	0.49753613049297263,	1,	20001
103:	0.4976109659912895,	1,	20002
104:	0.4976303177688103,	1,	20003
105:	0.49763820903677347,	1,	20004
106:	0.4976392238145865,	1,	20005
107:	0.4976486736468202,	1,	20006
108:	0.4976498391696281,	1,	20007
109:	0.49768076359800106,	1,	20008
110:	0.49769418001402865,	1,	20009
111:	0.49772929961970214,	1,	20010
112:	0.49778503471627145,	1,	20011
113:	0.4978288430010527,	1,	20012
114:	0.49783631079900725,	1,	20013
115:	0.4978391670152119,	1,	20014
116:	0.4978436060261401,	1,	20015
117:	0.4978567149288877,	1,	20016
118:	0.49785702559164213,	1,	20017
119:	0.49786417646107917,	1,	20018
120:	0.4979153381241507,	1,	20019
121:	0.49793458833258775,	1,	20020
122:	0.49799128058655606,	1,	20021
123:	0.4980270606369639,	1,	20022
124:	0.4980303547145416,	1,	20023
125:	0.4980421583522372,	1,	20024
126:	0.4980579257501404,	1,	20025
127:	0.4980712924364482,	1,	20026
128:	0.4981318260976946,	1,	20027
129:	0.49813194463089383,	1,	20028
130:	0.49813778662812636,	1,	20029
131:	0.4981487245914493,	1,	20030
132:	0.4981606324930924,	1,	20031
133:	0.49816387362878645,	1,	20032
134:	0.4982049455625337,	1,	20033
135:	0.4982372548419235,	1,	20034
136:	0.49824355551003874,	1,	20035
137:	0.49829253542744667,	1,	20036
138:	0.4983074143377958,	1,	20037
139:	0.49831020127758596,	1,	20038
140:	0.4983152710742039,	1,	20039
141:	0.49834336691141246,	1,	20040
142:	0.49838546521640137,	1,	20041
143:	0.4984261557888571,	1,	20042
144:	0.49845024039596497,	1,	20043
145:	0.49847632822339394,	1,	20044
146:	0.49849369632673857,	1,	20045
147:	0.49850340698774864,	1,	20046
148:	0.49851342559085166,	1,	20047
149:	0.4985656535556724,	1,	20048
150:	0.49858935274956884,	1,	20049
151:	0.49859938304304363,	1,	20050
152:	0.4986151956550755,	1,	20051
153:	0.49866773649724294,	1,	20052
154:	0.4987530089551291,	1,	20053
155:	0.49875645049414064,	1,	20054
156:	0.4987652568880141,	1,	20055
157:	0.4987686843692616,	1,	20056
158:	0.4987782823211142,	1,	20057
159:	0.49878619548250436,	1,	20058
160:	0.4988126444471903,	1,	20059
161:	0.4988128286633676,	1,	20060
162:	0.4988217736633037,	1,	20061
163:	0.49884275011775525,	1,	20062
164:	0.4988596050635521,	1,	20063
165:	0.4989077833236709,	1,	20064
166:	0.4989819453424398,	1,	20065
167:	0.49899868622978827,	1,	20066
168:	0.4990006829478725,	1,	20067
169:	0.49905535041690385,	1,	20068
170:	0.4990588987954123,	1,	20069
171:	0.49920730158844084,	1,	20070
172:	0.4992206239827207,	1,	20071
173:	0.4992287735706532,	1,	20072
174:	0.49923339232545694,	1,	20073
175:	0.49926007938975614,	1,	20074
176:	0.49926782260297764,	1,	20075
177:	0.4992835041530925,	1,	20076
178:	0.49929669144044486,	1,	20077
179:	0.49934473071862984,	1,	20078
180:	0.4993492630326051,	1,	20079
181:	0.4993622058894144,	1,	20080
182:	0.49937547305104957,	1,	20081
183:	0.49937794598834595,	19741,	39822
184:	0.5042374560255068,	1,	39823
185:	0.5053563116005355,	1,	39824
186:	0.5061294169698277,	1,	39825
187:	0.5110289236175756,	1,	39826
188:	0.5146604461216137,	1,	39827
189:	0.5165556259293246,	1,	39828
190:	0.5169340580127791,	1,	39829
191:	0.5179951758678784,	1,	39830
192:	0.5228510283582539,	116,	39946
193:	0.5230081949986909,	1,	39947
194:	0.5298702897554146,	1,	39948
195:	0.5422091228937046,	4,	39952
196:	0.5424836454134478,	1,	39953
197:	0.5427855568867045,	1,	39954
198:	0.5466433587491017,	1,	39955
199:	0.5491393388694349,	10,	39965
200:	0.5501096740222509,	35,	40000
[100, 101]
 center  range=[0.49751539351651397, 0.49753613049297263]
1St medin=0.4975257620047433
length =4,	 total Count=40000
1:	0.49745262984426786,	19999,	19999
2:	0.49751539351651397,	1,	20000
3:	0.49753613049297263,	1,	20001
4:	0.5501096740222509,	19999,	40000
[1, 2]
 center  range=[0.49751539351651397, 0.49753613049297263]
2St medin=0.4975257620047433
https://ideone.com/0g2Ne8
多数の浮動小数点の列の中央値
language:
Ruby (ruby 2.5.5)
created:
8 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!