- Palima Aethera は、Techaro の混沌としたインフラを救う候補者のように見えたが、ライブコーディングでわざと奇妙なソート解法を出し、面接の空気をひっくり返す
- 面接官の Jeff は名前の発音と実際の顔かどうかを確認した後、Palima の MovieFlix インフラ経験と FreeBSD の選択事例に強い関心を示す
- 数字配列のソート課題で、Palima は Haskell で値ごとにスレッドを作り、値に比例して眠った後に出力する sleepsort を実装する
- Palima はこの解法を「定数時間ソート」だと言い張り、遅延時間を
100000 から 10000 マイクロ秒刻みに減らして 10倍最適化したと説明し、Jeff を笑わせる
- 面接後、Palima は不採用を予想するが、Techaro はかなりの金額で採用意向を送り、Palima は仕事もそのうち勝手にソートされるだろうと言って眠ることにする
夢から始まった面接当日
- Palima は夢の中で手首の 覚醒のお守り が消えているのを見て、自分が夢を見ていると気づく
- 腕時計の振動で朝に目覚めた後、その日に大事な予定があることを思い出す
- 通勤は 30 秒で終わり、Palima は尾と背びれを収められるよう改造した椅子に座る
- ワークステーションは Firefox が古いと知らせ、スクリプトが新しいバージョンをビルドして実行する
Techaro 面接の始まり
- ビデオ会議は E100 系サービスで行われ、Palima はカメラ用の照明をつける
- 最初の面接官 Jeff は Palima の名前を間違って発音したが、すぐに言い直す
- Palima は
Pa-lee-mah、Aethera は Ay-theer-ah と発音すると伝える
- Jeff は他の人も正しく呼べるようにメモしておくと言う
- Jeff が バーチャルアバター を使っているのかと尋ねると、Palima は「これが本当の顔です」と答える
- Palima は採用説明だけを見ても、Techaro のインフラが混乱しており、英雄を必要としている状態だと把握する
経歴紹介とインフラ経験
- Palima は、デジタル自動装置を作って世に送り出し、目的を遂行させる仕事を多くしてきたと紹介する
- MovieFlix では人気映画やテレビ番組の 同時ストリーミングインフラ 構築に貢献した
- 公開できないプロジェクトも多く、Jeff は今そのうち少なくとも 3 つの恩恵を受けているはずだと付け加える
- 小さな会社に加わろうとする理由は、人々をもっと個人的に知りたいからであり、機械の中の匿名の部品のように働く魅力は長く続かないと考えている
- 好きなインフラプロジェクトとして、MovieFlix バックエンド向け OS カーネルのベンチマークを挙げる
- Palima は Linux が勝つことを期待していたが、
epoll(7) 以降は FreeBSD のほうが速く動いたため、FreeBSD を選んだ
- まだ FreeBSD のコミット権限があると思う、と付け加える
ライブコーディング: sleepsort
- Jeff は、Palima の経歴は Techaro が探している人物像に合っているように見えるが、全員を同じ基準で見るために コーディングチャレンジ を行う必要があると説明する
- 課題は、Web サイト上で数字配列をソートし、そのソート方法まで説明することだった
- 言語は自由で、Palima は Haskell のコードを書いた
- 実装は各数字ごとに別のグリーンスレッドを作り、
threadDelay (100000 * time) の後でチャネルに値を書いて出力する方式だった
- Palima はこのソートは比較を使わず、「時には少し休むだけでいい」と語る
- Jeff が入力値によって時間が変わるのではないかと尋ねると、Palima は計算量は時間のような副作用を気にしないと答える
最適化と予想外の結果
- Jeff が最適化方法を尋ねると、Palima は遅延倍率を変えただけだった
100000 * time を 10000 * time に減らす- Palima はこれで 10倍速くなった と説明する
- Jeff はついに大笑いし、Palima はなぜそんな変なソートアルゴリズムを書いたのかという質問に、「なぜそんな変な質問をしたのか」と切り返す
- Palima は、Techaro は自分を収めるには十分に複雑ではなく、Kubernetes の代わりに Typhoon Digital の単一専用サーバーでも十分だっただろうと判断する
- 面接を終えた後は、不採用メールがすぐ来るだろうと予想する
- だが Techaro はかなりの金額で採用したいというメールを送り、Palima は彼らが何を引き受けようとしているのか分かっているのだろうかと思う
- Palima は夕方までには仕事も勝手にソートされるだろうと言い、再び眠ることにする
1件のコメント
Hacker Newsの意見
定数時間でも多項式時間でもなく、擬多項式時間なんだよね。負の値では失敗しそうだし、入力を表現するビット数に対して線形にするなら
10000 * log(time + min(time) + 1)みたいな式が必要になる計算量理論では、数値アルゴリズムが擬多項式時間で動くというのは、実行時間が入力の数値そのもの、つまり入力に現れる最大の整数に対する多項式だという意味であって、入力長（その数を表すのに必要なビット数）に対する多項式という意味ではない
https://en.m.wikipedia.org/wiki/Pseudo-polynomial_time
計算量は計算モデル内のステップ数を扱うのであって、時計の時間がどれだけ経過したかを扱うわけではない。sleep sort は OS スケジューラの性質を利用していて、仮想時間環境では時間は次の予約イベントまで即座に進む。そういうものを計算モデルとして仮定すれば、実際には多項式計算量で動く
それと、人に教えるなら最低限 pseudo-polynomial の綴りくらいは正しく書いたほうがいい
1を並べて0で区切った単一入力を受け取る箱を作れるそれを整数に戻すのは線形時間だし、元の箱を呼び出して結果を返せば、今度は自分の入力長に対して多項式時間になる。整数と言ったけど本質はエンコーディング方式なので、小数点に
0を1つ、入力の区切りに00を使う、みたいなこともできるとにかくジョークの肝は、寝ている時間は数えないという点にあるんじゃないか？ コンピュータはその間ほかの仕事ができるわけだし。「バカっぽいけど好きだ」という感じで、かなり説得力がある
sleep sort は /prog/ [0] で始まった。当時 sleep sort スレに参加していた HN のロム専もかなりいたはずで、xena もその1人かもしれない :)
[0] https://www.cs.princeton.edu/courses/archive/fall13/cos226/l...
<=>演算子を発明した、という話だった。天才的元記事の作者が言っているように、この文章は aphyr の Interview シリーズ、たとえば “Rewriting the Technical Interview” のような話のスタイルにとても近い。どれも面白く読める
[0] - https://aphyr.com/posts/353-rewriting-the-technical-intervie...
https://joelgrus.com/2016/05/23/fizz-buzz-in-tensorflow/
さわり:
コンピュータでのソートは入力を読まなければならないので、最低でも線形時間が必要。入力について一様分布のような追加情報がなければなおさらそう
線形時間ソートには sleep sort、postman sort、counting sort などいろいろある。ただし、数字の集合やソート可能なキーが制限されている場合に限る
ただ、コンピュータの代わりにそろばんを使うなら、ほとんど本当に近い定数時間ソートがある: https://en.wikipedia.org/wiki/Bead_sort
かわいい話ではあるけれど、どんな意味でも定数時間ではない。
N個のスレッドを作って、ソート済みのウェイクアップリストに全部追加するには、OS や言語ランタイム次第で O(N log N) から O(N^2) かかる。どこかの裏側で、ソート済みリスト、ヒープ、または N^2 アルゴリズムが動いている。同様に、sleep sort 自体も、ソート済みの
N個の項目を出力するにはN個のスレッドを起こさなければならないので、少なくとも線形時間である。さらに悪いことに、実時間も値の大きさに応じて伸びる。最初に最小値と最大値を見つけて範囲を圧縮することはできるが、それも線形時間である。
ここでは「時間」という語の相反する二つの見方を使ったダジャレである。計算量解析の観点でソートアルゴリズムを定数時間にするのが不可能なのはその通り。
冗談の本当の意図は実時間のことだ。面接ではそちらの時間のほうが重要だし、現実には誰かが「整数のソート関数を書いてください」みたいな課題を出すとき、100 未満の数字しか使わないことはまれなので、このプログラムは体感的にはほぼ即座に実行される。
これは、コンピュータサイエンスがどう機能するかについての理解をひっくり返してからかう、微妙にメタ言語的な冗談だ。ウケなくて残念。
https://en.wikipedia.org/wiki/Ultimate_fate_of_the_universe#...
sleepに渡す引数は結局整数に帰着するはずなので、基数ソートのようなものを使って線形時間で処理することもできる。最大値の大きさへの依存が生じても得になる問題領域はある。
もちろん、実際にそんなシステムはない。システムコールのタイムアウトは普通、その方式が有利になる場所ではない。そして当然ながら、最大値に線形比例する方法より、
log(max_value)にしか比例しない基数ソートを直接適用するほうがよい。N個のスレッドを作ってソート済みのウェイクアップリストに追加するコストが O(N log N) から O(N^2) だというのは、スケジューリングシステムの根本的限界ではない。とりわけ、スレッド数に対して定数時間スケジューリングを可能にする特殊ハードウェアまで考えればなおさらだ。たとえば現実的に採算はまったく取れないが、距離ごとに巨大な鏡の集合へレーザーで情報パケットを跳ね返し、コンピュータに接続された検知器に戻すスケジューラを作ることはできる。
光速を使って指定した時間だけ遅延させる方式である。したがって sleep sort は、あるスレッドスケジューリング方式の隠れたアルゴリズム計算量に本質的に依存しているわけではなく、実用的ではないにせよ理論上は O(1) に最適化できる。
これが気に入ったなら、Protos という一種の続編もある: https://xeiaso.net/blog/protos
この「世界観」の話をもっと書いているが、風刺のエネルギーが満ちるまで少し時間がかかる。次回作は空間コンピューティングになるかもしれない。
それでも、その宇宙のほうが名前の付け方はうまそうだ。
threadDelay (100000 * time)をthreadDelay (10000 * time)に変えて「これで 10 倍速くなりました」と言う部分は、この記事に関係している: https://thedailywtf.com/articles/The-Speedup-Loop記事は読んでいないが、こういうのは嫌いだ。以前 Meta のリモート面接を受けたとき、相手がずっとマイクに向かって何か食べていた。
気が散りすぎて、for ループの書き方すら忘れた。
在職中なら休暇を取らなければならなかったし、「限られた有給をここで無駄にするのか？」「駐車できるかな？」「時間どおりに着けるかな？」といったストレスもあった。
そのうえ 30 分の「一次面接」を受け、数週間待ってから本格的な面接に呼ばれるか、あるいはそのまま連絡が途絶えることもあった。
全体のプロセスは 1 か月かかり、少なくとも 2 日分の休暇とかなりの移動が必要になることもあった。
今では採用担当者や人事が電話してきて、ビデオ通話が可能かどうかを尋ね、その日のうちに 15〜20 分話したあと、履歴書を意思決定者に回し、1 回以上のビデオ面接や技術セッションを設定する。会社によっては、自宅で気楽に適性試験や技術テストを受けてくれと言うところもある。
リモートワーカーなら昼休みに全部済ませることもできる。対面のコミュニケーション帯域のほうがずっと広いとはいえ、同じ日の朝に Tel Aviv の会社、昼に Warsaw の会社、夕方に California の会社を面接できるのはリモートだけだ。
1000 個のスレッドを作るのは、少なくとも線形時間ではないのか？ 対数までは減らせるかもしれないが、そのコードが自動的にそうしてくれるとは思えない。
sleep sort が定数時間になるには、入力に上限、つまり最大の数への制限が必要であり、入力の読み取りや処理、スレッド生成のような任意の作業を数えないことが必要になる。
しかし、そんなことを許すなら他のあらゆるソートも定数時間になる。どちらか一方だけでも十分そうだ。
スレッドランタイムが独自の時間概念を維持するなら、アルゴリズムは実時間でスリープする必要すらない
すべてのスレッドが作成されたあと、ランタイムは全スレッドがアイドル状態であり、次にスケジュールされるスレッドが時刻 N のスレッドだと気づけるので、現在時刻を N に更新してそのスレッドを実行すればよい。これを繰り返せば、
sleepを一切使わずにソート済み配列が得られる要するにソート処理は、スレッドがスリープを始めた時点ですでに終わっていて、その後で起こしてもらうための調停役、たとえばタイマーホイールなどに自分自身を登録した状態になっている。実際にスリープを実行する必要はない
Haskell は分からないが、Rust の tokio ランタイムでは
start_pausedでこれが可能になる: https://docs.rs/tokio/latest/tokio/runtime/struct.Builder.ht...いくつもの抽象化レイヤーと省略した実装詳細を脇に置けば、こうしたスケジューラで値をソートするのは単なるヒープソートだ :)