Блог

Мне нужно отсортировать таблицу рейтингов в Rails 3, поэтому у меня есть LeagueTable модель, Team model и Match model.
Базовая сортировка выполняется по сумме баллов, так что это простая часть. Но когда две команды набрали одинаковое количество очков, я хочу отсортировать их по очкам, набранным в матчах между этими двумя командами.
Я понятия не имею, как это сделать.

Редактировать:

 # league_table.rb model
class LeagueTable < ActiveRecord::Base
    belongs_to :team
end


# match.rb model
class Match < ActiveRecord::Base
    belongs_to :team_home, :class_name => "Team"
    belongs_to :team_away, :class_name => "Team"
end


# team.rb model
class Team < ActiveRecord::Base
    has_many :matches
end


# schema.rb
create_table "league_tables", :force => true do |t|
    t.integer  "team_id"
    t.integer  "points"
    t.integer  "wins"
    t.integer  "draws"
    t.integer  "looses"
    t.integer  "goals_won"
    t.integer  "goals_lost"
    t.datetime "created_at"
    t.datetime "updated_at"
    t.integer  "matches"
    t.integer  "priority"
  end

  create_table "matches", :force => true do |t|
    t.integer  "team_home_id"
    t.integer  "team_away_id"
    t.integer  "score_home"
    t.integer  "score_away"
    t.datetime "created_at"
    t.datetime "updated_at"
  end

  create_table "teams", :force => true do |t|
    t.string   "name"
    t.datetime "created_at"
    t.datetime "updated_at"
  end
  

Очень интересный вопрос. Вот (более менее), как я бы справился с этим, используя рекурсию и магию group_by .

1. Вам понадобится метод класса, который, учитывая массив команд, вычисляет количество очков (голов за, голов против …), набранных каждой командой в только матчах между этими командами. Предположим, вы возвращаете хэш хэшей: {team_foo => {:points => 10, :goals_for => 33, :goals_against => 6}, team_bar => {:points => 18, :goals_for => 50, :goals_against => 11}...} .
2. Окончательный порядок команд будет помещен в массив final_order , который сейчас пуст.
3. Сведите все команды в массив и примените метод, упомянутый выше. Теперь у вас должны быть команды и количество очков (голов за, голов против …), набранных всеми командами во всех сыгранных на данный момент играх. Сохраните это где-нибудь, скажем, под именем all_teams_scores .
4. Возьмите все команды и сгруппируйте их, используя group_by : teams.group_by {|t| all_teams_scores[t][:points]} . То, что вы получаете, OrderedHash выглядит следующим образом: {10 => [team_foo], 18 => [team_bar, team_xyz]} . Ключ — это то, по чему вы группируете, значение всегда является массивом. Сохраните этот хэш, например, как league_table .
5. Отсортируйте ключи league_table (не забудьте при необходимости поменять местами) и проверьте значения league_table в соответствии с ними. Если массив содержит два или более элемента, примените пункты 3.-5. к командам в этом массиве. Если массив содержит один элемент, добавьте этот элемент в final_order .
6. Выполнено.

Некоторые замечания:

• Помните, что в худшем случае у вас останутся две или более команд, которые набрали одинаковое количество очков (голов …) в прямых играх. Вам нужно это обработать или отсортировать случайным образом.
• Вышеуказанные шаги группируются только по точкам. Если вам нужно сначала отсортировать по очкам во всех играх, затем по очкам в прямых играх, это сработает. Если вы хотите сортировать по очкам во всех играх, по очкам в прямых играх, по голам во всех играх — вам нужно доработать приведенный выше алгоритм. Впрочем, это не должно быть сложно 😉
• Вы можете group_by использовать массив (что помогает, когда вы хотите отсортировать несколько объектов до или после сортировки по прямым играм).
• Если ваш сайт не будет интенсивно использоваться, генерируйте таблицу по запросу. Нет необходимости хранить это в базе данных — если только сезон не закончен и не требуется вносить изменения в результаты игры.
• Если вы решите сохранить таблицу в базе данных, убедитесь, что поля, относящиеся к положению команды в таблице, недоступны для редактирования пользователем. Вероятно, лучшим способом было бы реализовать приведенный выше алгоритм в виде хранимой процедуры (PostgreSQL поддерживает pl / Ruby, хотя я им никогда не пользовался), create view основываясь на этом, и получить доступ к таблице ранжирования из Rails через нее (представления, как правило, доступны только для чтения). Конечно, удаление доступа к этим полям из административного интерфейса также нормально для 99,99% ситуаций 😉
• Это может не быть (и, вероятно, таковым не является) оптимальным решением с точки зрения скорости или эффективности памяти (хотя я это не проверял), но я полагаю, что код, созданный в соответствии с этим методом, должен быть легким для чтения, понимания и последующего сопровождения.

