結城先生のクロッシング問題、復習メモ（Delphi）

 > 挑戦者求む！交差点をすばやく数えよう！ by The Essence of Programming http://t.co/2Xn4WbblEf @codeiqさんから

・「三十万個超の数値データを順々に読み出す、一つの数値を読み出すたび、『それより大きい既出の数値の個数』を積算していく」問題だと解釈。

　そこで、自分はDelphiで「既出の数値をリスト構造に昇順で保存する」という方法をとったが、9秒が限界。課題要件の「3秒未満」には至らなかった。

　9/3にいただいた結城先生の解説「マージソート版」は「あ、これだったのかぁ」という印象だったが、別解の「逆転表版」は目からうろこ。模範プログラム例はRubyとC。これをDelphiに移植して、「本当に（Delphiでも）1秒以下で正解が出せる」ことに、まず感激。

　ただ、「何でこのソースコードで、正解が出るのか」なかなかピンとこなかった。変数の動きを追いかけ追いかけ、ようやく、「上位ビットを配列の添字にしている」ことで「上位ビットが共通のデータ」をまとめて扱えていることを理解。

　なるほど、無駄が無く美しい。

ーーーーーーーーーーーーー

しばらくすると忘れそうなのでDelphi移植版に、いろいろコメントつけたのを置いておく。（フォームに出力用メモコンポーネントMemo1を置いている。）

procedure TForm1.Button1Click(Sender: TObject);
//逆転表版
var
    bits, i,j,k,s, datacount: Integer;
    cross_sum   : UINT64;
    nums : TList<Integer>; //課題の配列を入れておく
    invs : TList<Integer>; //逆転表用

    StringList:  TStringList; //ファイル読み出し用文字列リスト

begin
    Memo1.Lines.Add(DateTimeToStr(Now));//開始時刻記録

    cross_sum := 0;  //クロス数初期化

    //課題のデータを文字列リストに読み出し

    StringList := TStringList.Create;
    StringList.LoadFromFile('C:\temp\crossing.txt'); //ファイル置き場指定し読み出し

    //データ数 （＝314159個）が求まる↓
    datacount := StringList.Count;

    //作業用配列準備
    nums := TList<Integer>.Create;
    invs := TList<Integer>.Create;
    try
      for i := 0 to datacount -1 do begin
        nums.Add(StrToInt(StringList.Strings[I])); //文字列リストから数値リストへ変換
        invs.Add(0);//ゼロ埋め（メモリ確保）
      end;

      //配列の添え字を２進表記した場合の最上位ビットの桁位置をbitsへ。
      //配列要素数314159個だが 2^19で524288, 2^18で262144なのでbitsは18 になる
      for bits := 31 downto 1 do begin
        if (datacount and (1 shl bits))>0 then break;
      end;

      //上位ビットから順に処理。
      for k := bits downto 0 do begin
        //使う分だけ、invsの初期化
        for s := 0 to datacount div (1 shl (k+1)) do invs[s] := 0;

        //横、データ数の分だけスキャン
        for j := 0 to datacount-1 do begin
          s := nums[j] div (1 shl (k+1));//データの上位のビットだけ取り出す

          if nums[j] and (1 shl k)>0 then  invs[s] := invs[s]+1
          //↑そのビットが１のとき、
          //『上位ビットが共通で、その時点で初めて自分より大きいとわかる

　　  //自分よりも左にある数の個数』はゼロ。
          //上位ビット（s）が共通で、そのビットが1である個数：invs[s]を

　　  //インクリメントしておく

          else cross_sum := cross_sum + invs[s];
          //↑そのビットが0のとき、
          //『上位ビットが共通で、その時点で初めて自分より大きいとわかる

　　  //自分よりも左にある数の個数』は
          //その時点でのinvs[s]であるから、それをクロス数に追加。

        end;
      end;
      Memo1.Lines.Add(IntToStr(cross_sum));//結果の出力
    finally
      invs.Free;
      nums.Free;

      StringList.Free;
    end;
    Memo1.Lines.Add(DateTimeToStr(Now));//終了時刻記録
end;

＝＝＝＝＝＝＝＝＝＝＝＝＝

出力結果（処理時間一秒未満）

2013/09/05 15:21:01
24689222839
2013/09/05 15:21:01