Removendo elementos duplicados de uma matriz no Swift

252

Atualmente, no Swift, você simplesmente digita Set( yourArray )para tornar uma matriz única. (Ou um conjunto ordenado, se necessário.)

Antes que isso fosse possível, como foi feito?


Eu posso ter uma matriz que se parece com o seguinte:

[1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]

Ou, realmente, qualquer sequência de partes do mesmo tipo de dados. O que eu quero fazer é garantir que haja apenas um de cada elemento idêntico. Por exemplo, a matriz acima se tornaria:

[1, 4, 2, 6, 24, 15, 60]

Observe que as duplicatas de 2, 6 e 15 foram removidas para garantir que houvesse apenas um de cada elemento idêntico. O Swift fornece uma maneira de fazer isso facilmente, ou terei que fazer isso sozinho?

Altair357
fonte
11
A maneira mais fácil é converter a matriz em um NSSet, NSSet é uma coleção não ordenada de objetos, se necessário, para manter a ordem NSOrderedSet.
Andrea
Você pode usar a função de intersecção como você pode encontrar nesta classe com funções para matrizes: github.com/pNre/ExSwift/blob/master/ExSwift/Array.swift
Edwin Vermeer
Não faz parte do Swift, mas eu uso o Dollar. $.uniq(array) github.com/ankurp/Dollar#uniq---uniq
Andy
Provavelmente a resposta mais elegante, inteligente e rápida é fornecida pela resposta do mxcl abaixo. Que também ajuda a manter a ordem
Mel
1
Por que você não usa apenas Setda Swift? Você poderá fornecer uma lista de elementos não ordenados e exclusivos.
TibiaZ 11/03/19

Respostas:

133

Você pode fazer o seu próprio, por exemplo, desta forma ( atualizado para o Swift 1.2 com Set ):

func uniq<S : SequenceType, T : Hashable where S.Generator.Element == T>(source: S) -> [T] {
    var buffer = [T]()
    var added = Set<T>()
    for elem in source {
        if !added.contains(elem) {
            buffer.append(elem)
            added.insert(elem)
        }
    }
    return buffer
}

let vals = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
let uniqueVals = uniq(vals) // [1, 4, 2, 6, 24, 15, 60]

Versão Swift 3:

func uniq<S : Sequence, T : Hashable>(source: S) -> [T] where S.Iterator.Element == T {
    var buffer = [T]()
    var added = Set<T>()
    for elem in source {
        if !added.contains(elem) {
            buffer.append(elem)
            added.insert(elem)
        }
    }
    return buffer
}

E como uma extensão para Array:

extension Array where Element: Hashable {
    var uniques: Array {
        var buffer = Array()
        var added = Set<Element>()
        for elem in self {
            if !added.contains(elem) {
                buffer.append(elem)
                added.insert(elem)
            }
        }
        return buffer
    }
}
Jean-Philippe Pellet
fonte
12
Você também pode implementar o corpo dessa função comovar addedDict = [T:Bool](); return filter(source) { addedDict(true, forKey: $0) == nil }
Velocidade da velocidade do ar
1
@AirspeedVelocity: Você quis dizer em updateValue(true, forKey: $0)...vez deaddedDict(true, forKey: $0)...
Jawwad
1
Opa sim desculpe, acidentalmente o método! Deve ser return filter(source) { addedDict.updateValue(true, forKey: $0) == nil }como você diz.
Velocidade da velocidade do vento
21
Apenas uma palavra de cautela: evite discutir o desempenho de funções simples como essa até depender comprovadamente do desempenho deles; nesse ponto, a única coisa que você deve fazer é fazer uma referência. Muitas vezes vi código não sustentável ou código com menos desempenho devido a suposições. :) Além disso, esta é provavelmente mais fácil de entender:let uniques = Array(Set(vals))
Blixt
11
@Blixt concordou. Mais uma vez, aqui a vantagem está em respeitar a ordem dos elementos da matriz original.
Jean-Philippe Pellet
493

Você pode converter para um conjunto e retornar para uma matriz novamente com bastante facilidade:

let unique = Array(Set(originals))

Isso não é garantido para manter a ordem original da matriz.

Ben Packard
fonte
37
Existe uma maneira de usar um conjunto, preservando a ordem original da matriz?
Crashalot
6
@Crashalot Veja minha resposta.
Jean-Philippe Pellet
5
Se você precisa manter a objetos únicos por uma propriedade específica, que também implementar o protocolo Hashable e Equatable nessa classe, em vez de apenas usando o Array-> Set> matriz de transformação
Fawkes
2
Agradável!! Qual é a complexidade de tempo desta solução, por favor?
JW.ZG
2
Falha se os elementos em originalsnão forem Hashable; somente Hashabletipos de dados podem ser adicionados a um conjunto, mas qualquer tipo de dados pode ser adicionado a uma matriz.
Mecki
69

Muitas respostas estão disponíveis aqui, mas eu perdi essa extensão simples, adequada para o Swift 2 e superior:

extension Array where Element:Equatable {
    func removeDuplicates() -> [Element] {
        var result = [Element]()

        for value in self {
            if result.contains(value) == false {
                result.append(value)
            }
        }

        return result
    }
}

Torna super simples. Pode ser chamado assim:

let arrayOfInts = [2, 2, 4, 4]
print(arrayOfInts.removeDuplicates()) // Prints: [2, 4]

Filtragem com base nas propriedades

Para filtrar uma matriz com base nas propriedades, você pode usar este método:

extension Array {

    func filterDuplicates(@noescape includeElement: (lhs:Element, rhs:Element) -> Bool) -> [Element]{
        var results = [Element]()

        forEach { (element) in
            let existingElements = results.filter {
                return includeElement(lhs: element, rhs: $0)
            }
            if existingElements.count == 0 {
                results.append(element)
            }
        }

        return results
    }
}

Você pode chamar da seguinte maneira:

