public

  • Download Gist
20130520015455_create_temp_arrays.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11
class CreateTempArrays < ActiveRecord::Migration
def change
create_table :temp_arrays do |t|
t.string :array
t.boolean :sorted
t.integer :parent_id, :integer
 
t.timestamps
end
end
end
merge_sort_worker.rb
Ruby
1 2 3 4 5 6 7 8 9
require 'sidekiq'
 
class MergeSortWorker
include Sidekiq::Worker
 
def perform(array)
SortWorker.perform_async TempArray.create(array: array).id
end
end
merge_worker.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37
require 'sidekiq'
 
class MergeWorker
include Sidekiq::Worker
 
def finish(parent)
if parent.parent
MergeWorker.perform_async parent.parent.id
else
s = Redis::Semaphore.new(:creating_sorted_array, :connection => "localhost")
s.lock do
parent.reload rescue return
SortedArray.create array: parent.array
parent.destroy
end
end
end
 
def perform(parent_id)
parent = TempArray.includes(:parent).where(id: parent_id).first
return if parent.nil?
 
finish(parent) and return if parent.sorted?
 
if parent.children.present? && parent.children.all?(&:sorted?)
left = parent.children.first.array
right = parent.children.last.array
parent.children.destroy_all
 
parent.array = MergesArrays.merge left, right
parent.sorted = true
parent.save
 
finish parent
end
end
end
merges_arrays.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
class MergesArrays
def self.merge(left, right)
sorted = []
 
until left.empty? || right.empty?
if left.first <= right.first
sorted << left.shift
else
sorted << right.shift
end
end
 
sorted + left + right
end
end
sort_worker.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25
require 'sidekiq'
 
class SortWorker
include Sidekiq::Worker
 
def finish(temp_array)
temp_array.sorted = true
temp_array.save
MergeWorker.perform_async temp_array.parent.id
end
 
def perform(array_id)
temp_array = TempArray.find array_id
array = temp_array.array
 
finish(temp_array) and return if array.count <= 1
 
left, right = SplitsArray.split(array)
temp_left = temp_array.children.create(array: left, sorted: false)
temp_right = temp_array.children.create(array: right, sorted: false)
 
SortWorker.perform_async temp_left.id
SortWorker.perform_async temp_right.id
end
end
sorted_array.rb
Ruby
1 2 3 4 5 6 7 8
class SortedArray
def self.create(*args)
puts "--------------------"
puts "Saving:"
ap args
puts "--------------------"
end
end
splits_arrays.rb
Ruby
1 2 3 4 5 6 7 8
class SplitsArray
def self.split(array)
middle = array.count / 2
left = array[0, middle]
right = array[middle, (array.count - middle)]
[left, right]
end
end
temp_array.rb
Ruby
1 2 3 4 5
class TempArray < ActiveRecord::Base
serialize :array, Array
belongs_to :parent, class_name: TempArray, foreign_key: 'parent_id'
has_many :children, class_name: TempArray, foreign_key: 'parent_id'
end

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.