ゲーム百科 · 履歴の読み方

同時刻のイベントをどう並べる?|連番と入力順のタイブレーク

時刻が同じ履歴を、時刻・seq・元の入力位置で並べる例を解説。文字列順との違い、安定ソート、複数時計、因果関係と表示順を整理します。

約8分で読めますゲームの仕組み
情報処理設備を収容するデータセンターの建物
情報処理設備を収容するデータセンターの建物 · Kecko from Eastern Switzerland / CC BY 2.0 · 写真クレジット

イベントの時刻が同じでも、同じ出来事とは限りません。ミリ秒までの表示へ丸められた二つの記録や、別々の処理が同じ時刻に出した記録は、一覧で同じ数字になる場合があります。時刻だけで並べたときに順番が定まらないなら、同点を分ける規則を用意します。

タイブレークは、第一の比較が同じだった場合に使う次の比較です。ここでは数値の時刻time、整数の連番seq、元の入力位置の順に比べます。時刻が違えばseqは使わず、時刻もseqも同じなら入力順を保つという、優先順位を持った規則です。

一覧を再現しやすく並べることと、実際の因果関係を証明することは別です。異なる時計の記録には時刻のずれがあり、連番にも有効な範囲があります。小さな架空の記録で比較の手順を追い、並びからどこまで分かるかを整理します。

識別子、時刻、連番を別の情報として読む

例の記録にはid、time、seqを持たせます。idは記録の名前、timeは第一の並べ替えに使う数値、seqは同時刻の比較に使う整数です。役割を入れ替えないようにします。

項目この例での役割それだけでは分からないこと
id表示する記録名発生順や同一性
time第一の数値比較別時計の正確な因果順
seq同時刻で使う比較全システム共通の順序かどうか
入力位置最後の同点処理実際の発生時刻

idは順序とは限らない

AやBという識別子があっても、Aが先に起きたという意味は自動では付きません。名前がアルファベット順でも、発生や受付の順序とは別の場合があります。この例ではidを表示用の名前として使い、並べ替えのキーにはしません。

同じidを持つ二つの入力も、そのまま残します。並べ替える操作と、重複を判定して削除する操作は違うためです。名前が同じことだけで同じ出来事と決めず、入力した件数を保って順序だけを変えます。

timeの単位をそろえる

timeは架空のミリ秒の数値として扱います。1,000と999なら999が先です。別の単位や異なる基準の時刻を混ぜると、数値の大小が実際の時間の先後へ対応しなくなります。比較の前に単位と基準をそろえます。

秒で書いた1とミリ秒で書いた999を直接比較すると、1の方が小さいという数値の結果になります。しかし時間の長さでは1秒は1,000msです。ソートの式より前に、値が同じ尺度にあるかを確認する必要があります。

seqの範囲を確認する

連番seqがどの範囲で増えるかは、記録の仕様によります。一つの処理内で増える番号と、全システムで共有する番号は同じではありません。異なる処理のseqをそのまま比較して、全体の発生順と呼ばないようにします。

この操作例では入力したseqの小さい順という規則を明示して使います。連番が実際に何を表すかを自動判定しません。この例の比較規則を、実際の履歴へ適用する場合は、その連番の意味と範囲を別に確認します。

同時刻の記録を決めた順番に並べる
架空の数値時刻を使います。同じIDでも削除せず、並べ替えだけを行います。 図は横にスクロールできます。
サーバーラックに接続された複数の通信ケーブル
サーバーラックに接続された複数の通信ケーブル · VGrigas (WMF) / CC BY-SA 3.0 · 写真クレジット

第一のキーが違うなら、次のキーへ進まない

複数のキーは、足し合わせるのではなく順に比較します。時刻が同じ場合にだけseqを使い、両方同じなら元の入力位置へ進みます。

999は1,000より先

記録Cがtime999、seq5で、記録Aがtime1,000、seq1なら、Cが先になります。seqが5で大きくても、第一の時刻が小さいためです。各列を別々に小さい順へするという操作ではありません。

