Namaran

Code daily. Without assist.

2026-10-08

tac.rs

fn tac(text: &str) -> String {
    let mut out = String::new();
    for line in text.lines() {
        out = line.to_string() + "\n" + &out;
    }
    out
}

fn main() {
    let text: String = (0..1_000_000).map(|i| format!("{i}\n")).collect();
    let rev = tac(&text);
    println!("{} {}", rev.len(), rev.lines().next().unwrap_or(""));
}

tac は、テキストの行を逆の順に並べ替えた文字列を返すつもりの関数です。main は 0 から 999999 までの数を1行に1つずつ並べた100万行のテキストを渡し、結果の長さと先頭の行を出力します。引数も標準入力も使いません。いまは1分待っても何も出力されず、終わりません。本来はすぐに 6888890 999999 が出るはずです。

Answer

Wrong

for line in text.lines() {
    out = line.to_string() + "\n" + &out;
}

String の + が使い回すのは左のバッファで、右の &str はその後ろへコピーされます。この行で左にあるのは、line.to_string() で作ったばかりの数バイトの文字列です。それまでに積み上げた out は右の &out として、丸ごとその後ろへコピーされます。

1行足すたびにそれまでの結果を全部コピーするので、k 行目ではおよそ7k バイトを動かします。100万行では、合わせて数兆バイトのコピーになります。結果は正しいものの、かかる時間が行数の2乗に比例するので、実際には終わりません。

Right

for line in text.lines().rev() {
    out.push_str(line);
    out.push('\n');
}

行を後ろから取り出し、out の末尾に書き足します。push_str は out のバッファに足すだけなので、各行を1度ずつコピーすれば済み、容量が足りなくなったときの確保し直しを含めても、時間は全体の長さに比例します1。

  1. out.insert_str(0, line) のように先頭へ挿入しても同じことが起きます。先頭に入れるには、それまでの中身をすべて後ろへずらす必要があるからです。