Swift String Iterator // Собеседование, работа над ошибками

ios
swift
string

#1

Всем привет! Я написал небольшую статью, возможно будет интересно:


#2

У вас отстойная реализация :slight_smile:

На свифте оно выглядело бы так:

func isPalindrom(_ str: String) -> Bool {
    var str = str.lowercased().components(separatedBy: CharacterSet(charactersIn: "abcdefghijklmnopqrstuvwxyz0123456789").inverted).joined()
    while true {
        switch str.count {
        case 0...1:
            return true
        case 2...Int.max where str.removeFirst() == str.removeLast():
            break
        default:
            return false
        }
    }
}

P.S. И собеседование тоже отстойное :slight_smile:


#3

Вы не учли требования ни по памяти, ни по времени.
Использование массива, приведение к lowercased, joined. Это дополнительная память, и как минимум лишний проход по всей строке.
Затем removeFirst это линейное время.
Итого вы использовали дополнительно O(n) памяти и O(n * n) времени.
Может решение и выглядит компактным, но оно очень не эффективно.


#4

Так я и говорю что отстойное собеседование, лучше проще да лучше и на собеседовании я бы так и сказал :slight_smile:


#5

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


#6

Да, я сталкивался с таким)

Но с другой стороны во времена когда компании уровня Микрософт пишут на ReactNative считать количество проходов по строке это как то, ну не знаю, совсем бред.


#7

Мне понравилась ваша статья, даже очень!))


#8

О, спасибо! Постараюсь ещё что-нибудь написать)


#9

Не нравится мне перебор characters в любом случае. Не проверял в коде но исходная идея в моем случае было бы использование слов. Т.е. - 1. oпределяем string.count. 2. Получаем две substrings - половины, в случае нечетного количества string.count не включаем центральный character. (В ДНК палиндромы имеют четное количество букв). Используем .inverted для одной из половин и затем сравниваем половины одну нативную и другую инвертированную на наличие их равенства.

Было бы более интересно задание на функцию проверяющую на наличие внутри заданного string палиндромов с длинной в заданном диапазоне, с позиции времени.


#10

Здравствуйте! Интересная идея) Вы не биолог случайно?

  • С characters нужно работать аккуратно. Если вы просто вызовите characters, то получите сразу O(n) перебор и копию в виде массива O(n) памяти. Если я ничего не путаю, конечно;

  • На самом деле вы забыли про пробелы. К примеру, палиндром: Madam, I’m Adam.
    Если удалять пробелы из строки - будет копия и мы не выполним требование по памяти O(1);

  • И если вы посмотрите выводы, то поймете что в этой задаче центр палиндрома - не центр строки.

Было бы более интересно задание на функцию проверяющую на наличие внутри заданного string палиндромов с длинной в заданном диапазоне, с позиции времени.

Проблема в том, что тут есть символы которые не нужно учитывать и их нельзя вырезать.
Асимптотика решения всё равно будет O(n) в лучшем случае, так как нам нужно перебрать каждый символ строки. Вы уже говорите о строковых алгоритмах, сейчас изучаю их на втором семестре.


#11

Биолог.
Если есть символы которые нельзя учитывать то можно их всех заменить на “” (в исходном стринг или позже в ее половинах) используя .replacingOccurrences(of: “Any” , with: “” ). В остальном все так же. Не знаю что будет со временем и памятью, т.е. как реализована .replacingOccurrences(of: , with: ).


#12

Биолог это очень здорово) я пока учился была интересная задача на сравнение цепочек нуклеотидов с использованием быстрого преобразования Фурье. Интересно, но сложно)

На самом деле replacingOccurrences может не сделать копию, если строка больше никому не нужна. Что-то вроде “Copy on write”, но вроде незачем копировать если только 1 ссылка. Но это лишь догадка) Удаление любого символа из строки (массива) это O(n), так как нужно сдвинуть все остальные после него. В худшем случае O(n * n). Хотя там может использоваться не массив, а например, связный список. Так как всё равно нет рандомного доступа к символам строки.

Это удобное решение с replacingOccurrences, но оно не прошло бы) Требования были другие и тут тоже проверяют знания структур и работы с памятью.


#13

Меня тоже этот момент смутил, ещё в методе isCaseInsensitiveEqual происходит преобразование в строку и потом строки сравниваются.