timeとseqを足して一つの値にすると、別の規則になります。例えば999+5と1,000+1の大小は、時刻優先の比較と一致しません。キーごとの優先順位を保つことが、意図した一覧を作るために必要です。

同時刻ならseqを比較する

AとBがどちらもtime1,000で、Aのseq1、Bのseq2なら、Aを先へ置きます。時刻という第一の比較で差が出なかったため、第二の比較へ進みます。どの段階で順序が決まったかを分けると、結果を説明できます。

同点を破る規則は、数値の昇順以外にも考えられますが、ここでは小さいseqを先にします。規則の選択を明示しておけば、同じ入力から同じ並びを再現できます。暗黙の見た目の順序へ任せないことが大切です。

時刻もseqも同じなら入力位置

AとDがtime1,000、seq1で一致する場合、元の入力位置が前の方を残します。Aが二番目、Dが四番目ならAが先です。新しい時刻情報を発見したのではなく、同点の扱いを決めた結果です。

入力位置まで使うと、この入力に対して順番が一意に決まります。入力を別の順にしたら、完全な同点同士の順は変わり得ます。再現性の範囲は、比較規則だけでなく元の入力列も同じという条件です。

時刻・seq・入力順でイベントを並べる

架空のJSON配列を入力し、数値time、整数seq、元の入力位置の順で並べます。同じIDの記録も削除しません。

入力値を確かめる準備ができました。

架空の数値時刻を使います。同じIDでも削除せず、並べ替えだけを行います。

四件の記録を、比較した理由ごとに並べる

入力をB、A、C、Dの順とし、Cだけ時刻999、残りは1,000とします。AとDのseqを1、Bを2へすると、結果はC、A、D、Bです。

元の位置idtimeseq出力の位置
1B1,00024
2A1,00012
3C99951
4D1,00013

まずCが先頭になる

Cは入力では三番目ですが、時刻が999なので先頭へ移ります。ほかの三件の時刻は1,000です。入力の位置を最初の比較に使うのではなく、時刻が違う部分を先に処理します。

時刻が1違うことへ、実際の処理の差がどれほどあるかを付け足さないようにします。この例の単位は架空のミリ秒です。最初は数値として比較した結果を確認し、実際の履歴の意味はそのデータ仕様へ戻します。

AとDがBより前になる

時刻1,000の三件の中では、seq1のAとDが、seq2のBより前です。Bが元の入力で最初だったことは、第二のキーの比較を上書きしません。入力位置は最後の同点だけに使う規則です。

AとDは二つのキーが同じなので、元の入力でAが前だった関係を保ちます。最終的にC、A、D、Bとなります。結果だけでなく、各隣接の順序がどのキーで決まったかを追うと、規則の確認になります。

並べ替え前後で件数を保つ

入力は四件、出力も四件です。並べた後にAとDが同じtimeとseqでも、片方を消しません。時刻と連番の一致は、この操作では同点という意味であり、重複削除の条件ではありません。

同じidの記録を二つ入れた場合も、入力位置を持つ二件として残ります。重複らしく見えることと、実際に同じ記録の再送かどうかは別です。ここでは順序の確認へ対象を絞り、件数を変える判断を加えません。

複数のLANポートを備えた小型スイッチ
複数のLANポートを備えた小型スイッチ · Simon A. Eugster / CC BY-SA 3.0 · 写真クレジット

数値の比較と文字列の比較を混ぜない

文字列としての並びでは、"10"が"2"より前になる場合があります。時刻や連番を数値として比較したいなら、型と比較方法を確認します。

辞書式なら先頭の文字を比べる

文字列"10"と"2"を文字の順で比べると、先頭の1が2より前なので"10"が先になる例があります。数値10と2なら、2が小さい値です。同じ数字の見た目でも、比較の規則によって結果が変わります。

番号が固定幅の文字列なら別の設計もありますが、ここでは数値timeと整数seqを使います。どの型であるかを入力の段階で保つと、意図せず文字列順へなる問題を避けられます。見た目だけで比較しません。

欠損を0へ置き換えない

