🐚

ゆめみ新卒が自社のコーディング試験の模試を解いてみた(Golang)

6 min read 4

概要

こんにちは、2021年の4月にゆめみ社にサーバーサイドエンジニアとして入社した貝です🐚
最近、ゆめみがコーディング試験の模試を公開したみたいなので、解いてみようと思います!
「君これだと落とすよ」って言われないように頑張りますw

あと、ゆめみは通年募集行ってますので、もし興味を持った方は是非応募してくださいね!

https://www.yumemi.co.jp/category/recruit

問題

問題はこちらに載っています。とはいえ、見に行ってもらうのも大変なので、以下にコピペします。

概要

あなたは、ある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,score
2021/01/01 12:00,player0001,12345
2021/01/02 13:00,player0002,10000
2021/01/03 12:00,player0021,100
2021/01/04 12:10,player0031,200
2021/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.csv
rank,player_id,mean_score
1,player0001,10000
1,player0002,10000
3,player0003,9000
4,player0004,7000
5,player0005,1000
6,player0006,999
7,player0007,998
8,player0008,997
9,player0009,990
9,player0010,990
9,player0011,990
9,player0012,990

解答

方針

せっかくなので最近勉強始めたGolangで解いてみたいと思います〜
最初の方針としてはcsvから読み込んでユーザーIDをキーにした連想配列にデータを追加していけばいいかな、という感じですね。

{
  "player0001": ScoreData{sum: 400, count: 3},
  "player0002": ScoreData{sum: 500, count: 1},
  "player0004": ScoreData{sum: 1000, count: 10}
}

あと注意したいのはこのあたりでしょうか。メモリのこと考えるのきちい。。

対象のプレイログ全体は数千万行以上に肥大化することがあります。

同点の平均スコアのプレイヤーが居た場合において、10名以上のランキングが作られる事がある

実際に書いたコード

main.go
package main

import (...)

const (
	MaxRanking = 10
)

// プレイヤーごとのスコア情報
type ScoreData struct {
	sum   int
	count int
}

type ScoreMap map[string]ScoreData

type MeanScoreMap map[int][]string

func main() {
	// CLI引数からCSVのファイル名を取得
	flag.Parse()

	// fileを開く
	file, err := os.Open(flag.Arg(0))
	if err != nil {
		log.Fatal(err)
	}
	defer file.Close()

	r := csv.NewReader(file)
	// ヘッダー行の取得と検証
	header, _ := r.Read()
	validateHeader(header)

	// スコアを記録する連想配列を作成
	scoreMap := createScoreMap(r) // { playerID: ScoreData }

	// 平均値をキーとした連想配列の作成
	meanScoreMap := createMeanScoreMap(scoreMap) // { meanScore: playerIds[] }

	// 平均値の配列を作成してソートする
	meanScoreArr := make([]int, 0, len(meanScoreMap))
	for meanScore := range meanScoreMap {
		meanScoreArr = append(meanScoreArr, meanScore)
	}
	sort.Sort(sort.Reverse(sort.IntSlice(meanScoreArr)))

	// 出力
	output(meanScoreMap, meanScoreArr)
}

// ヘッダーの検証
func validateHeader(header []string) {
	if header[0] != "create_timestamp" || header[1] != "player_id" || header[2] != "score" {
		log.Fatal("header is invalid")
	}
}

func createScoreMap(r *csv.Reader) ScoreMap {
	scoreMap := make(map[string]ScoreData, 5000)
	for {
		// 1行ずつ読み込む
		record, err := r.Read()
		if err == io.EOF {
			break
		} else if err != nil {
			log.Fatal(err)
		}
		score, _ := strconv.Atoi(record[2])
		// scoreDataが初期化されていない場合は初期化する
		scoreData, ok := scoreMap[record[1]]
		if !ok {
			scoreMap[record[1]] = ScoreData{sum: 0, count: 0}
		}
		scoreData.sum += score
		scoreData.count += 1
		scoreMap[record[1]] = scoreData
	}
	return scoreMap
}

func createMeanScoreMap(scoreMap ScoreMap) MeanScoreMap {
	meanScoreMap := make(map[int][]string, 0, 500)
	for playerId, scoreData := range scoreMap {
		meanScore := int(math.Round(float64(scoreData.sum) / float64(scoreData.count)))
		// playerIds[]が初期化されていない場合は初期化する
		if _, ok := meanScoreMap[meanScore]; !ok {
			meanScoreMap[meanScore] = make([]string, 0, 5)
		}
		meanScoreMap[meanScore] = append(meanScoreMap[meanScore], playerId)
	}
	return meanScoreMap
}

