Melinda February 2016

Reduce instances of an object in an array by rule

I have a simple array of a custom objects.

I would like to reduce the array to one instance of each color selected by the largest size.

The solutions I have come up with seem long an unwieldy, what would be the best approach, i've tried looking at reduce and filter but couldn't work out how to apply here.

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

Answers


Michaël Azevedo February 2016

You can try this method using filter, but it can be time-consuming when you array is huge since you have to iterate through the array for each element.

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
}


dfri February 2016

You can avoid brute-force O(n^2) nested looping (and enumeration) solution by first sorting the array, and thereafter filtering out duplicate colour objects using e.g. hash value lookup (Method 1 below) or clever exclusion with regard to the sorted array (Method 2 below).

Note also class type naming convention (CamelCase): so Foo rather than foo.

Disclaimer: Don't stare yourself blind on the asymptotic complexity notations below, as premature optimization is, depending on the context and intended usage area of your program, generally something of a sin. I've included them below simply to have some measure to compare the different methods by. Choose the one that you think makes most sense to you.


Method 1

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.

  • Let Foo conform to Hashable (let hashValue relate to .color property).
  • Sort the array of Foo instances w.r.t. decreasing size (.size property).
  • Filter the sorted array w.r.t. to first occurrence of each color, using the conformance to Hashable to swiftly use O(1) hash value lookup for existing color in a Foo:Bool dictionary. Adapted from the comments by Airspeed Velocity in the following answer.

Method 2 (as proposed by Nikolai Ruhe):

Worst case...

    <


Eendje February 2016

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

A combination of Set and maxElement.

Since I used the examples of dfri's answer, it should be noted that the objects in array should conform to Hashable and Equatable. The answer is made just to show an alternative and personally I think the answer of dfri is a lot better (and faster).


Nikolai Ruhe February 2016

Here's a simple and very performant solution that does not need Hashable or any other modifications on Foo:

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

Post Status

Asked in February 2016
Viewed 3,480 times
Voted 9
Answered 4 times

Search




Leave an answer