let filteredElements = myElements.filterDuplicates { $0.PropertyOne == $1.PropertyOne && $0.PropertyTwo == $1.PropertyTwo }
Antoine
fonte
@Antoine Obrigado pela filtragem com base na extensão de propriedades. É realmente útil. Mas você pode, por favor, explicar como funciona. É muito difícil de entender para mim. Obrigado
Mostafa Mohamed Raafat 4/16
Atualizações para SWIFT 3: filterDuplicates func (_ includeElement: (_ lhs: Elemento, _ rhs: Elemento) -> Bool) -> [Element] {
cbartel
A primeira parte desta resposta ( extension Array where Element: Equatable) está sendo substituída por stackoverflow.com/a/36048862/1033581, que oferece uma solução mais poderosa ( extension Sequence where Iterator.Element: Equatable).
Cœur
7
Isso terá O(n²)desempenho de tempo, o que é realmente ruim para matrizes grandes.
Duncan C
Você deve usar um conjunto para acompanhar os elementos vistos até agora, para trazer essa O(n²)complexidade terrível de volta aO(n)
Alexander - Reinstate Monica
63

Swift 3.0

let uniqueUnordered = Array(Set(array))
let uniqueOrdered = Array(NSOrderedSet(array: array))
Jovan Stankovic
fonte
1
deixe uniqueOrderedNames = Array (NSOrderedSet (array: userNames)) as! [String] se você tiver um array de String, não de Qualquer #
Zaporozhchenko Oleksandr
Falha se os elementos em arraynão forem Hashable; somente Hashabletipos de dados podem ser adicionados a um conjunto, mas qualquer tipo de dados pode ser adicionado a uma matriz.
Mecki
Testado no Swift 5.1b5, considerando que os elementos são Hashable e o desejo de reter pedidos, a matriz NSOrderedSet (array: array). É marginalmente mais rápida que a função swift pura exclusiva () usando um conjunto com filtro. Testei com 5100 strings que resultaram em 13 valores únicos.
dlemex
62

Se você colocar as duas extensões no seu código, a Hashableversão mais rápida será usada quando possível e a Equatableversão será usada como fallback.

public extension Sequence where Element: Hashable {
  var firstUniqueElements: [Element] {
    var set: Set<Element> = []
    return filter { set.insert($0).inserted }
  }
}

public extension Sequence where Element: Equatable {
  var firstUniqueElements: [Element] {
    reduce(into: []) { uniqueElements, element in
      if !uniqueElements.contains(element) {
        uniqueElements.append(element)
      }
    }
  }
}

Se a ordem não for importante, você sempre poderá usar este inicializador de conjunto .

Jessy
fonte
tudo bem, entendi. Eu não era capaz de chamá-lo porque minha matriz é uma matriz de estruturas ... como eu iria lidar com isso no meu caso? struct de 20 variáveis diferentes, corda e [TEXTO]
David Procure
@ David Seek Parece que você não fez o seu rigoroso hashable ou equável. Isso está correto?
21716 Jessy
1
@DavidSeek assim, uniqueArray = nonUniqueArray.uniqueElements
Mert Celik
Sim, não se preocupe. conseguiu funcionar logo depois. Já faz quase 2 anos: P
David Seek
Isso terá O(n²)desempenho de tempo, o que é realmente ruim para matrizes grandes.
Duncan C
44

editar / atualizar Swift 4 ou posterior

Também podemos estender o RangeReplaceableCollectionprotocolo para permitir que ele seja usado com StringProtocoltipos também:

extension RangeReplaceableCollection where Element: Hashable {
    var orderedSet: Self {
        var set = Set<Element>()
        return filter { set.insert($0).inserted }
    }
    mutating func removeDuplicates() {
        var set = Set<Element>()
        removeAll { !set.insert($0).inserted }
    }
}

let integers = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
let integersOrderedSet = integers.orderedSet // [1, 4, 2, 6, 24, 15, 60]

"abcdefabcghi".orderedSet  // "abcdefghi"
"abcdefabcghi".dropFirst(3).orderedSet // "defabcghi"

Método de mutação:

var string = "abcdefabcghi"
string.removeDuplicates() 
string  //  "abcdefghi"

var substring = "abcdefabcdefghi".dropFirst(3)  // "defabcdefghi"
substring.removeDuplicates()
substring   // "defabcghi"

Para Swift 3 clique aqui

Leo Dabus
fonte
1
Eu gosto disso, ele também funciona com uma variedade de dicionários!
DeyaEldeen 28/09
6
O (N ^ 2) é ruim :(
Alexander - Restabelece Monica
1
O @Alexander Leo Dabus substituiu a reduceimplementação, agora a complexidade é diferente.
Cœur
1
Os resultados são interessantes. Para 1 milhão de itens exclusivos e 8 milhões, a versão do filtro é mais rápida. No entanto, a versão baseada em filtro leva 8,38x mais tempo para 8 milhões de itens exclusivos (um fio de cabelo ao longo do O(n)tempo), enquanto a versão baseada em mapa plano leva 7,47x mais para 8 milhões de entradas exclusivas que 1 milhão, sugerindo que a versão baseada em mapa plano é melhor . De alguma forma, a versão baseada em flatmap se sai um pouco melhor que o O(n)tempo!
Duncan C
1
De fato, quando eu executo o teste com mais 64x itens na matriz, a versão baseada em mapa plano é mais rápida.
Duncan C
43

Swift 4

public extension Array where Element: Hashable {
    func uniqued() -> [Element] {
        var seen = Set<Element>()
        return filter{ seen.insert($0).inserted }
    }
}

cada tentativa de inserttambém irá retornar uma tupla: (inserted: Bool, memberAfterInsert: Set.Element). Veja a documentação .

O uso do valor retornado ajuda a evitar o loop ou a execução de qualquer outra operação.

mxcl
fonte
7
Após a criação de perfis simples, esse método é realmente rápido. Suas centenas vezes mais rápido, em seguida, usando reduzir (_: _ :), ou mesmo reduzir (em: _ :)
Kelvin
3
@ Kelvin Porque todos os outros algoritmos eram O(n^2), e ninguém percebeu.
Alexander - Restabelece Monica
@ Kelvin, esta resposta é idêntica à resposta de Eneko Alonso + meu comentário (16 / jun / 17).
Cœur
27

Swift 4

Garantido para continuar solicitando.

extension Array where Element: Equatable {
    func removingDuplicates() -> Array {
        return reduce(into: []) { result, element in
            if !result.contains(element) {
                result.append(element)
            }
        }
    }
}
Alessandro Martin
fonte
Eu uso isso agora, só mudou o nome do método para removeDuplicates :)
J. Doe
Eu acho que esta solução é compacto, mas acredito que solução deanWombourne publicado um ano antes pode ser um pouco mais eficiente do que um reduce: em geral, é apenas mais uma linha em todo o seu projeto de escrever a sua função como: var unique: [Iterator.Element] = []; for element in self where !unique.contains(element) { unique.append(element) }; return unique. Admito que ainda não testei as performances relativas.
Cœur
3
Isso terá O(n²)desempenho de tempo, o que é realmente ruim para matrizes grandes.
Duncan C
@NickGaens Não, não é, é O(n²). Não há nada rápido nisso.
Alexander - Restabelece Monica
@ Cœur reduceou reduce(into:)não faria uma diferença crítica. Reescrever isso para não chamar repetidamente containsfaria uma diferença MUITO maior.
Alexander - Restabelece Monica
16

Aqui está uma categoria na SequenceTypequal preserva a ordem original da matriz, mas usa a Setpara fazer as containspesquisas para evitar o O(n)custo no contains(_:)método da matriz .

public extension Sequence where Element: Hashable {

    /// Return the sequence with all duplicates removed.
    ///
    /// i.e. `[ 1, 2, 3, 1, 2 ].uniqued() == [ 1, 2, 3 ]`
    ///
    /// - note: Taken from stackoverflow.com/a/46354989/3141234, as 
    ///         per @Alexander's comment.
    func uniqued() -> [Element] {
        var seen = Set<Element>()
        return self.filter { seen.insert($0).inserted }
    }
}

Se você não é Hashable ou Equatable, pode passar um predicado para fazer a verificação de igualdade:

extension Sequence {

    /// Return the sequence with all duplicates removed.
    ///
    /// Duplicate, in this case, is defined as returning `true` from `comparator`.
    ///
    /// - note: Taken from stackoverflow.com/a/46354989/3141234
    func uniqued(comparator: @escaping (Element, Element) throws -> Bool) rethrows -> [Element] {
        var buffer: [Element] = []

        for element in self {
            // If element is already in buffer, skip to the next element
            if try buffer.contains(where: { try comparator(element, $0) }) {
                continue
            }

            buffer.append(element)
        }

        return buffer
    }
}

Agora, se você não tem Hashable, mas é Equatable, você pode usar este método:

extension Sequence where Element: Equatable {

    /// Return the sequence with all duplicates removed.
    ///
    /// i.e. `[ 1, 2, 3, 1, 2 ].uniqued() == [ 1, 2, 3 ]`
    ///
    /// - note: Taken from stackoverflow.com/a/46354989/3141234
    func uniqued() -> [Element] {
        return self.uniqued(comparator: ==)
    }
}

Por fim, você pode adicionar uma versão do caminho da chave uniqued como esta:

extension Sequence {

    /// Returns the sequence with duplicate elements removed, performing the comparison usinig the property at
    /// the supplied keypath.
    ///
    /// i.e.
    ///
    /// ```
    /// [
    ///   MyStruct(value: "Hello"),
    ///   MyStruct(value: "Hello"),
    ///   MyStruct(value: "World")
    ///  ].uniqued(\.value)
    /// ```
    /// would result in
    ///
    /// ```
    /// [
    ///   MyStruct(value: "Hello"),
    ///   MyStruct(value: "World")
    /// ]
    /// ```
    ///
    /// - note: Taken from stackoverflow.com/a/46354989/3141234
    ///
    func uniqued<T: Equatable>(_ keyPath: KeyPath<Element, T>) -> [Element] {
        self.uniqued { $0[keyPath: keyPath] == $1[keyPath: keyPath] }
    }
}

Você pode colocar os dois no seu aplicativo, o Swift escolherá o caminho certo, dependendo do Iterator.Elementtipo da sua sequência .

deanWombourne
fonte
Heyyy finalmente alguém com uma O(n)solução. A propósito, você pode combinar as operações de "verificação" e "inserção" do conjunto em uma. Veja stackoverflow.com/a/46354989/3141234
Alexander - Reinstate Monica
Oh, isso é :) inteligente
deanWombourne
14

