Big O: [2] Pengaturan Waktu Pada Kode Kita

#bigonotation #algorithms #javascript

Bismillahirrahmanirrahim, Mari kita lanjutkan pembahasan tentang Big O Notation dari artikel sebelumnya. Bagi yang belum membaca artikel sebelumnya mungkin bisa dibaca terlebih dulu : Pendahuluan Big O

Sekarang kita akan masuk pada contoh konkrit yang akan sedikit menyenggol Big O Notation

Contoh:
Kita misalkan bahwa kita akan menulis sebuah fungsi yang akan menjumlahkan bilangan 1 sampai dengan n, 1+2+3. . .+n dan satu contoh solusi yang paling mudah dari permasalahan tersebut adalah sebagai berikut:

function jumlahDeret(n) {
 var jumlah = 0;

 for(var i = 1; i <= n; i++) {
  jumlah += i;
 };

 return jumlah;
}

Kita men-set nilai awal dari variabel jumlah sebesar 0. Kemudian for akan melakukan perulangan mulai dari bilangan 1 berdasarkan statement var i = 1; sampai dengan bilangan n berdasarkan statement i <= n;
dan kemudian pada setiap iterasinya i akan dijumlahkan dengan variabel jumlah berdasarkan aksi jumlah += i;

Setelah perulangan selesai maka fungsi akan mengembalikan nilai jumlah.

Selanjutnya kita panggil fungsi tersebut untuk melakukan penjumlahan, untuk melihat hasilnya kita dapat menggunakan console.log.

console.log(jumlahDeret(3));

Dan output-nya adalah 6, yang berarti 1+2+3.

Oke, selanjutnya contoh solusi yang kedua adalah sebagai berikut:

function jumlahDeret(n) {
 return n * (n + 1) / 2;
}

Dari contoh yang kedua ini kita bisa melihat banyak sekali perbedaan, bahkan benar-benar berbeda dari contoh yang pertama. Pada contoh yang kedua ini kita tidak menggunakan perulangan, melainkan kita hanya menggunakan formula matematika yaitu n * (n + 1) / 2

Jika kita jalankan dengan memberikan nilai n yang sama yaitu 3 maka outputnya pun akan sama, 6.

console.log(jumlahDeret(3));

// 3 * (3 + 1) / 2

Nah, di sinilah topik utama pembahasan kita kali ini. Mana solusi yang lebih baik? Contoh 1 atau Contoh 2 ?

Sebelum melangkah jauh ke sana, mari kita uraikan lagi tentang arti lebih baik.

Apa yang dimaksud lebih baik di sini?

Apakah maksudnya adalah lebih cepat saat melakukan penghitungan? bahkan dengan bilangan yang lebih besar? seperti bilangan 1 juta misalnya, atau 1 miliar?
Apakah lebih sedikit memakan memori? yang digunakan untuk menyimpan hasil penghitungan yang dilakukan saat fungsi dipanggil?
Atau apakah kodenya mudah dibaca oleh orang lain?

Hmm baiklah, sebenarnya semua arti di atas adalah arti yang valid. Dimana arti kata lebih baik mencakup dari ketiganya. Namun kita akan memfokuskan pembahasan kita pada arti lebih cepat dan lebih sedikit memakan memori karena kedua hal tersebut lebih penting ketimbang arti mudah dibaca.

Kita akan lebih dulu fokus mengevaluasi mana solusi yang memiliki runtime paling cepat. 1 atau 2?

Kita akan menggunakan fungsi bawaan milik Javascript untuk melakukan perhitungan waktu yaitu dengan method performance. Jadi kodenya seperti ini,

Contoh 1

function jumlahDeret(n) {
 var jumlah = 0;

 for(var i = 1; i <= n; i++) {
  jumlah += i;
 };

 return jumlah;
}

var w1 = performance.now();
jumlahDeret(1000000000);
var w2 = performance.now();

