論文の概要: Simple Symmetric Sustainable Sorting -- the greeNsort article
- arxiv url: http://arxiv.org/abs/2402.01816v1
- Date: Fri, 2 Feb 2024 14:21:51 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-07 00:02:59.900303
- Title: Simple Symmetric Sustainable Sorting -- the greeNsort article
- Title（参考訳）: シンメトリカルサステナブルソーティング - greeNsort の記事
- Authors: Jens Oehlschl\"agel
- Abstract要約: 連続した空間で動作する新しい単純なバイナリQuicksortとMergesortアルゴリズムを発見した。
新しいアルゴリズムは理論的な枠組みに適合する: 'Footprint' は異なるRAM要求のアルゴリズムを比較することができる。
以前の'Quicksorts'とは異なり、我々の'Zucksort'、'Zucksort'、'Ducksort'アルゴリズムはCPU効率とタイアダプティビティを最適に結合する。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We explored an uncharted part of the solution space for sorting algorithms:
the role of symmetry in divide&conquer algorithms. We found/designed novel
simple binary Quicksort and Mergesort algorithms operating in contiguous space
which achieve improved trade-offs between worst-case CPU-efficiency, best-case
adaptivity and RAM-requirements. The 'greeNsort' algorithms need less hardware
(RAM) and/or less energy (CPU) compared to the prior art. The new algorithms
fit a theoretical framework: 'Footprint' KPIs allow to compare algorithms with
different RAM-requirements, a new 'definition' of sorting API-targets
simplifies construction of stable algorithms with mirrored scan directions, and
our ordinal machine model encourages robust algorithms that minimize access
'distance'. Unlike earlier 'Quicksorts', our 'Zacksort', 'Zucksort' and
'Ducksort' algorithms optimally marry CPU-efficiency and tie-adaptivity. Unlike
earlier 'Mergesorts' which required 100% distant buffer, our 'Frogsort' and
'Geckosort' algorithms achieve similar CPU-efficiency with 50% or less local
buffer. Unlike natural Mergesorts such as 'Timsort' which are optimized for the
best case of full-presorting, our 'Octosort' and 'Squidsort' algorithms achieve
excellent bi-adaptivity to presorted best-cases without sacrificing worst-case
efficiency in real sorting tasks. Our 'Walksort' and 'Jumpsort' have lower
Footprint than the impressive low-memory 'Grailsort' and 'Sqrtsort' of
Astrelin. Given the current climate-emergency, this is a call to action for all
maintainers of sorting libraries, all software-engineers using custom sorting
code, all professors teaching algorithms, all IT professionals designing
programming languages, compilers and CPUs: check for better algorithms and
consider symmetric code-mirroring.
- Abstract（参考訳）: 我々は,アルゴリズムのソートのための解空間の非チャート部分を探索し,分割・コンカレントアルゴリズムにおける対称性の役割について検討した。
我々は,CPU効率,ベストケース適応性,RAM要求のトレードオフを改善するために,連続した空間で動作する新しい単純なバイナリQuicksortとMergesortアルゴリズムを考案・設計した。
greeNsort'アルゴリズムは、以前の技術に比べてハードウェア(RAM)やエネルギー(CPU)を少なくする。
新しいアルゴリズムは理論的な枠組みに適合する: 'footprint' kpiはアルゴリズムと異なるram要求を比較することができ、apiターゲットをソートする新しい'定義'は、ミラー付きスキャン方向の安定したアルゴリズムの構築を単純化し、我々の順序機械モデルは'距離'を最小限にする頑健なアルゴリズムを奨励する。
以前の'Quicksorts'とは異なり、我々の'Zucksort'、'Zucksort'、'Ducksort'アルゴリズムはCPU効率とタイアダプティビティを最適に結合する。
100%離れたバッファを必要とする以前の'Mergesorts'とは異なり、我々の'Frogsort'と'Geckosort'アルゴリズムは、50%以下のローカルバッファで同様のCPU効率を達成する。
完全並べ替えのベストケースに最適化された"timsort"のような自然なマージソートとは異なり、"octosort"と"squidsort"のアルゴリズムは、実際のソートタスクで最悪のケース効率を犠牲にすることなく、事前に並べ替えられたベストケースに対して優れたbi-adaptivityを達成します。
私たちの'Walksort'と'Jumpsort'は、Astrelinの印象的な低メモリ'Grailsort'と'Sqrtsort'よりもフットプリントが低い。
現在の気候の緊急性を考えると、これはライブラリをソートするすべてのメンテナ、カスタムソートコードを使用するソフトウェアエンジニア、アルゴリズムを教えるすべての教授、プログラム言語、コンパイラ、CPUを設計するすべてのITプロフェッショナルに対するアクションである。
関連論文リスト
- Rahmani Sort: A Novel Variant of Insertion Sort Algorithm with O(nlogn) Complexity [0.0]
本稿では,2進探索機構の新たな手法を用いて,前述した左サブアレイへの次のキー項目のソート位置を探索するアルゴリズムを提案する。
その結果,従来の挿入ソートアルゴリズムやマージソートアルゴリズムよりも,新しいアルゴリズムの方が優れた性能を示した。
論文 参考訳（メタデータ） (2024-02-29T12:38:57Z) - Sorting with Predictions [1.7042264000899532]
学習強化アルゴリズムのレンズをソートする根本的な問題について検討する。
我々は,$O(sum_i log eta_i)$の正確な比較だけで,新しい,シンプルなアルゴリズムを設計する。
比較複雑性は, 検証された誤差測度に対して理論的に最適であることを示す。
論文 参考訳（メタデータ） (2023-11-01T18:00:03Z) - Efficient Non-Parametric Optimizer Search for Diverse Tasks [93.64739408827604]
興味のあるタスクを直接検索できる,スケーラブルで汎用的なフレームワークを初めて提示する。
基礎となる数学表現の自然木構造に着想を得て、空間を超木に再配置する。
我々は,モンテカルロ法を木探索に適用し,レジェクションサンプリングと等価形状検出を備える。
論文 参考訳（メタデータ） (2022-09-27T17:51:31Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Rank-based Non-dominated Sorting [0.0]
我々は、高額な支配比較を避けるために、ソート安定性と順序情報を利用した非支配的なソート手法であるランクソートを導入する。
2つのアルゴリズム的変種が提案されている: 1つはRandOrdinal (RO) で、支配性を決定するために順序付き階数比較(英語版)(ordinal rank comparisons)を用いており、O(N) 空間を必要とする。
NSGA2アルゴリズムと合成ベンチマークを用いた実験シミュレーションにおいて,提案手法の有効性を他の手法と比較した。
論文 参考訳（メタデータ） (2022-03-25T13:59:42Z) - A Push-Relabel Based Additive Approximation for Optimal Transport [5.111364864495785]
最適な輸送を計算するための厳密なアルゴリズムは遅くなる。
我々は、OT距離の$varepsilon$approximationを求めるための、新しい非常に単純なアプローチを導入する。
我々のアルゴリズムは、OT距離を計算するために、O(n2/varepsilon2)$のほぼ最適実行時間を達成する。
論文 参考訳（メタデータ） (2022-03-07T21:40:14Z) - A Fully Single Loop Algorithm for Bilevel Optimization without Hessian
Inverse [121.54116938140754]
両レベル最適化問題に対して,Hessian 逆フリーな完全単一ループアルゴリズムを提案する。
我々のアルゴリズムは$O(epsilon-2)$と収束することを示す。
論文 参考訳（メタデータ） (2021-12-09T02:27:52Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Batch Bayesian Optimization on Permutations using Acquisition Weighted
Kernels [86.11176756341114]
決定点プロセスに基づく新しい効率的なバッチ取得方法であるLAWを紹介します。
本研究では,理論特性の知見を得るための後悔分析法を提案する。
二次代入などの置換を含むいくつかの標準問題に対する手法を評価する。
論文 参考訳（メタデータ） (2021-02-26T10:15:57Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。