Inspirados em https://www.swiftbysundell.com/posts/the-power-of-key-paths-in-swift , podemos declarar uma ferramenta mais poderosa que é capaz de filtrar a unicidade em qualquer keyPath. Graças aos comentários de Alexander sobre várias respostas relacionadas à complexidade, as soluções abaixo devem estar próximas do ideal.

Solução não mutante

Estendemos uma função que é capaz de filtrar a unicidade em qualquer keyPath:

extension RangeReplaceableCollection {
    /// Returns a collection containing, in order, the first instances of
    /// elements of the sequence that compare equally for the keyPath.
    func unique<T: Hashable>(for keyPath: KeyPath<Element, T>) -> Self {
        var unique = Set<T>()
        return filter { unique.insert($0[keyPath: keyPath]).inserted }
    }
}

Nota: no caso em que seu objeto não está em conformidade com RangeReplaceableCollection, mas está em conformidade com Sequence, você pode ter essa extensão adicional, mas o tipo de retorno sempre será uma matriz:

extension Sequence {
    /// Returns an array containing, in order, the first instances of
    /// elements of the sequence that compare equally for the keyPath.
    func unique<T: Hashable>(for keyPath: KeyPath<Element, T>) -> [Element] {
        var unique = Set<T>()
        return filter { unique.insert($0[keyPath: keyPath]).inserted }
    }
}

Uso

Se queremos unicidade para os próprios elementos, como na pergunta, usamos o keyPath \.self:

let a = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
let b = a.unique(for: \.self)
/* b is [1, 4, 2, 6, 24, 15, 60] */

Se queremos unicidade para outra coisa (como para iduma coleção de objetos), usamos o keyPath de nossa escolha:

let a = [CGPoint(x: 1, y: 1), CGPoint(x: 2, y: 1), CGPoint(x: 1, y: 2)]
let b = a.unique(for: \.y)
/* b is [{x 1 y 1}, {x 1 y 2}] */

Solução mutante

Estendemos uma função de mutação capaz de filtrar a unicidade em qualquer keyPath:

extension RangeReplaceableCollection {
    /// Keeps only, in order, the first instances of
    /// elements of the collection that compare equally for the keyPath.
    mutating func uniqueInPlace<T: Hashable>(for keyPath: KeyPath<Element, T>) {
        var unique = Set<T>()
        removeAll { !unique.insert($0[keyPath: keyPath]).inserted }
    }
}

Uso

Se queremos unicidade para os próprios elementos, como na pergunta, usamos o keyPath \.self:

var a = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
a.uniqueInPlace(for: \.self)
/* a is [1, 4, 2, 6, 24, 15, 60] */

Se queremos unicidade para outra coisa (como para iduma coleção de objetos), usamos o keyPath de nossa escolha:

var a = [CGPoint(x: 1, y: 1), CGPoint(x: 2, y: 1), CGPoint(x: 1, y: 2)]
a.uniqueInPlace(for: \.y)
/* a is [{x 1 y 1}, {x 1 y 2}] */
Cœur
fonte
1
Agora essa é uma boa implementação! Somente com esse caminho de chave, é possível converter os fechamentos, de modo que você possa usar um argumento de fechamento para oferecer suporte ao código arbitrário (em fechamentos) e a meras pesquisas de propriedade (por caminhos de chave). A única alteração que eu faria é fazer o keyPathpadrão \.self, porque essa é provavelmente a maioria dos casos de uso.
Alexander - Reinstate Monica
1
@Alexander Tentei usar o Self como padrão, mas então precisaria fazer Elementsempre Hashable. Uma alternativa para um valor padrão é a adição de uma sobrecarga simples, sem parâmetros:extension Sequence where Element: Hashable { func unique() { ... } }
Cœur
Ah sim, faz sentido!
Alexander - Restabelecer Monica
1
Brilhante ... simples, e o melhor de tudo 'flexível'. THX.
BonanzaDriver 01/10/19
12

Uma solução alternativa (se não ótima) a partir daqui usando tipos imutáveis ​​em vez de variáveis:

func deleteDuplicates<S: ExtensibleCollectionType where S.Generator.Element: Equatable>(seq:S)-> S {
    let s = reduce(seq, S()){
        ac, x in contains(ac,x) ? ac : ac + [x]
    }
    return s
}

Incluído para contrastar a abordagem imperativa de Jean-Pillippe com uma abordagem funcional.

Como um bônus, esta função funciona tanto com strings quanto com arrays!

Editar: Esta resposta foi escrita em 2014 para o Swift 1.0 (antes Setestava disponível no Swift). Não requer conformidade com Hashable e é executado em tempo quadrático.

Pliskin
fonte
8
Cuidado, não há uma, mas duas maneiras em que isso é executado em tempo quadrático - ambos containse array acrescentam execução em O (n). Embora ele tenha o benefício de exigir apenas equações, não é lavável.
Velocidade da velocidade
essa é uma maneira realmente complicada de escrever filter. É O (n ^ 2) (que é necessário se você não deseja exigir Hashableconformidade), mas pelo menos convide explicitamente isso
Alexander - Reinstate Monica
10

veloz 2

com resposta da função uniq :

func uniq<S: SequenceType, E: Hashable where E==S.Generator.Element>(source: S) -> [E] {
    var seen: [E:Bool] = [:]
    return source.filter({ (v) -> Bool in
        return seen.updateValue(true, forKey: v) == nil
    })
}

usar:

var test = [1,2,3,4,5,6,7,8,9,9,9,9,9,9]
print(uniq(test)) //1,2,3,4,5,6,7,8,9
Daniel Krom
fonte
O Boolvalor obviamente é redundante, pois seu código nunca o lê. Use um em Setvez de um Dictionarye você receberá meu voto positivo.
Nikolai Ruhe
10

No Swift 5

 var array: [String] =  ["Aman", "Sumit", "Aman", "Sumit", "Mohan", "Mohan", "Amit"]

 let uniq = Array(Set(array))
 print(uniq)

Saída será

 ["Sumit", "Mohan", "Amit", "Aman"]
Sanjay Mishra
fonte
2
Esta é uma repetição de muitas das respostas já aqui, e não preserva a ordem.
Alexander - Restabelecer Monica
9

Mais uma solução Swift 3.0 para remover duplicatas de uma matriz. Esta solução aprimora muitas outras soluções já propostas por:

  • Preservando a ordem dos elementos na matriz de entrada
  • Complexidade linear O (n): filtro de passagem única O (n) + inserção do conjunto O (1)

Dada a matriz inteira:

let numberArray = [10, 1, 2, 3, 2, 1, 15, 4, 5, 6, 7, 3, 2, 12, 2, 5, 5, 6, 10, 7, 8, 3, 3, 45, 5, 15, 6, 7, 8, 7]

Código funcional:

func orderedSet<T: Hashable>(array: Array<T>) -> Array<T> {
    var unique = Set<T>()
    return array.filter { element in
        return unique.insert(element).inserted
    }
}

orderedSet(array: numberArray)  // [10, 1, 2, 3, 15, 4, 5, 6, 7, 12, 8, 45]

Código de extensão da matriz:

extension Array where Element:Hashable {
    var orderedSet: Array {
        var unique = Set<Element>()
        return filter { element in
            return unique.insert(element).inserted
        }
    }
}

numberArray.orderedSet // [10, 1, 2, 3, 15, 4, 5, 6, 7, 12, 8, 45]