console.log(`Waktu berlalu: ${(w2 - w1) / 1000} detik`);

Variabel w1 akan memberitahu kita berapa milidetik yang berlalu sejak document dibuat. Terutama waktu yang didapatkan pada saat window terbuka, kemudian kita menyimpan waktu yang sudah didapatkan tersebut ke dalam variabel w1 sebelum fungsi jumlahDeret() kita panggil.

Selanjutnya kita memanggil fungsi jumlahDeret() yang argumennya berupa bilangan sebesar 1 miliar.

Kemudian kita dapatkan lagi waktu performance setelah fungsi jumlahDeret() dijalankan. Seharusnya ada penambahan beberapa milidetik akibat proses dari fungsi jumlahDeret() yang dipanggil.

Oke, kita sudah memiliki dua bilangan sekarang yaitu w1 dan w2. Untuk mendapatkan selisih waktunya maka kita gunakan formula matematika w2 - w1 / 1000. Kenapa dibagi 1000? itu karena untuk mengonversi dari milidetik ke detik.

Dan output yang saya dapatkan dari contoh 1 adalah sebagai berikut:

Waktu berlalu: 1.3605600000009872 detik

Output bisa berubah-ubah karena berkaitan dengan waktu proses.

Selanjutnya kita lakukan cara yang sama pada contoh 2:

function jumlahDeret(n) {
 return n * (n + 1) / 2;
}

var w1 = performance.now();
jumlahDeret(1000000000);
var w2 = performance.now();

console.log(`Waktu berlalu: ${(w2 - w1) / 1000} detik`);

Dan output yang saya dapatkan adalah:

Waktu berlalu: 0.00009499999578110874 detik

Sekarang kita sudah mengetahui mana solusi yang memiliki runtime atau waktu proses yang lebih singkat dengan data inputan yang sama yaitu 1 miliar.

Dan jreng jreng jreng, pemenangnya adalah Contoh 2.

Proses yang saya contohkan di atas sebenarnya bukanlah yang paling dapat diandalkan dalam pengaturan waktu.

Seperti sebelum dan sesudah kemudian membandingkannya dengan fungsi yang lain. Bagaimana fungsi yang ini lebih efisien daripada fungsi yang itu? apakah berdasarkan persentase kecepatannya? atau apakah karena saya melakukan pengurangan terhadap milidetiknya? ini jadi agak sedikit kurang jelas.

Itu semua membawa kita pada permasalahan terhadap waktu, yang menjadikannya kurang dapat diandalkan. Apa saja masalahnya?

Mesin yang berbeda akan merekam penggunaan waktu yang berbeda pula, pengaturan waktu jadi bergantung pada spesifikasi komputer/laptop yang kita punya.
Bahkan mesin yang sama pun akan merekam penggunaan waktu yang berbeda,
Jadi, untuk mendapatkan algoritma yang cepat, menggunakan metode kecepatan waktu tidaklah cukup

Lalu bagaimana cara kita menelusuri kode kita dan berbicara secara umum tentang kode mana yang lebih baik?

Saya tidak bilang kalau menggunakan metode ini merupakan ide yang buruk. Tapi alangkah baiknya jika ada cara lain yang tidak perlu melibatkan men-setup file baru untuk mendapatkan waktu seperti cara di atas.

Sekarang kita hanya melakukan tes pada kode yang hanya memakan waktu tidak sampai lima detik.

Lalu bagaimana jika kita memiliki kode yang membutuhkan waktu satu jam untuk sesuatu yang besar dan kita membandingkannya dengan versi lain yang membutuhkan waktu empat jam?

Kita tidak ingin melakukan tes tersebut untuk mencari tahu mana yang lebih cepat. Yang kita mau hanya memberikan nilai dan kemudian berbicara secara umum bagaimana membandingkan kode tanpa harus melakukan semua cara di atas.

Itulah yang akan dilakukan oleh Big O, dan akan hadir di artikel berikutnya. Sampai Jumpa ! :)