timeがない記録へ自動で0を入れると、最初の時刻として先頭に来る場合があります。欠損と実際の0は別の状態です。比較に必要な値がないなら、その扱いを明示する必要があります。

この操作例はtimeとseqを持つ架空の記録を入力する前提です。不完全な記録から欠けた値を推測しません。数値への変換ができたことだけで妥当とせず、必要な項目と整数の条件も確認します。

比較は同じ優先順位で行う

一部の二件では時刻優先、別の二件ではseq優先というように規則を変えると、全体の順序が矛盾する場合があります。すべての比較で同じキーの順を使う必要があります。例外を足す場合も規則として明示します。

比較結果が一貫していることは、同じ一覧を再現するための土台です。見た目で一部を手動移動した結果を、元の規則による並びとして残さないようにします。修正が必要なら、なぜその順にするかの情報を別に持たせます。

安定ソートは、同点の元の順を保つ

安定な並べ替えは、比較が同じとなる項目の元の順を保ちます。何を同点とするかは比較規則によるため、時刻だけを比べる場合とseqも使う場合で範囲が違います。

時刻だけなら同時刻の三件を保つ

時刻だけで安定に並べると、入力B、A、C、Dの例はC、B、A、Dです。時刻1,000のB、A、Dの元の順が保たれます。seqも比較するC、A、D、Bとは異なる結果です。

安定だからすべての意味で正しい順になる、という保証ではありません。元の入力順を保つという性質です。seqを反映したいなら比較キーへ含めます。安定性の名前だけで、必要な第二のキーが自動的に使われるわけではありません。

最後の入力位置を明示する利点

この例は最後に元の入力位置を比べるので、完全な同点の扱いが明確です。処理の名前を知らない人でも、同じtimeとseqのAとDは入力順、と読めます。実装の内部事情より、データの規則として説明できます。

入力位置は並べ替え前に付けます。並べ替えた後で付けた番号を元の入力順として使うと、比較の基準が循環します。元の列を保持し、出力位置とは別の項目へすることが必要です。

別の入力列との比較

同じ四件をA、D、C、Bの順へ入れ替えても、この例ではAがDより前です。しかしD、A、C、Bなら完全な同点の二件はD、Aになります。入力位置を最後に使う規則の結果であり、誤作動ではありません。

全入力の並びにかかわらず同じ最終順が必要なら、別の一意な比較キーを設計する問題になります。ここでは入力順を保つという契約です。目的に合う規則を選び、その保証の範囲を正確に述べます。

建物内の配線をまとめるネットワーク機器
建物内の配線をまとめるネットワーク機器 · JBequio / CC BY 4.0 · 写真クレジット

時刻順は、原因と結果の完全な証明ではない

異なる機器の時計にはずれがあり、記録する地点も異なる場合があります。数値の時刻を並べた結果と、実際にどの処理がどれを引き起こしたかを分けます。

発生時刻と記録時刻

ある出来事が発生してからログへ書かれるまでに時間があれば、ログの時刻が何を示すかが重要です。発生した瞬間、受信した瞬間、保存した瞬間では、同じ一件でも値が違う場合があります。列名だけで決め付けません。

時刻を比較する前に、各記録が同じ地点の意味を持つかを確認します。片方が発生時刻で片方が保存時刻なら、単純な大小が処理の前後へ対応するとは限りません。データの意味をそろえることが必要です。

時計の差が順序を入れ替える場合

二つの機器の時計が同じ基準へ十分にそろっていなければ、先に起きた出来事が大きい時刻を持つ場合があります。数値で昇順に並べても、この差を自動で補正するわけではありません。ソートは入力の値に従います。

同時刻の記録にseqを使っても、異なる時計間のずれを修理したことにはなりません。seqの有効範囲も関係します。表示順を安定させる仕組みと、複数機器の因果関係を扱う仕組みは、目的が異なります。

同時刻から同時発生を断定しない

ミリ秒へ丸めた二つの時刻が同じでも、実際の瞬間まで一致するとは限りません。より細かな時刻なら前後がある場合があります。表示の精度と、出来事の同時性を混同しないことが大切です。

