夏も初めのけだるい朝は 趣味のコードとたわむれる
夏も初めの以下省略:ふぉろー
このふたつにおいてもすぬごいバグを見逃しておりました。
そのために時間計算量がΟ(NlogN)になりません。
mergeでチョンボこいてまして、せっかく繋がった連を断ち切っておりました。
おわびに、改行で区切られた文字列の並ぶテキストファイルの各文字列を昇順に並べます。
凝ったマネはしてないけどかなり高速です。
10万行を5秒弱でソートしてくれました。
<業務連絡>鶏唐揚さーん、コレVBに仕立ててくれるぅ?
using System;
using System.IO;
namespace MergeSortOnFile_csharp {
interface IQueReader<T> where T : IComparable<T> {
bool Available { get; }
T Current { get; }
void Next();
bool InOrder { get; }
bool Disorder { get; }
void Reset();
}
interface IQueWriter<T> {
void Write(T val);
}
class StringQueReader : IQueReader<string> {
private TextReader reader_;
private string current_;
private string last_ = null;
public StringQueReader(string path) {
reader_ = new StreamReader(path);
Next(); Reset();
}
public bool Available { get { return current_ != null; }}
public string Current { get { return current_; }}
public void Next() { last_ = current_; current_ = reader_.ReadLine();}
public void Close() { reader_.Close();}
public bool InOrder { get { return Available && last_.CompareTo(current_) <= 0; }}
public bool Disorder { get { return !InOrder; }}
public void Reset() { last_ = current_ ; }
}
class StringQueWriter : IQueWriter<string> {
private TextWriter writer_;
public StringQueWriter(string path) { writer_ = new StreamWriter(path); }
public void Write(string obj) { writer_.WriteLine(obj);}
public void Close() { writer_.Close(); }
}
class Program {
// 二つのキューをマージ(併合)して一つにする
private static void merge<T>(IQueReader<T> reader1, IQueReader<T> reader2, IQueWriter<T> writer) where T : IComparable<T> {
// 入力である二つのキューが共に要素を持っている間
while ( reader1.Available && reader2.Available ) {
// いずれかが連の切れ目に達したら他方の連の切れ目までを出力して仕切り直し。
if ( reader1.Disorder ) {
while ( reader2.InOrder ) { writer.Write(reader2.Current); reader2.Next(); }
reader1.Reset(); reader2.Reset(); continue;
}
if ( reader2.Disorder ) {
while ( reader1.InOrder ) { writer.Write(reader1.Current); reader1.Next(); }
reader1.Reset(); reader2.Reset(); continue;
}
// より小さい要素を取り出して出力する
if ( reader1.Current.CompareTo(reader2.Current) < 0 ) {
writer.Write(reader1.Current);
reader1.Next();
} else {
writer.Write(reader2.Current);
reader2.Next();
}
}
// キューに残る(取り出されなかった)要素を出力する
while ( reader1.Available ) { writer.Write(reader1.Current); reader1.Next(); }
while ( reader2.Available ) { writer.Write(reader2.Current); reader2.Next(); }
}
// 一つの入力列を二つのキューに分割する
private static bool split<T>(IQueReader<T> reader, IQueWriter<T> writer1, IQueWriter<T> writer2) where T : IComparable<T> {
bool dest = true;
bool switched = false;
while ( reader.Available ) {
// 直前の要素より小さな要素を読み込んだら出力キューを切り替える
if ( reader.Disorder ) {
switched = true;
dest = !dest;
}
if ( dest ) writer1.Write(reader.Current); else writer2.Write(reader.Current);
reader.Next();
}
return switched;
}
public static void merge_sort(string in_path, string out_path) {
bool switched;
do {
StringQueReader reader = new StringQueReader(in_path);
StringQueWriter writer1 = new StringQueWriter("tmp1.txt");
StringQueWriter writer2 = new StringQueWriter("tmp2.txt");
switched = split(reader, writer1, writer2);
reader.Close();
writer1.Close();
writer2.Close();
StringQueReader reader1 = new StringQueReader("tmp1.txt");
StringQueReader reader2 = new StringQueReader("tmp2.txt");
StringQueWriter writer = new StringQueWriter(out_path);
merge(reader1, reader2, writer);
reader1.Close();
reader2.Close();
writer.Close();
in_path = out_path;
} while ( switched );
File.Delete("tmp1.txt");
File.Delete("tmp2.txt");
}
public static void Main() {
merge_sort("input.txt","result.txt");
}
}
}