Skip to content

Instantly share code, notes, and snippets.

@luan
Created May 20, 2013 03:41
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save luan/5610299 to your computer and use it in GitHub Desktop.
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
require 'sidekiq'
class MergeSortWorker
include Sidekiq::Worker
def perform(array)
SortWorker.perform_async TempArray.create(array: array).id
end
end
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
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
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
class SortedArray
def self.create(*args)
puts "--------------------"
puts "Saving:"
ap args
puts "--------------------"
end
end
class SplitsArray
def self.split(array)
middle = array.count / 2
left = array[0, middle]
right = array[middle, (array.count - middle)]
[left, right]
end
end
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment