区間データから重複を削除するアルゴリズム

A cyberpunk city

「手が空いたら次は 8191 番のタスクをお願いします。」

プロダクトマネージャが暇そうにしているウィンストンにそう言った。

ウィンストンは MostlySec 社1の会議室にいる。 MostlySec 社はセキュリティ分野2において独占的立場にある企業だ。 監視カメラ、監視ドローン、その他あらゆるトラッキングデバイス、そしてそれらを一元的に管理するクラウドベースのソフトウェアを開発している。 主要顧客には行政機関も含まれ、市民の監視には主に MostlySec 社の製品が使われている。

定例会議が終わり自分のデスクに戻ると、ウィンストンは自分に割り当てられたタスクを確認するために社内のプロジェクト管理ツールにアクセスした。 クラウド・インフラストラクチャのソフトウェア・エンジニア3として採用されてから 2 年になる彼にとっては、慣れきった行動だ。 8191 番のタスクのタイトル欄にはこう書いてあった。

viewrec: 指定範囲・タグで未取得の記録のみを取得するよう変更せよ

いつものタスクと少し毛色が異なる、と彼は思った。 彼は主に MostlySec 社のオンライン製品がアクセスするクラウド上のインフラストラクチャを管理するソフトウェアを開発しているが、 稀に手が空くと、このような専門外のタスク4が回ってくることがあるのだった。

viewrec とは、MostlySec 社の監視デバイスが休まずクラウド上に保存している動画・音声記録にアクセスするための単純なフロントエンド・コマンドだ。 クラウド上のデータには、動画に映っている人物といったオブジェクトの識別子、音声に登場する単語などの情報がタグ付けされている。 このコマンドを使えば、指定時間内に録画され、指定キーワードがタグ付けされた動画・音声記録をクラウド上から取得して再生できる。 例えば、2077 年 7 月 7 日の 09:005 から 17:00 の間に「freedom」か「liberty」という単語が発声された記録をすべて再生するには、次のように実行すれば良い。

$ viewrec --from 207707070900 --to 207707071700 --tags freedom liberty

データを 207707070900-207707071700-freedom-liberty.zip という名前の一つの圧縮ファイルとしてユーザの端末に保存6したあと、 中身のファイル7をすべて再生するという極めて単純な仕組みだ。

彼はタスクの説明を読み、問題を理解した。

どうやら、viewrec は自らの実行履歴を保存しており、全く同じパラメータで呼び出された場合は既にユーザの端末に保存されているファイルを再生するが、少しでもパラメータが異なる場合は再取得が行われるらしい。 それが一部の顧客に不評なのだ。 非力なネットワーク環境からアクセスしたり、少しだけ異なる時間やタグで何度も実行していて、端末のディスク容量が圧迫されてしまうからだろうか? 本当のところは分からない8が、とにかく、取得済みのデータをいちいちダウンロードしないようにして欲しいらしかった。

少し考えたあと、彼はタスクをおおまかに次の 2 つに分解した。

A. コマンドの実行履歴から未取得の区間およびタグを計算するモジュールを実装する
B. 上記モジュールを使って欠けたデータを取得し、保存済みのものとつないで再生できるようにする

なにか恐ろしい間違いをしているという気分9を振り払って、A から取り掛かることにした。

実行履歴の各区間がばらばらに並んでいくらでも重複する可能性があり、タグが複数あるという点が厄介だ。 実行パラメータで指定された区間と実行履歴の区間は複雑に重なる可能性がある。例えば、図1のケースを考えてみよう。

Overlapped interval data

図1. 時系列的に重なるコマンド実行履歴と対象範囲・タグ

ダウンロードするデータサイズをとにかく小さくしたいので、真面目に未取得部分を計算すると、図2のように細切れの区間・タグ列になる。

Unfetched interval data

図2. 未取得範囲とタグ

すぐに考えが及ぶ方針として、履歴の各区間データについて、指定区間との差分を逐一求める、というものがある。 ただ、先の例から明らかな通り、差分をとると細切れになる区間が発生し、さらに別の履歴との差分によって新たな細切れ区間が発生する可能性がある。 彼の頭には、その動作をすべての場合において正確に捉えられる知的容量はなかった10

彼は逃げるように席を立ち、コーヒーを買うために社内の自動販売機に向かった11。 自動販売機の近くに寄ると、それが恭しく挨拶をしてきた。

「おはようございます、ウィンストン、様。本日は何をお飲みになりますか?」

ウィンストンが「いつもの」とぶっきらぼうに答えると、シュガーフリー12のコーヒーが入ったアルミニウム缶がただちに排出された。

席を立ったついでに外を歩くことにした。外といっても、彼の職種では就業時間内の外出が原則禁じられているため、外を見渡せる密閉されていない連絡通路やテラスのことを指す。 外に出ると、あらゆる音が彼の耳に入ってきた。人々の声、自動車やドローンの動作音、クラクションの音、広告の音、高かったり低かったりするよく分からない人工的な音。 どこを見ようと視界を遮る建築物は、既に地面が見えないほど高いところにあるにもかかわらず、空が見えないほど高く続いていた。 コーヒーをちびちびとすすり、朝でもまばゆいネオンサインを眺めながら歩いていると、彼の頭に少しずつ活力が戻ってきた。

「細切れ…細切れ…」と唱え始めてから 11 分ほど経つと、問題解決のアイディアが浮かんだ。

「区間を最初から細切れにすればいいんだ!」

彼のアイディアは概ね次のようなものである(図3参照)。

1. 指定区間および履歴の区間を、始点と終点という 2 つの時点に分解してごちゃまぜにし、時系列順にソートする。このとき、指定区間の始点・終点にはそれと分かるようマーキングしておく
2. 時系列順に時点をみていき、各時点において履歴にあるタグ列を計算していく。このとき、同じ時点のものはまとめて扱う。
3. 指定区間の始点をみかけてから、時点ごとに指定区間と履歴にあるタグ列の差分をとり、それが空でないかつ前と変化している場合には区間データを生成する
4. 指定区間の終点をみかけたら、同様に区間データを生成する。それを含む今まで生成した区間データ列が、求める未取得区間データ列となる
Solved

図3. 区間を始点と終点にバラして並べると、重複区間の取り扱いが簡単になる

意気揚々と自分のデスクに戻ると、彼は早速モジュールのインターフェースを書き始めた。 用いるプログラミング言語は Rust13 と呼ばれるもので、67 年前から存在する(名前通り)錆びた言語である。 インターフェースを決めたあと、テストケースを書いていく。 こうすることで、コードの修正とテストを、テストが全て通るまで繰り返すという健全な開発サイクルが生まれる。 彼は、今回のようにテストケースを書きやすい問題に取り組むとき、その明快さに密かに喜びを感じるのだった14

彼が次のコード15に到達したとき、彼のターミナルには全てのテストが通ったことを伝える緑の文字列が踊った。

use std::collections::{HashMap, HashSet};
use std::fmt::Debug;
use std::iter::FromIterator;
use std::marker::Sized;

pub trait BoundOps: Copy + Debug + Eq + Ord
where
    Self: Sized,
{
}
impl<T> BoundOps for T where T: Copy + Debug + Eq + Ord {}

// タグ付き区間を表す構造体
#[derive(Clone, Debug, PartialEq)]
pub struct TaggedInterval<Bound>
where
    Bound: BoundOps,
{
    lower: Bound, // 区間の始点
    upper: Bound, // 区間の終点
    tags: HashSet<String>, // タグ
}

#[derive(Clone, Copy, Debug, PartialEq)]
enum BoundKind {
    Specified, // コマンドラインで指定されたもの
    History, // 履歴に存在するもの
}

#[derive(Clone, Copy, Debug, PartialEq)]
enum BoundDirection {
    Lower, // 始点
    Upper, // 終点
}

// タグ付き区間を始点・終点にバラした構造体
#[derive(Clone, Debug, PartialEq)]
struct TaggedBound<Bound>
where
    Bound: BoundOps,
{
    kind: BoundKind,
    direction: BoundDirection,
    bound: Bound,
    tags: HashSet<String>,
}

impl<Bound> TaggedBound<Bound>
where
    Bound: BoundOps,
{
    fn from_interval(interval: &TaggedInterval<Bound>, kind: BoundKind) -> (Self, Self) {
        (
            Self {
                kind,
                direction: BoundDirection::Lower,
                bound: interval.lower,
                tags: interval.tags.clone(),
            },
            Self {
                kind,
                direction: BoundDirection::Upper,
                bound: interval.upper,
                tags: interval.tags.clone(),
            },
        )
    }

    fn from_history(intervals: &Vec<TaggedInterval<Bound>>) -> Vec<Self> {
        let mut bounds = vec![];
        for iv in intervals {
            let (lower, upper) = Self::from_interval(iv, BoundKind::History);
            bounds.push(lower);
            bounds.push(upper);
        }
        bounds
    }

    fn from_specified(interval: &TaggedInterval<Bound>) -> Vec<Self> {
        let mut bounds = vec![];
        let (lower, upper) = Self::from_interval(interval, BoundKind::Specified);
        bounds.push(lower);
        bounds.push(upper);
        bounds
    }

    pub fn from_intervals(
        specified: &TaggedInterval<Bound>,
        history: &Vec<TaggedInterval<Bound>>,
    ) -> Vec<Self> {
        vec![Self::from_specified(specified), Self::from_history(history)].concat()
    }

    pub fn sort(bounds: &mut Vec<Self>) -> &mut Vec<Self> {
        bounds.sort_by(|x, y| x.bound.partial_cmp(&y.bound).unwrap());
        bounds
    }
}

