Class: Pwrake::RankQueueArray
- Inherits:
-
Object
- Object
- Pwrake::RankQueueArray
- Defined in:
- lib/pwrake/queue/queue_array.rb
Overview
Rank-Even Last In First Out
Instance Method Summary collapse
- #clear ⇒ Object
- #delete(t) ⇒ Object
- #empty? ⇒ Boolean
- #first ⇒ Object
-
#initialize(n) ⇒ RankQueueArray
constructor
A new instance of RankQueueArray.
- #last ⇒ Object
- #pop_last_max(a) ⇒ Object
- #push(t) ⇒ Object
- #shift ⇒ Object
- #shift_weighted ⇒ Object
- #size ⇒ Object
Constructor Details
#initialize(n) ⇒ RankQueueArray
Returns a new instance of RankQueueArray.
280 281 282 283 284 |
# File 'lib/pwrake/queue/queue_array.rb', line 280 def initialize(n) @q = [] @size = 0 @n = (n>0) ? n : 1 end |
Instance Method Details
#clear ⇒ Object
392 393 394 395 |
# File 'lib/pwrake/queue/queue_array.rb', line 392 def clear @q.clear @size = 0 end |
#delete(t) ⇒ Object
381 382 383 384 385 386 387 388 389 390 |
# File 'lib/pwrake/queue/queue_array.rb', line 381 def delete(t) n = 0 @q.each do |a| if a a.delete(t) n += a.size end end @size = n end |
#empty? ⇒ Boolean
300 301 302 |
# File 'lib/pwrake/queue/queue_array.rb', line 300 def empty? @size == 0 end |
#first ⇒ Object
361 362 363 364 365 366 367 368 369 |
# File 'lib/pwrake/queue/queue_array.rb', line 361 def first return nil if empty? @q.size.times do |i| a = @q[i] unless a.nil? || a.empty? return a.first end end end |
#last ⇒ Object
371 372 373 374 375 376 377 378 379 |
# File 'lib/pwrake/queue/queue_array.rb', line 371 def last return nil if empty? @q.size.times do |i| a = @q[-i-1] unless a.nil? || a.empty? return a.last end end end |
#pop_last_max(a) ⇒ Object
344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 |
# File 'lib/pwrake/queue/queue_array.rb', line 344 def pop_last_max(a) if a.size < 2 return a.pop end y_max = nil i_max = nil n = [@n, a.size].min (-n..-1).each do |i| y = a[i].input_file_size if y_max.nil? || y > y_max y_max = y i_max = i end end a.delete_at(i_max) end |
#push(t) ⇒ Object
286 287 288 289 290 291 292 293 294 |
# File 'lib/pwrake/queue/queue_array.rb', line 286 def push(t) r = t ? t.rank : 0 a = @q[r] if a.nil? @q[r] = a = [] end @size += 1 a.push(t) end |
#shift ⇒ Object
304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 |
# File 'lib/pwrake/queue/queue_array.rb', line 304 def shift if empty? return nil end (@q.size-1).downto(0) do |i| a = @q[i] next if a.nil? || a.empty? @size -= 1 if a.size <= @n return pop_last_max(a) else return shift_weighted end end raise "ELIFO: @q=#{@q.inspect}" end |
#shift_weighted ⇒ Object
321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 |
# File 'lib/pwrake/queue/queue_array.rb', line 321 def shift_weighted weight, weight_avg = RANK_STAT.rank_weight wsum = 0.0 q = [] @q.each_with_index do |a,i| next if a.nil? || a.empty? w = weight[i] w = weight_avg if w.nil? # w *= a.size wsum += w q << [a,wsum] end # x = rand() * wsum Log.debug "shift_weighted x=#{x} wsum=#{wsum} weight=#{weight.inspect}" q.each do |a,w| if w > x return a.pop end end raise "ELIFO: wsum=#{wsum} x=#{x}" end |
#size ⇒ Object
296 297 298 |
# File 'lib/pwrake/queue/queue_array.rb', line 296 def size @size end |