Memilih struktur data yang tepat di Swift

Halo lagi. Sebelum berangkat untuk akhir pekan kami ingin berbagi dengan Anda terjemahan materi yang disiapkan khusus untuk kursus dasar "iOS-developer . "

---

Memutuskan struktur data mana yang digunakan untuk mewakili sekumpulan nilai yang diberikan seringkali jauh lebih sulit daripada yang terlihat. Karena setiap jenis struktur data dioptimalkan untuk sejumlah kasus penggunaan tertentu, memilih pas yang tepat untuk setiap kumpulan data sering kali dapat berdampak besar pada kinerja kode kita.

Pustaka Swift standar dilengkapi dengan tiga struktur data utama - Array , Dictionary , dan Set , yang masing-masing memiliki serangkaian optimisasi, plus dan minus. Mari kita lihat beberapa karakteristik mereka, serta kasus-kasus di mana kita mungkin perlu melampaui perpustakaan standar untuk menemukan struktur data yang tepat untuk tujuan kita.

Linieritas array

Array mungkin adalah salah satu struktur data yang paling umum digunakan di Swift, dan ada alasan bagus untuk ini. Ini menyimpan elemen-elemennya secara berurutan, mereka mudah disortir dengan cara yang dapat diprediksi, dan nilai apa pun dapat disimpan di dalamnya: dari struktur ke instance kelas dan koleksi lainnya.

Sebagai contoh, di sini kita menggunakan larik untuk menyimpan koleksi bentuk-bentuk yang ditempatkan pada Canvas dalam aplikasi menggambar. Kemudian, ketika kita perlu merender kanvas menjadi gambar, kita hanya pergi melalui array untuk menggambar setiap elemen menggunakan DrawingContext - sebagai berikut:

 struct Canvas { var shapes: [Shape] func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } } 

Ketika datang ke rendering berurutan dari semua bentuk kita, seperti yang kita lakukan di atas, array cocok. Array tidak hanya menyimpan elemen-elemen mereka dengan cara yang sangat efisien, mereka juga memiliki urutan pengurutan yang dijamin, yang menyediakan urutan rendering yang dapat diprediksi tanpa harus melakukan pekerjaan tambahan.

Namun, seperti semua struktur data lainnya, array memiliki kekurangannya. Dalam kasus kami, kami akan menemukan salah satu kelemahannya ketika kami ingin menghapus bentuk dari kanvas. Karena elemen array disimpan oleh indeks, kita harus terlebih dahulu menemukan indeks yang dikaitkan dengan angka sebelum kita dapat menghapusnya:

 extension Canvas { mutating func remove(_ shape: Shape) { guard let index = shapes.firstIndex(of: shape) else { return } shapes.remove(at: index) } } 

Pada awalnya, kode di atas mungkin tidak tampak bermasalah, tetapi dapat menjadi hambatan kinerja untuk setiap kanvas yang mengandung sejumlah besar bentuk, karena firstIndex linier (O (N)) dalam hal kompleksitas waktu .

Meskipun kita dapat mengatasi keterbatasan ini di mana kita menggunakan jenis kanvas kita. Misalnya, selalu mengacu pada angka berdasarkan indeks, dan bukan berdasarkan nilai atau ID - ini akan membuat kode kita lebih kompleks dan lebih rapuh, karena kita harus selalu memastikan bahwa indeks kita tidak kedaluwarsa ketika kanvas yang kita gunakan bekerja dengan akan berubah.

Set kecepatan

Sebagai gantinya, mari kita lihat apakah kita dapat mengoptimalkan Canvas itu sendiri dengan mengubah struktur data yang mendasarinya. Mempertimbangkan masalah di atas, salah satu ide awal kami mungkin menggunakan Set (set) alih-alih Array . Seperti yang telah kita bahas dalam Kekuatan set di Swift , salah satu keuntungan signifikan set array adalah bahwa kedua insert dan delete selalu dapat dilakukan dalam waktu yang konstan (O (1)), karena item disimpan oleh nilai hash, bukan oleh indeks.

Dengan memperbarui Canvas untuk menggunakan set, kita mendapatkan yang berikut:

 struct Canvas { var shapes: Set<Shape> func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func remove(_ shape: Shape) { shapes.remove(shape) } } 

Sekali lagi, kode di atas mungkin terlihat benar, dan bahkan dikompilasi tanpa masalah. Namun, meskipun kami memecahkan masalah penghapusan, kami juga kehilangan urutan render stabil kami - karena, tidak seperti array, set tidak memberi kami urutan penyortiran yang dijamin - yang merupakan batu sandungan dalam situasi ini, karena sepertinya kami akan menggambar bentuk kustom di secara acak.

