Ustawić operacje (suma, przecięcie) na tablicy Swift?

100

Czy istnieją jakieś standardowe wywołania biblioteki, których mogę użyć do wykonania operacji na dwóch tablicach lub do samodzielnego wdrożenia takiej logiki (najlepiej tak funkcjonalnie i wydajnie, jak to tylko możliwe)?

functional-programming swift set-operations devios1
źródło
Zestaw można zaimplementować na szczycie słownika, jeśli chcesz to zrobić samodzielnie.
CodaFi,
@CodaFi Czy masz na myśli używanie kluczy w celu zapewnienia wyjątkowości?
devios1
Czy mógłbyś po prostu użyć `Dictionary <String, Void>?
David Berry,

Odpowiedzi:

184

Tak, Swift ma Setklasę.

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+ może wykonywać operacje na zestawach jako:

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

Swift 2.0 może obliczyć na argumentach tablicowych:

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

Swift 1.2+ potrafi obliczyć na zestawach:

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

Jeśli używasz niestandardowych struktur, musisz zaimplementować Hashable.

Podziękowania dla Michaela Sterna w komentarzach do aktualizacji Swift 2.0.

Podziękowania dla Amjada Husseiniego w komentarzach za informację Hashable.

joelparkerhenderson
źródło
8
Zauważ, że przynajmniej od Swift 2.0 możesz przekazać tablicę jako argument do tych funkcji. W ten sposób, set1.union(array2)a set1.exclusiveOr(array2)oba uzasadnione, oprócz postaci przedstawionych powyżej.
Michael Stern
A co jeśli chcesz przeciąć 5 tablic? Lub 6? A co, jeśli liczba tablic jest nieznana?
Nathan McKaskle
2
@Nathan Zależy od operacji zestawu. Na przykład, set union i set intersection są przemienne i asocjacyjne, więc możesz przetwarzać wiele zbiorów za pomocą iteracji lub tworzenia łańcuchów. Lub możesz utworzyć niestandardowe metody, które używają argumentów var, takich jak Set union_all (...) i intersect_all (...).
joelparkerhenderson
A co z tym, że tablice zawierają zduplikowane wartości, na przykład w celu ustalenia, czy 0 $ jest anagramem 1 $, gdzie znaki wejściowe mogą mieć zduplikowane litery?
Dave Kliman
1
Jeśli używasz niestandardowych struktur, musisz dostosować Hashable, co może być denerwujące, jeśli masz skomplikowaną strukturę
Amjad Husseini
0

Nie ma żadnych standardowych wywołań bibliotek, ale możesz zajrzeć do biblioteki ExSwift . Zawiera kilka nowych funkcji w tablicach, w tym różnicę, przecięcie i sumę.

Connor
źródło
1
Uwaga: Używałem ExSwift bez problemu w Swift 1.x, ale wydaje się, że jest on dość zepsuty dla Swift 2.x i od tego czasu nie był aktualizowany od kilku miesięcy. Istnieje mnóstwo widelców, którym można poświęcić więcej uwagi.
Robin Macharg
0

Najbardziej wydajną metodą, jaką znam, jest użycie liczb Godela. Google do kodowania godel.

Pomysł jest taki. Załóżmy, że masz N możliwych liczb i musisz utworzyć z nich zestawy. Na przykład N = 100 000 i chcesz tworzyć zestawy takie jak {1,2,3}, {5, 88, 19000} itd.

Chodzi o to, aby zachować listę N liczb pierwszych w pamięci i dla danego zbioru {a, b, c, ...} zakodować ją jako

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

Więc kodujesz zestaw jako BigNumber. Operacje na BigNumbers, mimo że są wolniejsze niż operacje na liczbach całkowitych, są nadal bardzo szybkie.

Aby połączyć 2 zestawy A, B, bierzesz

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

najmniejsza wspólna wielokrotność A i B jako A i B to zbiory i obie liczby.

Aby zrobić skrzyżowanie, które wybierzesz

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

Największy wspólny dzielnik.

i tak dalej.

To kodowanie nazywa się godelizacją, możesz wygooglować więcej, cały język arytmetyki zapisany przy użyciu logiki Fregego można zakodować za pomocą liczb w ten sposób.

Aby uzyskać operację jest członkiem? to bardzo proste --

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

Zdobycie kardynała jest trochę bardziej skomplikowane -

CARDINAL(S) = # of prime factors in s

rozkładasz liczbę S reprezentującą zbiór na iloczyn czynników pierwszych i dodajesz ich wykładniki. W przypadku, gdy zestaw nie pozwala na duplikaty, będziesz mieć wszystkie wykładniki 1.

alinsoar
źródło