読者です 読者をやめる 読者になる 読者になる

テストステ論

高テス協会会長が, テストステロンに関する情報をお届けします.

(rust report) tsortの実装を終了した

正味6Hくらいがんばって, テストを全パスするところまで持っていった. 私の貴重な週末がまたも失われた. 鬱すぎる.

性能を測ったので報告する. 平均で2倍くらい. 最悪ケースで5倍くらい悪い. 性能に関しては, もう少しテストをちゃんと作って, スケーラビリティがどうかという観点からみっちり比較しようと思う. たぶんだが, データが大きくなると急激に悪くなる. 理由をはっきりさせて, おれのせいなのかRustのせいなのか切り分けられたらと思う.

アルゴリズムは, Kahnのアルゴリズムというものを採用した. オーダーはO(|V|+|E|)

Rustはまだ制限の多い言語で, 私は直感的には, borrowに関するこの仕様はもう改善しようがないのではないかと思う(https://github.com/rust-lang/rust/issues/6393). そして, 私はこれが解決されないことにはRustはもう使わない.

  • (問題) 今はオブジェクトを獲得しました!というと, なんとブロックの中では掴み続けていることになる.
  • コードのロジックとしてもっと緻密に所有権を計算してプログラムの意に反しないようにすべきだ.
  • (graydon) これはバグと言ってもよいでしょう. 直そう
  • そして1年が経過...

みたいな話なので, 本質的に超難しいのではないか?解決不可能なレベルなのではないか?と思った. 終わってる. やはりこれからはGoだ. おれもGoを書こう.

この件で嵌って, データ構造を再設計して迂回する決定をしたり, 嵌りが多かった...


python-graphのランダムグラフジェネレータは, DAGを吐いてくれるわけではない. 性能を比較する意味では, 参考実装もMy実装も最後まで走り切る必要がある「ループのないケース」を使うのが良いから, DAGを生成するスクリプトを書いた. 以下のテスト結果における20000番台のものがそう(全部acyclic:trueとなってる). python-graph-coreの方には, DAG生成も提供しようぜということで提案して実装しておく.

スクリプトはこちら

import pygraph.algorithms.generators as Gen
import random

n = random.randint(10, 1000)
# e = n * (n-1) / 2 # number of edges
perms = list(range(0, n))
random.shuffle(perms)

edges = []
for i in range(0, n):
    for j in range(0, n):
        if i < j:
            edges.append((perms[i], perms[j]))

for x in edges:
    print "%d %d" % x

結果が合ってるかどうかの判定は雑. コマンドの返り値のみで判断している. 理由は, トポロジカルソーティングの結果はアルゴリズムによって一意とならないから. 結果を食って比較可能な一意な形に並び替えれば出来るけど, 簡単かどうかは分からない. Rubyのライブラリを使ってサクっと出来ないか少し調べるといいかも.

TEST0 result: OK, acyclic:false, time: t_new/t_ref=0.008210925/0.007810055
TEST1 result: OK, acyclic:false, time: t_new/t_ref=0.008487563/0.007252799
TEST10000 result: OK, acyclic:false, time: t_new/t_ref=0.008880578/0.007603313
TEST10001 result: OK, acyclic:false, time: t_new/t_ref=0.00935775/0.007227509
TEST10002 result: OK, acyclic:false, time: t_new/t_ref=0.011270499/0.00827578
TEST10003 result: OK, acyclic:false, time: t_new/t_ref=0.011002575/0.007269814
TEST10004 result: OK, acyclic:false, time: t_new/t_ref=0.009655182/0.007578746
TEST10005 result: OK, acyclic:false, time: t_new/t_ref=0.010526723/0.007509845
TEST10006 result: OK, acyclic:false, time: t_new/t_ref=0.010195026/0.007296646
TEST10007 result: OK, acyclic:false, time: t_new/t_ref=0.010189133/0.007073823
TEST10008 result: OK, acyclic:false, time: t_new/t_ref=0.010312123/0.007125364
TEST10009 result: OK, acyclic:false, time: t_new/t_ref=0.008918402/0.008080451
TEST2 result: OK, acyclic:true, time: t_new/t_ref=0.008940291/0.007120095
TEST20000 result: OK, acyclic:true, time: t_new/t_ref=0.008308604/0.007096346
TEST20001 result: OK, acyclic:true, time: t_new/t_ref=0.150148518/0.036990945
TEST20002 result: OK, acyclic:true, time: t_new/t_ref=0.276865307/0.063075643
TEST20003 result: OK, acyclic:true, time: t_new/t_ref=0.265780676/0.060969307
TEST20004 result: OK, acyclic:true, time: t_new/t_ref=0.053721754/0.016955997
TEST20005 result: OK, acyclic:true, time: t_new/t_ref=0.187657405/0.045124323
TEST20006 result: OK, acyclic:true, time: t_new/t_ref=0.0092122/0.007026648
TEST20007 result: OK, acyclic:true, time: t_new/t_ref=0.054046591/0.018080622
TEST20008 result: OK, acyclic:true, time: t_new/t_ref=0.01368067/0.00799225
TEST20009 result: OK, acyclic:true, time: t_new/t_ref=0.010110605/0.007186047
TEST3 result: OK, acyclic:false, time: t_new/t_ref=0.008197229/0.006892043
TEST4 result: OK, acyclic:true, time: t_new/t_ref=0.008175456/0.008035394
TEST5 result: OK, acyclic:false, time: t_new/t_ref=0.008236916/0.006966806
failures=[]
max ratio=4.389417116207599
min ratio=1.0174306325240554
ave ratio=1.8843519295185776
std dev=1.1215612866386258

実装はサボりにサボっている. GNU版では, 循環を見つけた場合, その循環を親切に列挙してくれる. しかしこれはたぶん超むずいしだるいということで, My実装ではやらないことにした. たぶん, 根本的にアルゴリズムを変更する必要があると思う.

最後にコードを貼り付ける. 引き継いだコードがゴミ同然だったので, 前の開発者の名前を残すか悩んだが, もしかしたらどこかでお世話になるかも知れないので名前を残すことにした. 今後は, 性能についてもう少し検証したあと, コードクリーンをしてプルリクという流れになる.

#![crate_name = "tsort"]

/*
 * This file is part of the uutils coreutils package.
 *
 * (c) Ben Eggers <ben.eggers36@gmail.com>
 * (c) Akira Hayakawa <ruby.wktk@gmail.com>
 *
 * For the full copyright and license information, please view the LICENSE
 * file that was distributed with this source code.
 */

#![feature(macro_rules)]

extern crate getopts;
extern crate libc;

use std::io;
use std::collections::{HashSet, HashMap};
use std::io::{print};

#[path = "../common/util.rs"]
mod util;

static NAME: &'static str = "tsort";
static VERSION: &'static str = "1.0.0";

pub fn uumain(args: Vec<String>) -> int {
    let opts = [
        getopts::optflag("h", "help", "display this help and exit"),
        getopts::optflag("V", "version", "output version information and exit"),
    ];

    let matches = match getopts::getopts(args.tail(), opts) {
        Ok(m) => m,
        Err(f) => crash!(1, "{}", f)
    };

    if matches.opt_present("h") {
        println!("{} v{}", NAME, VERSION);
        println!("");
        println!("Usage:");
        println!("   {} [OPTIONS] FILE", NAME);
        println!("");
        io::print(getopts::usage("Topological sort the strings in FILE. Strings are defined as any sequence of tokens separated by whitespace (tab, space, or newline). If FILE is not passed in, stdin is used instead.", opts).as_slice());
        return 0;
    }

    if matches.opt_present("V") {
        println!("{} v{}", NAME, VERSION);
        return 0;
    }

    let files = matches.free.clone();
    let input = if files.len() > 1 {
        crash!(1, "{}, extra operand '{}'", NAME, matches.free[1]);
    } else if files.is_empty() {
        "-".to_string()
    } else {
        files[0].to_string()
    };

    let mut reader = io::BufferedReader::new(
        if input.as_slice() == "-" {
            box io::stdio::stdin_raw() as Box<Reader>
        } else {
            box match io::File::open(&Path::new(input.clone())) {
                Ok(a) => a,
                _ => crash!(1, "{}: No such file or directory", input)
            } as Box<Reader>
        }
    );

    let mut g = Graph::new();
    loop {
        match reader.read_line() {
            Ok(line) => {
                let ab: Vec<&str> = line.as_slice().trim_right_chars('\n').split(' ').collect();
                if ab.len() > 2 {
                    crash!(1, "{}: input contains an odd number of tokens", input);
                }
                g.add_edge(ab[0].to_string(), ab[1].to_string());
            },
            _ => break
        }
    }

    g.run_tsort();
    if !g.is_acyclic() {
        crash!(1, "{}, input contains a loop:", input);
    }

    let mut writer = io::BufferedWriter::new(box io::stdio::stdout_raw() as Box<Writer>);
    for x in g.result.iter() {
        crash_if_err!(1, writer.write_line(x.as_slice()));
    }

    return 0
}

struct Graph {
    in_edges: HashMap<String, HashSet<String>>,
    out_edges: HashMap<String, Vec<String>>,
    result: Vec<String> // Ordered
}

// Kahn's algorithm
impl Graph {
    fn new() -> Graph {
        Graph {
            in_edges: HashMap::new(),
            out_edges: HashMap::new(),
            result: vec!(),
        }
    }

    fn has_node(&self, n: &String) -> bool {
        self.in_edges.contains_key(n)
    }

    fn has_edge(&self, from: &String, to: &String) -> bool {
        self.in_edges.get(to).contains(from)
    }

    fn init_node(&mut self, n: &String) {
        self.in_edges.insert(n.clone(), HashSet::new());
        self.out_edges.insert(n.clone(), vec!());
    }

    fn add_edge(&mut self, from: String,  to: String) {
        if !self.has_node(&to) {
            self.init_node(&to);
        }

        if !self.has_node(&from) {
            self.init_node(&from);
        }

        if !self.has_edge(&from, &to) {
            self.in_edges.get_mut(&to).insert(from.clone());
            self.out_edges.get_mut(&from).push(to.clone());
        }
    }

    fn run_tsort(&mut self) {
        let mut start_nodes = vec!();
        for (n, edges) in self.in_edges.iter() {
            if edges.is_empty() {
                start_nodes.push(n.clone());
            }
        }

        while !start_nodes.is_empty() {
            let n = start_nodes[0].clone();
            start_nodes.remove(0);

            self.result.push(n.clone());

            let n_out_edges = self.out_edges.get_mut(&n);
            while !n_out_edges.is_empty() {
                let m = n_out_edges.get(0).clone();
                n_out_edges.remove(0);

                let m_in_edges = self.in_edges.get_mut(&m);
                m_in_edges.remove(&n);

                if m_in_edges.is_empty() {
                    start_nodes.push(m);
                }
            }
        }
    }

    fn is_acyclic(&self) -> bool {
        for edges in self.out_edges.values() {
            if !edges.is_empty() {
                return false
            }
        }
        true
    }
}