マージ・ソート : 巨大データのソート法

C#, VB.NET, C++/CLI で学ぶアルゴリズム

いよいよ実装

　マージ・ソートのアルゴリズムは前述の通りです。それでは、このアルゴリズムに従って実装を始めましょう。

　……ここで一つ大事なこと。ここまでの説明で“連の切れ目”という言葉が何度となく出てきました。“連の切れ目”を検出するには“直後のデータが現在読み込んでいるデータより小さい”か否かを調べることになります。これはすなわち、データの読み込みに際し“データを常に一つ先読みしておかなければならない”ことを意味します。そこでまず“先読み”を行うクラスを作りましょう。先読みクラスのインターフェイスは次のとおり:

（C#） IQueReader, IQueWriter

interface IQueReader<T> where T : IComparable<T> {
  bool Available { get; } // 入力が空ではない
  T    Current { get; }   // 現在の値
  void ReadNext();        // 次を読め
  bool EndOfRun { get; }  // 連の切れ目か?
}

interface IQueWriter<T> {
  void Write(T val); // valを書け
}

（VB.NET） IQueReader, IQueWriter

Interface IQueReader(Of T As IComparable(Of T))
    ReadOnly Property Available() As Boolean ' 入力が空ではない
    ReadOnly Property Current() As T ' 現在の値
    Sub ReadNext() ' 次を読め
    ReadOnly Property EndOfRun() As Boolean ' 連の切れ目か?
End Interface

Interface IQueWriter(Of T)
    Sub Write(ByVal val As T) ' valを書け
End Interface

（C++/CLI） IQueReader, IQueWriter

generic<typename T> where T : IComparable<T>
interface class IQueReader {
  property bool Available { bool get(); } // 入力が空でなはい
  property T    Current   { T get(); }    // 現在の値
  void          ReadNext();               // 次を読め
  property bool EndOfRun  { bool get(); } // 連の切れ目か?
};

generic<typename T>
interface class IQueWriter {
  void Write(T val); // valを書け

};

　このインターフェイスを使ってデータを一つコピーするCopyおよび連をコピーするCopyRunを実装します。C#では拡張メソッドを使ってみました。

（C#） CopyTo, CopyRunTo

static class QueExtention {
  // readerからwriterへ一つコピーする
  public static void CopyTo<T>(this IQueReader<T> reader,
    IQueWriter<T> writer) where T : IComparable<T> {
    writer.Write(reader.Current); // readerの現在値をwriterに書いて
    reader.ReadNext(); // 次を読んでおく
  }
  // 連の切れ目に達するまでreaderからwriterに転写する
  public static void CopyRunTo<T>(this IQueReader<T> reader,
    IQueWriter<T> writer) where T : IComparable<T> {
    do {
      reader.CopyTo(writer);
    } while (!reader.EndOfRun);
  }
}

（VB.NET） CopyTo, CopyRunTo

' readerからwriterへ一つコピーする
Private Sub CopyTo(Of T As IComparable(Of T))( _
    ByVal reader As IQueReader(Of T), _
    ByVal writer As IQueWriter(Of T))
    writer.Write(reader.Current) ' readerの現在値をwriterに書いて
    reader.ReadNext() ' 次を読んでおく
End Sub

' 連の切れ目に達するまでreaderからwriterに転写する
Private Sub CopyRunTo(Of T As IComparable(Of T)) _
    (ByVal reader As IQueReader(Of T), _
    ByVal writer As IQueWriter(Of T))
    Do
        CopyTo(reader, writer)
    Loop Until reader.EndOfRun
End Sub

（C++/CLI） CopyTo, CopyRunTo

// readerからwriterへ一つコピーする
generic<typename T> where T : IComparable<T>
void CopyTo(IQueReader<T>^ reader, IQueWriter<T>^ writer) {
  writer->Write(reader->Current); // readerの現在値をwriterに書いて
  reader->ReadNext();
}