Esse código aproveita o resultado retornado pela insertoperação on Set, que é executada em O(1), e retorna uma tupla indicando se o item foi inserido ou se já existe no conjunto.

Se o item estava no conjunto, ele filterserá excluído do resultado final.

Eneko Alonso
fonte
1
Para não ser exigente, você realizará a inserção e o teste de associação quantas vezes houver elementos; portanto, você deve contar o custo como O (n) também. No entanto, isso não significa 3xO (n), porque esses Os não têm custo igual ao do filtro, portanto a adição de O (n) é maçãs para laranjas. Se considerarmos que as operações definidas são uma parte O (1) do custo do filtro, a complexidade é meramente O (n), embora com um "O" maior. Levando isso ao limite, você também pode evitar as inserções quando o elemento já estiver no conjunto.
Alain T.
Você está certo, usando defero código faria a operação de teste definido duas vezes, uma com containse outra com insert. Depois de ler a documentação do Swift, descobri que insertretorna uma tupla indicando se o elemento foi inserido ou não, então simplifiquei o código removendo a containsverificação.
Eneko Alonso 16/03
2
Agradável. Sua extensão poderia ser melhor por fazê-lo onextension Sequence where Iterator.Element: Hashable { ... }
Cœur
@AlainT. Não. Ambos inserte containstêm O(1)complexidade. O(1) + O(1) = O(1). Essas duas operações são executadas nvezes (uma vez por chamada do fechamento passada para filter, que é chamada uma vez por elemento) Ou seja, se uma operação leva uma quantidade constante de tempo, independentemente do tamanho da entrada, fazê-lo duas vezes ainda faz com que seja necessário um tempo constante isso é independentemente do tamanho da entrada. A complexidade total disso é O(n).
Alexander - Restabelece Monica
9

Swift 4.x:

extension Sequence where Iterator.Element: Hashable {
  func unique() -> [Iterator.Element] {
    return Array(Set<Iterator.Element>(self))
  }

  func uniqueOrdered() -> [Iterator.Element] {
    return reduce([Iterator.Element]()) { $0.contains($1) ? $0 : $0 + [$1] }
  }
}

uso:

["Ljubljana", "London", "Los Angeles", "Ljubljana"].unique()

ou

["Ljubljana", "London", "Los Angeles", "Ljubljana"].uniqueOrdered()
Rok Gregorič
fonte
Isto é O(n^2). Não faça isso.
Alexander - Restabelece Monica
8

Swift 5

extension Sequence where Element: Hashable {
    func unique() -> [Element] {
        NSOrderedSet(array: self as! [Any]).array as! [Element]
    }
}
blackjacx
fonte
Fiz algumas variações para poder selecionar uma chave para comparar. 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 } } }
Marcelo de Aguiar
Não há necessidade de usar a Boolquando o único valor que você usa é true. Você está buscando um "tipo de unidade" (um tipo com apenas um valor possível). O tipo de unidade de Swift é Void, cujo único valor é ()(também conhecido como tupla vazia). Então você pode apenas usar [T: Void]. Embora você não deva fazer isso, porque basicamente inventou Set. Use em Setvez disso. Consulte stackoverflow.com/a/55684308/3141234 Exclua esta resposta.
Alexander - Restabelecer Monica
8

Pense como um programador funcional :)

Para filtrar a lista com base se o elemento já ocorreu, você precisa do índice. Você pode usar enumeratedpara obter o índice e mapretornar à lista de valores.

let unique = myArray
    .enumerated()
    .filter{ myArray.firstIndex(of: $0.1) == $0.0 }
    .map{ $0.1 }

Isso garante o pedido. Se você não se importa com o pedido, a resposta existente Array(Set(myArray))é mais simples e provavelmente mais eficiente.


ATUALIZAÇÃO: Algumas notas sobre eficiência e correção

Algumas pessoas comentaram sobre a eficiência. Definitivamente, estou na escola de escrever código correto e simples primeiro e depois descobrir gargalos mais tarde, embora eu aprecie que seja discutível se isso é mais claro do que isso Array(Set(array)).

Este método é muito mais lento que Array(Set(array)). Conforme observado nos comentários, ele preserva a ordem e trabalha em elementos que não são Hashable.

No entanto, o método do @Alain T também preserva a ordem e também é muito mais rápido. Portanto, a menos que o seu tipo de elemento não seja lavável, ou você só precise de um liner rápido, sugiro ir com a solução deles.

Aqui estão alguns testes em um MacBook Pro (2014) no Xcode 11.3.1 (Swift 5.1) no modo Release.

A função de criação de perfil e dois métodos para comparar:

func printTimeElapsed(title:String, operation:()->()) {
    var totalTime = 0.0
    for _ in (0..<1000) {
        let startTime = CFAbsoluteTimeGetCurrent()
        operation()
        let timeElapsed = CFAbsoluteTimeGetCurrent() - startTime
        totalTime += timeElapsed
    }
    let meanTime = totalTime / 1000
    print("Mean time for \(title): \(meanTime) s")
}

func method1<T: Hashable>(_ array: Array<T>) -> Array<T> {
    return Array(Set(array))
}

func method2<T: Equatable>(_ array: Array<T>) -> Array<T>{
    return array
    .enumerated()
    .filter{ array.firstIndex(of: $0.1) == $0.0 }
    .map{ $0.1 }
}

// Alain T.'s answer (adapted)
func method3<T: Hashable>(_ array: Array<T>) -> Array<T> {
    var uniqueKeys = Set<T>()
    return array.filter{uniqueKeys.insert($0).inserted}
}

E uma pequena variedade de entradas de teste:

func randomString(_ length: Int) -> String {
  let letters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"
  return String((0..<length).map{ _ in letters.randomElement()! })
}

let shortIntList = (0..<100).map{_ in Int.random(in: 0..<100) }
let longIntList = (0..<10000).map{_ in Int.random(in: 0..<10000) }
let longIntListManyRepetitions = (0..<10000).map{_ in Int.random(in: 0..<100) }
let longStringList = (0..<10000).map{_ in randomString(1000)}
let longMegaStringList = (0..<10000).map{_ in randomString(10000)}

