40

数字の配列があるとしましょう:[2,3,3,4,2,2,5,6,7,2]

その配列の最小値または最大値を見つける最良の方法は何ですか?

現在、最大値を取得するために、配列をループして、既存の値よりも大きい場合は変数をその値にリセットしています。

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];

var maxValue:Number = 0;

for each (var num:Number in myArray)
{
    if (num > maxValue)
        maxValue = num;
}

これは、これを実行するための最良の方法とは思えません (可能な限りループを避けるようにしています)。

4

17 に答える 17

83

他のすべての人からの理論的な答えはすべてき​​ちんとしていますが、実用的にしましょう。ActionScript には必要なツールが用意されているため、この場合はループを記述する必要さえありません。

Math.min()まず、 andMath.max()は任意の数の引数を取ることができることに注意してください。また、オブジェクトでapply()使用できるメソッドを理解することも重要です。Functionを使用して関数に引数を渡すことができますArray。両方を活用しましょう。

var myArray:Array = [2,3,3,4,2,2,5,6,7,2];
var maxValue:Number = Math.max.apply(null, myArray);
var minValue:Number = Math.min.apply(null, myArray);

最良の部分は次のとおりです。「ループ」は実際には (Flash Player 内の) ネイティブ コードを使用して実行されるため、純粋な ActionScript ループを使用して最小値または最大値を検索するよりも高速です。

于 2009-01-08T23:51:41.577 に答える
30

すべての値をテストせずに最小値/最大値を取得する信頼できる方法はありません。並べ替えなどを試したくない場合は、配列をウォークスルーすると O(n) になります。これは、通常の並べ替えアルゴリズムよりも優れています。

于 2009-01-08T16:00:53.620 に答える
28

もしも

  1. 配列はソートされていません
  2. 最小値と最大値の検索は同時に行われます

次に、3n/2 回の比較で最小値と最大値を見つけるアルゴリズムがあります。必要なことは、配列の要素をペアで処理することです。ペアの大きい方を現在の最大値と比較し、ペアの小さい方を現在の最小値と比較する必要があります。また、配列に奇数の要素が含まれている場合は、特別な注意が必要です。

C++ コード (Mehrdad から一部のコードを借用)。

struct MinMax{
   int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   MinMax  min_max;
   int index;
   int n = end - start + 1;//n: the number of elements to be sorted, assuming n>0
   if ( n%2 != 0 ){// if n is odd

     min_max.Min = array[start];
     min_max.Max = array[start];

     index = start + 1;
   }
   else{// n is even
     if ( array[start] < array[start+1] ){
       min_max.Min = array[start];
       min_max.Max = array[start+1];
     }
     else{
       min_max.Min = array[start+1];
       min_max.Max = array[start];
     }
     index = start + 2;
   }

   int big, small;
   for ( int i = index; i < n-1; i = i+2 ){
      if ( array[i] < array[i+1] ){ //one comparison
        small = array[i];
        big = array[i+1];
      }
      else{
        small = array[i+1];
        big = array[i];
      }
      if ( min_max.Min > small ){ //one comparison
        min_max.Min = small;
      }
      if ( min_max.Max < big ){ //one comparison
        min_max.Max = big;
      }
   }

   return min_max;
}

必要な比較回数が 3n/2 であることは非常に簡単にわかります。ループは n/2 回実行され、各反復で 3 つの比較が実行されます。これはおそらく達成できる最適な方法です。現時点では、その明確なソースを指摘することはできません。(しかし、どこかでその証拠を見たと思います。)

上記の Mehrdad によって与えられた再帰的な解決策は、おそらくこの最小数の比較も達成します (最後の行を変更する必要があります)。しかし、彼が述べたように、同じ数の比較では、関数呼び出しのオーバーヘッドにより、反復ソリューションは常に再帰ソリューションよりも優れています。ただし、(Eric Belair のように) 少数の数値の最小値と最大値を見つけることだけを気にする場合、今日のコンピューターで上記のアプローチのいずれかを使用しても、違いに気付く人はいないでしょう。大規模な配列の場合、違いが大きくなる可能性があります。

このソリューションと Matthew Brubaker によって提供されたソリューションには O(n) の複雑さがありますが、実際には、関連する隠れた定数を慎重に評価する必要があります。彼のソリューションの比較回数は 2n です。2n 回の比較ではなく、3n/2 回の比較を使用したソリューションで得られる高速化は顕著です。

于 2009-07-26T07:41:50.860 に答える
21

配列がソートされていない限り、それが最善の方法です。ソートされている場合は、最初と最後の要素だけを取ります。

もちろん、ソートされていない場合、最初にソートして最初と最後を取得することは、一度ループするよりも効率が悪いことが保証されています。最高の並べ替えアルゴリズムでさえ、各要素を複数回 (各要素の平均 O(log N) 回) 調べる必要があります。これは合計 O(N*Log N) です。1 回の単純なスキャンは O(N) しかありません。

データ構造内の最大の要素にすばやくアクセスしたい場合は、ヒープを調べて、オブジェクトを何らかの順序で保持する効率的な方法を調べてください。

于 2009-01-08T16:10:07.360 に答える
12

