Палиндромы считают быструю оптимизацию
Эй, у меня есть вопрос об алгоритме подсчета количества палиндромов
Задача: Найти количество палиндромов в строке.
в моем функционале я использую метод "в лоб", как O(n^2), вы можете помочь сделать это в O(n) или O(nlogn)
func isPalindrome(string: String) -> Bool {
let str = (string.lowercased())
let strWithoutSpace = str.components(separatedBy: .whitespaces).joined(separator: "")
let strArray = Array(strWithoutSpace.characters)
var i = 0
var j = strArray.count-1
while i <= j {
if strArray[i] != strArray[j] { return false }
i+=1
j-=1
}
return true
}
func palindromsInString(string: String) -> Int {
var arrayOfChars = Array(string.characters)
var count = 0
for i in 0..<arrayOfChars.count-1 {
for x in i+1..<arrayOfChars.count {
if isPalindrome(string: String(arrayOfChars[i...x])) {
count+=1
}
}
}
return count
}
и да, в моем случае одно письмо не может быть палиндромом
3 ответа
Я не знаком с алгоритмом Манахера, но мне всегда нравилось находить эффективные алгоритмы, поэтому я подумал, что у меня есть шанс на это.
Ваш алгоритм определения, является ли строка палиндромом, похож на те, что я придумал, поэтому я решил просто использовать ваш isPalindrome функция, хотя я изменил ее, чтобы быть функцией в расширении String вместо этого, и я удалил логику удаления пробелов, так как я чувствовал, что это должно быть в вызове вызова, а не в самой функции определения палиндрома.
extension String {
func isPalindrome() -> Bool {
if length < 2 { return false }
let str = lowercased()
let strArray = Array(str.characters)
var i = 0
var j = strArray.count-1
while i <= j {
if strArray[i] != strArray[j] { return false }
i+=1
j-=1
}
return true
}
}
Посмотрев на ваш palindromsInString Решение выглядит как стандартное перебор, но простое и удобочитаемое решение.
Моя первая мысль о другом алгоритме была также довольно грубой силой, но это был совершенно другой подход, поэтому я называю это наивным решением.
Идея решения Naive состоит в том, чтобы создать массивы подстрок исходной строки и проверить, является ли каждая подстрока палиндромом или нет. Способ определения подстрок состоит в том, чтобы начать с максимально возможной подстроки (исходной строки), а затем получить 2 подстроки длины string.length-1, а потом string.length-2 и так до тех пор, пока, наконец, я не получу все подстроки длины 2 (я игнорирую подстроки длины 1, потому что вы сказали, что строка длины 1 не может быть палиндромом).
то есть: подстроки "test" больше длины 1 будут:
["test"] ["tes", "est"] ["te", "es", "st"]
Таким образом, вы просто просматриваете каждый из этих массивов и проверяете, есть ли палиндромы, и увеличиваете количество, если они:
Наивное решение:
extension String {
var length: Int { return characters.count }
func substringsOfLength(length: Int) -> [String] {
if self.length == 0 || length > self.length { return [] }
let differenceInLengths = self.length - length
var firstIndex = startIndex
var lastIndex = index(startIndex, offsetBy: length)
var substrings: [String] = []
for _ in 0..<differenceInLengths {
substrings.append(substring(with: Range(uncheckedBounds: (firstIndex, lastIndex))))
firstIndex = index(after: firstIndex)
lastIndex = index(after: lastIndex)
}
substrings.append(substring(with: Range(uncheckedBounds: (firstIndex, lastIndex))))
return substrings
}
}
extension String {
func containsAPalindromeNaive(ignoringWhitespace: Bool = true) -> Int {
let numChars = length
if numChars < 2 { return 0 }
let stringToCheck = (ignoringWhitespace ? self.components(separatedBy: .whitespaces).joined(separator: "") : self).lowercased()
var outerLoop = numChars
var count: Int = 0
while outerLoop > 0 {
let substrings = stringToCheck.substringsOfLength(length: outerLoop)
for substring in substrings {
if substring.isPalindrome() {
count += 1
}
}
outerLoop -= 1
}
return count
}
}
Я прекрасно знал, что этот алгоритм будет медленным, но я хотел реализовать его в качестве второй основы для моего реального решения.
Я называю это решение умным решением. Это многопроходное решение, которое использует количество и положение символов в строке.
На первом этапе я генерирую то, что я называю сопоставлением символов. Отображение символов - это словарь, который отображает Character к массиву индексов. Итак, вы перебираете строку и добавляете индекс каждого символа в массив, хранящийся под его символьным значением в качестве ключа.
Идея состоит в том, что палиндромы могут существовать только внутри строки, которая обозначена той же буквой. Поэтому вам нужно только проверять подстроки в строке по индексам конкретной буквы. В слове "тату" у вас есть 3 разных буквы: "т", "а", "о". Отображения символов будут выглядеть так:
t: [0,2,3]
a: [1]
o: [4,5]
Теперь я знаю, что палиндромы могут существовать в этом слове только между (0,2), (2,3) и (4,5). Поэтому мне нужно проверить только 3 подстроки (0,2), (0,3), (2,3) и (4,5). Так что мне нужно проверить только 4 подстроки. Это идея. И после того, как вы проверили все возможные подстроки, добавленные к определенной букве, вы можете игнорировать любые другие встречающиеся подстроки, начинающиеся с этой буквы, потому что вы уже проверили их.
Во втором проходе я перебираю каждый символ в строке и, если я еще не проверил эту букву, я просматриваю пары индексов перестановки, сгенерированных generateOrderedPairIndexPermutations для индексов в отображении символов и проверьте подстроки, чтобы видеть, являются ли они палиндромом. Затем я делаю 2 оптимизации здесь. Во-первых, если расстояние между индексом начального символа и индексом конечного символа меньше 3, это должен быть палиндром (расстояние 1 означает, что они последовательные, а расстояние 2 означает, что между ними есть одна буква, таким образом, также гарантированно будет палиндром). Во-вторых, поскольку я уже знаю, что первый и последний символы одинаковы, мне не нужно проверять всю подстроку, начиная со второй буквы до второй и до последней буквы. Так что, если подстрока будет "тестовой", и я всегда гарантирую себе, что подстрока записана одной и той же буквой, мне на самом деле не нужно проверять "тест", а вместо этого я могу просто проверить "эс". Это меньшая оптимизация, но, тем не менее, хорошая.
Умное решение:
extension Collection {
func generateOrderedPairIndexPermutations() -> [(Index,Index)] {
if count < 2 {
return []
}
var perms: [(Index,Index)] = []
var firstIndex = startIndex
while firstIndex != endIndex {
var secondIndex = index(firstIndex, offsetBy: 1)
while secondIndex != endIndex {
perms.append((firstIndex,secondIndex))
secondIndex = index(secondIndex, offsetBy: 1)
}
firstIndex = index(firstIndex, offsetBy: 1)
}
return perms
}
}
extension String {
func generateCharacterMapping() -> [Character : [Int]] {
var characterMapping: [Character : [Int]] = [:]
for (index, char) in characters.enumerated() {
if let indicesOfChar = characterMapping[char] {
characterMapping[char] = indicesOfChar + [index]
} else {
characterMapping[char] = [index]
}
}
return characterMapping
}
func containsAPalindromeSmart(ignoringWhitespace: Bool = true) -> Int {
let numChars = length
if numChars < 2 { return 0 }
let stringToCheck = (ignoringWhitespace ? self.components(separatedBy: .whitespaces).joined(separator: "") : self).lowercased()
let characterMapping = stringToCheck.generateCharacterMapping()
var count: Int = 0
var checkedChars: Set<Character> = Set()
for char in stringToCheck.characters {
if checkedChars.contains(char) == false {
if let characterIndices = characterMapping[char], characterIndices.count > 1 {
let perms = characterIndices.generateOrderedPairIndexPermutations()
for (i,j) in perms {
let startCharIndex = characterIndices[i]
let endCharIndex = characterIndices[j]
if endCharIndex - startCharIndex < 3 {
count += 1
} else {
let substring = stringToCheck.substring(with: Range(uncheckedBounds: (stringToCheck.index(stringToCheck.startIndex, offsetBy: startCharIndex+1), stringToCheck.index(stringToCheck.startIndex, offsetBy: endCharIndex))))
if substring.isPalindrome() {
count += 1
}
}
}
checkedChars.insert(char)
}
}
}
return count
}
}
Я чувствовал себя довольно хорошо об этом решении. Но я понятия не имел, насколько быстро это было на самом деле. Это было действительно быстро
Используя XCTest для измерения производительности, я провел каждый алгоритм через несколько тестов производительности. Использование этой строки в качестве базового источника: "Здесь несколько палиндромов" "Я видел машину или кошку", обновлено на основе предложений по использованию более строгой входной строки длиной 33 19 символов при удалении пробела и в нижнем регистре ("есть несколько множественных палиндромов в этом месте", "wasitacaroracatisaw"), я также создал копии, которые были этой строкой раз 2 ("есть несколько множественных палиндромов в этом месте, где есть несколько множественных палиндромов в этом месте", временами 4, раз 8) алгоритма, масштабирование количества букв и измерение масштабного коэффициента - путь.
Чтобы получить более точные данные, я проводил каждый тест в течение 10 итераций (мне бы хотелось, чтобы было больше итераций, но исходное решение и мое наивное решение не заканчиваются своевременно в тестах выше 4). Вот данные о времени, которые я собрал (скриншот таблицы был проще, чем вводить ее здесь снова):
ОБНОВЛЕНО 
ОБНОВЛЕНО Зеленый - Автор; Красный - Наивное Решение; Orange - это умное решение 
Как видите, и ваше исходное решение, и мое наивное решение работают в квадратичном времени (у вашего решения есть квадратичный коэффициент корреляции r=0,9997, а у моего наивного решения коэффициент r=0,9999; так что очень четко квадратично!). Мое наивное решение, кажется, находится под вашим решением, но они оба увеличиваются в квадрате, и поэтому, как мы уже знали, они равны O(n^2).
Интересная часть моего Smart Solution кажется линейной! Мои маленькие 5-точечные данные были получены с помощью регрессионного калькулятора, и у них коэффициент корреляции r=0,9917! Так что, если он не линейный, он так близко, что мне все равно.
Все решения работают в квадратичном времени. Ле вздох Но, по крайней мере, ошибка была обнаружена, устранена, и наука победила в этот день. Облом, что мое "умное решение" на самом деле не оказалось линейным. Тем не менее, я отмечу, что если входная строка уже не является гигантским палиндромом (как та, которую я в итоге изменил, чтобы она была), то оптимизация "Умного решения" заставляет ее работать намного быстрее, хотя все еще в квадратичном времени,
Я не знаю, легче ли понять мой алгоритм, чем алгоритм Манахера, но я надеюсь, что объяснил это хорошо. И результаты довольно многообещающие, поэтому я надеюсь, что вы найдете в этом пользу. Это на самом деле все еще правда. Я думаю, что это многообещающий алгоритм. Возможно, мой код для generateOrderedPairIndexPermutations не самый лучший
Обновлено для исправления ошибки, найденной Краскевичем
Вы можете использовать алгоритм Манахера, чтобы решить его за линейное время. Этот алгоритм обычно используется для нахождения самого длинного палиндрома, но он вычисляет максимальную длину палиндрома, центр которого находится в определенной позиции для каждой позиции в строке.
Вы можете найти описание и реализацию этого алгоритма в этом вопросе.
Вот решение "функционального программирования", на которое экспоненциальный характер процесса оказывает гораздо меньшее влияние, чем принятый ответ. (также намного меньше кода)
Это в 80% быстрее на коротких (19) струнах и в 90 раз на более длинных (190). Я формально не доказал это, но это кажется линейным O(n)?.
public func countPalindromes(in text:String) -> Int
{
let words = text.lowercased()
.components(separatedBy:CharacterSet.letters.inverted)
.filter{!$0.isEmpty}
.joined(separator:"")
let sdrow = String(words.characters.reversed())
let splits = zip( sdrow.characters.indices.dropFirst().reversed(),
words.characters.indices.dropFirst()
)
.map{ (sdrow.substring(from:$0),words.substring(from:$1), words[$1...$1] ) }
let count = splits.map{$0.1.commonPrefix(with:$0.0)} // even
.filter{ !$0.isEmpty }
.reduce(0){$0 + $1.characters.count}
+ splits.map{ $1.commonPrefix(with:$2 + $0)} // odd
.filter{$0.characters.count > 1 }
.reduce(0){$0 + $1.characters.count - 1}
return count
}
// how it works ...
// words contains the stripped down text (with only letters)
//
// sdrow is a reversed version of words
//
// splits creates split pairs for each character in the string.
// Each tuple in the array contains a reversed left part, a right part
// and the splitting character
// The right part includes the splitting character
// but the left part does not.
//
// [(String,String,String)] for [(left, right, splitChar)]
//
// The sdrow string produces the left part in reversed letter order .
// This "mirrored" left part will have a common prefix with the
// right part if the split character's position is in the middle (+1)
// of a palindrome that has an even number of characters
//
// For palindromes with an odd number of characters,
// the reversed left part needs to add the splitting character
// to match its common prefix with the right part.
//
// count computes the total of odd and even palindromes from the
// size of common prefixes. Each of the common prefix can produce
// as many palindromes as its length (minus one for the odd ones)
[EDIT] Я также сделал процедурную версию для сравнения, зная, что компилятор может лучше оптимизировать процедурный код, чем его декларативный аналог.
Это расширение типа Array (так что он может считать палиндромы всего сравнимого).
extension Array where Element:Comparable
{
public func countPalindromes() -> Int
{
if count < 2 { return 0 }
var result = 0
for splitIndex in (1..<count)
{
var leftIndex = splitIndex - 1
var rightIndex = splitIndex
var oddPalindrome = true
var evenPalindrome = true
while leftIndex >= 0 && rightIndex < count
{
if evenPalindrome
&& self[leftIndex] == self[rightIndex]
{ result += 1 }
else
{ evenPalindrome = false }
if oddPalindrome
&& rightIndex < count - 1
&& self[leftIndex] == self[rightIndex+1]
{ result += 1 }
else
{ oddPalindrome = false }
guard oddPalindrome || evenPalindrome
else { break }
leftIndex -= 1
rightIndex += 1
}
}
return result
}
}
public func countPalindromesFromArray(in text:String) -> Int
{
let words = text.lowercased()
.components(separatedBy:CharacterSet.letters.inverted)
.filter{!$0.isEmpty}
.joined(separator:"")
return Array(words.characters).countPalindromes()
}
Он работает в 5-13 раз быстрее, чем декларативный, и до 1200 раз быстрее, чем принятый ответ.
Увеличивающаяся разница в производительности с декларативным решением говорит мне, что это не было O(n). Процедурная версия может быть O(n), потому что его время будет зависеть от количества палиндромов, но будет пропорционально размеру массива.