func output(meanScoreMap MeanScoreMap, meanScoreArr []int) {
	fmt.Println("rank,player_id,mean_score")
	manCount := 0 // 出力済みの人数
	ranking := 1  // ランキング
	for _, meanScore := range meanScoreArr {
		for _, playerId := range meanScoreMap[meanScore] {
			str := fmt.Sprintf("%d,%s,%d", ranking, playerId, meanScore)
			fmt.Println(str)
			manCount += 1
		}
		if manCount >= MaxRanking {
			break
		}
		ranking += len(meanScoreMap[meanScore])
	}
}

セルフレビュー

  • 一通り書いた後、可読性を高めるためある程度の処理を関数に切り出した
  • csvが数千万行以上とのことなので、一度に読み込むとバッファオーバーフローすると思い1行ずつ読み込んだ。1万行ずつスライスして一度に読み込むなどの方がよいかと思ったが、Golangでのやり方がわからなかったので断念。
    • 実際3千万行のcsvで実験して10秒はかからなかったのでOKかなぁ
  • goroutineを使って読み込み処理を非同期に行えたらなおよかったかもしれない。
  • 配列/連想配列時の容量確保のベスプラはまだよくわかっていない。ひとまず要件からおおよその最大値の半分を確保しておいた。
  • Pythonにあるような集合とかsum()とかkeys()などの配列用関数とかがGolangにはないの結構冗長になっちゃうな、という気持ち。
- ranking += 1
+ ranking += len(meanScoreMap[meanScore])

tirapiさんのご指摘を受けて変更させていただきました🤲

おまけ(でっかいcsvを生成するコード)

package main

import (...)

const (
	MaxPlayers  = 10000
	Lines       = 30000000
	WriteBuffer = 10000
	Timestamp   = "1998/01/01 11:59"
)

func main() {
	// O_WRONLY:書き込みモード開く, O_CREATE:無かったらファイルを作成
	file, err := os.OpenFile("./game_score_log.csv", os.O_WRONLY|os.O_CREATE, 0600)
	if err != nil {
		log.Fatal(err)
	}
	defer file.Close()

	err = file.Truncate(0) // ファイルを空っぽにする(実行2回目以降用)
	if err != nil {
		log.Fatal(err)
	}

	w := csv.NewWriter(file)
	w.Write([]string{"create_timestamp", "player_id", "score"}) // ヘッダーの書き込み

	lineCount := 0
	for lineCount < Lines {
		for i := 0; i < WriteBuffer; i++ {
			playerId := fmt.Sprintf("player%d", rand.Intn(MaxPlayers))
			score := strconv.Itoa(rand.Intn(10000))
			w.Write([]string{Timestamp, playerId, score})
		}
		w.Flush()
		lineCount += WriteBuffer
	}
}

Discussion

コメント失礼します。
自分もGolangの学習をしており、コードの組み立て方などとても参考になりました!
執筆くださりありがとうございます!🙇‍♂️

細い部分になりますが出力例を見ると、同順位が発生した場合次の順位を飛ばして順位をつける仕様になっているかと思いました。
cf.

$ ./get_ranking game_score_log.csv
rank,player_id,mean_score
1,player0001,10000
1,player0002,10000
3,player0003,9000

ご確認いただけますと幸いです。よろしくお願いします!

お読みいただき、又丁寧なご指摘ありがとうございます!確かに、その仕様は見逃していました。
修正させていただきます🤲

回答お疲れさまでした!
ちょっと気になった点を以下にまとめています。

  • Goルーティンは正しくは goroutine (ゴルーチン)です。
  • 平均値を計算する際に int でキャストしていますが、小数点以下が切り捨てられるせいで同一順位でないプレイヤーも同一順位とみなされてしまいます。
  • ScoreData.sum が int のため要件的にオーバーフローする可能性があります。
  • meanScoreMap := make(map[int][]string, 500)meanScoreMap := make(map[int][]string, 0, 500) ですかね。
    • 前者の初期状態は len(meanScoreMap) == 500, cap(meanScoreMap) == 500 で後者の初期状態は len(meanScoreMap) == 0, cap(meanScoreMap) == 500 です。
    • そしてそのまま append すると、前者は len(meanScoreMap) == 501, cap(meanScoreMap) == 1024 で後者は len(meanScoreMap) == 1, cap(meanScoreMap) == 500 となります。
    • つまりせっかくアロケートしたスライスの要素が無駄になっています。
    • https://play.golang.org/p/8AG4wQvS4Ge
  • 今回はランキングの長さが可変長でしたが、固定長の場合はより適したソートアルゴリズムがあるかもしれません。

丁寧なコメント&&レビュー誠にありがとうございます🙏
特にGolangの知識不足が露呈していてお恥ずかしい限りです。参考の上修正させていただきたいと思います。

ログインするとコメントできます