arrays - 按规则减少数组中对象的实例

Question

我有一个简单的自定义对象数组。

我想将数组缩减为按最大尺寸选择的每种颜色的一个实例。

我想出的解决方案似乎很笨重，什么是最好的方法，我已经尝试查看 reduce 和 filter 但无法弄清楚如何在此处应用。

class foo {

    var color: String
    var size: Int
    var shape: String

    init(color:String, size:Int, shape:String){
        self.color = color
        self.size = size
        self.shape = shape
    }

}

var array = [foo]()

array.append(foo(color: "Blue", size: 2, shape: "Round"))
array.append(foo(color: "Red", size: 3, shape: "Square"))
array.append(foo(color: "Blue", size: 5, shape: "Round"))
array.append(foo(color: "Yellow", size: 1, shape: "Triangle"))
array.append(foo(color: "Blue", size: 1, shape: "Hexagon"))

Answer 1

您可以通过首先对数组进行排序，然后使用例如过滤掉重复的颜色对象来避免暴力 O(n^2) 嵌套循环(和枚举)解决方案哈希值查找(下面的方法 1)或针对排序数组的巧妙排除(下面的方法 2)。

另请注意类 type 命名约定(CamelCase):因此 Foo 而不是 foo。

免责声明:不要对下面的渐近复杂性符号视而不见，如 premature optimization根据程序的上下文和预期使用区域，这通常是一种罪过。我将它们包含在下面只是为了有一些措施来比较不同的方法。选择您认为最有意义的一项。

---

方法一

Worst case...

• time complexity: O(n log n)

• space complexity: O(n)

Where space complexity refers to space used in excess of the array to which the final result is assigned.

• 让Foo符合Hashable(让hashValue与.color属性相关)。
• 对 Foo 实例 w.r.t 的数组进行排序。减小尺寸(.size 属性)。
• 过滤排序数组 w.r.t.到每种颜色的第一次出现，使用对 Hashable 的一致性来快速使用 O(1) 散列值查找 Foo:Bool 中的现有颜色> 词典。改编自 Airspeed Velocity 在 the following answer 中的评论.

---

方法 2(由 Nikolai Ruhe 提出):

Worst case...

• time complexity: O(n log n)

• space complexity: O(1)

• 按颜色(主要)和大小(次要)对数组进行排序。
• 过滤排序数组中颜色与其前身颜色不同的元素。

---

对于第三种(可能是该应用程序的最佳方法)方法，see Nikolai Ruhe:s answer below , 分别提出了一个 O(n)/O(n) 时间/空间最坏情况复杂度的方法。

---

实现

[只有方法 1 需要此步骤] 使 Foo 符合 Hashable 和 Equatable:

/* Let Foo conform to Hashable */
class Foo : Hashable {

    var color: String
    var size: Int
    var shape: String

    init(color:String, size:Int, shape:String){
        self.color = color
        self.size = size
        self.shape = shape
    }

    var hashValue: Int {
        return color.hashValue
    }

}

/* And Equatable */
func ==(lhs: Foo, rhs: Foo) -> Bool {
    return lhs.color == rhs.color
}

下面是过滤器方法的设置和示例:

/* Foo array example */
var array = [Foo]()

array.append(Foo(color: "Blue", size: 2, shape: "Round"))
array.append(Foo(color: "Red", size: 3, shape: "Square"))
array.append(Foo(color: "Blue", size: 5, shape: "Round"))
array.append(Foo(color: "Yellow", size: 1, shape: "Triangle"))
array.append(Foo(color: "Blue", size: 1, shape: "Hexagon"))

根据您的规范过滤:

/* Method 1 (assumes Foo conforms to Hashable (& Equatable))   */
var addedDict = [Foo:Bool]()
var arrFiltered = array.sort{ $0.0.size > $0.1.size }
    .filter {addedDict.updateValue(true, forKey: $0) == nil }

/* Method 2 (as proposed by Nikolai Ruhe)                      */
var previousColor: String?
let arrFiltered = array.sort{ $0.color == $1.color ? $0.size > $1.size : $0.color < $1.color }
    .filter{ if $0.color != previousColor { previousColor = $0.color; return true }; return false }
    /* condensed .filter solution by @Nikolai Ruhe, thanks! */

结果:

for bar in arrFiltered {
    print(bar.color, bar.size)
}

/* Blue 5
   Red 3
   Yellow 1 */

排序步骤是此解决方案中的主要步骤(对于这两种方法)。来自 swift/stdlib/public/core/Sort.swift.gyb ，似乎 Swift 使用了 introsort (特别是 introsort 与 insertion sort 的混合体)，在最坏情况下运行为 O(n log n)。