ゆめみの採用試験サンプル問題をPHPで解いてみた

新卒・中途採用におけるコードチェックの実施とチェック時の観点について（株式会社ゆめみサーバサイドの場合）という記事を見ていたら採用試験サンプルが公開されていて、そしてその選択肢にPHPがあったので解いてみることにします。

べつに転職するつもりとかは全くありませんが。

問題

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
…

このようなCSVから以下の条件で抽出する。

・プレイヤー平均点の上位10人を抽出する。
・スコアは四捨五入し、同点の場合は11人以上抽出される場合がある。
・プレイヤー数は1万人以下、ログは数千万行。

回答

/*
    スコア表からランキング上位10位を抜き出して標準出力するバッチ

    ここらへんにGitHubとかRedmineとかへのリンク
    詳細はそっちに書いとけばいいよ。
*/
(new Ranking())->run($argv);

class Ranking
{
    /**
     * スコア表からランキング上位10位を抜き出す
     * @param array $argv 1にCSVファイル名
     * @return void 中で標準出力してる
     */
    public function run(array $argv):void
    {
        // ファイル読み込み
        $fp = new SplFileObject($argv[1], 'r');
        $fp->setFlags(SplFileObject::SKIP_EMPTY | SplFileObject::DROP_NEW_LINE);
        $fp->fgetcsv(); // ヘッダ行捨てる

        // プレイヤー単位で集計
        $scores = [];
        while ($line = $fp->fgetcsv()) {
            if (isset($scores[$line[1]])) {
                $scores[$line[1]]['cnt']++;
                $scores[$line[1]]['total'] += (int)$line[2];
            } else {
                $scores[$line[1]] = [
                    'cnt' => 1,
                    'total' => (int)$line[2],
                ];
            }
        }

        // スコアをキーにした配列にする
        $ranking = [];
        foreach ($scores as $player=>$v) {
            $ranking[(int)round($v['total'] / $v['cnt'])][] = $player;
        }

        // スコア降順ソート
        krsort($ranking, \SORT_NUMERIC);

        // 10位まで出力
        $rank = 1;
        $fp = fopen('php://stdout', 'w');
        fputcsv($fp, ['rank', 'player_id', 'mean_score']);
        foreach ($ranking as $score=>$players) {
            // 同着は全員出力
            foreach ($players as $player) {
                fputcsv($fp, [$rank, $player, $score]);
            }
            // 出力人数が10を超えていたら終了
            $rank += count($players);
            if ($rank > 10) {
                break;
            }
        }
    }
}

適当なので1メソッド中にだばだば書いてますが、採用試験などちゃんとした場であればきちんとメソッドを分けた方がいいでしょう。
あと内部使用前提なので引数のチェックもしていなかったりと、随所に手抜きが見られますね。

考え方

function run(){
	// ファイルを読み込む

	// 平均点を出す

	// 上位10人抜き出す

	// 画面表示

}

自分がよくやるのは、だいたいこんなかんじで最初に全景をコメントしておき、順番に実装していくやりかたです。
もちろんコーディング中に都合が悪くなって予定変更することも多々ありますが、見通しが立っていればそういうのもやりやすいですからね。

ログの量が膨大なので、file_get_contentsやfileは使用できません。
fgetcsvなどで逐次処理していくことになります。

必要なのは平均値なので、まずはプレイヤーごとに合計点数と件数だけ抽出します。
プレイヤー数は最大1万人なので、抽出した後のデータであればメモリは問題なく足ります。

次いで点数の高い順に並び変えます。
ここで必要なのは上位10人だけであって下位まで全てソートする必要はないので、尺取り法かなにかで上位だけ取り出そうと思ったのですが、同着10位になったときの処理とかが思いのほか面倒だったのでばっさりカットして素直にソート関数を使いました。
最大1万レコードしかないのでこれで十分です。
もっと人数が増えて参加者1億人とかになったら動かなくなる可能性はありますが、そうなったらそのときに考えればいいんですよ。

最後はランキングの上から10位まで抜き出して完了です。
同着は全員出力するという条件のせいで、脱出条件が少々わかりにくいですね。
この書き方であれば、全員同点1位とかの極端な入力でも問題なく動作します。

stdoutは標準出力です。
プレイヤー名にクォートや改行が入っていたりしたら手動でのCSV出力は面倒なので、そのあたりをfputcsvに任せつつ標準出力することができます。
プレイヤー名にはA-Za-z0-9しか入らないことはプログラムを書きあげてから気付きました。

ということで、これで題意を満たしつつそれなりに動くコードができあがりました。
ロジック的には極めて普通に実装しただけなので、華麗なアルゴリズムで高速化！少メモリ！みたいな技巧はありません。
わかりやすくやるのが一番ですよ。

パフォーマンス測定

10万レコードで1秒、メモリ6メガバイト
100万レコードで2秒、メモリ6メガバイト
1000万レコードで16秒、メモリ6メガバイト
1億レコードで2分43秒、メモリ6メガバイト

レコード数がいくら増えてもメモリ消費量は増えません。
これなら要件上の問題はありませんね。

感想

設問の難易度は、たしかにそんなに難しくないです。
問題文にもあるように、どうしてそのように実装したかの意図を説明できるようにしておくほうが大事でしょう。
私の書いたプログラムの意図は、「とりあえず動けばそれでいい」です。

実装時間は測ってませんでしたが100分はかかってませんしおそらく60分未満です。
なんなら記事を書く時間のほうが長かったまである。
採用試験であれば、残り時間は引数チェックの追加とか、メソッド内で出力しているのをどうにかするとか、読み込みにSplFileObjectを使ってるのに書き込みはfputcsvという非対称性をどうにかするとか、拡張性のためにDependency Injectionするとか、そういうのにも手を付けてみるとよいのではないでしょうか。