クイックソートは教科書的に実装すると最初のうちは少数のスタックに対して値を積んでいく作業になる為、超並列アーキテクチャではこのスタックの先頭を奪い合ってスケールしない事が知られている。だからそうしたアーキテクチャではマージソートや(メモリが潤沢な場合は)基数ソートがよく用いられる
いわゆるバケットソートですね。確かにバケットソートは計算量とスケーラビリティの双方で優れている為、それが可能な条件を満たしている場合積極的に選ぶべきアルゴリズムだと思います。
-
-
はい、適した用途の場合は、効果があります。年間2000億円節約はすごいと思うのですが、あまり大したことないと思われるのでしょうか? コメントがなかったので気になりました。
-
応用して結果を出したという点では凄い事だと思うんですが、バケットソートは基数ソートの特殊なケースで、その方法でスケーラビリティを維持しようというのはGPUを使った高速化まわりの話では定番の手法といった感じです。
- 1 more reply
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.