// 重複した要素を持ち得る ベクタ v1 と v2 の差分を求める。
// 例) ["freedom", "freedom"] - ["freedom"] = ["freedom"]
fn difference_with_dups(v1: &Vec<String>, v2: &Vec<String>) -> Vec<String> {
    let mut result = v1.clone();
    let mut counts: HashMap<String, i128> = HashMap::new();
    v2.iter().for_each(|s| {
        counts.entry(s.clone()).and_modify(|n| *n += 1).or_insert(1);
    });
    result.retain(|s| {
        *counts
            .entry(s.clone())
            .and_modify(|n| *n -= 1)
            .or_insert(-1)
            < 0
    });
    result
}

impl<Bound> TaggedInterval<Bound>
where
    Bound: BoundOps,
{
    pub fn new(lower: Bound, upper: Bound, tags: HashSet<String>) -> Self {
        Self { lower, upper, tags }
    }

    // 未取得範囲・タグを求めるアルゴリズム
    pub fn difference(self, history: Vec<Self>) -> Vec<Self> {
        let mut bounds = TaggedBound::from_intervals(&self, &history);
        TaggedBound::sort(&mut bounds);

        let mut result = vec![];
        let mut in_specified_range = false;
        let mut current_tags = vec![];
        let mut current_bound = self.lower;
        let num_bounds = bounds.len();
        let mut i = 0;

        while i < num_bounds {
            let mut specified_lower_found = false;
            let mut specified_range_will_be_over = false;
            let mut lower_tags = vec![];
            let mut upper_tags = vec![];
            let mut j = i;

            while j < num_bounds && bounds[j].bound.eq(&bounds[i].bound) {
                match bounds[j].kind {
                    BoundKind::History => match bounds[j].direction {
                        BoundDirection::Lower => {
                            bounds[j]
                                .tags
                                .iter()
                                .for_each(|t| lower_tags.push(t.clone()));
                        }
                        BoundDirection::Upper => {
                            bounds[j]
                                .tags
                                .iter()
                                .for_each(|t| upper_tags.push(t.clone()));
                        }
                    },
                    BoundKind::Specified => match bounds[j].direction {
                        BoundDirection::Lower => {
                            specified_lower_found = true;
                        }
                        BoundDirection::Upper => {
                            specified_range_will_be_over = true;
                        }
                    },
                }
                j += 1;
            }

            let mut next_tags = difference_with_dups(&current_tags, &upper_tags);
            next_tags.append(&mut lower_tags);

            let continuous = in_specified_range
                && HashSet::<String>::from_iter(next_tags.iter().cloned())
                    .eq(&HashSet::from_iter(current_tags.iter().cloned()));

            if in_specified_range && (!continuous || specified_range_will_be_over) {
                let current_tag_set = current_tags.iter().cloned().collect();
                let tags: HashSet<String> =
                    self.tags.difference(&current_tag_set).cloned().collect();
                if !tags.is_empty() {
                    let tagged_bound = TaggedInterval::new(current_bound, bounds[i].bound, tags);
                    result.push(tagged_bound);
                }
            }

            if specified_range_will_be_over {
                break;
            }
            if specified_lower_found {
                in_specified_range = true;
            }
            if !continuous {
                current_bound = bounds[i].bound;
            }

            i = j;
            current_tags = next_tags;
        }

        result
    }
}

モジュールの実装を完了したあと、それを使ったデータの取得・結合(タスクB)まで、一気に書き上げることができた。 まだ終業時刻まで時間があったが、一刻も早く成果を伝えたかったので、セルフレビューをさっさと終わらせ、プルリクエスト16を出した。

プルリクエストの通知を受け取った同僚のオブライエンは、向かい側のデスクからひょこっと顔を出し、声を抑えて皮肉を言った。

「これで善良でない市民の摘発がまた少し捗るわけだ。良い仕事したね!」

