Bukan rahasia lagi bahwa salah satu hiburan favorit bagi pengembang perangkat lunak adalah mewawancarai pemberi kerja. Kita semua melakukan ini dari waktu ke waktu dan untuk alasan yang sangat berbeda. Dan yang paling jelas dari mereka - mencari pekerjaan - saya pikir, bukan yang paling umum. Menghadiri wawancara adalah cara yang baik untuk tetap fit, mengulangi dasar-dasar yang terlupakan, dan mempelajari sesuatu yang baru. Dan jika berhasil, tingkatkan juga rasa percaya diri. Kami bosan, kami menetapkan sendiri status "terbuka untuk menawarkan" dalam beberapa jenis jaringan sosial "bisnis" seperti
"LinkedIn" - dan pasukan manajer sumber daya manusia sudah menyerang kotak masuk kami untuk pesan yang masuk.
Dalam prosesnya, sementara semua keributan ini terjadi, kita dihadapkan dengan banyak pertanyaan yang, seperti yang mereka katakan di sisi lain dari tirai yang runtuh secara implisit, adalah “cincin bel”, dan rinciannya tersembunyi di balik
kabut perang . Mereka paling sering dipanggil hanya dalam pengujian oleh algoritma dan struktur data (secara pribadi, saya tidak punya data sama sekali) dan sebenarnya wawancara.
Salah satu pertanyaan paling umum dalam wawancara untuk programmer dari spesialisasi apa pun adalah daftar. Misalnya, daftar yang ditautkan secara tunggal. Dan algoritma dasar terkait. Misalnya, putar balik. Dan biasanya ini terjadi entah bagaimana seperti ini: "Bagus, tapi bagaimana Anda akan memperluas daftar yang terhubung sendiri?" Hal utama adalah mengejutkan pelamar dengan pertanyaan ini.
Sebenarnya, semua ini mendorong saya untuk menulis ulasan singkat ini untuk pengingat dan peneguhan yang konstan. Jadi, bercanda, lihat!
Daftar tertaut tunggal
Daftar tertaut adalah salah satu
struktur data dasar. Setiap elemen (atau node) terdiri dari, pada kenyataannya, data yang tersimpan dan tautan ke elemen tetangga. Daftar tertaut tunggal hanya menyimpan tautan ke elemen berikutnya dalam struktur, dan daftar
tertaut dua kali menyimpan tautan ke berikutnya dan sebelumnya. Organisasi data semacam itu memungkinkan mereka untuk ditempatkan di area memori apa pun (tidak seperti, misalnya, sebuah
array , semua elemen yang harusnya ditempatkan di memori satu demi satu).
Ada banyak lagi yang bisa dikatakan tentang daftar, tentu saja: mereka bisa melingkar (mis., Elemen terakhir menyimpan tautan ke yang pertama) atau tidak (mis. Tidak ada tautan ke elemen terakhir). Daftar dapat diketik, mis. mengandung data dengan tipe yang sama atau tidak. Dan seterusnya dan seterusnya.
Lebih baik coba menulis beberapa kode. Sebagai contoh, entah bagaimana Anda bisa membayangkan daftar simpul:
final class Node<T> { let payload: T var nextNode: Node? init(payload: T, nextNode: Node? = nil) { self.payload = payload self.nextNode = nextNode } }
"Generik" adalah jenis yang mampu menyimpan muatan jenis apa pun di bidang
payload .
Daftar itu sendiri diidentifikasi secara mendalam oleh simpul pertama:
final class SinglyLinkedList<T> { var firstNode: Node<T>? init(firstNode: Node<T>? = nil) { self.firstNode = firstNode } }
Node pertama dinyatakan opsional, karena daftar mungkin kosong.
Secara teori, tentu saja, di kelas Anda perlu mengimplementasikan semua metode yang diperlukan - menyisipkan, menghapus, akses ke node, dll, tetapi kami akan melakukannya lain waktu. Pada saat yang sama, kami akan memeriksa apakah menggunakan struct (yang Apple secara aktif mendorong kita dengan contoh kita) adalah pilihan yang lebih baik, dan mungkin mengingat pendekatan "Copy-on-write" .Penyebaran daftar tautan tunggal
Cara pertama. Siklus
Sudah waktunya untuk turun ke bisnis yang kita di sini hari ini! Dan cara paling efektif untuk menghadapinya adalah dua cara. Yang pertama adalah loop sederhana, dari yang pertama ke yang terakhir.
Siklus bekerja dengan tiga variabel, yang sebelum awal diberi nilai node sebelumnya, saat ini dan berikutnya. (Pada saat ini, nilai node sebelumnya secara alami kosong.) Siklus dimulai dengan memeriksa bahwa node berikutnya tidak kosong, dan jika demikian, tubuh siklus dieksekusi. Tidak ada keajaiban yang terjadi di loop: pada simpul saat ini, bidang yang merujuk ke elemen berikutnya diberikan tautan ke yang sebelumnya (pada iterasi pertama, nilai tautan, masing-masing, diatur ulang, yang sesuai dengan keadaan hubungan di simpul terakhir). Baik dan selanjutnya variabel yang sesuai dengan node sebelumnya, saat ini dan selanjutnya diberi nilai baru. Setelah keluar dari loop, node saat ini (yaitu, iterable terakhir secara umum) ditugaskan nilai tautan baru ke node berikutnya, karena keluar dari loop terjadi tepat pada saat simpul terakhir dalam daftar menjadi arus.
Dalam kata-kata, tentu saja, semua ini terdengar aneh dan tidak dapat dipahami, jadi lebih baik untuk melihat kode:
extension SinglyLinkedList { func reverse() { var previousNode: Node<T>? = nil var currentNode = firstNode var nextNode = firstNode?.nextNode while nextNode != nil { currentNode?.nextNode = previousNode previousNode = currentNode currentNode = nextNode nextNode = currentNode?.nextNode } currentNode?.nextNode = previousNode firstNode = currentNode } }
Untuk verifikasi, kami menggunakan daftar node yang payloadnya merupakan pengidentifikasi
integer sederhana. Buat daftar sepuluh elemen:
let node = Node(payload: 0)
Segalanya tampak baik-baik saja, tetapi kita adalah manusia, bukan komputer, dan akan menyenangkan bagi kita untuk mendapatkan bukti visual dari kebenaran daftar yang dibuat dan algoritma yang dijelaskan di atas. Mungkin cetakan sederhana sudah cukup. Untuk membuat output dapat dibaca, tambahkan implementasi protokol
CustomStringConvertible node dengan pengenal integer:
extension Node: CustomStringConvertible where T == Int { var description: String { let firstPart = """ Node \(Unmanaged.passUnretained(self).toOpaque()) has id \(payload) and """ if let nextNode = nextNode { return firstPart + " next node \(nextNode.payload)." } else { return firstPart + " no next node." } } }
... Dan daftar yang sesuai untuk menampilkan semua node secara berurutan:
extension SinglyLinkedList: CustomStringConvertible where T == Int { var description: String { var description = """ List \(Unmanaged.passUnretained(self).toOpaque()) """ if firstNode != nil { description += " has nodes:\n" var node = firstNode while node != nil { description += (node!.description + "\n") node = node!.nextNode } return description } else { return description + " has no nodes." } } }
Representasi string dari tipe kami akan berisi alamat di memori dan pengenal integer. Dengan menggunakannya, kami mengatur pencetakan daftar sepuluh simpul yang dihasilkan:
print(String(describing: list))
Luaskan daftar ini dan cetak lagi:
list.reverse() print(String(describing: list))
Anda mungkin memperhatikan bahwa alamat dalam memori daftar dan node tidak berubah, dan node daftar dicetak dalam urutan terbalik. Referensi ke elemen berikutnya dari simpul sekarang menunjuk ke yang sebelumnya (yaitu, misalnya, elemen berikutnya dari simpul "5" sekarang bukan "6", tetapi "4"). Dan itu berarti kita berhasil!
Cara kedua. Rekursi
Cara kedua yang diketahui untuk melakukan putar balik yang sama didasarkan pada
rekursi . Untuk mengimplementasikannya, kita akan mendeklarasikan fungsi yang mengambil simpul pertama dari daftar, dan mengembalikan simpul pertama "baru" (yang merupakan yang terakhir sebelum).
Parameter dan nilai pengembalian adalah opsional, karena di dalam fungsi ini dipanggil lagi dan lagi pada setiap simpul berikutnya sampai kosong (mis. Sampai akhir daftar tercapai). Oleh karena itu, dalam tubuh fungsi, perlu untuk memeriksa apakah simpul yang disebut fungsi kosong dan apakah simpul ini memiliki yang berikut. Jika tidak, maka fungsi mengembalikan apa yang diteruskan ke argumen.
Sebenarnya, saya jujur mencoba menggambarkan algoritma lengkap dalam kata-kata, tetapi pada akhirnya saya menghapus hampir semuanya, karena hasilnya tidak mungkin untuk dipahami. Untuk menggambar diagram alur dan secara formal menjelaskan langkah-langkah algoritma - juga, dalam hal ini, saya pikir itu tidak masuk akal, karena akan lebih nyaman bagi Anda dan saya untuk hanya membaca dan mencoba memahami kode
Swift :
extension SinglyLinkedList { func reverseRecursively() { func reverse(_ node: Node<T>?) -> Node<T>? { guard let head = node else { return node } if head.nextNode == nil { return head } let reversedHead = reverse(head.nextNode) head.nextNode?.nextNode = head head.nextNode = nil return reversedHead } firstNode = reverse(firstNode) } }
Algoritme itu sendiri "dibungkus" oleh metode dari jenis daftar aktual, untuk kenyamanan panggilan.
Itu terlihat lebih pendek, tetapi, menurut saya, lebih sulit untuk dipahami.
Kami menyebut metode ini pada hasil dari penyebaran sebelumnya dan mencetak hasil baru:
list.reverseRecursively() print(String(describing: list))
Dapat dilihat dari output bahwa semua alamat dalam memori tidak berubah lagi, dan node sekarang mengikuti dalam urutan asli (yaitu, mereka "dikerahkan" lagi). Dan itu berarti kita melakukannya dengan benar lagi!
Kesimpulan
Jika Anda melihat metode pembalikan dengan hati-hati (atau melakukan percobaan dengan penghitungan panggilan), Anda akan melihat bahwa loop dalam kasus pertama dan panggilan metode internal (rekursif) dalam kasus kedua terjadi satu kali kurang dari jumlah node dalam daftar (dalam kasus kami, sembilan kali). Anda juga dapat memperhatikan apa yang terjadi di sekitar loop dalam kasus pertama - urutan penugasan yang sama - dan untuk pemanggilan metode pertama, non-rekursif, dalam kasus kedua. Ternyata dalam kedua kasus "lingkaran" diulang tepat sepuluh kali untuk daftar sepuluh node. Dengan demikian, kami memiliki
kompleksitas linier untuk kedua algoritma -
O (n) .
Secara umum, kedua algoritma yang dijelaskan ini dianggap paling efektif untuk menyelesaikan masalah ini. Mengenai kompleksitas komputasi, tidak mungkin menghasilkan algoritma dengan nilai yang lebih rendah: dengan satu atau lain cara, Anda perlu "mengunjungi" setiap node untuk menetapkan nilai baru ke yang disimpan di dalam tautan.
Fitur lain yang layak disebut adalah "kompleksitas memori yang dialokasikan". Kedua algoritma yang diusulkan membuat sejumlah variabel baru (tiga dalam kasus pertama dan satu dalam yang kedua). Ini berarti bahwa jumlah memori yang dialokasikan tidak tergantung pada karakteristik kuantitatif dari data input dan dijelaskan oleh fungsi konstan - O (1).
Tetapi, pada kenyataannya, dalam kasus kedua ini tidak demikian. Bahaya rekursi adalah memori tambahan dialokasikan untuk setiap panggilan rekursif pada
stack . Dalam kasus kami, kedalaman rekursi sesuai dengan jumlah data input.
Dan akhirnya, saya memutuskan untuk bereksperimen sedikit lebih: dengan cara yang sederhana dan primitif saya mengukur waktu eksekusi absolut dari dua metode untuk jumlah data input yang berbeda. Seperti ini:
let startDate = Date().timeIntervalSince1970
Dan inilah yang saya dapatkan (ini adalah data mentah dari
Playground ):
(Sayangnya, komputer saya belum menguasai nilai yang lebih besar.)
Apa yang bisa dilihat dari tabel? Belum ada yang istimewa. Meskipun sudah terlihat bahwa metode rekursif berperilaku sedikit lebih buruk dengan jumlah node yang relatif kecil, tetapi di suatu tempat antara 100 dan 1000 mulai terlihat lebih baik.
Saya juga mencoba tes sederhana yang sama di dalam proyek
"Xcode" lengkap. Hasilnya adalah sebagai berikut:
Pertama, perlu disebutkan bahwa hasilnya diperoleh setelah mengaktifkan mode optimisasi "agresif" yang ditujukan untuk kecepatan eksekusi (
-Ofast ), yang sebagian karena jumlahnya sangat kecil. Menarik juga bahwa dalam kasus ini metode rekursif menunjukkan dirinya sedikit lebih baik, sebaliknya, hanya pada ukuran data input yang sangat kecil, dan sudah ada dalam daftar 100 node, metode ini hilang. Dari 100.000, ia membuat program berakhir secara tidak normal.
Kesimpulan
Saya mencoba untuk membahas topik yang agak klasik dari sudut pandang bahasa pemrograman favorit saya saat ini, dan saya harap Anda penasaran untuk mengikuti perkembangannya dan juga diri saya sendiri. Saya juga sangat senang jika Anda berhasil mempelajari sesuatu yang baru - maka saya pasti membuang-buang waktu saya di artikel ini (bukannya duduk dan menonton
acara TV ).
Jika seseorang memiliki keinginan untuk melacak aktivitas sosial saya, di sini ada tautan ke "Twitter" saya , di mana pertama-tama ada tautan ke pos baru saya dan sedikit lagi.