Indeks Pengindeksan

Ayo terus bereksperimen. Sekarang mari kita lihat apakah kita dapat mengoptimalkan Canvas dengan memperkenalkan Dictionary , yang memungkinkan kita untuk mencari indeks bentuk apa pun berdasarkan ID-nya. Kami akan mulai dengan mengubah tingkat akses untuk array shapes kami menjadi private sehingga kami dapat mengontrol penyisipan elemen menggunakan metode add baru. Dan setiap kali angka baru ditambahkan, kami juga menambahkan indeksnya ke kamus kami:

 struct Canvas { private var shapes = [Shape]() private var indexes = [Shape.ID : Int]() func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func add(_ shape: Shape) { let index = shapes.count indexes[shape.id] = index shapes.append(shape) } } 

Karena sekarang kita selalu tahu pada indeks berapa angka yang diberikan disimpan, kita dapat dengan cepat melakukan penghapusan dalam waktu yang konstan, seperti ketika menggunakan set:

 extension Canvas { mutating func remove(_ shape: Shape) { guard let index = indexes[shape.id] else { return } shapes.remove(at: index) indexes[shape.id] = nil } } 

Namun, ada bug yang cukup serius dalam implementasi Canvas kami yang baru. Setiap kali kami menghapus suatu bentuk, sebenarnya kami membatalkan semua indeks yang lebih tinggi dari yang baru saja kami hapus - karena masing-masing elemen ini akan bergerak satu langkah ke awal array. Kami dapat memecahkan masalah ini dengan menyesuaikan indeks ini setelah setiap penghapusan, tetapi ini akan membawa kami kembali ke wilayah O (N), yang kami coba hindari sejak awal.

Implementasi terbaru kami memiliki kelebihan. Secara umum, menggunakan kombinasi dari dua struktur data dapat menjadi ide bagus dalam situasi seperti itu, karena kita sering dapat menggunakan kekuatan dari satu struktur data untuk mengkompensasi kekurangan yang lain, dan sebaliknya.

Jadi, mari kita coba lagi dengan kombinasi yang berbeda, tetapi kali ini mari kita mulai dengan mempertimbangkan persyaratan nyata kita:

• Kami membutuhkan sisipan dan penghapusan agar memiliki kompleksitas waktu yang konstan, dan harus mungkin untuk menghapus angka tanpa mengetahui indeks dasarnya.
• Kami membutuhkan pesanan penyortiran yang dijamin untuk dapat mempertahankan pesanan rendering yang stabil.

Melihat persyaratan di atas, ternyata meskipun kita membutuhkan urutan penyortiran yang stabil, kita sebenarnya tidak membutuhkan indeks. Ini akan membuat daftar tertaut menjadi sempurna untuk kasus penggunaan kami.

Daftar tertaut terdiri dari node, di mana setiap node berisi tautan (atau tautan) ke simpul berikutnya dalam daftar, yang berarti bahwa simpul tersebut dapat diurutkan dengan cara yang dapat diprediksi - tanpa perlu pembaruan indeks apa pun saat item dihapus. Namun, pustaka standar Swift (sejauh ini) tidak mengandung tipe daftar tertaut, jadi jika kita ingin menggunakannya, kita harus membuatnya terlebih dahulu.

Buat daftar tertaut

Mari kita mulai dengan mendeklarasikan struktur List yang akan melacak node pertama dan terakhir dalam daftar kami. Kami akan membuat kedua properti ini hanya baca di luar tipe kami untuk memastikan konsistensi data:

 struct List<Value> { private(set) var firstNode: Node? private(set) var lastNode: Node? } 

Selanjutnya, mari kita buat tipe Node kita (node), yang akan kita buat kelas, karena kita ingin dapat merujuk ke node dengan referensi, dan bukan oleh nilai . Daftar kami akan terhubung dua kali lipat, yang berarti bahwa setiap node akan berisi tautan ke tetangga berikutnya dan yang sebelumnya. Setiap node juga akan menyimpan nilai - seperti ini:

 extension List { class Node { var value: Value fileprivate(set) weak var previous: Node? fileprivate(set) var next: Node? init(value: Value) { self.value = value } } } 

Alasan kami membuat properti sebelumnya lemah adalah untuk menghindari loop penahan yang akan muncul jika kami menjaga tautan kuat di kedua arah. Untuk mempelajari lebih lanjut tentang menghindari siklus penyimpanan, lihat artikel "Manajemen Memori" .

