論文の概要: Energy and Time Complexity for Sorting Algorithms in Java

• arxiv url: http://arxiv.org/abs/2311.07298v2
• Date: Wed, 8 May 2024 09:23:19 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-09 19:10:37.520056
• Title: Energy and Time Complexity for Sorting Algorithms in Java
• Title（参考訳）: Javaにおけるソーティングアルゴリズムのエネルギーと時間複雑性
• Authors: Kristina Carter, Su Mei Gwen Ho, Mathias Marquar Arhipenko Larsen, Martin Sundman, Maja H. Kirkeby,
• Abstract要約: 本稿では、ソートアルゴリズムにおける時間複雑性とエネルギー消費の関係について検討する。 これは、Bubble Sort、Counting Sort、Merge Sort、Quick SortというJavaで実装されたアルゴリズムに焦点を当てている。 カウントソート、マージソート、クイックソートのエネルギー消費の99%以上は、時間的複雑さに依存している。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: The article investigates the relationship between time complexity and energy consumption in sorting algorithms, focusing on commonly-used algorithms implemented in Java: Bubble Sort, Counting Sort, Merge Sort, and Quick Sort. The significance of understanding this relationship is driven by the increasing energy demands of Information and Communication Technology systems and the potential for software optimization to contribute to energy efficiency. If we find a strong correlation between time complexity and energy usage, it would enhance the ability of software developers to create energy-efficient applications. This quantitative study researches the execution of four selected sorting algorithms with input varying over input sizes (25000 to 1 million) and input order types (best, worst, and random cases) on a single kernel in a Java-enabled system. The input size is adjusted according to the type's maximum execution time, resulting in 136 combinations, totalling 12960 measurements. Wall time and the CPU energy consumption is measured using Intel's RAPL. Statistical analysis are used to examine the correlations between time complexity, wall time, and energy consumption. The study finds a strong correlation between time complexity and energy consumption for the sorting algorithms tested. More than 99% of the variance in energy consumption for Counting Sort, Merge Sort, and Quick Sort depend on their time complexities. More than 94% of the variance in energy consumption for Bubble Sort depends on its time complexity. The results affirm that time complexity can serve as a reliable predictor of energy consumption in sequential sorting algorithms. This discovery could guide software developers in choosing energy-efficient algorithms by considering time complexities.
• Abstract（参考訳）: この記事では、Javaで実装されている一般的なアルゴリズムであるBubble Sort、Counting Sort、Merge Sort、Quick Sortに焦点を当て、ソートアルゴリズムにおける時間複雑性とエネルギー消費の関係について検討する。 この関係を理解することの重要性は、情報通信技術のエネルギー需要の増加と、ソフトウェア最適化がエネルギー効率に寄与する可能性によってもたらされる。 時間複雑性とエネルギー使用量の間に強い相関関係があれば、ソフトウェア開発者がエネルギー効率の良いアプリケーションを作成する能力を高めるでしょう。 この定量的研究は、入力サイズ(25000～100万)と入力順序タイプ(ベスト、最悪の、ランダムなケース)の4つの選択されたソートアルゴリズムをJava対応システム上で実行することを研究する。 入力サイズは、タイプが実行する最大時間に応じて調整され、合計で12960の合計136の組み合わせとなる。 壁面時間とCPUエネルギー消費はIntelのRAPLを用いて測定される。 統計分析は、時間複雑性、壁時間、エネルギー消費の相関関係を調べるために用いられる。 この研究は、テストされたソートアルゴリズムの時間複雑性とエネルギー消費との間に強い相関関係を見出した。 カウントソート、マージソート、クイックソートのエネルギー消費の99%以上は、時間的複雑さに依存している。 バブルソートのエネルギー消費の94%以上は、その時間の複雑さに依存する。 その結果、時間複雑性はシーケンシャルソートアルゴリズムにおけるエネルギー消費の信頼できる予測因子として機能することを確認した。 この発見は、時間的複雑さを考慮し、エネルギー効率のよいアルゴリズムを選択することを促す。

関連論文リスト