Dá como saída:

Mean time for method1 on shortIntList: 2.7358531951904296e-06 s
Mean time for method2 on shortIntList: 4.910230636596679e-06 s
Mean time for method3 on shortIntList: 6.417632102966309e-06 s
Mean time for method1 on longIntList: 0.0002518167495727539 s
Mean time for method2 on longIntList: 0.021718120217323302 s
Mean time for method3 on longIntList: 0.0005312927961349487 s
Mean time for method1 on longIntListManyRepetitions: 0.00014377200603485108 s
Mean time for method2 on longIntListManyRepetitions: 0.0007293639183044434 s
Mean time for method3 on longIntListManyRepetitions: 0.0001843773126602173 s
Mean time for method1 on longStringList: 0.007168249964714051 s
Mean time for method2 on longStringList: 0.9114790915250778 s
Mean time for method3 on longStringList: 0.015888616919517515 s
Mean time for method1 on longMegaStringList: 0.0525397013425827 s
Mean time for method2 on longMegaStringList: 1.111266262292862 s
Mean time for method3 on longMegaStringList: 0.11214958941936493 s
Tim MB
fonte
1
ao contrário Array(Set(myArray)), isso funciona para coisas que não sãoHashable
Porter crianças
1
... e, diferentemente Array(Set(myArray))da ordem da sua matriz, é mantida.
Sander Saelmans
Parece a melhor resposta para mim, pelo menos no momento em que o Swift 5 já é a versão atual.
oradyvan
Esta é uma solução muito elegante; infelizmente, também é bastante lento.
Colin Stark
1
@ TimMB Oh, eu li mal sua postagem. Eu vi a adaptação de alguém que a usou lastIndex(of:). Discordo totalmente sobre o ponto de clareza versus otimização neste caso. Não acho que essa implementação seja particularmente clara, especialmente se comparada a uma solução simples baseada em conjunto. De qualquer forma, esse código deve ser extraído para uma função de extensão. Esse algoritmo se torna basicamente inutilizável, mesmo com um tamanho de entrada baixo, como nos milhares a dezenas de milhares. Não é difícil encontrar esses conjuntos de dados, as pessoas podem ter milhares de músicas, arquivos, contatos etc.
Alexander - Reinstate Monica
6

Para matrizes onde os elementos não são hashable nem comparáveis ​​(por exemplo, objetos complexos, dicionários ou estruturas), essa extensão fornece uma maneira generalizada de remover duplicatas:

extension Array
{
   func filterDuplicate<T:Hashable>(_ keyValue:(Element)->T) -> [Element]
   {
      var uniqueKeys = Set<T>()
      return filter{uniqueKeys.insert(keyValue($0)).inserted}
   }

   func filterDuplicate<T>(_ keyValue:(Element)->T) -> [Element]
   { 
      return filterDuplicate{"\(keyValue($0))"}
   }
}

// example usage: (for a unique combination of attributes):

peopleArray = peopleArray.filterDuplicate{ ($0.name, $0.age, $0.sex) }

or...

peopleArray = peopleArray.filterDuplicate{ "\(($0.name, $0.age, $0.sex))" }

Você não precisa se preocupar em criar valores Hashable e permite usar diferentes combinações de campos para obter exclusividade.

Nota: para uma abordagem mais robusta, consulte a solução proposta por Coeur nos comentários abaixo.

stackoverflow.com/a/55684308/1033581

[EDIT] alternativa Swift 4

Com o Swift 4.2, você pode usar a classe Hasher para criar um hash muito mais fácil. A extensão acima pode ser alterada para aproveitar isso:

extension Array
{
    func filterDuplicate(_ keyValue:((AnyHashable...)->AnyHashable,Element)->AnyHashable) -> [Element]
    {
        func makeHash(_ params:AnyHashable ...) -> AnyHashable
        { 
           var hash = Hasher()
           params.forEach{ hash.combine($0) }
           return hash.finalize()
        }  
        var uniqueKeys = Set<AnyHashable>()
        return filter{uniqueKeys.insert(keyValue(makeHash,$0)).inserted}     
    }
}

A sintaxe de chamada é um pouco diferente porque o fechamento recebe um parâmetro adicional que contém uma função para hash de um número variável de valores (que deve ser Hashable individualmente)

peopleArray = peopleArray.filterDuplicate{ $0($1.name, $1.age, $1.sex) } 

Ele também funcionará com um único valor de exclusividade (usando $ 1 e ignorando $ 0).

peopleArray = peopleArray.filterDuplicate{ $1.name } 
Alain T.
fonte
Isso pode gerar resultados aleatórios, dependendo do comportamento de "\()", pois pode não fornecer valores exclusivos, como em conformidade com o Hashableshould. Por exemplo, se todos os seus elementos estiverem em conformidade Printable, retornando o mesmo description, sua filtragem falhará.
Cœur
Acordado. A seleção dos campos (ou fórmula) que produzirão o padrão de exclusividade desejado terá que levar isso em consideração. Para muitos casos de uso, isso fornece uma solução ad-hoc simples que não requer alteração da classe ou estrutura do elemento.
Alain T.
2
@AlainT. Não faça isso, realmente. O objetivo de String não é ser um mecanismo de geração de chaves ad-hoc do gueto. Apenas restrinja Ta ser Hashable.
Alexander - Restabelece Monica
@Alexander eu apliquei essa idéia em uma nova resposta: stackoverflow.com/a/55684308/1033581
Cœur
Resposta perfeita como eu quero. Muito obrigado.
Hardik Thakkar
4

Você pode usar diretamente uma coleção de conjuntos para remover duplicados e convertê-los novamente em uma matriz

var myArray = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
var mySet = Set<Int>(myArray)

myArray = Array(mySet) // [2, 4, 60, 6, 15, 24, 1]

Depois, você pode solicitar seu array como quiser

