Penulis materi, terjemahan yang kami terbitkan hari ini, mengatakan bahwa ia yakin bahwa banyak pengembang JavaScript terutama menggunakan tipe data seperti
Number ,
String ,
Object ,
Array , dan
Boolean . Dalam kebanyakan kasus, ini sudah cukup. Tetapi jika Anda perlu membuat kode secepat dan scalable mungkin, penggunaan tipe data ini tidak selalu dibenarkan.
Pada artikel ini, kita akan berbicara tentang bagaimana, menggunakan tipe data
Set , yang menyediakan kemampuan untuk bekerja dengan koleksi nilai unik, membuat kode lebih cepat. Ini terutama berlaku untuk kode proyek skala besar. Tipe
Array dan
Set memiliki banyak kesamaan, tetapi menggunakan tipe data
Set dapat memberikan programmer fitur yang jelas terwujud selama pelaksanaan program yang tidak dimiliki
Array .
Apa perbedaan antara Array dan Set tipe data?
Fitur utama dari tipe data
Array (kami akan memanggil objek dari jenis ini "array") adalah bahwa array adalah kumpulan nilai yang diindeks. Ini berarti bahwa data dalam array disimpan menggunakan indeks.
const arr = [A, B, C, D]; console.log(arr.indexOf(A));
Tidak seperti array, objek dari tipe
Set (kami akan menyebutnya "koleksi") adalah koleksi yang berisi data dalam format kunci / nilai. Alih-alih menggunakan indeks, koleksi menyimpan item menggunakan kunci. Elemen yang disimpan dalam koleksi dapat diurutkan sesuai urutannya ditambahkan ke koleksi, sementara koleksi tidak dapat menyimpan elemen yang sama. Dengan kata lain, semua elemen koleksi harus unik.
Apa kekuatan utama dari koleksi ini?
Jika Anda membandingkan koleksi dan array, maka Anda dapat menemukan beberapa keunggulan dibandingkan koleksi di atas array, terutama terlihat dalam situasi di mana kinerja program penting:
- Cari item. Metode array
indexOf() dan includes() , digunakan untuk mencari elemen dan memeriksa apakah suatu elemen memiliki elemen, bekerja perlahan. - Menghapus item. Item dapat dihapus dalam koleksi berdasarkan nilainya. Dalam sebuah array, ekuivalen dari tindakan semacam itu akan menggunakan metode
splice() , berdasarkan indeks elemen. Seperti halnya pencarian item, menghapus item menggunakan indeks adalah operasi yang lambat. - Sisipkan item. Jauh lebih cepat untuk menambahkan elemen ke koleksi daripada menggunakan metode seperti
push() dan unshift() dalam array. - Bekerja dengan nilai
NaN . Metode indexOf() tidak dapat digunakan untuk menemukan nilai NaN dalam array, saat menggunakan metode koleksi has() , Anda dapat menentukan apakah memiliki NaN di dalamnya. - Menghapus item duplikat.
Set objek hanya menyimpan nilai unik. Jika Anda perlu menghindari menyimpan elemen duplikat dalam beberapa struktur data, ini adalah keunggulan signifikan mereka daripada array. Ketika bekerja dengan array untuk menghapus elemen duplikat harus menulis kode tambahan.
Daftar lengkap metode objek objek
Set dapat ditemukan di
sini .
Pada kompleksitas waktu algoritma
Metode yang digunakan array untuk mencari elemen memiliki kompleksitas waktu linear - O (N). Dengan kata lain, waktu pencarian elemen sebanding dengan ukuran array.
Tidak seperti array, metode yang digunakan oleh koleksi untuk menemukan, menghapus, dan menambahkan elemen memiliki kompleksitas waktu O (1). Ini berarti bahwa ukuran koleksi hampir tidak berpengaruh pada waktu kerja metode tersebut.
Di sini Anda dapat membaca lebih lanjut tentang kompleksitas waktu dari algoritma.
Seberapa cepat koleksi daripada array?
Meskipun indikator kinerja kode JavaScript sangat dipengaruhi oleh berbagai faktor, khususnya, mereka bergantung pada sistem tempat kode dijalankan, pada runtime kode yang digunakan, pada ukuran data yang diproses, saya harap hasil pengujian saya akan memberi Anda kesempatan untuk membandingkan array dan koleksi dari sudut pandang praktis, dan pahami bagaimana koleksi lebih cepat daripada array. Sekarang kita akan mempertimbangkan tiga tes sederhana dan menganalisis hasilnya.
Preparation Persiapan tes
Sebelum melakukan tes apa pun, mari buat array dengan sejuta elemen dan koleksi yang sama. Demi kesederhanaan, kami akan menggunakan siklus, nilai penghitung pertama yang akan 0, dan yang terakhir - 999999:
let arr = [], set = new Set(), n = 1000000; for (let i = 0; i < n; i++) { arr.push(i); set.add(i); }
▍Test No. 1: memeriksa keberadaan elemen dalam array dan koleksi
Pertama, kami akan memeriksa keberadaan elemen
123123 dalam array dan koleksi, mengetahui sebelumnya bahwa elemen tersebut ada dalam struktur data ini.
let result; console.time('Array'); result = arr.indexOf(123123) !== -1; console.timeEnd('Array'); console.time('Set'); result = set.has(123123); console.timeEnd('Set');
Berikut adalah hasil dari tes ini:
Array: 0.173ms Set: 0.023ms
Koleksi ini 7,54 kali lebih cepat dari array.
▍Test No. 2: penyisipan elemen
Sekarang mari kita coba menambahkan elemen ke array dan koleksi.
console.time('Array'); arr.push(n); console.timeEnd('Array'); console.time('Set'); set.add(n); console.timeEnd('Set');
Inilah yang terjadi:
Array: 0.018ms Set: 0.003ms
Koleksinya 6,73 kali lebih cepat dari array.
▍Test 3: hapus satu item
Sekarang mari kita hapus item dari setiap struktur data (misalnya, yang ditambahkan dalam tes sebelumnya). Array tidak memiliki metode bawaan untuk menghapus elemen, jadi kami akan membuat fungsi pembantu untuk menjaga kode kami dalam kondisi baik:
const deleteFromArr = (arr, item) => { let index = arr.indexOf(item); return index !== -1 && arr.splice(index, 1); };
Dan di sini adalah kode tes:
console.time('Array'); deleteFromArr(arr, n); console.timeEnd('Array'); console.time('Set'); set.delete(n); console.timeEnd('Set');
Hasilnya adalah sebagai berikut:
Array: 1.122ms Set: 0.015ms
Dalam hal ini, koleksinya adalah 74,13 kali lebih cepat daripada array!
Secara umum, dapat dicatat bahwa kinerja kode dapat meningkat secara signifikan dengan menggunakan koleksi, bukan array. Perhatikan beberapa contoh praktis.
Contoh # 1: menghapus nilai duplikat dari array
Jika Anda perlu menghapus nilai duplikat dari array dengan cepat, Anda bisa mengubahnya menjadi koleksi. Ini mungkin cara termudah untuk menghilangkan nilai duplikat:
const duplicateCollection = ['A', 'B', 'B', 'C', 'D', 'B', 'C'];
Contoh 2: Tugas wawancara di Google
Dalam salah satu
materi saya
, saya memeriksa empat opsi untuk menjawab pertanyaan yang diajukan oleh pewawancara dari Google. Wawancara dilakukan dengan menggunakan C ++, tetapi jika JavaScript digunakan sebagai ganti bahasa ini, struktur data
Set akan digunakan untuk menyelesaikan masalah.
Jika Anda ingin memahami jawaban untuk pertanyaan ini lebih dalam - baca artikel di atas. Di sini saya hanya menunjukkan solusi yang sudah jadi.
▍ Tugas
Diberikan array bilangan bulat yang tidak disortir dan nilai
sum . Tulis fungsi yang mengembalikan
true jika, sebagai hasil menambahkan dua elemen array ini, kita mendapatkan nilai
sum . Jika tidak ada elemen seperti itu dalam array, fungsi tersebut akan mengembalikan
false .
Ternyata, misalnya, bahwa jika kita diberi array
[3, 5, 1, 4] dan nilai
sum adalah
9 , maka fungsi tersebut harus mengembalikan
true , karena
4+5=9 .
OlSolusi
Anda dapat mendekati masalah ini menggunakan ide berikut: Anda perlu mengulangi lebih dari array, membuat struktur
Set data saat diurutkan, ke mana nilai akan ditambahkan yang melengkapi nilai yang ditemukan ke nilai
sum .
Mari kita analisis ide ini menggunakan contoh array di atas. Ketika kita bertemu
3 , kita dapat menambahkan angka
6 ke koleksi, karena kita tahu bahwa kita perlu menemukan dua angka yang totalnya
9 . Lalu, setiap kali kita menemukan nilai baru dari array, kita dapat memeriksa koleksi dan melihat apakah ada. Ketika kami memenuhi angka
5 , kami akan menambahkan
4 ke koleksi. Dan ketika, akhirnya, kami sampai ke nomor
4 , kami menemukannya di koleksi dan dapat mengembalikan
true .
Berikut ini solusi untuk masalah ini:
const findSum = (arr, val) => { let searchValues = new Set(); searchValues.add(val - arr[0]); for (let i = 1, length = arr.length; i < length; i++) { let searchVal = val - arr[i]; if (searchValues.has(arr[i])) { return true; } else { searchValues.add(searchVal); } }; return false; };
Dan inilah solusi yang lebih ringkas:
const findSum = (arr, sum) => arr.some((set => n => set.has(n) || !set.add(sum - n))(new Set));
Karena kompleksitas waktu metode
Set.prototype.has() adalah O (1), menggunakan struktur data
Set untuk menyimpan angka yang melengkapi angka-angka yang ditemukan dalam array ke nilai yang diberikan memungkinkan Anda untuk menemukan solusi dalam waktu linier (O (N)).
Jika solusinya bergantung pada metode
Array.prototype.indexOf() atau pada metode
Array.prototype.includes() , kompleksitas waktu masing-masing adalah O (N), maka kompleksitas waktu total dari algoritma tersebut adalah O (N
2 ). Akibatnya, ia akan menjadi jauh lebih lambat.
Ringkasan
Jika Anda belum pernah menemukan tipe data
Set di JavaScript sebelumnya, maka kami harap sekarang, setelah mengetahuinya, Anda akan dapat menggunakannya dengan manfaat dalam proyek Anda.
Pembaca yang budiman! Bagaimana Anda menerapkan struktur data
Set di kode Anda?