ruby ​​में बैचों द्वारा सॉर्ट करें

Question

क्षमा करें अगर इससे पहले पूछा गया है, तो मुझे यकीन नहीं है कि इसके लिए भी खोज कैसे करें और मैंने जो खोजा है, वह कोई उपयोगी उत्तर नहीं देता है।

यहां मेरा मुद्दा है, मेरे पास एक ढांचा है जो मूल रूप से उन नौकरियों का प्रबंधन करता है जो पीबीएस क्लस्टर को सबमिट किए जाएंगे और प्रत्येक नौकरी को इनपुट फ़ाइल से पढ़ने की आवश्यकता होगी। हम ऐसे मामले में हैं जिनमें हमारे पास 5k से अधिक नौकरियां हैं जिन्हें चलाने की आवश्यकता है और बैच हैं, कहें, ~ 30 जो विभिन्न फाइलों से पढ़ते हैं लेकिन बाकी बाकी फाइल को पढ़ते हैं जो किसी अन्य नौकरी से पढ़ा जा रहा है।

आईडी द्वारा नौकरी सूची को सॉर्ट करने में सक्षम होने के कारण इसे आसानी से निपटाया जा सकता है (हालांकि सबसे अच्छा समाधान शायद हमारे पास समय के लिए सबसे तेज़ समाधान नहीं है) जिसका मूल रूप से अर्थ है कि यह कौन सी फाइल से पढ़ा जा रहा है अर्थात मैं

a = [1,2,3,4,1,2,3,4,1,2,3,4] 

में इस

a = [1,1,1,2,2,2,3,3,3,4,4,4] 

की तरह एक सरणी सॉर्ट करने के लिए चाहते हैं वहाँ रूबी में इस तरह के एक आदेश को प्राप्त करने का कोई तरीका है? मैं एक एल्गोरिदम खरीद सकता हूं शायद यह पहले से ही किया जा चुका है और कोई जवाब जानता है।

धन्यवाद!

Answer 1

मूल विचार और बग खोजने के लिए @Cary Swoveland के लिए समाधान @ sagarpandya82 को

धन्यवाद!

def safe_transpose_and_flatten(array) 
    l = array.map(&:length).max 
    array.map{|e| e.values_at(0...l)}.transpose.flatten.compact 
end 

def sort_by_batches(array) 
    safe_transpose_and_flatten(array.sort.group_by{|i| i}.values) 
end 

या यह एक लाइनर (सापेक्ष पठनीयता के लिए कई लाइनों पर विभाजित):

या तो 2 तरीकों का उपयोग

def sort_by_batches(array) 
    array.group_by{|i| i }.values     # Chunks of equal values, 
     .sort_by{|v| -v.size }     # sorted by decreasing length, 
     .reduce(&:zip)       # transposed, 
     .map{|r| r.flatten.compact.sort }.flatten # flattened and sorted 
end 

उदाहरण

a = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4] 
sort_by_batches(a) # => [1, 2, 3, 4, 1, 2, 3, 4, 1, 2, 3, 4] 

a = [1, 1, 3, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 1, 1] 
sort_by_batches(a) # => [1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 3, 4, 1, 3] 

a = [1,2,2,3,3,3] 
sort_by_batches(a) # => [1, 2, 3, 2, 3, 3] 

कदम

यहाँ दूसरी सरणी के लिए कदम हैं:

[1, 1, 3, 2, 2, 2, 3, 3, 3, 4, 4, 4, 5, 1, 1] # input 
{1=>[1, 1, 1, 1], 3=>[3, 3, 3, 3], 2=>[2, 2, 2], 4=>[4, 4, 4], 5=>[5]} # group_by 
[[1, 1, 1, 1], [3, 3, 3, 3], [2, 2, 2], [4, 4, 4], [5]] # values 
[[1, 1, 1, 1], [3, 3, 3, 3], [2, 2, 2], [4, 4, 4], [5]] # sort_by -length 
[[[[[1, 3], 2], 4], 5], [[[[1, 3], 2], 4], nil], [[[[1, 3], 2], 4], nil], [[[[1, 3], nil], nil], nil]] # zip 
[[1, 2, 3, 4, 5], [1, 2, 3, 4], [1, 2, 3, 4], [1, 3]] # map(&:flatten) and compact 
[1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 3, 4, 1, 3] # flatten 

.reduce(&:zip).map(&:flatten).compact एक माना जाता है कि सुरक्षित पक्षांतरित के रूप में पहली बार में इस्तेमाल किया गया था, लेकिन यह काम नहीं किया जब पहली सरणी दूसरों की तुलना में छोटी थी।

पहली विधि this ट्रांसपोज़िंग के लिए उत्तर का उपयोग करती है, एक-लाइनर zip का उपयोग करने से पहले लंबाई घटाने से सरणी को प्रकार देता है।

class Job 
    attr_reader :id 
    def initialize(id) 
    @id = id 
    end 

    def self.sort_by_batches(jobs) 
    safe_transpose_and_flatten(jobs.sort_by{|j| j.id}.group_by{|j| j.id}.values) 
    end 

    def to_s 
    "Job %d" % id 
    end 
end 

jobs = [1, 1, 1, 2, 2, 2, 3, 3, 3, 4, 4, 4].map{|i| Job.new(i)} 
Job.sort_by_batches(jobs) 

