Rust - как эффективно удалить символы из начала строки?

У меня есть длинная строка, хранящаяся в переменной в Rust. Я часто удаляю некоторые символы с его фронта с помощью метода drain и использую возвращаемое им значение:

my_str.drain(0..i).collect::<String>();

Проблема в том, что слив из этой строки выполняется в программе очень часто и сильно замедляет ее (занимает ~99,6% времени выполнения). Это очень затратная операция, так как каждый раз всю строку приходится перемещать влево в памяти.

Я вообще не сливаю с конца струны (что должно быть гораздо быстрее), только спереди.

Как я могу сделать это более эффективным? Есть ли какая-то альтернатива String, которая использует другой макет памяти, который будет лучше для этого варианта использования?

И можете ли вы просто перевернуть его, а затем снова перевернуть перед использованием? В этот момент префиксы становятся суффиксами, и если вам редко требуется доступ к фактическому значению - это должно работать. Кроме того, вы можете использовать итератор и перейти к следующему символу вместо удаления префикса. Также вы можете просто сохранить позицию индекса, указывающую на текущее начало строки, и, наконец, обрезать все. Вероятно, дополнительный контекст (пример кода, а также объяснение того, обращаетесь ли вы к строке между удалениями и какова длина строки и префиксов) может спасти этот вопрос от закрытия «нужны детали отладки».

SUTerliakov 19.11.2022 19:18

Метод VecDeque<char> с pop_front тоже может быть полезен.

SUTerliakov 19.11.2022 19:24
VecDeque хорошо выглядит @SUTerliakov
FireFragment 19.11.2022 19:28

Jmb 19.11.2022 20:08
Замена символа по определенному индексу в JavaScript
Замена символа по определенному индексу в JavaScript
В JavaScript существует несколько способов заменить символ в строке по определенному индексу.
1
4
101
3
Перейти к ответу Данный вопрос помечен как решенный

Ответы 3

По предложению @SUTerliakov использование VecDeque<char> в данном случае намного эффективнее, чем String как методом pop_front, так и методом drain (при сливе спереди конечно)

VecDeque<char> имеет недостаток, заключающийся в том, что строка хранится в основном в UTF-32, который менее компактен, чем String UTF-8, и несовместим с str.
Colonel Thirty Two 20.11.2022 01:55

Как заявил @Jmb, сохранение исходной строки нетронутой и работа со срезами, безусловно, является большой победой.

Я не знаю из вопроса контекст и использование этих строк, но этот быстрый и грязный тест показывает существенную разницу в производительности.

Этот бенчмарк ущербен, потому что при каждом повторении стоит бесполезный clone(), нет разминки, нет черного ящика для результата, нет статистики... но он просто дает представление.

use std::time::Instant;

fn with_drain(mut my_str: String) -> usize {
    let mut total = 0;
    'work: loop {
        for &i in [1, 2, 3, 4, 5].iter().cycle() {
            if my_str.len() < i {
                break 'work;
            }
            let s = my_str.drain(0..i).collect::<String>();
            total += s.len();
        }
    }
    total
}

fn with_slice(my_str: String) -> usize {
    let mut total = 0;
    let mut pos = 0;
    'work: loop {
        for &i in [1, 2, 3, 4, 5].iter().cycle() {
            let next_pos = pos + i;
            if my_str.len() <= next_pos {
                break 'work;
            }
            let s = &my_str[pos..next_pos];
            pos = next_pos;
            total += s.len();
        }
    }
    total
}

fn main() {
    let my_str = "I have a long string stored in a variable in Rust.
I often remove some characters from its front with a drain method and use the value returned from it:
my_str.drain(0..i).collect::<String>();
The problem is, that draining from this string is done really often in the program and it's slowing it down a lot (it takes ~99.6% of runtime). This is a very expensive operation, since every time, the entire string has to be moved left in the memory.
I do not drain from the end of the string at all (which should be much faster), just from the front.
How can I make this more efficient? Is there some alternative to String, that uses a different memory layout, which would be better for this use case?
".to_owned();
    let repeat = 1_000_000;
    let instant = Instant::now();
    for _ in 0..repeat {
        let _ = with_drain(my_str.clone());
    }
    let drain_duration = instant.elapsed();
    let instant = Instant::now();
    for _ in 0..repeat {
        let _ = with_slice(my_str.clone());
    }
    let slice_duration = instant.elapsed();
    println!("{:?} {:?}", drain_duration, slice_duration);
}
/*
$ cargo run --release
    Finished release [optimized] target(s) in 0.00s
     Running `target/release/prog`
5.017018957s 310.466253ms
*/
Ответ принят как подходящий

Если вы не можете использовать слайсы из-за продолжительности жизни, вы можете использовать тип, обеспечивающий совместное владение, например SharedString из крейта общей строки или Str из крейта bytes-utils. Первый выглядит более полнофункциональным, но оба предоставляют методы, которые могут брать префикс из строки в O(1), поскольку исходные данные никогда не перемещаются.

Другие вопросы по теме