Проще сразу строку мучать:

func isPalindrom2(_ str: String) -> Bool {
    let set = CharacterSet(charactersIn: "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLKMNOPQRSTUVWXYZ0123456789")
    var range = str.startIndex..<str.endIndex
    
    while range.lowerBound < range.upperBound {
        var left: Substring!
        var right: Substring!
        
        while let r = str.rangeOfCharacter(from: set, range: range) {
            range = r.upperBound..<range.upperBound
            left = str[r]
            break
        }
        while let r = str.rangeOfCharacter(from: set, options: .backwards, range: range) {
            range = range.lowerBound..<r.lowerBound
            right = str[r]
            break
        }
        guard left != nil && right != nil else { break }
        guard left == right || left.lowercased() == right.lowercased() else { return false }
    }
    return true
}

И значительно быстрее:

P.S. Тестировал строкой в 1000000 символов


#14

В плане общего решения у вас вроде тоже самое происходит, только вместо моих переборов за вас это делает rangeOfCharacter.
Не понимаю зачем while, если сразу идёт break.

В строку приходится приобразовывать, так как у Character не нашёл способа сравнения без учёта регистра. У вас тоже тут lowercased копию делает, лучше использовать именно сравнение. Там возможно это без копии происходит.

Тесты тоже сделал, вроде получается одинаково. Я не смог нормально реализовать, чтобы тестовые данные использовались одинаковые и оптимизаций строк не было. У вас возможно как раз это) поменяйте местами методы, будет разница? или по одному.

Сейчас нет времени разбираться, а так интересно)


#15

У меня моё решение на 1_000_000 выигрывает немного) а на больших цифрах начинает потихоньку проигрывать. Возможно из-за преобразования в строку, или что-то ещё.


#16

Тут сложно что то лучше придумать.

Break если одна из строк nil.

CaseInsensitiveCompare работает медленнее чем просто сравнение строк, в моём искусственном тесте по крайней мере, по этому я их сначала просто сравниваю а потом в нижнем регистре.

Нет разницы и по одному такой же результат, видимо разница из за кривого теста.


#17

Вероятно что rangeOfCharacter более эффективен чем просто перебор.

Из моего небольшого опыта использование string.range(of: ) эффективнее чем простой перебор массивов.
Если есть два массива strings и надо найти сколько раз string из одного массива встречается в strings другого, то решени в лоб с перебором двух массивом в моем случае было порядка четырех раз медленнее чем поиск range of string из первого массова в строке составленной из strings второго массива.


#18

Благодаря вам наткнулся на то что, можно итератор использовать в for in, вроде этого:

struct StringDownIterator: IteratorProtocol, Sequence {
    private let str: String
    private let count: Int
    private var current = 0
    init(_ str: String) {
        self.str = str
        count = str.count
    }
    mutating func next() -> Character? {
        guard -current < count else { return nil }
        current -= 1
        return str[str.index(str.endIndex, offsetBy: current)]
    }
}

extension String {
    func makeDownIterator() -> StringDownIterator {
        return StringDownIterator(self)
    }
}

let iter = "ABC".makeDownIterator()

for c in iter {
    print(c) // C B A
}

Прям как в es6 (только там for of) :slight_smile:


#19

Добавил тесты и ваше решение в репозитой. Github.

Посмотрите, если интересно. Там действительно уходит время на инициализацию строки, пришлось для этого отдельный тест создать чтобы это время не учитывалось в остальных реальных тестах.

While внутри while там можно смело заменить на if, я это тоже добавил как альтернативное решение. Также использовал уже готовые множества символов, это не совсем правильно в рамках задачи, но часто просто буквы нужны.

Также поразбирался, получается у вас могут быть случаи с O(n) доп. памятью. Когда у нас вся строка, кроме центрального символа состоит из корректных символов. Мы дойдем до центра и lowercased() создаст 2 строки из Substring. А это уже похоже на доп. память.

CaseInsensitiveCompare забыл проверить)


#20

Возможно там используются строковые алгоритмы. Например, Z-функция. С её помощью можно за O(n + m) искать вхождение одной строки в другую. Вроде там в примерах это было. А у вас получается O(n * m), то есть перемножение длинн строк. Но это лишь догадка)