Подсчет инверсий с сортировкой слияний, Swift

Question

У меня проблема с инверсией обращения с Swift. Мне требуется 45 минут, и через 45 минут происходит сбой Xcode. Я никогда не получаю ответа. Можете ли вы мне помочь, чтобы выяснить, в чем проблема? Потому что эта проблема заняла у людей всего несколько секунд. Что не так с кодами? Btw проблемы подсчета инверсии в массиве (100000 несортированных целые числа)

import UIKit 
var count: Int = Int() 


func mergeSort(_ array: [Int]) -> [Int] { 
    guard array.count > 1 else { return array }  

    let middleIndex = array.count/2    

    let leftArray = mergeSort(Array(array[0..<middleIndex])) 


    let rightArray = mergeSort(Array(array[middleIndex..<array.count])) 


    return merge(leftPile: leftArray, rightPile: rightArray)    
} 
func merge(leftPile: [Int], rightPile: [Int]) -> [Int] { 

    var leftIndex = 0 
    var rightIndex = 0 



    var orderedPile = [Int]() 


    while leftIndex < leftPile.count && rightIndex < rightPile.count { 
     if leftPile[leftIndex] < rightPile[rightIndex] { 
      orderedPile.append(leftPile[leftIndex]) 
      leftIndex += 1 
     } else if leftPile[leftIndex] > rightPile[rightIndex] { 
      orderedPile.append(rightPile[rightIndex]) 
      count += leftPile.count - leftIndex 
      rightIndex += 1 

     } else { 
      orderedPile.append(leftPile[leftIndex]) 
      leftIndex += 1 
      orderedPile.append(rightPile[rightIndex]) 
      rightIndex += 1 
     } 
    } 


    while leftIndex < leftPile.count { 
     orderedPile.append(leftPile[leftIndex]) 
     leftIndex += 1 
    } 

    while rightIndex < rightPile.count { 
     orderedPile.append(rightPile[rightIndex]) 
     rightIndex += 1 
    } 




    return orderedPile 

} 

func ready(fileName: String) -> [Int] { 
    guard let path = Bundle.main.path(forResource: fileName, ofType: "txt") else { 
     return [Int]() 
    } 

    do { 
     let numbers = try String(contentsOfFile: path).components(separatedBy: "\r\n") 
      .flatMap {Int($0)} 
     mergeSort(numbers) 




     return numbers 
    } catch { 
     return [Int]() 
    } 
} 
ready(fileName: "IntegerArray")) 
print(count) 

Answer 1

Хорошо. Решаемые. Не используйте игровые площадки для запуска этого. Откройте проект x-кода , и он займет ~ 1 секунду.

Answer 2

Я думаю, что есть некоторые вещи, о вашей реализации, которые держат вещи. Я перестроил свой проект в детской площадке, и по сравнению код к следующему, который я думаю, это более «классический» способ реализации алгоритма:

func mergeAlt(leftPile: [Int], rightPile: [Int]) -> [Int] { 

    var leftPileCopy = leftPile 
    var rightPileCopy = rightPile 

    var orderedPile = [Int]() 

    while !leftPileCopy.isEmpty && !rightPileCopy.isEmpty { 
     if leftPileCopy.first! <= rightPileCopy.first! { 
      orderedPile.append(leftPileCopy.first!) 
      leftPileCopy.removeFirst() 
     } else { 
      orderedPile.append(rightPileCopy.first!) 
      rightPileCopy.removeFirst() 
     } 
    } 

    // By this stage, only one array will have anything in it 
    while !leftPileCopy.isEmpty { 
     orderedPile.append(leftPileCopy.first!) 
     leftPileCopy.removeFirst() 
    } 

    while !rightPileCopy.isEmpty { 
     orderedPile.append(rightPileCopy.first!) 
     rightPileCopy.removeFirst() 
    } 
    return orderedPile 
} 

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

Например, я провел это на игровой площадке против вашей реализации на массиве из 1000 случайных чисел. В вашем алгоритме выполняется «сравнительный» раздел кода (т. Е. «Если leftPile [index] < rightPile [index] ...») почти 8000 раз для каждой сваи, а затем запускает код для обработки остаточного кода (т.е. «while leftIndex < leftPile.count ...») более 1000 раз для каждой сваи. Вышеупомянутая реализация выполняется 500 раз для теста сравнения, а затем 4 раза для обработки любых остаточных элементов.

Не могли бы вы запустить это для своего большего массива и сообщить мне, если это поможет?

Answer 3

В случае, если кто-то здесь, пытаясь найти граф Инверсия Swift 4 версию, основанную на Merge Сортировать

import Foundation 

func sortAndCount(_ array : [Int]) -> ([Int], Int) { 
    guard array.count > 1 else { 
     return (array, 0) 
    } 

    let middleIndex = array.count/2 
    let (leftArray, leftCount) = sortAndCount(Array(array[0..<middleIndex])) 
    let (rightArray, rightCount) = sortAndCount(Array(array[middleIndex..<array.count])) 
    let (finalArray, splitCount) = mergeAndCountSplitInversation(leftArray, rightArray) 
    return (finalArray, leftCount + rightCount + splitCount) 
} 

func mergeAndCountSplitInversation(_ leftPile: [Int], _ rightPile: [Int]) -> ([Int], Int) { 
    var leftIndex = 0 
    var rightIndex = 0 
    var orderedPile = [Int]() 
    var inversationCount = 0 

    while leftIndex < leftPile.count && rightIndex < rightPile.count { 
     if leftPile[leftIndex] <= rightPile[rightIndex] { 
      orderedPile.append(leftPile[leftIndex]) 
      leftIndex += 1 
     } else { 
      orderedPile.append(rightPile[rightIndex]) 
      rightIndex += 1 
      inversationCount = inversationCount + leftPile.count - leftIndex 
     } 
    } 

    while leftIndex < leftPile.count { 
     orderedPile.append(leftPile[leftIndex]) 
     leftIndex += 1 
    } 

    while rightIndex < rightPile.count { 
     orderedPile.append(rightPile[rightIndex]) 
     rightIndex += 1 
    } 

    print("inversion for array - \(orderedPile)") 
    print("count - \(inversationCount)") 
    return (orderedPile, inversationCount) 
} 

func inverstionCountNaive (_ array :[Int]) -> Int { 
    var inverstionCount = 0 
    for i in 0..<array.count-1 { 
     for j in i+1..<array.count { 
      if array[i] > array[j] { 
       inverstionCount += 1 
      } 
     } 
    } 

    return inverstionCount 
} 

let array = [2, 1, 3, 1, 2] 

print("origin - \(array)") 
print("sorted - \(sortAndCount(array))") 
print("naive approuch count - \(inverstionCountNaive(array))")