Pertanyaan Apa cara terbaik untuk mendapatkan nilai minimum atau maksimum dari Array angka?


Katakanlah saya memiliki Array angka: [2,3,3,4,2,2,5,6,7,2]

Apa cara terbaik untuk menemukan nilai minimum atau maksimum dalam Array itu?

Saat ini, untuk mendapatkan maksimum, saya mengulang melalui Array, dan menyetel ulang variabel ke nilai jika lebih besar dari nilai yang ada:

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;
}

Ini sepertinya bukan cara terbaik untuk melakukan ini (saya mencoba menghindari loop kapan saja mungkin).


31
2018-01-08 15:57


asal


Jawaban:


Jawaban teoretis dari semua orang semuanya rapi, tetapi mari kita menjadi pragmatis. ActionScript menyediakan alat yang Anda butuhkan sehingga Anda bahkan tidak perlu menulis perulangan dalam kasus ini!

Pertama, perhatikan itu Math.min() dan Math.max() dapat mengambil sejumlah argumen. Juga, penting untuk memahami apply() metode tersedia untuk Function objek. Ini memungkinkan Anda untuk meneruskan argumen ke fungsi menggunakan Array. Mari manfaatkan keduanya:

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);

Inilah bagian yang terbaik: "loop" sebenarnya dijalankan menggunakan kode asli (di dalam Flash Player), jadi lebih cepat daripada mencari nilai minimum atau maksimum menggunakan loop ActionScript murni.


80
2018-01-08 23:51



Tidak ada cara yang dapat diandalkan untuk mendapatkan minimum / maksimum tanpa menguji setiap nilai. Anda tidak ingin mencoba semacam atau semacam itu, berjalan melalui array adalah O (n), yang lebih baik daripada algoritma semacam apa pun dapat dilakukan dalam kasus umum.


28
2018-01-08 16:00



Jika

  1. Array tidak diurutkan
  2. Menemukan min dan max dilakukan secara bersamaan

Kemudian ada algoritma yang menemukan min dan max dalam 3n / 2 jumlah perbandingan. Apa yang perlu dilakukan adalah memproses elemen-elemen array secara berpasangan. Pasangan yang lebih besar harus dibandingkan dengan max saat ini dan yang lebih kecil dari pasangan harus dibandingkan dengan min saat ini. Juga, seseorang perlu berhati-hati jika array mengandung jumlah elemen ganjil.

Dalam kode c ++ (meminjam beberapa kode dari 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;
}

Sangat mudah untuk melihat bahwa jumlah perbandingan yang dibutuhkan adalah 3n / 2. Loop berjalan n / 2 kali dan dalam setiap iterasi 3 perbandingan dilakukan. Ini mungkin yang paling optimal yang bisa dicapai. Pada saat ini, saya tidak bisa menunjukkan sumber pasti itu. (Tapi, saya pikir saya telah melihat bukti di suatu tempat.)

Solusi rekursif yang diberikan oleh Mehrdad di atas, mungkin juga mencapai jumlah perbandingan minimal ini (baris terakhir perlu diubah). Tetapi dengan jumlah perbandingan yang sama, solusi iteratif akan selalu mengalahkan solusi rekursif karena overhead dalam fungsi panggilan seperti yang dia sebutkan. Namun, jika seseorang hanya peduli tentang mencari min dan max beberapa nomor (seperti Eric Belair), tidak ada yang akan melihat perbedaan dalam komputer saat ini dengan salah satu pendekatan di atas. Untuk array besar, perbedaannya bisa signifikan.

Meskipun solusi ini dan solusi yang diberikan oleh Matthew Brubaker memiliki kompleksitas O (n), dalam prakteknya seseorang harus hati-hati menilai konstanta tersembunyi yang terlibat. Jumlah perbandingan dalam solusinya adalah 2n. Percepatan yang diperoleh dengan solusi dengan perbandingan 3n / 2 dibandingkan dengan perbandingan 2n akan terlihat.


27
2017-07-26 07:41



Kecuali susunannya disortir, itulah yang terbaik yang akan Anda dapatkan. Jika diurutkan, cukup ambil elemen pertama dan terakhir.

Tentu saja, jika tidak disortir, maka pengurutan pertama dan meraih yang pertama dan terakhir dijamin kurang efisien daripada hanya mengulang satu kali. Bahkan algoritma pengurutan terbaik harus melihat setiap elemen lebih dari satu kali (rata-rata waktu O (log N) untuk setiap elemen, yaitu total O (N * Log N). Pemindaian sederhana sekali saja hanya O (N).

Jika Anda menginginkan akses cepat ke elemen terbesar dalam struktur data, lihatlah tumpukan untuk cara yang efisien untuk menyimpan objek dalam semacam pesanan.


19
2018-01-08 16:10



Anda harus mengulang melalui larik, tidak ada cara lain untuk memeriksa semua elemen. Hanya satu koreksi untuk kode - jika semua elemen negatif, maxValue akan menjadi 0 di bagian akhir. Anda harus menginisialisasi dengan nilai minimum yang mungkin untuk integer.
Dan jika Anda akan mencari array berkali-kali adalah ide yang baik untuk mengurutkan terlebih dahulu, daripada pencarian lebih cepat (pencarian biner) dan elemen minimum dan maksimum hanyalah yang pertama dan terakhir.


12
2018-01-08 16:03



Tergantung pada apa yang Anda sebut "terbaik." Dari sudut pandang teoritis, Anda tidak dapat memecahkan masalah dalam waktu kurang dari O(n) dalam mesin Turing deterministik.

Algorif yang naif adalah loop terlalu dan memperbarui min, maks. Namun, solusi rekursif akan membutuhkan lebih sedikit perbandingan daripada algoritma naive, jika Anda ingin mendapatkan min, max secara bersamaan (tidak selalu lebih cepat karena fungsi panggilan overhead).

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) } ;
}