Надеюсь, это поможет.

Вот как я бы это сделал :

1. Во-первых, я бы просто отсортировал команды по набранным очкам. Как вы сказали, это довольно тривиально.

2. Затем я бы прошелся по отсортированному массиву и проверил возможные команды, у которых одинаковые баллы. Это отобразилось бы в новом массиве хэшей. Для каждого набора команд, которые я бы нашел с одинаковыми баллами, я бы обозначил хэшем. Подумайте о 3 конкурирующих командах :

 { :TeamA => 3, :TeamB => 2 }
{ :TeamA => 3,  :TeamC => 4 }
{ :TeamB => 1,  :TeamC => 0 }
  

1. Теперь я бы разобрался. Чтобы упростить задачу, у вас может быть максимальный или минимальный элемент (каждый раз представляющий команду).

Прохождение с максимальной :

 1. max = TeamA
2. max = TeamC
  

Итак, самая сильная команда — TeamC. Исключите эту команду и повторите. Последние 2 хэша теперь удалены, и у нас остается только первый, который показывает, что TeamA > TeamB. Итак, окончательная сортировка будет :

TeamC > Команда > TeamB

ОБРАТИТЕВНИМАНИЕ: TeamC не лучше TeamB, когда рассматриваются только эти двое. Этот алгоритм дает в целом лучшую команду, основанную на выигрышных очках.

Ваш случай на самом деле проще. Вы просто хотите сравнить две команды. Следовательно, хэш, подобный :

 { :TeamA => 3, :TeamB => 2 }
  

ясно указывает, что TeamA лучше, чем TeamB, и должна быть оценена выше. Если вы хотите сравнить 3 команды, набравшие одинаковые очки, у вас должны быть другие критерии, например, команда, набравшая больше очков, лучше.

Редактировать

Если следующие 2 фактора для получения лучшей команды — это забитые голы, а затем разница в потерях, у вас будет другой хэш, подобный :

 { :TeamA => [3, 2], :TeamA => [2, 1], :TeamC => [1, 1] }
  

С [3,2], указывающим [разница забитых мячей и потерянных очков]. Теперь вы можете легко определить лучшие команды на основе этих двух параметров.

Я бы добавил rival_points столбец в вашу LeagueTable модель и обновил его, только если есть другие команды с таким же количеством очков.

Я думал о чем-то подобном этому (не проверял, работает ли это):

 class LeagueTable
  after_save :set_order_of_equals

  def set_order_of_equals
    LeagueTable.all.each do |lt|
      points_against_rivals = 0
      LeagueTable.where('points = ? and matches = ? and team_id <> ?', lt.points, lt.matches, lt.team_id).each do |lt_same_points|
        points_against_rivals  = lt.team.points_against(lt_same_points.team)
      end
      lt.rival_points = points_against_rivals
      LeagueTable.after_save.clear # clear the after_save callback to prevent it from running endlessly
      lt.save
    end
  end
end


class Team
  def points_against(opponent)
    points = 0

    # Home games
    matches.where(:team_away => opponent).each do |m|
      if m.score_home == m.score_away
        points  = 1
      elsif m.score_home > m.score_away
        points  = 3
      end
    end

    # Away games
    matches.where(:team_home => opponent).each do |m|
      if m.score_away == m.score_home
        points  = 1
      elsif m.score_away > m.score_home
        points  = 3
      end
    end

    points
  end
end

# With this you can get the correct order like this
lt = LeagueTable.order('points desc, matches asc, rival_points desc')
  

Вот тяжелое, но эффективное решение с использованием SQL. Большая часть сложной логики выполняется в базе данных.

Добавьте новый столбец с именем group_rank в league_tables таблицу (по умолчанию должно быть 0). Проверьте, нет ли столкновения точек во время save работы. Если имеет место точечное столкновение, рассчитайте group_rank для сталкивающихся команд.

Таким образом, вы можете расположить команды в правильном порядке, используя простое order предложение.

 LeagueTable.all(:order => "points ASC, group_rank ASC")
  

Добавьте after_save обратный вызов для определения точечного столкновения в LeagueTable модели.

 # league_table.rb model
class LeagueTable < ActiveRecord::Base
  belongs_to :team

  after_save :update_group_rank

  def update_group_rank
    return true unless points_changed?
    # rank the rows with new points and old points
    rank_group(points) and rank_group(points_was) 
  end
  

