amarao (amarao_san) wrote,
amarao
amarao_san

Category:

Rust-строковое

А вот строки в 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
}
Tags: rust
Subscribe

  • systemd-networkd, netlink и arp флуд

    Нереально странный баг пофикшен с помощью eBPF затычки. Для меня большой неожиданностью является реакция на него.…

  • Rust soundness

    Каждый раз, когда я сталкиваюсь с маленькими "но" в Rust'е, это ощущение тщательной продуманности. Например, простейшие fold-функции для итераторов:…

  • still_ntp

    В ходе локального мозгового штурма у меня родилась суперидея. Надо написать ntp сервер, который может отдавать указанную дату. Т.е. сказали при…

  • Post a new comment

    Error

    default userpic

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 13 comments

  • systemd-networkd, netlink и arp флуд

    Нереально странный баг пофикшен с помощью eBPF затычки. Для меня большой неожиданностью является реакция на него.…

  • Rust soundness

    Каждый раз, когда я сталкиваюсь с маленькими "но" в Rust'е, это ощущение тщательной продуманности. Например, простейшие fold-функции для итераторов:…

  • still_ntp

    В ходе локального мозгового штурма у меня родилась суперидея. Надо написать ntp сервер, который может отдавать указанную дату. Т.е. сказали при…