本文介绍了Swift 3泛型:如何找到两个通用数组的通用集合的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我试图在Swift 3中找到两个通用数组的通用集合。我在下面的代码中遇到了类型兼容性错误。这发生在我试图向commons数组添加元素的行上:error:can not invoke'append'with type of''(T.Iterator.Element)'commonSet.append(lhsItem)

这个问题的解决方案是什么?

c> func commonElements< T:Sequence,U:Sequence>(_lhs:T,_rhs:U) - > [T]
其中T.Iterator.Element:Equatable,
.Iterator.Element == U.Iterator.Element
{
var commonSet = [T]()

lhsItem lhs {
rhsItem rhs {
if lhsItem == rhsItem {
commonSet.append(lhsItem)
}
}
}

return commonSet
}

commonElements([1,2,3],[3,5])


解决方案

Hashable类型解决方案



 扩展序列,其中Iterator.Element:Hashable {
func相交< T:Sequence>(with other:T) - > [Iterator.Element]
其中T.Iterator.Element == Self.Iterator.Element {
let otherSet = Set(other)
返回self.filter(otherSet.contains)
}
}

这就是我写这个的方式,它包含你的一些修改代码:


  1. 不用用2个参数编写全局函数(或者更糟糕的是,一个静态函数可以任意嵌套在某种不相关的类型中)可以将它写为 Sequence 的扩展名。这带来了一些很好的语法: a.intersect(with:b),而不是 commonElements(a,b)
  2. 您的方法中的嵌套for循环会导致 O(N ^ 2)时间复杂性。这种方法是 O(N),但有额外的约束:元素 Hashable 。可以对非可哈希元素进行辅助定义。它比你的空间复杂程度更糟。你的 O(1),而这是 O(M)空间复杂度,其中 M 是第二个列表的大小。

  3. 我改变了初始化为空的数组的追加到最初完整数组的过滤。它的语法较短。



比较类型的解决方案

 扩展序列其中Iterator.Element:Comparable {
func相交< T:Sequence>(with other:T) - > [Iterator.Element]
其中T.Iterator.Element == Self.Iterator.Element {
让arrayA = self.sorted()
让arrayB = other.sorted()
var indexA = 0,indexB = 0

var intersection:[Iterator.Element] = []
,而indexA< arrayA.count&& indexB< arrayB.count {
let a = arrayA [indexA]
let b = arrayB [indexB]

if(a< b){indexA + = 1} $ b $如果(b else / *隐含:a == b * / {
intersection.append(a)
indexA + = 1
indexB + = 1
}
}

返回交点;




$ b $ p
$ b

这个解决方案比较慢,使用 O(N * log_2(N))的复杂性,但仍然好于 O(N ^ 2)。它的空间复杂度 O(2N),因为它使得两个序列都有重复的排序副本。


I am trying to find the common set of two generic arrays in Swift 3. I got a type compatibility error with the code below. This happens on the line where I am trying to add an element to the commons array: "error: cannot invoke 'append' with an argument list of type '(T.Iterator.Element)' commonSet.append(lhsItem)"

What is the solution to this problem?

func commonElements<T: Sequence, U: Sequence>(_ lhs: T, _ rhs: U) -> [T]
    where T.Iterator.Element: Equatable,
          T.Iterator.Element == U.Iterator.Element
{
    var commonSet = [T]()

    for lhsItem in lhs {
        for rhsItem in rhs {
            if lhsItem == rhsItem {
                commonSet.append(lhsItem)
            }
        }
    }

    return commonSet
}

commonElements([1,2,3], [3,5])
解决方案

Solution for Hashable types

extension Sequence where Iterator.Element: Hashable {
    func intersect<T: Sequence>(with other: T) -> [Iterator.Element]
    where T.Iterator.Element == Self.Iterator.Element {
        let otherSet = Set(other)
        return self.filter(otherSet.contains)
    }
}

That's how I would write this, which contains a few modifications of your code:

  1. Instead of writing a global function (or worse, a static function that's arbitrarily nested in some unrelated type) with 2 parameters, you can write it as an extension of Sequence. This brings about some nice syntax: a.intersect(with: b), rather than commonElements(a, b).
  2. The nested for-loops in your approach lead to O(N^2) time complexity. This approach is O(N), but has the additional constraint that Element is Hashable. A secondary definition can be made that works for non-hashable Elements. It has worse space complexity than yours. Yours is O(1), whereas this is has O(M) space complexity, where M is the size of the second list.
  3. I changed the appending of an initially-empty Array to the filtering of an initially full Array. It's shorter syntax.

Solution for Comparable types

extension Sequence where Iterator.Element: Comparable {
    func intersect<T: Sequence>(with other: T) -> [Iterator.Element]
    where T.Iterator.Element == Self.Iterator.Element {
        let arrayA = self.sorted()
        let arrayB = other.sorted()
        var indexA = 0, indexB = 0

        var intersection: [Iterator.Element] = []
        while indexA < arrayA.count && indexB < arrayB.count {
            let a = arrayA[indexA]
            let b = arrayB[indexB]

            if      (a < b) { indexA += 1 }
            else if (b < a) { indexB += 1 }
            else /* implied: a == b */ {
                intersection.append(a)
                indexA += 1
                indexB += 1
            }
        }

        return intersection;
    }
}

This solution is slower, with O(N * log_2(N)) complexity, but still much better than O(N^2). It has space complexity O(2N), because it makes duplicated, sorted copies of both sequences.

这篇关于Swift 3泛型:如何找到两个通用数组的通用集合的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

10-22 05:09