ゆめみのコーディング模擬試験をGoでやってみた
こんにちは。
今回は、Go言語の勉強もかねて、ゆめみさんのサーバーサイドコーディング模擬試験を解いてみました。
取り合えず内容抜粋。
概要
あなたは、あるe-sports大会で集められたゲームのプレイログをもとに、ランキング上位10人を算出することになりました。
このランキングを算出するCLIプログラムの開発をしてください。
ゲームのプレイログの構造
プレイログは3列のCSVファイルとして提供されます。
1行目は、ヘッダとしてcreate_timestamp,player_id,scoreと記載されています。
プレイログは2行目以降に記録されており、1行目のヘッダーの各項目に対応したデータが記載されています。
player_idはゲームにエントリしているプレイヤーごとに一つづつ払い出された個別のIDで、このIDが異なると別のプレイヤーと見做します。
player_idの構成要素はアルファベットの大文字、小文字、および数字の0-9のみとなります。
scoreは正の整数となります。
同一のプレイヤーが複数回のプレイを実施したときには、複数行のログが記録されます。
対象のプレイログ全体は数千万行以上に肥大化することがあります。
プレイヤーの総数は1万人を超えることはありません。
ゲームのプレイログサンプル
create_timestamp,player_id,score2021/01/01 12:00,player0001,123452021/01/02 13:00,player0002,100002021/01/03 12:00,player0021,1002021/01/04 12:10,player0031,2002021/01/05 12:00,player0041,300
入力ルール
CLIアプリケーションは1つの引数を受け取る
上記の引数は処理対象のゲームプレイログを示すファイル名である
出力ルール
各プレイヤーにおける、全てのプレイの平均点を利用したランキングを算出して、その上位10名を出力してください。
出力は3列のCSV形式とする
1行目はヘッダとして、rank,player_id,mean_scoreを出力する
上記ヘッダに準じて2列目以降を出力する
rankの項目には平均スコア上位から1,2,3,…の数字が割り当てられる
平均スコアは四捨五入で整数で丸められる
同点の平均スコアのプレイヤーが居た場合、rankingの数字は同じ数字が割り当てられる
同点の平均スコアのプレイヤーが居た場合において、10名以上のランキングが作られる事がある
入出力例
$ ./get_ranking game_score_log.csvrank,player_id,mean_score1,player0001,100001,player0002,100003,player0003,90004,player0004,70005,player0005,10006,player0006,9997,player0007,9988,player0008,9979,player0009,9909,player0010,9909,player0011,9909,player0012,990
解答
Go言語を書くときはフラット構成が好きなのでフラット構成でやります。
まあ、とりあえずこの規模であればmain.goに書いていって問題ないと思うので、main.goに書きます。
対象のプレイログ全体は数千万行以上に肥大化することがあります。
とありますが、Go はストリーム指向なので、io.Reader
を使い効率的に入力を扱えます。CSV ファイルの行数が長くてもメモリ不足になる事はありません。たぶん。
書いてみた
package main
import ( "encoding/csv" "errors" "fmt" "io" "log" "math" "os" "sort" "strconv")
// rankLimit は出力するランキングの上限です。const rankLimit = 10
type Score struct { Sum int Count int}
type PlayerData map[string]*Score
type MeanScore map[int][]string
func main() { if len(os.Args) < 2 { log.Fatal("処理対象のゲームプレイログCSVファイルを指定してください。") } csvFile := os.Args[1]
f, err := os.Open(csvFile) if err != nil { log.Fatal("指定されたファイルにアクセスできません。") } defer f.Close()
r := csv.NewReader(f)
// 1行目はヘッダー header, err := r.Read() if err != nil { log.Fatal("CSVファイルの読み込みに失敗しました。") } if !checkHeader(header) { log.Fatal("不正なCSVファイルです。") }
// プレイヤーのスコアを集計 p, err := LoadScore(r) if err != nil { log.Fatal(err) }
// 平均スコアを計算 m := CalcMeanScore(p)
// ランキングを出力 PrintRank(m)
}
// checkHeader はヘッダーの内容をチェックします。func checkHeader(header []string) bool { return header[0] == "create_timestamp" && header[1] == "player_id" && header[2] == "score"}
// AddScore はプレイヤーのスコアを集計します。func (d PlayerData) AddScore(id string, score int) { if _, ok := d[id]; !ok { // プレイヤーが存在しない場合は初期化 d[id] = &Score{} } d[id].Sum += score d[id].Count++}
// CalcMeanScore はプレイヤーの平均スコアを計算します。// math.Round で四捨五入しています。func (s Score) CalcMeanScore() int { return int(math.Round(float64(s.Sum) / float64(s.Count)))}
// LoadScore はCSVファイルからスコアを読み込みます。func LoadScore(r *csv.Reader) (PlayerData, error) { p := PlayerData{} for { record, err := r.Read() if err == io.EOF { break } if err != nil { return p, errors.New("CSVファイルの読み込みに失敗しました。") } score, err := strconv.Atoi(record[2]) if err != nil { return p, errors.New("スコアの読み込みに失敗しました。") } p.AddScore(record[1], score) } return p, nil}
// AddPlayer はプレイヤーのスコアを追加します。func (m MeanScore) AddPlayer(score int, id string) { if _, ok := m[score]; !ok { m[score] = []string{} } m[score] = append(m[score], id)}
// CalcMeanScore はプレイヤーの平均スコアを計算します。func CalcMeanScore(d PlayerData) MeanScore { m := MeanScore{} for id, s := range d { score := s.CalcMeanScore() m.AddPlayer(score, id) } return m}
// SortMeanScore は平均スコアの降順 でソートします。func SortMeanScore(m MeanScore) []int { meanScore := make([]int, 0, len(m)) for s := range m { meanScore = append(meanScore, s) } sort.Sort(sort.Reverse(sort.IntSlice(meanScore))) return meanScore}
// PrintRank はランキングを出力します。func PrintRank(m MeanScore) { keys := SortMeanScore(m) rank := 1
fmt.Println("rank,player_id,mean_score")
for _, k := range keys { // 同率の場合プレイヤーID順にソート sort.Strings(m[k]) for _, id := range m[k] { fmt.Printf("%d,%s,%d\n", rank, id, k) } rank += len(m[k]) // rankLimit に達したら終了 if rank > rankLimit { break } }}
わからないこと
- メソッドの使い方は適切か?
- 関数分けは適切か?
- もっといい処理方法や書き方がある?
完走した感想
公式に与えられているテストはすべて通りました。
また、3000万行のCSVでは8-9秒台、5000万行のCSVでは13-14秒台でした。
総括
全体で1時間ほどかかりました。内容としては非常に面白く楽しかったです。
結構時間がかかってしまった気がします。もう少し早く書けるようになりたい。