Уменьшить экземпляры объекта в массиве по правилу

Question

У меня есть простой массив пользовательских объектов.

Я хотел бы уменьшить массив до одного экземпляра каждого цвета, выбранного наибольшим размером.

Решения, которые я придумал, кажутся довольно громоздкими, что было бы лучшим подходом, я пробовал смотреть на сокращение и фильтрацию, но не мог понять, как подать заявку здесь.

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 ниже).

Отметим также класс типа именования (CamelCase): так Foo, а не foo.

Отказа от ответственности: Не смотрите сам слеп на асимптотической нотации сложности ниже, так как premature optimization есть, в зависимости от контекста и предполагаемой область применения вашей программы, вообще что-то грех. Я включил их ниже просто, чтобы иметь некоторую меру, чтобы сравнить различные методы. Выберите тот, который, по вашему мнению, имеет для вас наибольший смысл.

---

Метод 1

Наихудший ...

• время сложность: O(n log n)

• пространство сложность: O(n)

где пространство сложность относится к пространству, используемому в избытке массива , которому назначен конечный результат.

• Пусть Foo соответствовать Hashable (пусть hashValue относятся к .color собственности).
• Сортировка массива Foo экземпляров w.r.t. убывающий размер (.size свойство).
• Отфильтровать отсортированную массив w.r.t. до первого появления каждого цвета, используя соответствие Hashable для быстрого использования O(1) поиск значения хеш для существующего цвета в словаре Foo:Bool. Адаптировано из комментариев Airspeed Velocity в the following answer.

---

Метод 2 (как это было предложено Николаем Ruhe):

худшем случае ...

• время сложность: O(n log n)

• пространство сложность: 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 (в частности, гибрид интросортирования в сочетании с insertion sort), работающий в худшем случае, как O(n log n).

Answer 2

Вы можете попробовать этот метод с использованием фильтра, но это может занять много времени, когда вы массив огромно, так как вы должны перебирать массив для каждого элемента.

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 
} 

Answer 3

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 намного лучше (и быстрее).

Answer 4

Вот простой и очень производительным решением, которое не нуждается в Hashable или каких-либо других модификаций на 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)