集計とランキングの実装方法の考察
検証用のセットアップ
require "active_record"
require "table_format"
ActiveSupport::LogSubscriber.colorize_logging = false
ActiveRecord::Base.establish_connection(adapter: "sqlite3", database: ":memory:")
ActiveRecord::Migration.verbose = false
ActiveRecord::Schema.define do
create_table :histories do |t|
t.string :name
t.string :ox
end
end
class History < ActiveRecord::Base; end
History.create!(name: "a", ox: "x")
History.create!(name: "b", ox: "o")
History.create!(name: "b", ox: "o")
History.create!(name: "b", ox: "x")
History.create!(name: "c", ox: "o")
History.create!(name: "c", ox: "o")
ActiveRecord::Base.logger = ActiveSupport::Logger.new(STDOUT)
集計対象を確認する
tp History
# > History Load (0.1ms) SELECT "histories".* FROM "histories"
# > |----|------|----|
# > | id | name | ox |
# > |----|------|----|
# > | 1 | a | x |
# > | 2 | b | o |
# > | 3 | b | o |
# > | 4 | b | x |
# > | 5 | c | o |
# > | 6 | c | o |
# > |----|------|----|
勝敗が o x で入っている。
group + count → Hash は集計の方向が違う
tp h = History.group(:name, :ox).count # => {["a", "x"]=>1, ["b", "o"]=>2, ["b", "x"]=>1, ["c", "o"]=>2}
# > History Count (0.1ms) SELECT COUNT(*) AS "count_all", "histories"."name" AS "histories_name", "histories"."ox" AS "histories_ox" FROM "histories" GROUP BY "histories"."name", "histories"."ox"
# > |------------|---|
# > | ["a", "x"] | 1 |
# > | ["b", "o"] | 2 |
# > | ["b", "x"] | 1 |
# > | ["c", "o"] | 2 |
# > |------------|---|
group(:name, :ox)
で複合キーのハッシュが作れるので、
h[["b", "o"]] # => 2
h[["c", "x"]] # => nil
とすれば任意のユーザーの勝敗数が O(1) で求まる。しかし求めたいのは全体のランキングであって個々の勝敗数ではない。そこでハッシュキーに入っているユーザー名を利用してテーブルにしてみると、
tp h.collect { |k, _| k.first }.uniq.collect { |e|
{ name: e, o: h[[e, "o"]] || 0, x: h[[e, "x"]] || 0 }
}.sort_by { |e| -e[:o] }
# > |------|---|---|
# > | name | o | x |
# > |------|---|---|
# > | b | 2 | 1 |
# > | c | 2 | 0 |
# > | a | 0 | 1 |
# > |------|---|---|
なんだこれ。first して uniq するなどあきらかに不自然である。ユニークなユーザー配列がどこにもないのが問題なので再度DBから引くと、
tp History.distinct.pluck("name").collect { |e|
{ name: e, o: h[[e, "o"]] || 0, x: h[[e, "x"]] || 0 }
}.sort_by { |e| -e[:o] }
# > History Pluck (0.1ms) SELECT DISTINCT "histories"."name" FROM "histories"
# > |------|---|---|
# > | name | o | x |
# > |------|---|---|
# > | b | 2 | 1 |
# > | c | 2 | 0 |
# > | a | 0 | 1 |
# > |------|---|---|
となり、すこしはましになるがなぜ二度もDBにアクセスすることになってしまったのだろう。これはデータをハッシュで取得したのが失敗だった。
group + select → Array は正しい
count ではなく select に置き換える。そして勝った回数を score とする。
tp History.select([
"name",
"COUNT(ox = 'o') AS score",
]).group("name").collect(&:attributes)
# > History Load (0.1ms) SELECT "histories"."name", COUNT(ox = 'o') AS score FROM "histories" GROUP BY "histories"."name"
# > |------|-------|----|
# > | name | score | id |
# > |------|-------|----|
# > | a | 1 | |
# > | b | 3 | |
# > | c | 2 | |
# > |------|-------|----|
だが score がおかしい。これは次のように、
tp History.select([
"name",
"sum(CASE WHEN ox = 'o' THEN 1 ELSE 0 END) AS score",
]).group("name").collect(&:attributes)
# > History Load (0.1ms) SELECT "histories"."name", sum(CASE WHEN ox = 'o' THEN 1 ELSE 0 END) AS score FROM "histories" GROUP BY "histories"."name"
# > |------|-------|----|
# > | name | score | id |
# > |------|-------|----|
# > | a | 0 | |
# > | b | 2 | |
# > | c | 2 | |
# > |------|-------|----|
ox = 'o'
の真偽を 1
0
としてその和を求めるとうまくいく。が、どういうわけか COUNT(ox = 'o' OR NULL)
としても同様の結果になる。
tp items = History.select([
"name",
"COUNT(ox = 'o' OR NULL) AS score",
]).group("name").collect(&:attributes)
# > History Load (0.1ms) SELECT "histories"."name", COUNT(ox = 'o' OR NULL) AS score FROM "histories" GROUP BY "histories"."name"
# > |------|-------|----|
# > | name | score | id |
# > |------|-------|----|
# > | a | 0 | |
# > | b | 2 | |
# > | c | 2 | |
# > |------|-------|----|
不可解な構文だが SQL はそういうものなので考えてはいけない。
工夫していろいろ集計しておく (おまけ)
勝数を score とするだけではおもしろくないので他の情報も求めておく場合は、
tp History.select([
"name",
"COUNT(ox = 'o' OR NULL) AS o_count",
"COUNT(ox = 'x' OR NULL) AS x_count",
"COUNT(*) AS total",
"COUNT(ox = 'o' OR NULL) / CAST(COUNT(*) as REAL) AS ratio",
]).group("name").collect(&:attributes)
# > History Load (0.1ms) SELECT "histories"."name", COUNT(ox = 'o' OR NULL) AS o_count, COUNT(ox = 'x' OR NULL) AS x_count, COUNT(*) AS total, COUNT(ox = 'o' OR NULL) / CAST(COUNT(*) as REAL) AS ratio FROM "histories" GROUP BY "histories"."name"
# > |------|---------|---------|-------|--------------------|----|
# > | name | o_count | x_count | total | ratio | id |
# > |------|---------|---------|-------|--------------------|----|
# > | a | 0 | 1 | 1 | 0.0 | |
# > | b | 2 | 1 | 3 | 0.6666666666666666 | |
# > | c | 2 | 0 | 2 | 1.0 | |
# > |------|---------|---------|-------|--------------------|----|
などとする。割り算のときは CAST(xxx as REAL)
として浮動小数点型にしないといけない。キャストするのは除数・被除数の一方だけでよい。
順序を考慮する
order("score DESC")
を追加する。
tp items = History.select([
"name",
"COUNT(ox = 'o' OR NULL) AS score",
]).group("name").order("score DESC").collect(&:attributes)
# > History Load (0.1ms) SELECT "histories"."name", COUNT(ox = 'o' OR NULL) AS score FROM "histories" GROUP BY "histories"."name" ORDER BY score DESC
# > |------|-------|----|
# > | name | score | id |
# > |------|-------|----|
# > | c | 2 | |
# > | b | 2 | |
# > | a | 0 | |
# > |------|-------|----|
と、この時点でランキングの並びだけは取れる。さにらランクを求めるには、
tp items.collect { |e|
e.merge(:rank => items.count { |o| o["score"] > e["score"] }.next)
}
# > |------|-------|----|------|
# > | name | score | id | rank |
# > |------|-------|----|------|
# > | c | 2 | | 1 |
# > | b | 2 | | 1 |
# > | a | 0 | | 3 |
# > |------|-------|----|------|
とする。ただ O(N^2) になっているのでかなり遅い。替わりに DB で計算するには、
ActiveRecord::Schema.define do
create_table :rankings do |t|
t.string :name
t.integer :score
end
end
class Ranking < ActiveRecord::Base; end
Ranking.create!(items)
tp Ranking.all.collect { |e|
sql = "SELECT COUNT(*) + 1 FROM rankings WHERE score > #{e.score}"
rank = ActiveRecord::Base.connection.select_value(sql)
e.attributes.merge(rank: rank)
}
# > Ranking Load (0.1ms) SELECT "rankings".* FROM "rankings"
# > (0.1ms) SELECT COUNT(*) + 1 FROM rankings WHERE score > 2
# > (0.0ms) SELECT COUNT(*) + 1 FROM rankings WHERE score > 2
# > (0.0ms) SELECT COUNT(*) + 1 FROM rankings WHERE score > 0
# > |----|------|-------|------|
# > | id | name | score | rank |
# > |----|------|-------|------|
# > | 1 | c | 2 | 1 |
# > | 2 | b | 2 | 1 |
# > | 3 | a | 0 | 3 |
# > |----|------|-------|------|
とすればよいが計算量は変わってないので実用に耐えない。
Redis の ZADD + ZCOUNT
名前とスコアのペアのソートしていない配列を用意し、
tp items = History.select([
"name",
"COUNT(ox = 'o' OR NULL) AS score",
]).group("name").collect(&:attributes)
# > History Load (0.1ms) SELECT "histories"."name", COUNT(ox = 'o' OR NULL) AS score FROM "histories" GROUP BY "histories"."name"
# > |------|-------|----|
# > | name | score | id |
# > |------|-------|----|
# > | a | 0 | |
# > | b | 2 | |
# > | c | 2 | |
# > |------|-------|----|
ZADD で投入し、
require "redis-client"
redis = RedisClient.new
redis.call("FLUSHDB")
items.each do |e|
redis.call("ZADD", "key1", e["score"], e["name"])
end
ZRANGE を呼ぶと、
tp redis.call("ZRANGE", "key1", 0, -1, :rev, :withscores)
# > |------------|
# > | ["c", 2.0] |
# > | ["b", 2.0] |
# > | ["a", 0.0] |
# > |------------|
ソートされた状態で取得できる。
続いて ZCOUNT に score + 1 を与えると、
redis.call("ZCOUNT", "key1", 2 + 1, "+inf") + 1 # => 1
redis.call("ZCOUNT", "key1", 2 + 1, "+inf") + 1 # => 1
redis.call("ZCOUNT", "key1", 0 + 1, "+inf") + 1 # => 3
ランクが求まる。したがって ZRANGE の結果でループして ZCOUNT にスコアを与えれば、
tp redis.call("ZRANGE", "key1", 0, -1, :rev, :withscores).collect { |name, score|
{
name: name,
score: score,
rank: redis.call("ZCOUNT", "key1", score + 1, "+inf") + 1,
}
}
# > |------|-------|------|
# > | name | score | rank |
# > |------|-------|------|
# > | c | 2.0 | 1 |
# > | b | 2.0 | 1 |
# > | a | 0.0 | 3 |
# > |------|-------|------|
全体のランクが求まる。ZCOUNT は O(log(N)) なので一瞬でランクが取れる。
リアルタイムでランクを出す
上の例はランキングを作る直前でまとめて ZADD したけどこれをリアルタイムで更新していくとランクもリアルタイムに出せるようになる。リアルタイムで更新するには正誤を記録したタイミングが適しているので、
class History < ActiveRecord::Base
after_create do
score = History.where(name: name, ox: "o").count
redis = RedisClient.new
redis.call("ZADD", "key1", score, name)
end
end
とする。
そこで仮にスコア100を出したユーザーのランクを調べるには、
redis.call("ZCOUNT", "key1", 100 + 1, "+inf") + 1
とする。
ランクと一緒に勝敗数もリアルタイムで出す
require "redis-client"
require "active_record"
require "table_format"
ActiveSupport::LogSubscriber.colorize_logging = false
ActiveRecord::Base.establish_connection(adapter: "sqlite3", database: ":memory:")
ActiveRecord::Migration.verbose = false
ActiveRecord::Schema.define do
create_table :histories do |t|
t.string :name
t.string :ox
end
create_table :rankings do |t|
t.string :name
t.integer :o_count
t.integer :x_count
t.integer :total
t.integer :score
t.integer :rank
end
end
class History < ActiveRecord::Base
after_create do
history = History.select([
"COUNT(ox = 'o' OR NULL) AS o_count",
"COUNT(ox = 'x' OR NULL) AS x_count",
]).find_by(name: name)
ranking = Ranking.find_or_initialize_by(name: name)
ranking.o_count = history.o_count
ranking.x_count = history.x_count
ranking.save!
end
end
class Ranking < ActiveRecord::Base
default_scope { order(:rank) }
before_validation do
self.total = o_count + x_count
self.score = o_count
end
after_save do
if saved_change_to_attribute?(:score)
redis.call("ZADD", "key1", score, name)
end
end
def rank_update
update!(rank: rank_in_redis)
end
private
def rank_in_redis
redis.call("ZCOUNT", "key1", score + 1, "+inf") + 1
end
def redis
@redis ||= RedisClient.new
end
end
RedisClient.new.call("FLUSHDB")
History.create!(name: "a", ox: "x")
History.create!(name: "b", ox: "o")
History.create!(name: "b", ox: "o")
History.create!(name: "b", ox: "x")
History.create!(name: "c", ox: "o")
History.create!(name: "c", ox: "o")
Ranking.find_each(&:rank_update)
tp Ranking
# > |----|------|---------|---------|-------|-------|------|
# > | id | name | o_count | x_count | total | score | rank |
# > |----|------|---------|---------|-------|-------|------|
# > | 2 | b | 2 | 1 | 3 | 2 | 1 |
# > | 3 | c | 2 | 0 | 2 | 2 | 1 |
# > | 1 | a | 0 | 1 | 1 | 0 | 3 |
# > |----|------|---------|---------|-------|-------|------|
- 個々の集計結果を事前に保持しておくための Ranking モデルを用意する
- これまでは History → Redis だった
- そうではなく History → Ranking →←Redis とする
- Ranking にはランキングに必要なものを入れる
- ユーザー (ユニーク)
- 勝数
- 負数
- 合計 (総バトル数)
- スコア (わかりやすいように勝数とする)
- 勝率 (勝数 / (勝数 + 敗数)) なんかもあっていい
- ランク
- History.create のタイミングで Ranking をユーザーで引いて登録または更新する
- このとき Ranking への登録と同時にランクを更新してはいけない
- 複数人で対戦しているのであれば一式登録し終えてからランクを更新する
- Ranking をビューに表示する
- 個々
- ユーザーに結び付いたレコードを表示する
- ランキング全体
- ランクでソートした結果をそのままビューに出す
- 個々
Discussion