# rank_group Метод:

   def rank_group(group_points)
    group_count = LeagueTable.count(:conditions =>{:points => group_points})
    return true unless group_count > 1 # nothing to do
    sql = "UPDATE league_tables JOIN
      (
      SELECT c.team_id, SUM(IF(c.score = 0, 1, c.score)) group_rank
      FROM   (
        SELECT ca.team_home_id team_id, (ca.score_home-ca.score_away) score
        FROM   matches ca, 
               (SELECT cba.team_id 
                FROM league_tables cba 
                WHERE cba.points = #{group_points}
               ) cb
        WHERE  ca.team_home_id = cb.team_id  AND ca.score_home >= ca.score_away
        UNION
        SELECT cc.team_away_id team_id, (cc.score_away-cc.score_home) score
        FROM   matches cc, 
               (SELECT cda.team_id 
                FROM league_tables cda 
                WHERE cda.points = #{group_points}
               ) cd
        WHERE  cc.team_away_id = cd.team_id AND cc.score_away >= cc.score_home
               ) c
        GROUP BY c.team_id
      ) b ON league_tables.team_id = b.team_id
      SET league_tables.group_rank = b.group_rank"
      connection.execute(sql)
      return true
  end
end
  

Обязательно добавьте индекс в points столбец.

Примечание: Это решение будет работать в MySQL. Переписать SQL для работы с другими базами данных довольно просто.

Я думаю, что это сложно сделать, используя сортировку базы данных. Предварительный расчет перекрестной таблицы с очками между командами возможен, но как использовать это при поиске. Я полагаю, что проблема станет еще сложнее, если три команды сыграют вничью.

Сортируйте то, что вы можете, из базы данных. Затем снова просмотрите список, чтобы отсортировать связи. Вы должны рассчитать тай-брейк для затронутых команд. Либо вы помещаете команды в новый массив сверху вниз, либо добавляете столбец для тай-брейков к командам и прибегаете ко второму проходу.

Я бы добавил в ваш класс модели метод, который разрешает тай-брейки и возвращает отсортированный массив.

Задача нетривиальная, но может быть забавной.

ваша проблема звучит действительно интересно. Я участвовал во многих соревнованиях (волейбол), и в случае равенства очков (когда очки зарабатываются на основе выигранных или проигранных матчей) команда, набравшая наибольшее количество очков и наименьшее количество контрапунктов, будет отсортирована первой. Итак, в этом случае, вместо того, чтобы смотреть на отдельные матчи, просто отсортируйте по общему количеству выигранных и проигранных мячей.

Тогда это было бы просто:

 LeagueTable.all.order('points desc, goals_won desc, goals_lost desc')
  

что, я думаю, было бы довольно приличным порядком. Затем выбирается самая атакующая команда в целом. Вы также отдаете предпочтение наиболее защищенной команде, сортируя по order('points desc, goals_lost desc, goals_won desc') .

Но это всего лишь короткий путь. Я полагаю, вы не вольны изменять правила сортировки по своему усмотрению, и это действительно приятная проблема для решения. Вот некоторый код, как бы я к этому подошел

 all_teams_simple_sort = LeagueTable.all.sort('points desc')
all_teams_sorted = []

teams_equal_points = []
prev_team = all_teams_simple_sort[1]
prev_points = all_teams_simple_sort[1].points

(2..all_teams_simple_sort.size).each do |team_index|
  team = all_teams_simple_sort[team_index]
  if team.points == prev_team.points
    teams_equal_points << prev_team if teams_equal_points.size == 0
    teams_equal_points << team
  else        
    if teams_equal_points.size > 0
      add_equals_sorted_to all_teams_sorted, teams_equal_sorted
      teams_equal_sorted = []
    else
      all_teams_sorted << prev_team
    end
    all_teams_sorted << team
  end
  prev_team = team   
end
  

Это должно охватить все команды, объединить все команды с равными очками и добавить все остальные, если необходимо.

Теперь нам нужно только написать самую сложную функцию add_equals_sorted_to , которая добавит команды с равными очками в правильном порядке к результату- сортировке.

 def add_equals_sorted_to(result_sorted, equals_unsorted)
  team_ids = equals_unsorted.collect(amp;:team_id)
  # get all the matches for between those teams
  matches = Match.where('team_home_id in (?) and team_away_id in (?)', team_ids.join(','), team_ids.join(','))

  # create an empty hash for each team
  team_score = {}
  team_ids.each {|id| team_scores[id] = {:won => 0, :lost => 0} }
  matches.each do |match|
    team_scores[match.team_home_id] = {:won => team_scores[match.team_home_id][:won]   match.score_home, :lost => team_scores[match.team_home_id][:lost]   match.score_away }
    team_scores[match.team_away_id] = {:won => team_scores[match.team_away_id][:won]   match.score_away, :lost => team_scores[match.team_home_id][:lost]   match.score_home }
  end

  # get the team with the highest :won and add to result_sorted 
  #   and repeat until no more left   
end
  

Этот код не тестировался 🙂 Но я надеюсь, что это должно помочь вам начать.