Orz日記 by Akio Morita

_ [SAD]sort再実装の残作業

次に作るもの

• sort済みlist containerへの1要素挿入 tfinsertsort
  • 挿入元と出力がlist containerなのでインタプリタヒープ断片化の原因となり得るが、それを変更するには構築途上のreference container型を導入する必要がある
  • ソースコンテナ内のNull[...]要素を展開する機能がある
    • テンポラリコンテナへのシーケンス展開エンジンが必要
• 整数配列へのインデックスソート tfsorti (tfsortsymbolstk実装用)(r6179にて実装 2021.05.20)
• 実数配列へのインデックスソート spsort (spkick実装用)(r6182にて実装 2021.05.20)
• Intersection/Complementの再実装
  • 現行実装には問題点あり
    • 3要素以上は、再帰呼び出しにて実装している (スタック消費)
    • Intersectionに関しては、サイズ最小のリストを種にすべき
    • 積集合・和集合の抽出に使う整列済みリストは、union_listで得られるリストコンテナを使っている (SADインタプリタヒープを消費・断片化している)
      • 再帰呼び出しでは、一時割り当てしたリストコンテナを再帰的に生産するので、ワーストケースのインタプリタヒープ消費は、種リストの長さNに対して $O(N^2)$ (再帰毎にリストが短くなるケースが最悪)
    • Intersection/Complementどちらの場合も、出力候補となるリストの長さは単調現象となるので、一時領域の再割り当てを行う必要は無い

性能に関しては、オリジナル実装では実数リスト等のケースで比較ルーチンがソートエンジン内に展開されているのに対して、qsort(3)等では関数呼び出しが必須となる点は不利だが、実数リストコンテナではインデックスソートではなく、出力配列を直接スワップすることで間接参照コストを低減する最適化を行ったため、N = 2^24でのテストでは、整列・逆整列・準整列・ランダムの各パターンで、オリジナル実装よりも概ね良好な性能が得られている

ISO C++がテンプレート版sortがつかえれば、比較ルーチンのinline展開により更なる改善が得られると思われる