Почему эти алгоритмы должны вести себя иначе? - PullRequest
Новая
       8

Почему эти алгоритмы должны вести себя иначе?

0 голосов
/ 10 февраля 2019

Для личного назидания, я возился с .reduce() Свифта и столкнулся с необычным поведением, которое я не могу понять.

Я потратил довольно много неожиданного времени (не менее 6 часов) на исследования и эксперименты, и я в замешательстве.

У меня есть два алгоритма (я написал второй.), Которые появляютсясделать то же самое, то есть посчитать количество символов (в данном случае «а»), которые появляются в бесконечной строке с повторяющимся узором.Оба алгоритма ведут себя одинаково примерно в 50% случаев.Один использует .reduce () дважды, а другой - рабочий - использует цикл for.

Алгоритм, который работает во всех случаях: 

let str = readLine()!
let length = Int(readLine()!)!

let fullRepetitions = length / str.characters.count
let lengthLastRep = length % str.characters.count

var count = fullRepetitions * str.characters.reduce(0) { $1 == "a" ? $0 + 1 : $0 }

for i in 0..<lengthLastRep {
    if str[str.index(str.startIndex, offsetBy: i)] == "a" {
        count += 1
    }
}

print(count)

Итот, который не , но должен , выглядит так: 

let pattern = readLine()!
let length = Int(readLine()!)!
let fullyRepeatedPatterns = length / pattern.count
let lastPatternLength = pattern.count % length
var countOfAs = fullyRepeatedPatterns * pattern.reduce(0, { $1 == "a" ? $0 + 1 : $0 })
countOfAs += pattern
    .prefix(upTo: pattern.index(pattern.startIndex, offsetBy: lastPatternLength - 1))
    .reduce(0, { $1 == "a" ? $0 + 1 : $0 })
print(countOfAs)

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

Сначала я подумал, что нашел свою проблему при выполнении по модулю, чтобы получить длину последнего паттерна, , если я изменю 2-й алгоритм так, чтобы он был похож наво-первых, он не только прекращает выполнение в пограничных случаях, но и имеет серьезную ошибку во время выполнения. То есть изменение этого значения: 

let lastPatternLength = pattern.count % length

На это: 

let lastPatternLength = length % pattern.count

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

Что еще интереснее, ошибки не согласованы.Вход с: 

aab
882787

То есть "aab" повторяется 882787 раз, и это похоже на ошибку выключения одного ... Или то, что кажется отключением одного .Однако ... 

let pattern = "aab"
let length = 882787

let fullyRepeatedPatterns = length / pattern.count
let lastPatternLength = pattern.count % length
var countOfAs = fullyRepeatedPatterns * pattern.reduce(0, { $1 == "a" ? $0 + 1 : $0 })
countOfAs += pattern
    .prefix(upTo: pattern.index(pattern.startIndex, offsetBy: lastPatternLength - 1))
    .reduce(0, { $1 == "a" ? $0 + 1 : $0 })
print("expected 588525 but got \(countOfAs)")

Я знаю правильный ответ заранее, поэтому могу сказать:

Я ожидал 588525, но получил 588526.

но при вводе: 

babbaabbabaababaaabbbbbbbababbbabbbababaabbbbaaaaabbaababaaabaabbabababaabaabbbababaabbabbbababbaabb
860622337747

выключено на 27!

Наконец, , как будто бы очень раздражает специально , ввод: 

ababa
3

отключен на -1.

Есть много случаев, когда оба алгоритма работают, например: 

aba
10

Но меня это не волнует.

Может кто-нибудь объяснить, что яздесь не хватает?

1 Ответ

0 голосов
/ 10 февраля 2019

Первое: 

let lastPatternLength = pattern.count % length

должно быть 

let lastPatternLength = length % pattern.count

, как в исходном алгоритме.Например: 

pattern = "abab"
length = 11

length / pattern.count = 11 / 4 = 2
length % pattern.count = 11 % 4 = 3

означает, что для получения общей длины 11 необходимы две копии шаблона и три дополнительных символа. * Это иногда приводило к ошибке времени выполнения в ваших тестахпроисходит из-за второй ошибки: в 

.prefix(upTo: pattern.index(pattern.startIndex, offsetBy: lastPatternLength - 1))

вы не должны вычитать одно из lastPatternLength, оно должно быть 

.prefix(upTo: pattern.index(pattern.startIndex, offsetBy: lastPatternLength))

, потому что prefix(upTo:) возвращает подпоследовательность до, но не включая данный индекс.Вы также можете упростить его до 

.prefix(lastPatternLength)
...