// 連の切れ目に達するまでreaderからwriterに転写する
generic<typename T> where T : IComparable<T>
void CopyRunTo(IQueReader<T>^ reader, IQueWriter<T>^ writer) {
  do {
    CopyTo(reader,writer); ' 次を読んでおく
  } while ( !reader->EndOfRun );
}

　ソート対象となるのは文字列なので、これらインターフェイスをstringに対して実装します。

（C#） StringQueReader, StringQueWriter

// 文字列版QueReader : IQueReader<string> の実装
class StringQueReader : IQueReader<string> {
  private TextReader reader_;
  private string last_ = null;
  public StringQueReader(TextReader reader) {
    reader_ = reader;
    ReadNext();
  }
  public bool Available { get { return Current != null; }}
  public string Current { get; private set; }
  public void ReadNext() {
    last_ = Current; Current = reader_.ReadLine();}
  public void Close() { reader_.Close(); }
  public bool EndOfRun {
    get { return !Available || Current.CompareTo(last_) < 0; }}
}

// 文字列版QueWriter : IQueWrite<string>の実装
class StringQueWriter : IQueWriter<string> {
  private TextWriter writer_;
  public StringQueWriter(TextWriter writer) { writer_ = writer; }
  public void Write(string val) { writer_.WriteLine(val);}
  public void Close() { writer_.Close(); }
}

（VB.NET） StringQueReader, StringQueWriter

' 文字列版QueReader : IQueReader(Of String) の実装
Class StringQueReader : Implements IQueReader(Of String)

    Private reader_ As TextReader
    Private last_ As String
    Private current_ As String

    Public Sub New(ByVal reader As TextReader)
        reader_ = reader
        ReadNext()
    End Sub

    Public ReadOnly Property Available() As Boolean _
        Implements IQueReader(Of String).Available
        Get
            Return Current <> Nothing
        End Get
    End Property

    Public ReadOnly Property Current() As String _
        Implements IQueReader(Of String).Current
        Get
            Return current_
        End Get
    End Property

    Public ReadOnly Property EndOfRun() As Boolean _
        Implements IQueReader(Of String).EndOfRun
        Get
            Return Not Available OrElse current_.CompareTo(last_) < 0
        End Get
    End Property

    Public Sub ReadNext() Implements IQueReader(Of String).ReadNext
        last_ = current_
        current_ = reader_.ReadLine()
    End Sub

    Public Sub Close()
        reader_.Close()
    End Sub

End Class

' 文字列版QueWriter : IQueWrite<string>の実装
Class StringQueWriter : Implements IQueWriter(Of String)

    Private writer_ As TextWriter
    Public Sub New(ByVal writer As TextWriter)
        writer_ = writer
    End Sub
    Public Sub Write(ByVal val As String) _
        Implements IQueWriter(Of String).Write
        writer_.WriteLine(val)
    End Sub
    Public Sub Close()
        writer_.Close()
    End Sub
End Class

（C++/CLI） StringQueReader, StringQueWriter

// 文字列版QueReader : IQueReader<String^> の実装
ref class StringQueReader : public IQueReader<String^> {
private:
  TextReader^ reader_;
  String^     last_;
  String^     current_;
public:
  StringQueReader(TextReader^ reader) : reader_(reader),
   last_(nullptr) { ReadNext(); }
  property bool Available {
    virtual bool get() { return current_ != nullptr; }
  }
  property String^ Current {
    virtual String^ get() { return current_; }
  }
  virtual void ReadNext() { last_ = current_;
    current_ = reader_->ReadLine(); }
  void Close() { reader_->Close(); }
  property bool EndOfRun {
    virtual bool get() {
      return !Available || current_->CompareTo(last_) < 0; }
  }
};

// 文字列版QueWriter : IQueWrite<String^>の実装
ref class StringQueWriter : public IQueWriter<String^> {
private:
  TextWriter^ writer_;
public:
  StringQueWriter(TextWriter^ writer) : writer_(writer) {}
  virtual void Write(String^ val) { writer_->WriteLine(val); }
  void Close() { writer_->Close(); }
};