Rust-строковое

[amarao]

А вот строки в Rust'е неожиданно сложны. Например, такая простая вещь, как strstr() (поиск начала подстроки в строке) с каждой итераций раздумий всё сложнее и сложнее. Особенно, если делать эффективно.

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

Итератор chars не очень хороший, потому что он из любого символа (даже 1-байтового) делает 4 байта. Это значит, что для поиска подстроки в гигабайтной строке нам нужно будет перемолотить 4 ГБ в режиме записи (вероятнее всего, в регистр, но всё равно...)

Т.е. первая задача, которая у нас будет, это реализация считающего Window поверх String/str без копирования. Внутри это указатель на первый символ и байтовая длина (при том, что количество символов в window фиксировано, байтовый размер будет прыгать очень неровно).

Основываться она должна на str-итераторе по символам. Такой итератор получает &str, после чего начинает возвращать &str в один символ (in-place, без копирования!). Т.е. ещё уровнем ниже, это fat pointer на байты строки, который указывает на начало символа и содержит в себе его длину, кроме того, он содержит в себе (для удобства, видимо), адрес начала строки, и её оригинальный размер.

Перед тем, как изобретать всё своё с нуля, надо ещё раз перечитать что String и str умеют из коробки (игнорируя существование find и matches, разумеется).

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

.. Сделал. Получил заслуженные 40мс (нижние 27% всех решений). Нырять в устройства fat pointers я пока не готов.

pub fn str_str(haystack: String, needle: String) -> i32 {
    if needle.len() == 0 {return 0};
    let haystack_vec: Vec<char> = haystack.chars().collect();
    let needle_vec: Vec<char> = needle.chars().collect();
    let mut pos = 0;
    for candidate in haystack_vec.windows(needle_vec.len()){
        if candidate == needle_vec.as_slice(){
            return pos as i32;
        }
        pos += 1;
    }
    -1
}

Comments

[juan_gandhi]

Красивое.

[yurikhan]

А у нас задача-минимум — повторить strstr, или задача-максимум — сделать нормальный поиск первого вхождения юникодной подстроки в юникодной строке?

Потому что если первое, то, наверно, можно и с байтами поработать; а если второе, то здравствуй, каноническое упорядочениие диакритик вот такой вышины, здравствуй, компатибилити-эквивалентность вот такой ширины, крокодилы-бегемоты, обезьяны-кашалоты и 🦜.

Байтовый индекс конвертируется в символьный индекс как количество по диапазону [0, byte_index) байт в диапазонах [0, 0x7F]∪[0xC0, 0xFF], например. Сложность вычисления — линейная, что при квадратичной сложности самого strstr по байтам асимптотику не ухудшает.

[amarao]

Я бы сказал, что работать надо в условиях rust'ового определения символа в строке. Я полез в эту кроличью нору, char в Rust - это unicode code point. Насколько я понимаю, Rust сам по себе перевод в D-форму не делает, а вот проверка, что "ё" и её нормальная форма это одно и тоже ... о, да. Прелюбопытнейшая задача.

[permeakra]

Это проблема не раста, а юникода. Пока речь не идет о работе с текстом по существу, строки в расте можно и нужно воспринимать его как последовательность байт. А вот если надо, то надо подцеплять ICU или эквивалент.

Полистай на досуге первую часть вот отсиюда https://www.oreilly.com/library/view/fonts-encodings/9780596102425/ , там такое лютое червие живет, что диву даешься.

[amarao]

Да, я полез в эту нору и понял, что Rust'овый юникод только про codepoints, так что с ними можно работать как с codepoints, что чуть более благородно, чем [u8].

[permeakra]

Нельзя. Потому что нормализация и прочий шрот.

[permeakra]

Подумав, решил конкретизировать.

Строки в unicode/utf8 могут быть эквиваленты но неравны. Или не быть, в зависимости от контекста. И одна графема может быть представлена несколькими разными байтовыми последовательностями. Поэтому сравнивать их и/или работать с ними по существу можно только специализированным инструментарием, понимая внутреннюю кухню. Потому что делать самому по стандарту с учетом тамошнего червия - это слишком долго практически всегда.