Rails 3 сложная сортировка - PullRequest
       1

Rails 3 сложная сортировка

2 голосов
/ 29 апреля 2011

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

EDIT:

# 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

Ответы [ 6 ]

1 голос
/ 06 мая 2011

Очень интересный вопрос.Вот (более менее), как бы я справился с этим, используя рекурсию и магию 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. Done.

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

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

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

1 голос
/ 04 мая 2011

Вот тяжелое, но эффективное решение 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 для работы с другими базами данных.

1 голос
/ 02 мая 2011

Я бы добавил столбец 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')
1 голос
/ 02 мая 2011

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

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

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

{ :TeamA => 3, :TeamB => 2 }
{ :TeamA => 3,  :TeamC => 4 }
{ :TeamB => 1,  :TeamC => 0 }
  1. Теперь я бы отсортировал. Чтобы упростить задачу, у вас может быть элемент max или min (каждый раз представляющий команду).

Обход с макс .:

1. max = TeamA
2. max = TeamC

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

TeamC> TeamA> TeamB

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

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

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

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

EDIT

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

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

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

0 голосов
/ 04 мая 2011

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

Так что тогда будет легко:

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(&: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

Этот код не тестировался :) Но я надеюсь, что вы должны начать.

0 голосов
/ 01 мая 2011

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

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

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

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

Добро пожаловать на сайт PullRequest, где вы можете задавать вопросы и получать ответы от других членов сообщества.
...