यह आउटपुट:

Job 1 
Job 2 
Job 3 
Job 4 
Job 1 
Job 2 
Job 3 
Job 4 
Job 1 
Job 2 
Job 3 
Job 4 

Answer 2

आप एक मिलान समारोह के साथ ऐसा कर सकता है:

def collate(input) 
    # Split the input array up into chunks of identical values 
    # and sort the resulting groups. 
    sets = input.group_by { |v| v }.values.sort_by(&:first) 

    # Recombine these into a single output array by iterating over 
    # each set and transposing values. Any nil values are scrubbed 
    # with compact. 
    (0...sets.map(&:length).max).flat_map do |i| 
    sets.map do |s| 
     s[i] 
    end 
    end.compact 
end 

आप कुछ कम तुच्छ डेटा पर इस काम देख सकते हैं:

input = [1,1,3,2,2,2,3,3,3,4,4,4,5,1,1] 

collate(input) 
# => [1, 2, 3, 4, 5, 1, 2, 3, 4, 1, 2, 3, 4, 1, 3] 

यहाँ 5 केवल एक बार दिखाई देता है।

Answer 3

कोड

def doit(a)  
    b = a.sort.slice_when { |x,y| x != y } 
    b.max_by(&:size).size.times.flat_map { |i| b.each_with_object([]) { |c,arr| 
    arr << c[i] unless c[i].nil? } } 
end 

उदाहरण

doit [5, 1, 7, 2, 3, 3, 5, 2, 3, 1, 4] 
    #=> [1, 2, 3, 4, 5, 7, 1, 2, 3, 5, 3] 

स्पष्टीकरण

उदाहरण के रूप में इस कदम हैं के लिए।

a = [5, 1, 7, 2, 3, 3, 5, 2, 3, 1, 4] 

c = a.sort 
    #=> [1, 1, 2, 2, 3, 3, 3, 4, 5, 5, 7] 
b = c.slice_when { |x,y| x != y } 
    #=> #<Enumerator: #<Enumerator::Generator:0x007fb8a99d94c8>:each> 

हम तत्वों कि (ब्लॉक करने के लिए और पारित कर दिया) प्रगणक b द्वारा उत्पन्न कर रहे देख सकते हैं यह एक सरणी के लिए कनवर्ट करके:

b.to_a 
    #=> [[1, 1], [2, 2], [3, 3, 3], [4], [5, 5], [7]] 

सतत,

c = b.max_by(&:size) 
    #=> [3, 3, 3] 
d = c.size 
    #=> 3 
e = d.times 
    #=> #<Enumerator: 3:times> 
e.to_a 
    #=> [0, 1, 2] 
e.flat_map { |i| b.each_with_object([]) { |c,arr| arr << c[i] unless c[i].nil? } } 
    #=> [1, 2, 3, 4, 5, 7, 1, 2, 3, 5, 3] 

यहाँ

कुछ अंतिम puts स्टेटमेंट्स के साथ अंतिम ऑपरेशन है।

3.times.flat_map do |i| 
    puts "i=#{i}" 
    b.each_with_object([]) do |c,arr| 
    puts " c=#{c}, c[#{i}]=#{c[i]}, arr=#{arr}" 
    arr << c[i] unless c[i].nil? 
    puts " arr after arr << c[#{i}]=#{arr}" unless c[i].nil? 
    end 
end 

# i=0 
# c=[1, 1], c[0]=1, arr=[] 
#  arr after arr << c[0]=[1] 
# c=[2, 2], c[0]=2, arr=[1] 
#  arr after arr << c[0]=[1, 2] 
# c=[3, 3, 3], c[0]=3, arr=[1, 2] 
#  arr after arr << c[0]=[1, 2, 3] 
# c=[4], c[0]=4, arr=[1, 2, 3] 
#  arr after arr << c[0]=[1, 2, 3, 4] 
# c=[5, 5], c[0]=5, arr=[1, 2, 3, 4] 
#  arr after arr << c[0]=[1, 2, 3, 4, 5] 
# c=[7], c[0]=7, arr=[1, 2, 3, 4, 5] 
#  arr after arr << c[0]=[1, 2, 3, 4, 5, 7] 
# i=1 
# c=[1, 1], c[1]=1, arr=[] 
#  arr after arr << c[1]=[1] 
# c=[2, 2], c[1]=2, arr=[1] 
#  arr after arr << c[1]=[1, 2] 
# c=[3, 3, 3], c[1]=3, arr=[1, 2] 
#  arr after arr << c[1]=[1, 2, 3] 
# c=[4], c[1]=, arr=[1, 2, 3] 
# c=[5, 5], c[1]=5, arr=[1, 2, 3] 
#  arr after arr << c[1]=[1, 2, 3, 5] 
# c=[7], c[1]=, arr=[1, 2, 3, 5] 
# i=2 
# c=[1, 1], c[2]=, arr=[] 
# c=[2, 2], c[2]=, arr=[] 
# c=[3, 3, 3], c[2]=3, arr=[] 
#  arr after arr << c[2]=[3] 
# c=[4], c[2]=, arr=[3] 
# c=[5, 5], c[2]=, arr=[3] 
# c=[7], c[2]=, arr=[3] 
#=> [1, 2, 3, 4, 5, 7, 1, 2, 3, 5, 3]