Orz日記 by Akio Morita

_ [SAD]Intersection/Complement

sort engine入れ替え後にregressionしたので調査したが、リストをスタック上に展開して舐める際に、空のリストが考慮されていないのが、原因だった

オリジナルコードだと、直前にUnion1をスタック経由で呼び出す際の引数がスタック上に存在するので、無効参照を避けているが、演算結果は結果が正しくない

問題を起こすのは、第二引数が空のリストのケース

Intersection[{3,1,{},2}, {}]

空集合との積集合なので{}を返すべきところを{{}}を返す

Complement[{3,1,{},2}, {}]

空集合を除外するので、{1,2,3,{}}を返すべきところを{1,2,3}を返す

さらに、戻り値の構築をitflistで行うため、スタックが空(空集合)のケースでは、itflistからitfcrelistmへ頭部(ntfoper, mtfleftbrace)で移譲され、itfcrelistmが構築済みのiaxnulll空リストコンテナの参照を返すが、その後にcopyheadで頭部を挿入する過程で、構築済み空リストが汚染されている

_ [SAD]再入可能なqsort(3)

標準化という意味での本命は、ISO C11 Annex.Kのqsort_s(3)だけど実装している環境はFreeBSDやMicrosoftぐらいか？

glibcのqsort_rは戻り値が無い以外は、ほぼqsort_s

次点は、ISO C++にlabmdaで標準化された無形クロージャに対応する機能がISO Cで標準化されることとだが…どうなんでしょう？

実装例的には、LLVM/clangのBlock構文拡張がそのものズバリなのだが…

GCCのNested Function拡張も近いけど、あくまでもローカルスコープ上で定義・参照可能な関数なので、リテラルで引数に積めない、クロージャとして戻り値に出来ないあたりがlambdaやBlock構文拡張に劣る

実用面では、FreeBSDのGitHubからqsort/qsort_sの実装を持ち込む辺りか？

古い教科書には、平均的なケースではオーバーヘッドが多いmergesortはquicksortに勝てない的な言説が書かれているが、現代的なハードウェアでの実測だと比較回数が同程度の状況でmergesortがquicksortに劣る事例は以外と少ない、またその差が小さい模様

初期順序が同一でも比較操作時の間接参照が増えるとquicksortに逆転されることから、キャッシュ階層が深い計算機環境では、mergesortの方がメモリアクセスの連続性が高い(マージ操作)ためにキャッシュ効き易いためではと推測される

ちなみに、heapsortの実行時間は$N\log{N}$で安定だが、quick/mergesortに比べて数倍〜10倍程度遅い模様

$O(N)$の作業領域が安定して確保出来る状況であれば、mergesortを標準にしたほうが良さそうだが、標準実装してるのはBSD系ぐらいで、再入可能なmergesortを標準実装してるのはBlock拡張付きのDarwinとFreeBSDぐらいなのが玉に瑕