🦀
ゆめみの【新卒・中途採用】サーバーサイドエンジニア応募者向けの模試をRustで解いてみた。
はじめに
精神衛生を保つために、常に転職はできるようにしておきたいですよね。ということで今回はゆめみさんがホームページで公開しているサーバーサイドエンジニア応募者向けの模試を解いてみました。なお解法はゆめみの新卒の方がGolangで解いていた解法を全面的に参考にしました。
私の解法が合格基準に達しているかどうかは全く不明ですし、合っているかも分からないので、そこはご了承ください。
問題
元記事から引用しています。
概要
あなたは、ある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
結果を標準出力に表示するCLIアプリケーションとして実装してください。
入力ルール
- CLIアプリケーションは1つの引数を受け取る
- 上記の引数は処理対象のゲームプレイログを示すファイル名である
出力ルール
- 各プレイヤーにおける、全てのプレイの平均点を利用したランキングを算出して、その上位10名を出力してください。
- 出力は3列のCSV形式とする
- 1行目はヘッダとして、rank,player_id,mean_scoreを出力する
- 上記ヘッダに準じて2列目以降を出力する
- rankの項目には平均スコア上位から1,2,3,…の数字が割り当てられる
- 平均スコアは四捨五入で整数で丸められる
- 同点の平均スコアのプレイヤーが居た場合、rankingの数字は同じ数字が割り当てられる
- 同点の平均スコアのプレイヤーが居た場合において、10名以上のランキングが作られる事がある
解法
解法の大まかな方針としては
- player_idをキー、ScoreData{合計, 出現回数}をバリューとした連想配列を作る。
- 平均点数をキー、player_idのリストをバリューとした連想配列を作る。
- 上位10名を出力する。
というような感じでコーディングしました。
Cargo.toml
[package]
name = "script"
version = "0.1.0"
edition = "2018"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
anyhow = "1.0.44"
rand = "0.8.4"
csv = "1"
serde = { version = "1", features = ["derive"]}
ranking.rs
use std::collections::{HashMap, BTreeMap};
use std::fs::File;
use std::io::BufReader;
use std::path::Path;
use std::env;
use serde::Deserialize;
struct ScoreData {
sum: u64,
count: u64,
}
#[derive(Debug, Deserialize)]
struct Record {
create_timestamp: String,
player_id: String,
score: u64,
}
fn main() {
let args: Vec<String> = env::args().skip(1).collect();
if args.len() == 0 {
return;
}
solve(&args[0]).expect("Can't generate ranking");
}
fn solve(filename: impl AsRef<Path>) -> anyhow::Result<()> {
// 1. player_idをキー、ScoreData{合計, 出現回数}をバリューとした連想配列を作る。
let mut score_map = HashMap::new();
set_player_map(filename, &mut score_map)?;
// 2. 平均点数をキー、plyer_idのリストをバリューとした連想配列を作る。
let mut mean_map = BTreeMap::new();
set_mean_map(&mut mean_map, &score_map);
// 3. 上位10名を出力する。
print(&mean_map);
Ok(())
}
fn set_player_map(filename: impl AsRef<Path>, score_map: &mut HashMap<String, ScoreData>) -> anyhow::Result<()> {
let file = File::open(filename)?;
let reader = BufReader::new(file);
let mut reader = csv::Reader::from_reader(reader);
for result in reader.deserialize() {
let result: Record = result?;
let score_data = score_map.entry(result.player_id).or_insert(ScoreData { sum: 0, count: 0 });
score_data.sum += result.score;
score_data.count += 1;
}
Ok(())
}
fn set_mean_map(mean_map: &mut BTreeMap<u64, Vec<String>>, score_map: &HashMap<String, ScoreData>) {
for (player_id, score_data) in score_map.iter() {
let mean_score = (score_data.sum as f64 / score_data.count as f64).round() as u64;
let player_list = mean_map.entry(mean_score).or_insert(vec![]);
player_list.push(player_id.clone());
}
}
fn print(mean_map: &BTreeMap<u64, Vec<String>>) {
let limits = 10;
let mut rank = 1;
let mut total_count = 0;
for (mean_score, player_list) in mean_map.iter().rev() {
let mut count = 0;
for player in player_list {
println!("{}, {}, {}", rank, player, mean_score);
total_count += 1;
count += 1;
}
if total_count >= limits {
break;
}
rank += count;
}
}
１つずつ見ていきます。
main関数
fn main() {
let args: Vec<String> = env::args().skip(1).collect();
if args.len() == 0 {
return;
}
solve(&args[0]).expect("Can't generate ranking");
}
これは単にファイル名をsolve関数に渡しているだけですね。 env::args().skip(1).collect()はコマンドライン引数を取るための定石です。
solve関数
fn solve(filename: impl AsRef<Path>) -> anyhow::Result<()> {
// 1. player_idをキー、ScoreData{合計, 出現回数}をバリューとした連想配列を作る。
let mut score_map = HashMap::new();
set_player_map(filename, &mut score_map)?;
// 2. 平均点数をキー、player_idのリストをバリューとした連想配列を作る。
let mut mean_map = BTreeMap::new();
set_mean_map(&mut mean_map, &score_map);
// 3. 上位10名を出力する。
print(&mean_map);
Ok(())
}
これは先程示した、解法の方針を関数に分割しています。それぞれ見てみましょう。
1. player_idをキー、ScoreData{合計, 出現回数}をバリューとした連想配列を作る。
#[derive(Debug, Deserialize)]
struct Record {
create_timestamp: String,
player_id: String,
score: u64,
}
struct ScoreData {
sum: u64,
count: u64,
}
fn set_player_map(filename: impl AsRef<Path>, score_map: &mut HashMap<String, ScoreData>) -> anyhow::Result<()> {
let file = File::open(filename)?;
let reader = BufReader::new(file); // 1
let mut reader = csv::Reader::from_reader(reader);
for result in reader.deserialize() { // 2
let result: Record = result?;
let score_data = score_map.entry(result.player_id).or_insert(ScoreData { sum: 0, count: 0 }); // 3
score_data.sum += result.score;
score_data.count += 1;
}
Ok(())
}
ここでのポイントは以下の通りです。
- ファイルが数千万行になる場合もあるということで、性能を気にして
BufReaderでバッファリングしています。 - csvクレートを使ってファイルをパースしています。
- HashMapのentry APIを使って、そのキーに対応する値があれば、それを返す、なければ
or_insertで値を挿入し、それを返すという処理をスッキリ記述しています。entry関数についてはこの記事が参考になります。
2. 平均点数をキー、player_idのリストをバリューとした連想配列を作る。
fn set_mean_map(mean_map: &mut BTreeMap<u64, Vec<String>>, score_map: &HashMap<String, ScoreData>) { // 1
for (player_id, score_data) in score_map.iter() {
let mean_score = (score_data.sum as f64 / score_data.count as f64).round() as u64;
let player_list = mean_map.entry(mean_score).or_insert(vec![]); // 2
player_list.push(player_id.clone());
}
}
ここでのポイントは以下の通りです。
-
BTreeMapを使っています。これはキーのソート順を維持したいためです。 - ここも
Entry APIを使っています。
3. 上位10名を出力する。
fn print(mean_map: &BTreeMap<u64, Vec<String>>) {
let limits = 10;
let mut rank = 1;
let mut total_count = 0;
for (mean_score, player_list) in mean_map.iter().rev() { // 1
let mut count = 0;
for player in player_list {
println!("{}, {}, {}", rank, player, mean_score);
total_count += 1;
count += 1;
}
if total_count >= limits {
break;
}
rank += count;
}
}
ここでのポイントは以下の通りです。
- BTreeなので
mean_map.iter().rev()のように書けばキーの降順で値を取り出すことができます。
おまけ
おまけとしてcsvファイルを生成するコードをのせておきます。
Cargo.toml
[package]
name = "script"
version = "0.1.0"
edition = "2018"
# See more keys and their definitions at https://doc.rust-lang.org/cargo/reference/manifest.html
[dependencies]
anyhow = "1.0.44"
rand = "0.8.4"
csv = "1"
serde = { version = "1", features = ["derive"]}
gen_csv.rs
use std::fs::OpenOptions;
use std::io::prelude::*;
use std::io::BufWriter;
use rand::prelude::*;
use rand::{thread_rng, Rng};
fn main() {
gen_csv(30000000).expect("Can't generate csv file");
}
fn gen_csv(limits: u64) -> anyhow::Result<()>{
let mut rng = thread_rng();
let file = OpenOptions::new()
.read(true)
.write(true)
.create(true)
.open("score.txt")?;
file.set_len(0)?;
let mut file = BufWriter::new(file);
file.write(b"create_timestamp,player_id,score\n")?;
let timestamp = "1998/01/01 11:59";
for _ in 0..limits {
let id: u8 = random();
let player_id = format!("player{}", id);
let score = rng.gen_range(0..10000);
let line = format!("{},{},{}\n", timestamp, player_id, score);
file.write(line.as_bytes())?;
}
Ok(())
}
おわりに
ゆめみさんのサーバーサイドの模試を解いてみましたが、Golangの解法記事を見てから解いてみたにも関わらず、一時間くらいかかってしまいました。。普段業務では全然コードを書く機会がないので、余暇の時間に少しでも時間をとって、コーディングしていきたいと感じました。
Discussion