Оптимизация двойного хода для l oop с помощью swift - PullRequest
Новая
       6

Оптимизация двойного хода для l oop с помощью swift

1 голос
/ 20 января 2020

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

Итак, мне нужно пройти двойное for l oop, чтобы сравнить все элементы.

Если данные достаточно велики, этот алгоритм неэффективен.

Есть ли способ оптимизации? 

let data = [
  "10000", // count
  "asdfqwerty", "asdfzxcvgh", "asdfpoiuyt",
  ...
]

for i in 1..<data.count {
  let string = data[i]
  for j in (i + 1)..<data.count {
    let newMin = string.minimumEditDistance(other: data[j])

    if min >= newMin {
      // some logic
    }
  }
}

extension String {
  public func minimumEditDistance(other: String, `default`: Int = 10) -> Int {
    let m = self.count
    let n = other.count

    if m == 0 || n == 0 {
      return `default`
    }

    var matrix = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1)

    // initialize matrix
    for index in 1...m {
      // the distance of any first string to an empty second string
      matrix[index][0] = index
    }

    for index in 1...n {
      // the distance of any second string to an empty first string
      matrix[0][index] = index
    }

    // compute Levenshtein distance
    for (i, selfChar) in self.enumerated() {
      for (j, otherChar) in other.enumerated() {
        if otherChar == selfChar {
          // substitution of equal symbols with cost 0
          matrix[i + 1][j + 1] = matrix[i][j]
        } else {
          // minimum of the cost of insertion, deletion, or substitution
          // added to the already computed costs in the corresponding cells
          matrix[i + 1][j + 1] = Swift.min(matrix[i][j] + 1, matrix[i + 1][j] + 1, matrix[i][j + 1] + 1)
        }
      }
    }
    return matrix[m][n]
  }
}

1 Ответ

1 голос
/ 20 января 2020

Вы можете достичь желаемого поведения, отсортировав свой массив, используя minimumEditDistance в качестве функции сортировки, а затем взяв первый или последний элемент (зависит от того, как вы определяете сортировку) и что вам нужно - мин или макс. Вероятно, он будет запущен в O(N*log(N)) времени. Который уже лучше, чем экспоненциальный.

Как упомянул @Sultan, он будет работать не для всех расстояний, поскольку транзитивность применима только к метрикам (функциям, которые определяют расстояние между каждым элементом набора). Вы используете расстояние Левенштейна в качестве алгоритма расстояния редактирования, которое действительно является метрикой c. Решение, которое я упомянул, должно помочь в некоторых обстоятельствах.

...