Проблема с алгоритмом сортировки в RailsWizard

Question

RailsWizard , инструмент для генерации шаблонов рельсов, позволяет устанавливать порядок рецептов, указывая, какие рецепты должны выполняться до (run_before опция) и после (run_after) данного рецепта, как описано в https://github.com/intridea/rails_wizard/wiki/Recipe-Configuration

Это реализовано в Recipe классе :

module RailsWizard
  class Recipe
    extend Comparable

    def self.<=>(another)
      return -1 if another.run_after.include?(self.key) || self.run_before.include?(another.key)
      return 1 if another.run_before.include?(self.key) || self.run_after.include?(another.key)
      self.key <=> another.key # simple sort by name
    end
  end
end

Однако этот алгоритм часто обеспечивает неправильный порядок, см. соответствующую проблему и демонстрационный скрипт для этой проблемы: https://gist.github.com/987025

Как бы вы исправили этот алгоритм?

Answer 1

Проблема с алгоритмом заключается в том, что оператор сравнения не определяет Строгий слабый порядок .

В частности, ему не хватает транзитивности (если x

• n
• l
• m

Последнее, m

Сначала нужно исправить оператор так, чтобы он никогда не предоставлял противоречивую информацию.Во-вторых, я думаю, что нам нужно либо распространять транзитивное упорядочение, чтобы транзитивность поддерживалась для несмежных элементов, либо нам нужно использовать алгоритм O (n ^ 2), который сравнивает каждый элемент с любым другим элементом.

Сортировка выбора соответствует этому критерию, так что вот ваш код, использующий сортировку выбора и оператор сравнения before?.

require 'yaml'
hash = YAML.load '
a:
  after: 
  before: 
l:
  after: 
  before: 
n:
  after: 
  before: l
b:
  after: 
  before: 
m:
  after: 
  before: 
c:
  after: 
  before: 
z:
  after: 
  before: 
'
hash.each do |k,v|
  v.each do |vk,vv|
    v[vk] = (vv||'').split
  end
end

class Hash
  def without *ks
    delete_if { |k,v| ks.include? k }
  end
  def delete! *ks
    #print "\n\nwithout: #{ks.join(', ')}"
    replace without *ks
  end
end

def print_keys hash
  puts hash.map(&:first).join('  ')
end

def sort hash
  array = hash.to_a
  selection_sort array
  print_keys array
  Hash[array]
end

def selection_sort array
  (0...array.length).each do |i|
    min = i
    ((i+1)...array.length).each do |j|
      min = j if before?(array[j], array[min])
    end
    temp = array[min]
    array[min] = array[i]
    array[i] = temp
  end
end

def before? a, b
  b.last['after'].include?(a.first) || a.last['before'].include?(b.first)
end

def test hash
  puts nil,nil
  print_keys hash
  puts '-'*hash.count*3
  hash.count.times { hash = sort hash }
end

test hash

И это дает:

$ ruby sort_test.rb 


a  l  n  b  m  c  z
---------------------
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z
a  n  l  b  m  c  z