myArray.sort{$0 < $1} // [1, 2, 4, 6, 15, 24, 60]
Vincent Choubard
fonte
"Então você pode solicitar sua matriz da maneira que desejar". E se eu quiser a mesma ordem da matriz original? Não é tão fácil.
Alexander - Restabelece Monica
3

Versão de sintaxe um pouco mais sucinta da resposta Swift 2 de Daniel Krom , usando um nome à direita e argumento abreviado, que parece basear-se na resposta original de Airspeed Velocity :

func uniq<S: SequenceType, E: Hashable where E == S.Generator.Element>(source: S) -> [E] {
  var seen = [E: Bool]()
  return source.filter { seen.updateValue(true, forKey: $0) == nil }
}

Exemplo de implementação de um tipo personalizado que pode ser usado com uniq(_:)(que deve estar em conformidade e Hashable, portanto Equatable, porque Hashablese estende Equatable):

func ==(lhs: SomeCustomType, rhs: SomeCustomType) -> Bool {
  return lhs.id == rhs.id // && lhs.someOtherEquatableProperty == rhs.someOtherEquatableProperty
}

struct SomeCustomType {

  let id: Int

  // ...

}

extension SomeCustomType: Hashable {

  var hashValue: Int {
    return id
  }

}

No código acima ...

id, conforme usado na sobrecarga de ==, pode ser qualquer Equatabletipo (ou método que retorna um Equatabletipo, por exemplo, someMethodThatReturnsAnEquatableType()). O código comentado demonstra a extensão da verificação de igualdade, onde someOtherEquatablePropertyhá outra propriedade de um Equatabletipo (mas também pode ser um método que retorna um Equatabletipo).

id, conforme usado na hashValuepropriedade computada (necessária para conformidade Hashable), pode ser qualquer Hashable(e, portanto Equatable) propriedade (ou método que retorna um Hashabletipo).

Exemplo de uso uniq(_:):

var someCustomTypes = [SomeCustomType(id: 1), SomeCustomType(id: 2), SomeCustomType(id: 3), SomeCustomType(id: 1)]

print(someCustomTypes.count) // 4

someCustomTypes = uniq(someCustomTypes)

print(someCustomTypes.count) // 3
Scott Gardner
fonte
Não há necessidade de usar a Boolquando o único valor que você usa é true. Você está buscando um "tipo de unidade" (um tipo com apenas um valor possível). O tipo de unidade de Swift é Void, cujo único valor é ()(também conhecido como tupla vazia). Então você pode apenas usar [T: Void]. Embora você não deva fazer isso, porque basicamente inventou Set. Use em Setvez disso. Veja stackoverflow.com/a/55684308/3141234
Alexander - Reinstate Monica
3

Caso você precise de valores classificados, isso funciona (Swift 4)

let sortedValues = Array(Set(array)).sorted()

Mauricio Chirino
fonte
2
Você está perdendo a ordem dos elementos neste caso.
Shmidt 16/11
Não, é para isso que .sorted()serve o final. Saudações.
Mauricio Chirino
@MauricioChirino E se sua matriz original fosse [2, 1, 1]? Ele sairia [1, 2], que não está ordenado: p
Alexander - Reinstate Monica
2
@MauricioChirino Não, não sou. Se o objetivo é remover valores duplicados de uma sequência, mantendo a ordem na qual os elementos apareceram exclusivamente, isso não faz isso. O exemplo de contador muito claro é [2, 1, 1]. A primeira aparição de elementos únicos, em ordem é [2, 1]. Essa é a resposta correta. Mas, usando o seu algoritmo (incorreto), você obtém [1, 2], que é classificado, mas não está na ordem correta e original.
Alexander - Restabelece Monica
2
Falha se os elementos em arraynão forem Hashable; somente Hashabletipos de dados podem ser adicionados a um conjunto, mas qualquer tipo de dados pode ser adicionado a uma matriz.
Mecki
3

Aqui está uma solução que

  • Não usa NStipos herdados
  • É razoavelmente rápido com O(n)
  • É conciso
  • Preserva a ordem dos elementos
extension Array where Element: Hashable {

    var uniqueValues: [Element] {
        var allowed = Set(self)
        return compactMap { allowed.remove($0) }
    }
}
Erik Aigner
fonte
2

aqui eu fiz uma solução O (n) para objetos. Solução não de poucas linhas, mas ...

struct DistinctWrapper <T>: Hashable {
    var underlyingObject: T
    var distinctAttribute: String
    var hashValue: Int {
        return distinctAttribute.hashValue
    }
}
func distinct<S : SequenceType, T where S.Generator.Element == T>(source: S,
                                                                distinctAttribute: (T) -> String,
                                                                resolution: (T, T) -> T) -> [T] {
    let wrappers: [DistinctWrapper<T>] = source.map({
        return DistinctWrapper(underlyingObject: $0, distinctAttribute: distinctAttribute($0))
    })
    var added = Set<DistinctWrapper<T>>()
    for wrapper in wrappers {
        if let indexOfExisting = added.indexOf(wrapper) {
            let old = added[indexOfExisting]
            let winner = resolution(old.underlyingObject, wrapper.underlyingObject)
            added.insert(DistinctWrapper(underlyingObject: winner, distinctAttribute: distinctAttribute(winner)))
        } else {
            added.insert(wrapper)
        }
    }
    return Array(added).map( { return $0.underlyingObject } )
}
func == <T>(lhs: DistinctWrapper<T>, rhs: DistinctWrapper<T>) -> Bool {
    return lhs.hashValue == rhs.hashValue
}

// tests
// case : perhaps we want to get distinct addressbook list which may contain duplicated contacts like Irma and Irma Burgess with same phone numbers
// solution : definitely we want to exclude Irma and keep Irma Burgess
class Person {
    var name: String
    var phoneNumber: String
    init(_ name: String, _ phoneNumber: String) {
        self.name = name
        self.phoneNumber = phoneNumber
    }
}

