抄録/ポイント:
抄録/ポイント
文献の概要を数百字程度の日本語でまとめたものです。
部分表示の続きは、JDreamⅢ(有料)でご覧頂けます。
J-GLOBALでは書誌(タイトル、著者名等)登載から半年以上経過後に表示されますが、医療系文献の場合はMyJ-GLOBALでのログインが必要です。
ここでは,広範囲の入力サイズ,入力分布,データタイプ,およびマシンのための最速の既知技術を表す新しい逐次および並列ソーティングアルゴリズムを提案した。驚いたことに,速度利点の一部は,入力アレイを超える空間のかなりの量を必要としない,現場で動作するアルゴリズムの追加特徴のためである。以前に,現場特徴は,しばしば性能ペナルティを意味した。著者らの主なアルゴリズム的貢献は,おそらくキャッシュ効率が高い,現場データ分布に対するブロックワイズアプローチである。また,動的負荷分散とメモリ局所性を考慮したこの手法を並列化する。著者らの新しい比較ベースのアルゴリズムIn-situ並列スーパースカラーサンプル(IPS4o)は,この技術を枝なし決定木と組み合わせる。多くの等しい要素を考慮して,分布度を動的に順応することによって,著者らは,ほとんど3の因子によって,最良の以前の現場並列比較ベースのソーティングアルゴリズムより性能が優れている高ロバストアルゴリズムを得た。また,このアルゴリズムは,現場,並列あるいは逐次設定で考慮しないかどうかにかかわらず,最良の比較ベース競争者より優れている。もう一つの驚くべき結果は,IPS4oが,広範囲の状況において,最良(in situまたはin situ)整数ソーティングアルゴリズムよりも性能が優れていることである。残りの事例(しばしば,ほぼ均一な入力分布,小さな鍵,あるいは逐次設定を含む)の多くにおいて,著者らの新しいIn-pace並列Super Scalar Radix Sort(IPS2Ra)は最良のアルゴリズムである。若干の意味で「最良」ソーティングアルゴリズムを持つためのClaimsは,すべて真実でない多くの論文で見つけることができる。したがって,著者らは,21の最先端のソーティング符号,6つのデータタイプ,10の入力分布,4つの機械,4つのメモリ割り当て戦略,および7桁以上の入力サイズを含む,大規模な実験研究に関する著者らの結論を基礎づけた。これは,関連する出版物で報告された測定のコンクリートセット外の多くの競争者における主要な性能問題を明らかにしながら,著者らのアルゴリズムのロバスト性能に関する主張を確認した。これは,ロバスト汎用ソーティングのための比較ベースアルゴリズムを好む一つの理由を与える整数ソーティングアルゴリズムに対して特に真実である。Please refer to this article’s citation page on the publisher website for specific rights information. Translated from English into Japanese by JST.【JST・京大機械翻訳】