• Moderate Exponential-time Quantum Dynamic Programming Across the Subsets for Scheduling Problems [0.20971479389679337]
  量子最小探索と動的プログラミングの組み合わせは、NPハード問題の複雑さを改善するのに特に効果的であることが証明されている。 本稿では,NP-ハード単一マシンスケジューリング問題に対して,そのような改善を実現する境界付きエラーハイブリッドアルゴリズムを提案する。 我々のアルゴリズムは、よく知られた古典的アルゴリズムと比較して指数関数的な部分の複雑さを減らし、時には擬似多項式因子のコストがかかる。
  論文  参考訳（メタデータ） (2024-08-11T10:28:49Z)
• EKM: An exact, polynomial-time algorithm for the $K$-medoids problem [1.9405875431318445]
  EKM: 最悪の$Oleft(NK+1right)$複雑性でこの問題を正確に解くための新しいアルゴリズムを提案する。 EKMは、フォーマルなプログラムステップを用いて、変換プログラミングと生成の最近の進歩に従って開発されている。 我々は,アルゴリズムのウォールタイム実行時間が,合成データセット上での最悪の時間複雑性解析と一致することを示した。
  論文  参考訳（メタデータ） (2024-05-16T15:11:37Z)
• Quantum-Based Feature Selection for Multi-classification Problem in Complex Systems with Edge Computing [15.894122816099133]
  マルチクラス化問題,すなわちQReliefFに対する量子ベースの特徴選択アルゴリズムを提案する。 我々のアルゴリズムは、O(M) から O(sqrt(M)) への複雑さを減らし、最も近い隣人を見つけるのに優れている。
  論文  参考訳（メタデータ） (2023-10-01T03:57:13Z)
• Efficient distributed representations with linear-time attention scores normalization [3.8673630752805437]
  本研究では,有界ノルムを持つ埋め込みベクトルに対するアテンションスコア正規化定数の線形時間近似を提案する。 推定公式の精度は、競合するカーネルメソッドを桁違いに上回る。 提案アルゴリズムは高度に解釈可能であり,任意の埋め込み問題に容易に適応できる。
  論文  参考訳（メタデータ） (2023-03-30T15:48:26Z)
• HUSP-SP: Faster Utility Mining on Sequence Data [48.0426095077918]
  高実用性シーケンシャルパターンマイニング (HUSPM) が重要視されている。 シークエンスプロジェクション(seqPro)と呼ばれるコンパクトな構造を設計し、シークエンスプロ構造(HUSP-SP)を用いた効率的なアルゴリズムを提案する。 HUSP-SPは, 実行時間, メモリ使用量, 検索空間のプルーニング効率, スケーラビリティにおいて, 最先端のアルゴリズムを著しく上回っている。
  論文  参考訳（メタデータ） (2022-12-29T10:56:17Z)
• Quantum Clustering with k-Means: a Hybrid Approach [117.4705494502186]
  我々は3つのハイブリッド量子k-Meansアルゴリズムを設計、実装、評価する。 我々は距離の計算を高速化するために量子現象を利用する。 我々は、我々のハイブリッド量子k-平均アルゴリズムが古典的バージョンよりも効率的であることを示す。
  論文  参考訳（メタデータ） (2022-12-13T16:04:16Z)
• Searching for More Efficient Dynamic Programs [61.79535031840558]
  本稿では,プログラム変換の集合,変換プログラムの効率を評価するための単純な指標,およびこの指標を改善するための探索手順について述べる。 実際に、自動検索は初期プログラムの大幅な改善を見出すことができることを示す。
  論文  参考訳（メタデータ） (2021-09-14T20:52:55Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• ACSS-q: Algorithmic complexity for short strings via quantum accelerated approach [1.4873907857806357]
  符号化定理法を用いて,アルゴリズムの複雑性を推定する量子回路を提案する。 ユースケースとして,アルゴリズムの複雑さに基づくタンパク質-タンパク質相互作用の応用フレームワークを提案する。
  論文  参考訳（メタデータ） (2020-09-18T14:41:41Z)
• Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
  本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。 我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
  論文  参考訳（メタデータ） (2020-08-29T14:58:26Z)
• Learning to Accelerate Heuristic Searching for Large-Scale Maximum Weighted b-Matching Problems in Online Advertising [51.97494906131859]
  バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。 既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。 我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
  論文  参考訳（メタデータ） (2020-05-09T02:48:23Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。