W Swift po prostu piszesz, Set( yourArray )
aby tablica była unikalna. (W razie potrzeby zamówiony zestaw).
Zanim było to możliwe, jak to się stało?
Mogę mieć tablicę, która wygląda następująco:
[1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
Lub, naprawdę, dowolna sekwencja podobnie wpisanych części danych. Chcę tylko upewnić się, że istnieje tylko jeden identyczny element. Na przykład powyższa tablica wyglądałaby następująco:
[1, 4, 2, 6, 24, 15, 60]
Zauważ, że duplikaty 2, 6 i 15 zostały usunięte, aby upewnić się, że istnieje tylko jeden z każdego identycznego elementu. Czy Swift zapewnia sposób na to łatwo, czy też muszę to zrobić sam?
arrays
swift
standard-library
Altair357
źródło
źródło
NSSet
, NSSet to nieuporządkowana kolekcja obiektów, jeśli trzeba zachować porządek NSOrdersSet.$.uniq(array)
github.com/ankurp/Dollar#uniq---uniqSet
z Swift? Będziesz mógł podać listę nieuporządkowanych i unikalnych elementów.Odpowiedzi:
Możesz rzucić własny, np. Tak ( zaktualizowany do Swift 1.2 z zestawem ):
Wersja Swift 3:
I jako rozszerzenie dla
Array
:źródło
var addedDict = [T:Bool](); return filter(source) { addedDict(true, forKey: $0) == nil }
updateValue(true, forKey: $0)...
oaddedDict(true, forKey: $0)...
return filter(source) { addedDict.updateValue(true, forKey: $0) == nil }
tak, jak mówisz.let uniques = Array(Set(vals))
Możesz dość łatwo przekonwertować na zestaw i ponownie z powrotem na tablicę:
Nie gwarantuje się utrzymania oryginalnej kolejności tablicy.
źródło
originals
nie sąHashable
;Hashable
do zestawu można dodawać tylko typy danych, ale do tablicy można dodawać dowolny typ danych.Wiele odpowiedzi jest dostępnych tutaj, ale brakowało mi tego prostego rozszerzenia, odpowiedniego dla Swift 2 i nowszych:
Sprawia, że jest to bardzo proste. Można nazwać tak:
Filtrowanie na podstawie właściwości
Aby przefiltrować tablicę na podstawie właściwości, możesz użyć tej metody:
Możesz zadzwonić w następujący sposób:
źródło
extension Array where Element: Equatable
) jest zastępowana przez stackoverflow.com/a/36048862/1033581, który oferuje bardziej wydajne rozwiązanie (extension Sequence where Iterator.Element: Equatable
).O(n²)
wydajność czasową, co jest naprawdę złe dla dużych tablic.O(n²)
złożoność z powrotem doO(n)
Swift 3.0
źródło
array
nie sąHashable
;Hashable
do zestawu można dodawać tylko typy danych, ale do tablicy można dodawać dowolny typ danych.Jeśli umieścisz oba rozszerzenia w kodzie, szybsza
Hashable
wersja zostanie użyta, gdy to możliwe, aEquatable
wersja zostanie wykorzystana jako rezerwowa.Jeśli kolejność nie jest ważna, zawsze możesz użyć tego inicjatora Ustaw .
źródło
O(n²)
wydajność czasową, co jest naprawdę złe dla dużych tablic.edytuj / aktualizuj Swift 4 lub nowszy
Możemy również rozszerzyć
RangeReplaceableCollection
protokół, aby umożliwić jego stosowanie również zStringProtocol
typami:Metoda mutacji:
Aby wyświetlić Swift 3, kliknij tutaj
źródło
reduce
implementację, więc teraz złożoność jest inna.O(n)
czasie), podczas gdy wersja oparta na płaskiej mapie zajmuje 7,47x dłużej dla 8 milionów unikalnych wpisów niż 1 milion, co sugeruje, że wersja oparta na płaskiej mapie skaluje się lepiej . W jakiś sposób wersja oparta na płaskiej mapie działa nieco lepiej niżO(n)
czas!Szybki 4
każda próba
insert
będzie również powrót krotki:(inserted: Bool, memberAfterInsert: Set.Element)
. Zobacz dokumentację .Korzystanie ze zwróconej wartości pomaga nam uniknąć zapętlania lub wykonywania innych operacji.
źródło
O(n^2)
i nikt tego nie zauważył.Szybki 4
Gwarantujemy utrzymanie zamówienia.
źródło
reduce
: ogólnie rzecz biorąc, jest to po prostu jeszcze jedna linia w całym projekcie, aby napisać swoją funkcję jako:var unique: [Iterator.Element] = []; for element in self where !unique.contains(element) { unique.append(element) }; return unique
. Przyznaję, że nie testowałem jeszcze względnych wyników.O(n²)
wydajność czasową, co jest naprawdę złe dla dużych tablic.O(n²)
. Nie ma w tym nic szybkiego.reduce
lubreduce(into:)
nie zrobiłby krytycznej różnicy. Przepisanie tego, aby nie powtarzać połączeń,contains
zrobiłoby DUŻO większą różnicę.Oto kategoria, w
SequenceType
której zachowana jest pierwotna kolejność tablicy, ale używa onaSet
do wykonaniacontains
odnośników, aby uniknąćO(n)
kosztówcontains(_:)
metody Array .Jeśli nie jesteś Hashable lub Equatable, możesz przekazać predykat w celu sprawdzenia równości:
Teraz, jeśli nie masz Hashable, ale jesteś Equatable, możesz użyć tej metody:
Na koniec możesz dodać wersję klucza unikatowego w następujący sposób:
Możesz umieścić oba te elementy w swojej aplikacji, Swift wybierze właściwą w zależności od
Iterator.Element
typu sekwencji .źródło
O(n)
rozwiązaniem. Nawiasem mówiąc, możesz połączyć operacje zestawów „zaznacz” i „wstaw” w jedną. Zobacz stackoverflow.com/a/46354989/3141234Zainspirowany https://www.swiftbysundell.com/posts/the-power-of-key-paths-in-swift , możemy zadeklarować mocniejsze narzędzie, które jest w stanie filtrować jedność na dowolnym keyPath. Dzięki komentarzom Aleksandra na różne odpowiedzi dotyczące złożoności poniższe rozwiązania powinny być prawie optymalne.
Rozwiązanie niemutujące
Rozszerzamy o funkcję, która jest w stanie filtrować unikalność na dowolnym keyPath:
Uwaga: w przypadku, gdy Twój obiekt nie jest zgodny z RangeReplaceableCollection, ale jest zgodny z Sekwencją, możesz mieć to dodatkowe rozszerzenie, ale typem zwracanym zawsze będzie Array:
Stosowanie
Jeśli chcemy jednoznaczności dla samych elementów, jak w pytaniu, używamy keyPath
\.self
:Jeśli chcemy unicity dla czegoś innego (jak dla
id
zbioru obiektów), wówczas używamy wybranej ścieżki keyPath:Rozwiązanie mutujące
Rozszerzamy o funkcję mutacji, która może filtrować unikalność na dowolnym keyPath:
Stosowanie
Jeśli chcemy jednoznaczności dla samych elementów, jak w pytaniu, używamy keyPath
\.self
:Jeśli chcemy unicity dla czegoś innego (jak dla
id
zbioru obiektów), wówczas używamy wybranej ścieżki keyPath:źródło
keyPath
ustawienie domyślne\.self
, ponieważ prawdopodobnie jest to większość przypadków użycia.Element
zawsze robićHashable
. Alternatywą dla wartości domyślnej jest dodanie zwykłego przeciążenia bez parametrów:extension Sequence where Element: Hashable { func unique() { ... } }
Alternatywne (jeśli nie optymalne) rozwiązanie stąd wykorzystujące niezmienne typy zamiast zmiennych:
Uwzględniono w celu kontrastowania imperatywnego podejścia Jean-Pillippe z funkcjonalnym podejściem.
Jako bonus, ta funkcja działa zarówno z łańcuchami, jak i tablicami!
Edycja: Ta odpowiedź została napisana w 2014 roku dla Swift 1.0 (wcześniej
Set
była dostępna w Swift). Nie wymaga zgodności hashable i działa w kwadratowym czasie.źródło
contains
i tablica, dołączają w O (n). Chociaż ma tę zaletę, że wymaga tylko możliwości zrównania, a nie mieszania.filter
. To O (n ^ 2) (które jest wymagane, jeśli nie chcesz wymagaćHashable
zgodności), ale powinieneś przynajmniej to wyraźnie nazwaćszybki 2
z odpowiedzią funkcji uniq :
posługiwać się:
źródło
Bool
wartość jest oczywiście zbędna, ponieważ Twój kod nigdy jej nie czyta. UżyjSet
zamiast a,Dictionary
a dostaniesz moją opinię.W Swift 5
Wyjście będzie
źródło
Jeszcze jedno rozwiązanie Swift 3.0 do usuwania duplikatów z tablicy. To rozwiązanie poprawia wiele innych rozwiązań już zaproponowanych przez:
Biorąc pod uwagę tablicę liczb całkowitych:
Kod funkcjonalny:
Kod rozszerzenia tablicy:
Ten kod wykorzystuje wynik zwracany przez
insert
operację onSet
, która jest wykonywanaO(1)
, i zwraca krotkę wskazującą, czy element został wstawiony lub czy już istniał w zestawie.Jeśli element był w zestawie,
filter
wykluczy go z końcowego wyniku.źródło
defer
kodu wykona operację testowania zestawu dwa razy, jeden zcontains
i jeden zinsert
. Podczas dalszej lektury dokumentacji Swift odkryłem, żeinsert
zwraca krotkę wskazującą, czy element został wstawiony, czy nie, więc uprościłem kod usuwająccontains
kontrolę.extension Sequence where Iterator.Element: Hashable { ... }
insert
icontains
mająO(1)
złożoność.O(1) + O(1) = O(1)
. Te dwie operacje są następnie wykonywanen
razy (jeden raz na wywołanie zamknięciafilter
, które jest wywoływane raz na element) To znaczy, jeśli operacja zajmuje stałą ilość czasu niezależnie od wielkości wejściowej, to wykonanie tej czynności dwa razy nadal wymaga stałego czasu to jest niezależnie od rozmiaru wejściowego. Całkowita złożoność tego jestO(n)
.Swift 4.x:
stosowanie:
lub
źródło
O(n^2)
. Nie rób tegoSzybki 5
źródło
extension Sequence { // Returns distinct elements based on a key value. func distinct<key: Hashable>(by: ((_ el: Iterator.Element) -> key)) -> [Iterator.Element] { var existing = Set<key>() return self.filter { existing.insert(by($0)).inserted } } }
Bool
, gdy jedyną wartością, której używasz, jesttrue
. Sięgasz po „typ jednostki” (typ z tylko jedną możliwą wartością). Typ jednostki Swifta toVoid
, którego jedyną wartością jest()
(inaczej pusta krotka). Więc możesz po prostu użyć[T: Void]
. Chociaż nie powinieneś tego robić, ponieważ po prostu wynalazłeśSet
. UżyjSet
zamiast tego. Zobacz stackoverflow.com/a/55684308/3141234 Usuń tę odpowiedź.Myśl jak funkcjonalny programista :)
Aby przefiltrować listę na podstawie tego, czy element już wystąpił, potrzebujesz indeksu. Możesz użyć,
enumerated
aby uzyskać indeks imap
powrócić do listy wartości.To gwarantuje porządek. Jeśli nie masz nic przeciwko zamówieniu, to istniejąca odpowiedź
Array(Set(myArray))
jest prostsza i prawdopodobnie bardziej wydajna.AKTUALIZACJA: Kilka uwag na temat wydajności i poprawności
Kilka osób skomentowało wydajność. Zdecydowanie jestem w szkole, pisząc najpierw poprawny i prosty kod, a potem odkrywam wąskie gardła, choć doceniam, że dyskusyjne jest to, czy jest to bardziej zrozumiałe niż
Array(Set(array))
.Ta metoda jest znacznie wolniejsza niż
Array(Set(array))
. Jak zauważono w komentarzach, zachowuje porządek i działa na elementach, które nie są haszowalne.Jednak metoda @Alain T zachowuje również porządek i jest znacznie szybsza. Tak więc, chyba że twój typ elementu nie jest haszowalny lub potrzebujesz tylko jednej linijki, to sugeruję skorzystanie z ich rozwiązania.
Oto kilka testów na MacBooku Pro (2014) na Xcode 11.3.1 (Swift 5.1) w trybie Release.
Funkcja profilera i dwie metody porównywania:
I niewielka różnorodność wejść testowych:
Podaje jako wynik:
źródło
Array(Set(myArray))
tego działa to w przypadku rzeczy, które nie sąHashable
Array(Set(myArray))
do kolejności w tablicy jest zachowana.lastIndex(of:)
. W tym przypadku całkowicie nie zgadzam się co do jasności względem punktu optymalizacji. Nie sądzę, aby ta implementacja była szczególnie jasna, szczególnie w porównaniu z prostym rozwiązaniem opartym na zestawie. W każdym razie taki kod należy wyodrębnić do funkcji rozszerzenia. Algorytm ten staje się praktycznie bezużyteczny nawet przy niskim rozmiarze wejściowym, jak w tysiącach do dziesiątek tysięcy. Nie jest trudno znaleźć takie zestawy danych, ludzie mogą mieć tysiące piosenek, plików, kontaktów itp.W przypadku tablic, w których elementy nie są mieszalne ani porównywalne (np. Złożone obiekty, słowniki lub struktury), to rozszerzenie zapewnia ogólny sposób usuwania duplikatów:
Nie musisz zawracać sobie głowy tworzeniem wartości Hashable i pozwala to na użycie różnych kombinacji pól dla wyjątkowości.
Uwaga: aby uzyskać bardziej niezawodne podejście, zobacz rozwiązanie zaproponowane przez Coeur w komentarzach poniżej.
stackoverflow.com/a/55684308/1033581
[EDYCJA] Swift 4 alternatywa
W Swift 4.2 możesz użyć klasy Hasher, aby zbudować skrót znacznie łatwiej. Powyższe rozszerzenie można zmienić, aby to wykorzystać:
Składnia wywoływania jest nieco inna, ponieważ zamknięcie otrzymuje dodatkowy parametr zawierający funkcję mieszającą zmienną liczbę wartości (która musi być mieszalna indywidualnie)
Będzie również działał z jedną wartością unikalności (użycie 1 $ i ignorowanie 0 $).
źródło
"\()"
, ponieważ może nie dać unikalnych wartości, takich jak zgodność zHashable
powinnością. Na przykład, jeśli wszystkie elementy są zgodnePrintable
przez wszystkie zwracane to samodescription
, oznacza to, że filtrowanie nie powiedzie się.T
do byciaHashable
.Możesz użyć bezpośrednio zestawu kolekcji, aby usunąć duplikat, a następnie rzutować go z powrotem do tablicy
Następnie możesz zamówić swoją tablicę, jak chcesz
źródło
Nieco bardziej zwięzła wersja składniowa odpowiedzi Swift 2 Daniela Kroma , wykorzystująca końcowe zamknięcie i krótką nazwę argumentu, która wydaje się być oparta na oryginalnej odpowiedzi Airspeed Velocity :
Przykład implementacji niestandardowego typu, którego można używać
uniq(_:)
(który musi być zgodnyHashable
, a zatemEquatable
ponieważHashable
rozszerzaEquatable
):W powyższym kodzie ...
id
, użyte w przeciążeniu==
, może być dowolnyEquatable
typ (lub metoda, która zwracaEquatable
typ, npsomeMethodThatReturnsAnEquatableType()
.). Skomentowany kod pokazuje rozszerzenie sprawdzania równości, gdziesomeOtherEquatableProperty
jest inną właściwościąEquatable
typu (ale może być również metodą zwracającąEquatable
typ).id
, użyte wehashValue
właściwości obliczonej (wymaganej do zgodnościHashable
), może być dowolnąHashable
(a tym samymEquatable
) właściwością (lub metodą zwracającąHashable
typ).Przykład użycia
uniq(_:)
:źródło
Bool
, gdy jedyną wartością, której używasz, jesttrue
. Sięgasz po „typ jednostki” (typ z tylko jedną możliwą wartością). Typ jednostki Swifta toVoid
, którego jedyną wartością jest()
(inaczej pusta krotka). Więc możesz po prostu użyć[T: Void]
. Chociaż nie powinieneś tego robić, ponieważ po prostu wynalazłeśSet
. UżyjSet
zamiast tego. Zobacz stackoverflow.com/a/55684308/3141234Jeśli potrzebujesz posortowanych wartości, działa to (Swift 4)
let sortedValues = Array(Set(array)).sorted()
źródło
.sorted()
jest koniec. Pozdrowienia.[2, 1, 1]
? Wyjdzie[1, 2]
, to nie jest zamówione: p[2, 1, 1]
. Pierwsze pojawienie się unikalnych elementów, w kolejności, to[2, 1]
. To poprawna odpowiedź. Ale używając (niepoprawnego) algorytmu otrzymujesz[1, 2]
, który jest posortowany, ale nie ma prawidłowej, oryginalnej kolejności.array
nie sąHashable
;Hashable
do zestawu można dodawać tylko typy danych, ale do tablicy można dodawać dowolny typ danych.Oto rozwiązanie, które
NS
typówO(n)
źródło
tutaj zrobiłem jakieś O (n) rozwiązanie dla obiektów. Nie kilka linii, ale ...
źródło
Set
z niestandardowymDistinctWrapper
, powinieneś użyćDictionary
z odrębnych atrybutów do obiektów. Kiedy będziesz postępować zgodnie z tą logiką, ostatecznie skończysz implementować [Dictionary.init(_:uniquingKeysWith:)
] pastebin.com/w90pVe0p ( https://developer.apple.com/documentation/... , który jest teraz wbudowany w bibliotekę standardową. Sprawdź, jak proste jest to pastebin.com/w90pVe0pUżyłem odpowiedzi @ Jean-Philippe Pelleta i stworzyłem rozszerzenie Array, które wykonuje operacje podobne do zestawów na tablicach, zachowując kolejność elementów.
źródło
Bool
, gdy jedyną wartością, której używasz, jesttrue
. Sięgasz po „typ jednostki” (typ z tylko jedną możliwą wartością). Typ jednostki Swifta toVoid
, którego jedyną wartością jest()
(inaczej pusta krotka). Więc możesz po prostu użyć[T: Void]
. Chociaż nie powinieneś tego robić, ponieważ po prostu wynalazłeśSet
. UżyjSet
zamiast tego. Zobacz stackoverflow.com/a/55684308/3141234To tylko bardzo prosta i wygodna implementacja. Obliczona właściwość w rozszerzeniu tablicy, która ma elementy możliwe do porównania.
źródło
O(n^2)
.Stosowanie:
źródło
O(n²)
.Gotowe....
Przykład
wyjście arrayWithoutDuplicates - [1,2,4,6,8]
źródło
Lekko zwarta wersja oparta na rozszerzeniu tablicy @ Jean-Philippe Pelleta:
źródło
insert
zwraca krotkę, która mówi, czy element już tam był, czy został dodany po raz pierwszy. stackoverflow.com/a/55684308/3141234 Usuń tę odpowiedź.Zawsze możesz użyć Słownika, ponieważ Słownik może przechowywać tylko unikalne wartości. Na przykład:
Jak widać, wynikowa tablica nie zawsze będzie „uporządkowana”. Jeśli chcesz posortować / zamówić tablicę, dodaj to:
.
źródło
Najprostszym sposobem byłoby użycie NSOrdersSet, który przechowuje unikatowe elementy i zachowuje kolejność elementów. Lubić:
źródło