let persons: [Person] = [Person("Irma Burgess", "11-22-33"), Person("Lester Davidson", "44-66-22"), Person("Irma", "11-22-33")]
let distinctPersons = distinct(persons,
    distinctAttribute: { (person: Person) -> String in
        return person.phoneNumber
    },
    resolution:
    { (p1, p2) -> Person in
        return p1.name.characters.count > p2.name.characters.count ? p1 : p2
    }
)
// distinctPersons contains ("Irma Burgess", "11-22-33") and ("Lester Davidson", "44-66-22")
kas-kad
fonte
1
Em vez de usar um Setcom um costume DistinctWrapper, você deve usar um Dictionaryatributo de distinctAttributes para objetos. Ao seguir essa lógica, você acabaria implementando [ Dictionary.init(_:uniquingKeysWith:)] pastebin.com/w90pVe0p(https://developer.apple.com/documentation/… , que agora está embutido na biblioteca padrão. pastebin.com/w90pVe0p
Alexander - Restabelece Monica
2

Usei a resposta de Jean-Philippe Pellet e fiz uma extensão Array que realiza operações de conjunto em matrizes, mantendo a ordem dos elementos.

/// Extensions for performing set-like operations on lists, maintaining order
extension Array where Element: Hashable {
  func unique() -> [Element] {
    var seen: [Element:Bool] = [:]
    return self.filter({ seen.updateValue(true, forKey: $0) == nil })
  }

  func subtract(takeAway: [Element]) -> [Element] {
    let set = Set(takeAway)
    return self.filter({ !set.contains($0) })
  }

  func intersect(with: [Element]) -> [Element] {
    let set = Set(with)
    return self.filter({ set.contains($0) })
  }
}
Will Richardson
fonte
Não há necessidade de usar a Boolquando o único valor que você usa é true. Você está buscando um "tipo de unidade" (um tipo com apenas um valor possível). O tipo de unidade de Swift é Void, cujo único valor é ()(também conhecido como tupla vazia). Então você pode apenas usar [T: Void]. Embora você não deva fazer isso, porque basicamente inventou Set. Use em Setvez disso. Veja stackoverflow.com/a/55684308/3141234
Alexander - Reinstate Monica
2

Esta é apenas uma implementação muito simples e conveniente. Uma propriedade calculada em uma extensão de uma matriz que possui elementos equáveis.

extension Array where Element: Equatable {
    /// Array containing only _unique_ elements.
    var unique: [Element] {
        var result: [Element] = []
        for element in self {
            if !result.contains(element) {
                result.append(element)
            }
        }

        return result
    }
}
DaveAMoore
fonte
1
Isto também é O(n^2).
Alexander - Restabelece Monica
2
func removeDublicate (ab: [Int]) -> [Int] {
var answer1:[Int] = []
for i in ab {
    if !answer1.contains(i) {
        answer1.append(i)
    }}
return answer1
}

Uso:

let f = removeDublicate(ab: [1,2,2])
print(f)
Jack Rus
fonte
Eu acho que isso é o mais simples
Jack Rus
ele mantém a ordem e lhe dá uma matriz que você quer
Jack Rus
Isto também é O(n²).
Alexander - Restabelece Monica
2
  1. Primeiro adicione todos os elementos de uma matriz ao NSOrderedSet.
  2. Isso removerá todas as duplicatas em sua matriz.
  3. Converta novamente esse conjunto de pedidos em uma matriz.

Feito....

Exemplo

let array = [1,1,1,1,2,2,2,2,4,6,8]

let orderedSet : NSOrderedSet = NSOrderedSet(array: array)

let arrayWithoutDuplicates : NSArray = orderedSet.array as NSArray

saída de arrayWithoutDuplicates - [1,2,4,6,8]

Mahendra Thotakura
fonte
2

Uma versão ligeiramente reduzida, com base na resposta de extensão de matriz de Jean-Philippe Pellet:

extension Array where Element: Hashable {

    var uniques: Array {
        var added = Set<Element>()
        return filter { element in
            defer { added.insert(element) }
            return !added.contains(element)
        }
    }
}
Sander Saelmans
fonte
Isso realiza duas operações de hash por elemento, o que é desnecessário. insertretorna uma tupla que informa se o elemento já estava lá ou foi adicionado pela primeira vez. stackoverflow.com/a/55684308/3141234 Exclua esta resposta.
Alexander - Restabelecer Monica
1

Você sempre pode usar um dicionário, porque um dicionário pode conter apenas valores exclusivos. Por exemplo:

var arrayOfDates: NSArray = ["15/04/01","15/04/01","15/04/02","15/04/02","15/04/03","15/04/03","15/04/03"]

var datesOnlyDict = NSMutableDictionary()
var x = Int()

for (x=0;x<(arrayOfDates.count);x++) {
    let date = arrayOfDates[x] as String
    datesOnlyDict.setValue("foo", forKey: date)
}

let uniqueDatesArray: NSArray = datesOnlyDict.allKeys // uniqueDatesArray = ["15/04/01", "15/04/03", "15/04/02"]

println(uniqueDatesArray.count)  // = 3

Como você pode ver, a matriz resultante nem sempre estará em 'ordem'. Se você deseja classificar / ordenar a matriz, adicione isto:

var sortedArray = sorted(datesOnlyArray) {
(obj1, obj2) in

    let p1 = obj1 as String
    let p2 = obj2 as String
    return p1 < p2
}

println(sortedArray) // = ["15/04/01", "15/04/02", "15/04/03"]

.

AT3D
fonte
1

A maneira mais fácil seria usar o NSOrderedSet, que armazena elementos exclusivos e preserva a ordem dos elementos. Gostar:

func removeDuplicates(from items: [Int]) -> [Int] {
    let uniqueItems = NSOrderedSet(array: items)
    return (uniqueItems.array as? [Int]) ?? []
}

let arr = [1, 4, 2, 2, 6, 24, 15, 2, 60, 15, 6]
removeDuplicates(from: arr)
sgl0v
fonte
Gostaria de saber como esse desempenho se compara às melhores respostas aqui. Você já comparou?
Alexander - Restabelece Monica