同じ値を持つために必要なタイブレークは、失われた細かな時刻を復元する操作ではありません。決めた順に表示するための規則です。結果の順序へ、元データが持たない精密さを付け足さないようにします。

架空のJSON配列で、比較の段階を確認する

操作例にはid、time、seqを持つ記録の配列を入力します。時刻、seq、元の入力位置の順で並べ、各記録の値と元位置を表示します。

一つだけ値を変えてみる

Bのtimeを1,000から998へ変えると、seq2のままでもCより前へ移ります。第一の時刻が優先されるためです。次にtimeを戻してseqだけを変えると、同時刻のグループの中で順が変わります。

複数の値を一度に変えると、どの比較で動いたかが分かりにくくなります。一つずつ変え、出力の順序の理由を言葉へ戻します。単に望む並びが出るまで数字を調整するより、比較規則を確認できます。

同点の二件を入れ替える

AとDのtimeとseqを同じにして、入力位置だけを入れ替えると、出力でも二件の順が入れ替わります。最後のタイブレークを確かめる操作です。同じidを付けても、片方が消えるわけではありません。

出力に元の入力位置が出るので、並べ替え後の番号と照合できます。入力位置は一から数えた表示として読み、seqとは別です。三つのキーを混同せず、どれが最終的に順序を決めたかを確認します。

実際の履歴の変更とは分ける

この例は入力した架空の記録を並べるだけで、実際の取引状態や保存済み履歴を書き換えません。欠けた時刻の推定、因果関係の判定、同じ記録の削除も行いません。計算した範囲を保って結果を読みます。

履歴の一覧を理解する際は、表示順の規則と各項目の意味を一緒に見ます。同じ時刻の二件があっても、落ち着いて次のキーを確認できます。順番が決まったことと、実際の発生順が証明されたことを区別するのが基本です。

ケーブルが接続されたネットワークスイッチ群
ケーブルが接続されたネットワークスイッチ群 · ShakataGaNai / CC BY-SA 3.0 · 写真クレジット

よくある質問

時刻が同じなら同じイベントですか。

限りません。時刻の表示精度が粗い場合や別の処理が同じ時刻を持つ場合があります。この例では同点として次のseqを比較します。同じtimeやidだけを理由に、片方を削除する操作は行いません。

時刻とseqは足して比較しますか。

足しません。時刻が違えば時刻だけで決め、同じ場合にseqを比較します。両方同じなら元の入力位置です。キーの優先順位を保つ規則であり、合計値の大小とは別の並べ方です。

安定ソートならseqも反映されますか。

安定性は、比較上の同点の元の順を保つ性質です。seqを比較に含めなければ自動では使われません。時刻だけの安定ソートと、時刻・seqの順で比較する結果は違う場合があります。

"10"と"2"の順序がおかしいのはなぜですか。

文字列の規則では先頭の文字を比べ、"10"が"2"より前になる場合があります。数値なら2が先です。時刻や連番をどういう型で持ち、どの比較を使ったかを確認します。

完全に同点なら何を使いますか。

この例では元の入力位置を使います。同じtimeとseqを持つ二件は入力の前後を保ちます。新しい時間情報を得たわけではなく、表示の同点処理を決めたものです。入力列も再現性の条件になります。

小さいseqは必ず実際の発生が先ですか。

連番の仕様と有効範囲によります。一つの処理内の番号を、全システムの発生順と無条件に見なせません。この例は小さいseqを先にする規則を使いますが、実際の意味を自動で判定しません。

時刻順なら因果関係も分かりますか。

異なる時計のずれや、発生と記録の地点の違いがあるため、数値の並びだけでは完全な因果関係を証明できません。ソートは入力値に従う操作です。時刻の意味と時計の条件を別に確認します。

同じIDを二つ入れると削除されますか。

削除しません。入力の件数を保ち、時刻、seq、元の入力位置で並べるだけです。重複の判定や実際の履歴の更新は行いません。表示順を決めることと、記録の同一性を判断することを分けています。