Фильтр против раздела в Swift

Question

Я пытаюсь найти ненулевой элемент в данном массиве и переместить нули назад.Применяя фильтр подход, это работает.Применение подхода с разделами дает мне массив, который не является непостоянной проблемой.

Мне интересно преимущества использования фильтров и разделов с точки зрения сложности времени, а также сложности пространства.Обычно, что предпочтительно использовать?

var inputArray = [1,4,0,0,5,1,0] 

Подход фильтра

func NonZeroArrayWithFilter(array:[Int]) -> [Int] {
  return array.filter({$0 > 0}) + array.filter({$0 == 0})
}

Подход раздела

func NonZeroArrayWithPartition(array:[Int]) -> [Int] {
  return array.partition(by: { $0 > 0 }) + array.partition(by: { $0 == 0 })
}

Answer 1

Обратите внимание, что partition возвращает только индекс, а не массив, как filter.partition выполняет переиндексацию вашего массива в зависимости от условия, он упорядочит все элементы с неудовлетворительными параметрами, прежде чем они будут удовлетворены.Итак, partition вернет первый индекс удовлетворяющего элемента.Ошибка, которую вы получаете за использование мутирующего члена для partition, будет решена следующим образом.

func NonZeroArrayWithPartition(array: [Int]) -> [Int] {
    var array = array
//    return array.partition(by: { $0 > 0 }) + array.partition(by: { $0 == 0 }) // your statement
    _ = array.partition(by: {$0 == 0})
    return array
}

Ваше утверждение прокомментировано, потому что оно пройдет Array.Index (то есть индекс массива), в то время как функция должна вернутьмассив, если int.При использовании этого подхода вы можете объявить так, иначе вы получите предупреждение.let inputArray = [1,4,0,0,5,1,0]Вот еще один подход к тому же.

var inputArray = [1,4,0,0,5,1,0]
...
NonZeroArrayWithPartition(array: &inputArray)
...
func NonZeroArrayWithPartition(array:inout [Int]) -> [Int] {
    _ = array.partition(by: {$0 == 0})
    return array
}

Это изменит исходный массив (т.е. вызов по ссылке)Вот несколько утверждений, чтобы вы могли лучше понять, что поведение partition.

var inputArray = [1,4,0,0,5,1,0]
print(inputArray)
print(NonZeroArrayWithFilter(array: inputArray))
print(inputArray)
print(NonZeroArrayWithPartition(array: &inputArray))
print(inputArray)

будет выглядеть примерно так:

[1, 4, 0, 0, 5, 1, 0][1, 4, 5, 1, 0, 0, 0][1, 4, 0, 0, 5, 1, 0][1, 4, 1, 5, 0, 0, 0][1, 4, 1, 5, 0, 0, 0]

Вот документация для partition.Лично я предлагаю использовать функцию partition для такого подхода.Потому что функция фильтра создаст 2 массива, и вам нужно присоединиться к ним, а секция просто переиндексировать массив.

Answer 2

Вот краткое решение:

array.sorted { $1 == 0 * $0 }

Это O (n log n) .Это коротко, но не так быстро, как O (2 n) вашего подхода фильтра .

Более эффективное решение будет:

func zeroTail(_ array:[Int]) -> [Int] {
    guard !array.isEmpty else { return array }

    var tempo = Array(repeating: 0, count: array.count)
    var index = 0
    array.forEach { element in
        if element != 0 {
            tempo[index] = element
            index += 1
        }
    }
    return tempo
}

zeroTail([0,1,2,0,6,0,2,5,0])  //[1, 2, 6, 2, 5, 0, 0, 0, 0]

Обходит массив только один раз: O (n) .

partition эффективен, но здесь он не подходит, поскольку он меняет элементы, которые belong in the second partition, с другими, которые этого не делают.И это противоречит требованию сохранения исходного порядка ненулевых элементов.

---

Вы также можете определить расширение для Array в целом:

extension Array where Element: Comparable {
    func withTail(_ value: Element) -> [Element] {
        guard !self.isEmpty else { return self }

        var tempo: [Element] = Array(repeating: value, count: self.count)
        var index: Int = 0
        self.forEach { element in
            if element != value {
                tempo[index] = element
                index += 1
            }
        }
        return tempo
    }
}

И вот некоторыеварианты использования:

[0, 1, 2, 0, 6, 0, 2, 5, 0].withTail(0)            //[1, 2, 6, 2, 5, 0, 0, 0, 0]
["c", "a", "c", "b", "c", "d", "c"].withTail("c")  //["a", "b", "d", "c", "c", "c", "c"]
[1.2, 2.3, 4.5, 1.2].withTail(6.0)                 //[1.2, 2.3, 4.5, 1.2] 
[Character]().withTail("a")                        //[]

Answer 3

filter возвращает массив элементов, соответствующих вашему состоянию;partition переупорядочивает массив так, что все элементы, соответствующие вашему условию, находятся перед теми, которые не соответствуют.Например:

var array = [1, 5, 2, 6]
array.filter { $0 < 4 } // returns [1, 2]

// reorders `array` to [1, 2, 5, 6], and returns 2:
// all elements before array[2] are smaller than 4
array.partition { $0 < 4 }

Другими словами, partition не возвращает новый массив.

Answer 4

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

let array = [1,2,0,6,0,2,5]
func nonZeroSortDescriptor(lhs: Int, rhs: Int -> Bool {
    return rhs == 0
}
array.sorted(by: nonZeroSortDescriptor)
//1,2,6,2,5,0,0

UPD

Также @Alexander был прав, сложность такого рода будет O(2N + 1)Поэтому здесь оптимизирован способ сортировки:

func NonZeroArrayWithFilterFast(array:[Int]) -> [Int] {
    var zerosCount = 0
    return array.filter({
        if $0 == 0 {
            zerosCount += 1
        }
        return $0 > 0
    }) + [Int](repeating: 0, count: zerosCount)
}
NonZeroArrayWithFilterFast(array: array)

Сложность этого алгоритма равна O(N)

Answer 5

filter создает новый массив и сохраняет исходный нетронутым.partition(by:) работает с массивом на месте.Либо вам нужно сделать ваш массив изменчивым, либо вам нужно сделать изменяемую копию.Например:

extension MutableCollection where Self.Element: ExpressibleByIntegerLiteral & Equatable {
    mutating func moveZerosToEnd() -> Self {
        var copy = self
        _ = copy.partition(by: { $0 == 0 })
        return copy
    }
}

var inputArray = [1,4,0,0,5,1,0] 

print(inputArray.moveZerosToEnd())