直接話せる距離にいながら、我々は普段テキストチャットでやりとりをする。 しかし、この種のことを言うときには、オブライエンは決まって声を出してウィンストンに伝えるのだった。 賢いつもりだろうが、我々の話し声もほぼ間違いなく監視されているだろう。

そのうちオブライエンは蒸発するかもしれないな、と思いながら、言われたことが少し頭にひっかかっていた。 MostlySec 社の社員である自分は中々良い暮らしをしているが、文字通り下層に住む市民たちとの格差が大きく、かつ年々さらに大きくなっていること、そして MostlySec 社の製品が圧政の維持に大きく貢献していることも理解していた。

MostlySec 社への自分の貢献が、自分にとっても実際に大きな利益をもたらしていることに、一瞬ぞっとした。 罪悪感が芽生える前に彼は思考を止め、いつもの心地よい結論を棚から出した。 現実的に考える力を持っていれば、誰もヒーロー役をやりたいわけがない。下層市民が安全で豊かな生活を求めるように、自分もそうしているだけなのだ。

エピローグ

その日の仕事を終えて自宅に戻ると、彼はウェブ検索サービスを使って、今日のタスクのアルゴリズムのことを調べてみた。

「区間データから重複を削除するアルゴリズム」

こんな検索キーワードでは、ろくな結果は出なかった。代わりに、次のキーワードで検索した。

「アルゴリズム 区間 差分」

すると、技術系 Q&A サービスの回答17がヒットした。質問は、区間セット A と B の差分 A - B を求めるというものだった。 回答者は次のように述べる。

プログラミングを学び始めた頃に簡単な計算機プログラムを書いたことを思い出してください。
区間を入れ子可能な括弧のパージングだと思えば、簡単に差分を求めることができます。

その質問はウィンストンのタスクとは異なる上に、実は回答に誤り18があったが、区間を始点と終点に分割するという基本的なアイディアは同じだった。 普段極めて単純なアルゴリズムしか扱わないウィンストンでも、そのアイディアを人類史上初めて発明したと思っていたわけでは決してない。 それにもかかわらず、大切な宝物を奪われたような気分になった。

そして、自分が提出したコードにパフォーマンス上の問題が生じる可能性がある19ことに気がついた。 恐らくレビューでその点を指摘されるのだろう。帰宅するまで少しばかり高揚していた気分はすっかり失われ、床に就いた。


  1. この物語はフィクションであり、実在の人物・団体とは一切関係ない。

  2. サイバーセキュリティの製品も扱っているが、フィジカルセキュリティが主。

  3. サーバやネットワークを物理的に構成・管理するのではなく、それらのリソース上でサービスを円滑に動かすための仕組みを作るポジション。

  4. 専門外といっても、一般的なソフトウェア・エンジニアが持ち合わせていない専門知識を要する特殊なタスクではない。

  5. タイムゾーンは全て UTC+0 である。

  6. 何らかの事情により、ストリーミングの仕組みはない。

  7. ほとんどの場合、中身のファイルは監視デバイスごとに分かれている。

  8. もっと顧客へのヒアリングを行い、問題の本質を明らかにしてから解決方法を考えたいところだが、人間は常に最善の行動をするわけではない。

  9. 素面のソフトウェア・エンジニアの多くは、ある程度以上の知的作業を要するタスクに取り組むとき、しばしばこの恐ろしい感覚を味わう。

  10. 基本的に、自分の頭でその動作原理を捉えきれないようなアルゴリズムを正しくコーディングすることはできない。

  11. 一筋縄ではいかない問題に直面したときの彼の習慣となっている。

  12. 果糖中毒 19億人が太り過ぎの世界はどのように生まれたのか?』という昔の本を読んで以来、彼は砂糖入りの飲料水を飲むのが恐ろしくなった。

  13. https://www.rust-lang.org/ を見よ。

  14. ソフトウェア・エンジニアがそのような問題に取り組むことは意外と少ない。彼のような職種であれば尚更だ。

  15. 彼は関数型プログラミングが嫌いなわけではない。ぎこちないコードになっているのは、Rust で書き慣れていないためだ。テストを含むコード全文は https://github.com/builtinnya/tagged-interval を見よ。

  16. 書いたパッチをソフトウェアに取り込んでもらうために行う申請のこと。パッチが他者によってレビューされ、問題なければソフトウェアに取り込まれる。

  17. https://stackoverflow.com/a/11892761 を見よ。

  18. https://stackoverflow.com/questions/11891109/algorithm-to-produce-a-difference-of-two-collections-of-intervals#comment55146875_11892761 を見よ。

  19. 例えば、指定区間と少しも重ならない履歴区間についてタグ列を求める必要はない。