Ini sebenarnya semua kode yang kita butuhkan sehingga nilai-nilai dapat disimpan dalam daftar tertaut kami. Tetapi ini hanya bagian pertama dari teka-teki itu, seperti pada koleksi lainnya, kami juga ingin dapat mengulanginya dan mengubah isinya. Mari kita mulai dengan iterasi, yang, berkat desain Swift yang sangat berorientasi pada protokol, dapat dengan mudah diimplementasikan dengan memastikan kepatuhan dengan protokol Sequence dan menerapkan metode makeIterator :

 extension List: Sequence { func makeIterator() -> AnyIterator<Value> { var node = firstNode return AnyIterator { //   ,    ,    : let value = node?.value node = node?.next return value } } } 

Karena iterasi di atas sangat sederhana, kami menggunakan AnyIterator standar AnyIterator untuk menghindari perlunya menerapkan tipe iterator khusus. Untuk skenario yang lebih kompleks, ini dapat diimplementasikan dengan menambahkan kecocokan ke IteratorProtocol .

Selanjutnya, mari kita tambahkan API untuk mengubah daftar tertaut kami, dimulai dengan sisipan. Kami akan memperluas List dengan metode append , yang menambahkan simpul baru untuk nilai yang dimasukkan dan kemudian mengembalikan simpul ini - seperti ini:

 extension List { @discardableResult mutating func append(_ value: Value) -> Node { let node = Node(value: value) node.previous = lastNode lastNode?.next = node lastNode = node if firstNode == nil { firstNode = node } return node } } 

Di atas, kita menggunakan atribut @discardableResult , yang memberi tahu kompiler untuk tidak menghasilkan peringatan apa pun jika hasil memanggil metode kita tidak digunakan, karena kita tidak selalu tertarik pada simpul yang telah dibuat.

Karena daftar tertaut tidak didasarkan pada indeks, tetapi pada pemeliharaan rantai nilai melalui tautan, penerapan penghapusan hanya masalah memperbarui tetangga berikut dan tetangga sebelumnya dari simpul jarak jauh sehingga mereka saling menunjuk satu sama lain sebagai gantinya:

 extension List { mutating func remove(_ node: Node) { node.previous?.next = node.next node.next?.previous = node.previous //  « »,        ,    : if firstNode === node { firstNode = node.next } if lastNode === node { lastNode = node.previous } } } 

Berdasarkan hal tersebut di atas, versi awal Daftar kami selesai, dan kami siap untuk memverifikasi dalam tindakan. Mari perbarui Kanvas untuk menggunakan daftar baru kami, serta kamus yang memungkinkan kami untuk dengan cepat menemukan simpul mana yang cocok dengan ID bentuk yang diberikan:

 struct Canvas { private var shapes = List<Shape>() private var nodes = [Shape.ID : List<Shape>.Node]() func render() -> Image { let context = DrawingContext() shapes.forEach(context.draw) return context.makeImage() } mutating func add(_ shape: Shape) { nodes[shape.id] = shapes.append(shape) } mutating func remove(_ shape: Shape) { guard let node = nodes.removeValue(forKey: shape.id) else { return } shapes.remove(node) } } 

Sekarang kami memiliki kedua penyisipan dan penghapusan cepat, dan urutan penyortiran yang dapat diprediksi, tanpa perlu menambahkan kompleksitas tambahan untuk proses panggilan - ini sangat keren! Dan, karena Daftar baru kami adalah tipe yang sepenuhnya universal, sekarang kami dapat menggunakannya kapan pun kami perlu lagi menyimpan nilai tanpa indeks secara linear.

Kesimpulan

Terlepas dari kenyataan bahwa struktur data sangat mendasar sehingga dapat ditemukan dalam semua jenis bahasa pemrograman, keputusan tentang yang mana yang akan digunakan dalam setiap situasi tertentu mungkin masih memerlukan pemikiran, pengujian, dan eksperimen yang signifikan, terutama jika kita ingin sehingga kode kita tetap efektif saat set data bertambah.

Sangat mungkin juga bahwa struktur data yang sesuai untuk setiap situasi tertentu dapat berubah seiring waktu seiring perubahan persyaratan kami, dan kadang-kadang menggunakan kombinasi beberapa struktur data, dan bukan hanya satu, dapat menjadi cara untuk mencapai karakteristik kinerja yang diperlukan.

Kami akan terus mengeksplorasi dunia struktur data dalam artikel berikut ini, dengan fokus pada hal-hal yang belum diimplementasikan di perpustakaan standar. Seperti banyak hal lain, kadang-kadang kita perlu memperluas pemikiran kita di luar Swift untuk memilih struktur data yang tepat untuk setiap situasi.

Anda dapat menemukan saya di Twitter atau mengirim email kepada saya jika Anda memiliki pertanyaan, komentar, atau umpan balik.

Terima kasih atas perhatian anda!