Setel operasi (union, intersection) di Swift array?

100

Apakah ada panggilan pustaka standar yang dapat saya gunakan untuk melakukan operasi set pada dua larik, atau mengimplementasikan sendiri logika tersebut (idealnya berfungsi dan seefisien mungkin)?

functional-programming swift set-operations devios1
sumber
Satu set dapat diimplementasikan di atas kamus jika Anda ingin melakukannya sendiri.
CodaFi
@CodaFi Apakah yang Anda maksud dengan menggunakan tombol untuk memastikan keunikan?
devios1
Bisakah Anda menggunakan `Dictionary <String, Void>?
David Berry

Jawaban:

184

Ya, Swift memiliki Setkelasnya.

let array1 = ["a", "b", "c"]
let array2 = ["a", "b", "d"]

let set1:Set<String> = Set(array1)
let set2:Set<String> = Set(array2)

Swift 3.0+ dapat melakukan operasi pada set sebagai:

firstSet.union(secondSet)// Union of two sets
firstSet.intersection(secondSet)// Intersection of two sets
firstSet.symmetricDifference(secondSet)// exclusiveOr

Swift 2.0 dapat menghitung argumen array:

set1.union(array2)       // {"a", "b", "c", "d"} 
set1.intersect(array2)   // {"a", "b"}
set1.subtract(array2)    // {"c"}
set1.exclusiveOr(array2) // {"c", "d"}

Swift 1.2+ dapat menghitung set:

set1.union(set2)        // {"a", "b", "c", "d"}
set1.intersect(set2)    // {"a", "b"}
set1.subtract(set2)     // {"c"}
set1.exclusiveOr(set2)  // {"c", "d"}

Jika Anda menggunakan struct kustom, Anda perlu menerapkan Hashable.

Terima kasih kepada Michael Stern di komentar untuk pembaruan Swift 2.0.

Terima kasih kepada Amjad Husseini di kolom komentar untuk info Hashable.

joelparkerhenderson
sumber
8
Perhatikan bahwa, setidaknya sejak Swift 2.0, Anda bisa meneruskan array sebagai argumen untuk fungsi ini. Jadi, set1.union(array2)dan set1.exclusiveOr(array2)keduanya sah, selain bentuk yang ditunjukkan di atas.
Michael Stern
Bagaimana jika Anda ingin memotong 5 array? Atau 6? Bagaimana jika jumlah array tidak diketahui?
Nathan McKaskle
2
@Nathan Tergantung pada operasi set. Misalnya, set union dan set intersection bersifat komutatif dan asosiatif, jadi Anda bisa memproses banyak set dengan menggunakan iterasi atau rangkaian. Atau Anda bisa membuat metode kustom yang menggunakan var args, seperti Set union_all (...) dan intersect_all (...).
joelparkerhenderson
Bagaimana jika array Anda berisi nilai duplikat, misalnya untuk menentukan apakah $ 0 adalah anagram $ 1 di mana karakter input dapat memiliki huruf duplikat?
Dave Kliman
1
Jika Anda menggunakan struct kustom, Anda harus menyesuaikan Hashable, yang mungkin mengganggu jika Anda memiliki struct yang rumit
Amjad Husseini
0

Tidak ada panggilan perpustakaan standar, tetapi Anda mungkin ingin melihat perpustakaan ExSwift . Ini mencakup banyak fungsi baru pada Array termasuk perbedaan, persimpangan dan penyatuan.

Connor
sumber
1
Catatan peringatan: Saya telah menggunakan ExSwift tanpa masalah untuk Swift 1.x tetapi tampaknya cukup rusak untuk Swift 2.x, dan hingga tulisan ini belum diperbarui dalam beberapa bulan. Ada banyak sekali garpu yang mungkin mendapat perhatian lebih.
Robin Macharg
0

Metode paling efisien yang saya tahu adalah dengan menggunakan nomor godel. Google untuk pengkodean godel.

Idenya begitu. Misalkan Anda memiliki N kemungkinan nomor dan perlu membuat set dari mereka. Misalnya, N = 100.000 dan ingin membuat himpunan seperti {1,2,3}, {5, 88, 19000} dll.

Idenya adalah untuk menyimpan daftar bilangan prima N dalam memori dan untuk himpunan tertentu {a, b, c, ...} Anda menyandikannya sebagai

 prime[a]*prime[b]*prime[c]*...

Jadi Anda mengenkode satu set sebagai BigNumber. Operasi dengan BigNumbers, meskipun faktanya mereka lebih lambat daripada operasi dengan Integer, masih sangat cepat.

Untuk menyatukan 2 set A, B, Anda ambil

  UNITE(A, B) = lcm(a, b)

kelipatan persekutuan terendah dari A dan B karena A dan B adalah himpunan dan kedua bilangan tersebut.

Untuk membuat persimpangan yang Anda ambil

 INTERSECT(A, B) = gcd (a, b)

pembagi persekutuan terbesar.

dan seterusnya.

Pengkodean ini disebut godelisasi, Anda dapat mencari lebih banyak di Google, semua bahasa aritmatika yang ditulis menggunakan logika Frege dapat dikodekan menggunakan angka dengan cara ini.

Untuk mendapatkan operasi is-member? itu sangat sederhana -

ISMEMBER(x, S) = remainder(s,x)==0

Untuk mendapatkan kardinal itu sedikit lebih rumit -

CARDINAL(S) = # of prime factors in s

Anda menguraikan bilangan S yang mewakili himpunan dalam produk faktor prima dan menambahkan eksponennya. Jika himpunan tidak mengizinkan duplikat, Anda akan memiliki semua eksponen 1.

alinsoar
sumber