配列をループする必要があり、すべての要素をチェックする他の方法はありません。コードの修正が 1 つだけあります。すべての要素が負の場合、maxValue は最後に 0 になります。整数の可能な最小値で初期化する必要があります。
また、配列を何度も検索する場合は、最初に並べ替えることをお勧めします。検索が高速になり (バイナリ検索)、最小要素と最大要素が最初と最後に表示されるだけです。

于 2009-01-08T16:03:57.170 に答える
4

何を「最高」と呼ぶかによります。O(n)理論的な観点からは、決定論的チューリング マシンよりも短い時間で問題を解決することはできません。

単純なアルゴリズムはループしすぎて、最小値、最大値を更新します。ただし、最小値と最大値を同時に取得したい場合は、単純なアルゴリズムよりも再帰的なソリューションで必要な比較が少なくなります (関数呼び出しのオーバーヘッドにより、必ずしも高速になるとは限りません)。

struct MinMax{
   public int Min,Max;
}

MinMax FindMinMax(int[] array, int start, int end) {
   if (start == end)
      return new MinMax { Min = array[start], Max = array[start] };

   if (start == end - 1)
      return new MinMax { Min = Math.Min(array[start], array[end]), Max = Math.Max(array[start], array[end]) } ;

   MinMax res1 = FindMinMax(array, start, (start + end)/2);
   MinMax res2 = FindMinMax(array, (start+end)/2+1, end);
   return new MinMax { Min = Math.Min(res1.Min, res2.Min), Max = Math.Max(res1.Max, res2.Max) } ;
}

最も簡単な解決策は、最初と最後のアイテムを並べ替えて取得することですが、明らかに最速ではありません;)

最小値または最大値を見つけるためのパフォーマンス面での最良の解決策は、作成した単純なアルゴリズムです (単一のループを使用)。

于 2009-01-08T16:06:56.587 に答える
2

これは、実際のアプリケーション要件によって異なります。

あなたの質問が単なる仮説である場合、基本はすでに説明されています。これは典型的な検索対ソートの問題です。その場合、アルゴリズム的には O(n) よりも優れたものを達成することはできないことはすでに述べました。

しかし、実際の使用を見てみると、物事はより興味深いものになります。次に、配列の大きさと、データ セットへの追加と削除に関連するプロセスを考慮する必要があります。このような場合、オンザフライでソートして、挿入/削除時に計算上の「ヒット」を取得するのが最善の方法です。事前にソートされた配列への挿入はそれほど高価ではありません。

Min Max リクエストに対する最も速いクエリ応答は、常に並べ替えられた配列からのものです。他の人が述べたように、最初または最後の要素を取得するだけで、O(1) コストがかかるからです。

関連する計算コストと Big O 表記法に関する技術的な説明については、こちらのウィキペディアの記事を参照してください。

ニック。

于 2009-01-08T16:18:50.043 に答える
2

配列を 1 回作成していて、最大値を 1 回だけ見つけたい場合は、反復処理が最適です。

配列を変更したいときや、ときどき最大要素を知りたいときは、Priority Queueを使用する必要があります。そのための最適なデータ構造の 1 つはFibonacci Heapです。これが複雑すぎる場合は、速度は遅いがそれでも優れたBinary Heapを使用します。

最小値と最大値を見つけるには、2 つのヒープを構築し、そのうちの 1 つの数値の符号を変更するだけです。

于 2009-01-08T16:12:27.573 に答える
1

配列のソートは、配列の特定のサイズまでループするよりも高速であることに注意してください。配列が小さい場合 (そして、いつでもそうなる場合)、ソリューションは完全に問題ありません。ただし、配列が大きくなりすぎる可能性がある場合は、条件付きを使用して、配列が小さい場合は並べ替えアプローチを使用し、配列が大きすぎる場合は通常の反復を使用する必要があります。

于 2009-01-28T21:21:30.250 に答える
0

最小値と最大値の両方を同時に見つけたい場合は、ループを次のように変更できます。

int min = int.maxValue;
int max = int.minValue;

foreach num in someArray {
  if(num < min)
    min = num;
  if(num > max)
    max = num;
}

これにより、O(n) タイミングが達成されるはずです。

于 2009-01-08T16:29:50.520 に答える
-5

みんなのコメント (興味を持っていただきありがとうございます) を読んだ後、これを行うための "最善の" 方法 (コードの量が少なく、パフォーマンスが最高) は、単純に配列を並べ替えてから、配列の最初の値を取得することであることがわかりました。

var myArray:Array /* of Number */ = [2,3,3,4,2,2,5,6,7,2];

myArray.sort(Array.NUMERIC);

var minValue:int = myArray[0];

これは、オブジェクトの配列でも機能します。単に Array.sortOn() 関数を使用してプロパティを指定するだけです。

// Sample data
var myArray:Array /* of XML */ = 
    [
    <item level="2" name="a" />
    <item level="3" name="b" />
    <item level="3" name="c" />
    <item level="2" name="d" />
    <item level="5" name="e" />
    ]

// Perform a descending sort on the specified attribute in Array to get the maximum value
myArray.sortOn("@level", Array.DESCENDING | Array.NUMERIC);

var lowestLevel:int = myArray[0].@level;

これがいつか他の誰かに役立つことを願っています!

于 2009-01-23T22:34:00.820 に答える