Solusi yang paling sederhana adalah memilah dan mendapatkan item pertama dan terakhir, meskipun itu jelas bukan yang tercepat;)

Solusi terbaik, kinerja-bijaksana, untuk menemukan minimum atau maksimum adalah algoritma naif yang Anda tulis (dengan satu loop).


4
2018-01-08 16:06



Math.max () sebenarnya kode as3 dikompilasi ke AVM2 opcode, dan dengan demikian tidak lebih "asli" daripada kode as3 lainnya. Sebagai akibatnya, itu belum tentu implementasi tercepat.

Sebenarnya, mengingat bahwa itu bekerja pada tipe Array, itu lebih lambat daripada yang ditulis dengan hati-hati kode usign Vector:

Saya melakukan perbandingan patokan cepat dari beberapa implementasi Vector dan Array yang naif dari Math.max, menggunakan PerformanceTest dari gskinner (Vector dan Array yang diisi dengan Angka acak yang identik). Implementasi Vector tercepat ternyata lebih dari 3x lebih cepat daripada Math.max dengan SDK / release player terbaru (flash player WIN 14,0,0,122 RELEASE, dikompilasi dengan AIR SDK 14):

rata-rata 3,5 ms untuk 1.000.000 nilai, dibandingkan dengan Math.max () rata-rata 11ms:

function max(values:Vector.<Number>):Number
{
    var max:Number = Number.MIN_VALUE;
    var length:uint = values.length;
    for (var i:uint = 0; i < length ; ++i)
        if (values[i] > max)
            max = values[i];
    return max;
}

Kesimpulannya adalah bahwa jika Anda prihatin dengan kinerja, Anda harus menggunakan Vector over Array di mana saja Anda dapat di tempat pertama, dan tidak selalu bergantung pada implementasi standar, terutama ketika mereka memaksa penggunaan Array

PS: implementasi yang sama dengan untuk setiap () loop 12x lebih lambat ...!


3
2017-08-27 13:47



Ini tergantung pada persyaratan aplikasi dunia nyata.

Jika pertanyaan Anda hanyalah hipotetis, maka dasar-dasarnya sudah dijelaskan. Ini adalah pencarian tipikal vs masalah sortir. Sudah disebutkan bahwa secara algoritme Anda tidak akan mencapai lebih baik daripada O (n) untuk kasus itu.

Namun, jika Anda melihat penggunaan praktis, hal-hal menjadi lebih menarik. Anda kemudian harus mempertimbangkan seberapa besar array, dan proses yang terlibat dalam menambah dan menghapus dari kumpulan data. Dalam kasus ini, yang terbaik adalah mengambil 'pukulan' komputasional pada waktu penyisipan / penghapusan dengan menyortir dengan cepat. Penyisipan ke dalam susunan yang telah diurutkan sebelumnya tidak terlalu mahal.

Respons kueri tercepat untuk permintaan Min Max akan selalu dari array yang diurutkan, karena seperti yang telah disebutkan orang lain, Anda cukup mengambil elemen pertama atau terakhir - memberi Anda biaya O (1).

Untuk sedikit lebih banyak penjelasan teknis tentang biaya komputasi yang terlibat, dan notasi O Big, periksa artikel Wikipedia sini.

Nick.


2
2018-01-08 16:18



Jika Anda sedang membangun array sekali dan ingin menemukan maksimum hanya sekali, iterasi adalah yang terbaik yang dapat Anda lakukan.

Ketika Anda ingin memodifikasi larik dan terkadang ingin mengetahui elemen maksimum, Anda harus menggunakan a Antrean Prioritas. Salah satu struktur data terbaik untuk itu adalah a Fibonacci Heap, jika ini terlalu rumit, gunakan a Tumpukan Biner yang lebih lambat tapi masih bagus.

Untuk menemukan minimum dan maksimum, cukup buat dua tumpukan dan ubah tanda angka di salah satunya.


2
2018-01-08 16:12



Harap perhatikan bahwa menyortir array hanya akan lebih cepat yang mengulang hingga ukuran tertentu dari array. Jika array Anda kecil (dan akan seperti itu setiap saat) maka solusi Anda baik-baik saja. Tetapi jika mungkin terlalu besar Anda harus menggunakan kondisional untuk menggunakan pendekatan semacam ketika array kecil, dan iterasi normal ketika terlalu besar


1
2018-01-28 21:21



Jika Anda ingin menemukan kedua min dan max pada saat yang sama, loop dapat dimodifikasi sebagai berikut:

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

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

Ini harus mencapai waktu O (n).


0
2018-01-08 16:29