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

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"))

- Magrafear

---

我看到了提出的问题。我尝试将解决方案应用到我的示例中，但对我来说并不简单，因为它不仅仅是一个整数数组。 - Magrafear

你还没有展示你的尝试代码或者一个样例输出。 - Wain

Answer 1

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

还要注意类类型命名约定（CamelCase）：因此使用Foo而不是foo。 免责声明：不要盯着下面的渐近复杂性符号看得眼花缭乱，因为早期优化根据程序的上下文和预期使用领域，通常是一种错误。我仅包含它们以便比较不同的方法。选择您认为最有意义的方法。

---

方法1

最坏情况...

• 时间复杂度: O(n log n)

• 空间复杂度: O(n)

其中空间复杂度是指超过分配给最终结果的数组所使用的空间。

• 让Foo符合Hashable(让hashValue与.color属性相关联)。
• 按照大小递减的顺序对Foo实例数组进行排序(.size属性)。
• 使用符合Hashable的实现，通过在Foo:Bool字典中迅速使用O(1)哈希值查找现有颜色来过滤已排序的数组中的每种颜色的第一个出现。从Airspeed Velocity在以下答案中的评论中改编而来。

---

方法二（由Nikolai Ruhe提出）：

最坏情况下...

• 时间复杂度：O(n log n)

• 空间复杂度：O(1)

• 按颜色（主要）和大小（次要）对数组进行排序。
• 过滤已排序的数组，找出与它们前面的元素颜色不同的元素。

---

对于第三种方法（可能是此应用程序的最佳方法），请参见下面 Nikolai Ruhe 的答案，介绍了一种具有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（具体来说是介绍排序和插入排序的混合体）进行排序，在最坏情况下运行时间为 O(n log n)。

- dfrib

---

为什么不使用 Set 和 maxElement 呢？ :) - Eendje

我已经翻译了，但是不确定是否更好。我想也许你可以把它做得更好 :p 我会将其作为答案发布以供您查看 :) - Eendje

@NikolaiRuhe 这是一个有意想要实现懒加载（懒加载由我而非 Swift 术语的懒加载）的实现方式，.hashValue 计算属性的比较等于 .color String 属性的 hashvalue 比较。然而，我意识到两个不同的字符串有可能返回相同的 hash 值，所以在这里最好使用 .color。感谢您的提醒。 - dfrib

@dfri 字符串的hashValue碰撞非常普遍，因此比较哈希值显然是一个错误。 - Nikolai Ruhe

使用 updateValue（…） 的返回值很好，我总是忘记这个。 - Michaël Azevedo

Answer 2

let result = Set(array).flatMap { color in array.filter { $0 == color }.maxElement { $0.0.size < $0.1.size } }

Set 和 maxElement 的组合。

由于我使用了 dfri 答案中的示例，因此应注意 array 中的对象应符合 Hashable 和 Equatable。答案仅用于展示另一种替代方案，个人认为 dfri 的答案更好（也更快）。

- Eendje

---

我本来要删除这个“答案”（我只是想展示dfri），但能告诉我为什么要踩吗？ - Eendje

可能是因为它难以理解和繁琐？这是我的看法。 - Nikolai Ruhe

我认为这是一个有效的答案（无论如何不应该被踩），即使它本身有点复杂。Eendje：可能要明确提到这个答案依赖于Foo符合Hashable和Equatable（符合前者的要求符合后者）：可能有人在没有确定这种一致性的情况下尝试了你的代码行。 - dfrib

就像我之前说的（以及在 dfri 的回答评论中提到的），我只是向他展示了如何将 Set 和 maxElement 结合使用，因为在评论中发布它会有点难以阅读。但我猜即使是为了展示，也值得被点踩。 - Eendje

@dfri：是的，这就是为什么我提到我使用你的答案作为基础 :) 但无论如何，我都打算删除这个答案 :) - Eendje

Answer 3

这里有一个简单而且非常高效的解决方案，不需要在 Foo 上进行任何修改，也不需要使用 Hashable ：

var biggestFoos = [String: Foo]()
for foo in array where biggestFoos[foo.color]?.size < foo.size {
    biggestFoos[foo.color] = foo
}
let result = Array(biggestFoos.values)

- Nikolai Ruhe

---

在我坐公交回家的路上，我意识到一个[String: Foo]字典解决方案将是一个更好的方法；当我写了一个出来（虽然没有像你上面的for ... where那么简洁），并且正当我进入这个帖子更新我的答案时，我看到你已经远远超过了我。我相信这个O(n)的解决方案（过早的优化是一种罪恶，但由于我已经在我的解决方案中使用了大O符号...）应该是被接受的答案，+1。 - dfrib

@dfri 谢谢。我认为你对于排序原始数组的想法有些好处，可以改进成一个很好的解决方案。优点是它不需要额外的存储空间。因此，如果有空间限制的话，理想的算法应该是按颜色（主要）和尺寸（次要）对数组进行排序，然后选择每个具有与其前任不同颜色的元素。这是一个有趣的练习（你会得到我的投票） :) - Nikolai Ruhe

感谢您的反馈和想法。这确实是一个有趣的练习，但我认为它变得有点混乱了（https://gist.github.com/dfrib/847071ff64c856db8f1c），也许是因为我受到了Swift.SO对简洁代码答案的影响。 - dfrib

@dfri 是的，压缩并不总是好事。这是我筛选数组中第一次出现新颜色的版本：var previousColor: String?; let result = array.filter { if $0.color != previousColor { previousColor = $0.color; return true }; return false } - Nikolai Ruhe

很好，自然而然地，.filter 比狭隘的扩展更为优美。如果我把完整的排序-筛选解决方案添加到我的答案中（当然也附上原作者的姓名），你介意吗？ - dfrib

@dfri 当然，请开始。 - Nikolai Ruhe

Answer 4

你可以尝试使用过滤器来实现此方法，但如果数组很大，由于你需要为每个元素迭代数组，这可能会耗费很多时间。

let arrayFiltered = array.filter { (fooElement) -> Bool in
    for (idx, fooItem) in array.enumerate() {

        if fooItem.color == fooElement.color && fooItem.size > fooElement.size {
            return false
        }
    }
    return true
}

- Michaël Azevedo