Sortieren Array nach Chargen in Ruby

Question

Sorry, wenn dies zuvor gefragt wurde, bin ich mir nicht sicher, wie man überhaupt danach suchen und was ich gesucht habe ergibt keine sinnvolle Antwort.

Hier ist mein Problem, ich habe ein Framework, das im Grunde verwaltet die Jobs, die an einen PBS-Cluster übermittelt werden und jeder Job muss aus einer Eingabedatei lesen. Wir sind in einem Fall, in dem wir mehr als 5k Jobs ausführen müssen, und es gibt Chargen von, sagen wir, ~ 30, die aus verschiedenen Dateien lesen, aber der Rest von ihnen liest aus einer Datei, die von einem anderen Job gelesen wird.

Dies könnte leicht behandelt werden (obwohl nicht die beste Lösung kaufen vielleicht die schnellste für die Zeitskala, die wir haben) durch Sortieren der Job-Liste durch die ID, die im Grunde bedeutet, aus welcher Datei wird es lesen , also würde ich ein Array sortieren, wie diese

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

in mögen

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

gibt es eine Möglichkeit in ruby, eine solche Anordnung zu erreichen? Ich könnte mir einen Algorithmus kaufen, vielleicht ist es schon erledigt und jemand kennt die Antwort.

Danke!

Answer 1

Lösung

Dank @ sagarpandya82 für die ursprüngliche Idee und @Cary Swoveland für Fehlersuche!

Entweder verwenden 2-Methoden:

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 

Oder diese Liner (aufgeteilt auf mehrere Linien für die relative Lesbarkeit):

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 

Beispiel

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] 

Schritte

Hier sind die Schritte für die zweite Reihe:

[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 wurde zunächst als vermeintlich sichere transponieren verwendet, aber es hat nicht funktioniert, wenn die erste Reihe der andere war kleiner als.

Die erste Methode Verwendung this Antwort für die Transponierung, die Ein-Liner sortiert die Arrays durch abnehmende Länge vor der Verwendung zip.

Anwendung auf Jobklasse

Hier ist eine sehr einfache Jobklasse als Beispiel:

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) 

Es gibt:

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

Sie können dies tun mit einer Sortierfunktion:

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 

Sie diese Arbeit auf etwas weniger trivial Daten sehen:

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] 

Hier 5 nur einmal auftaucht.

Answer 3

-Code

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 

Beispiel

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

Erklärung

Beispiel für die Schritte sind wie folgt.

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> 

Wir können die Elemente sehen, die von der Enumerator erzeugt werden b (und weiter zum Block), indem es auf ein Array Umwandeln:

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

Continuing,

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] 

Hier ist die letzte Operation mit einigen enthaltenen puts Aussagen.

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]