Оптимізація швидкості виконання векторного повороту в Rust

5 Березня 2024 в 23:05 30

У задачах програмування, зокрема на платформі LeetCode, часто виникає необхідність в оптимізації швидкості виконання алгоритмів. Однією з таких задач є поворот вектору, де ефективність рішення може значно впливати на час виконання програми. У цій статті розглянемо два різних підходи до вирішення завдання повороту вектору в мові програмування Rust і порівняємо їх ефективність.

Просте рішення

Перше рішення, яке розглянемо, є простим і зручним, але менш ефективним за швидкістю виконання. Воно полягає в застосуванні одного циклу з використанням методів векторів для повороту елементів. Нижче наведений код цього рішення:

```rust
impl Solution {
    pub fn rotate(nums: &mut Vec<i32>, k: i32) {
        let i = nums.len() - 1;
        let mut x = 0;
        while x < k as usize {
            let e = nums[i];
            nums.remove(i);
            nums.insert(0, e);
            x = x + 1;
        }
    }
}

```rust

impl Solution {

pub fn rotate(nums: &mut Vec<i32>, k: i32) {

let i = nums.len() - 1;

let mut x = 0;

while x < k as usize {

let e = nums[i];

nums.remove(i);

nums.insert(0, e);

x = x + 1;

}

Це рішення працює коректно, але має недолік – велику кількість операцій зміни вектора, що призводить до повільного виконання програми на великих об’ємах даних.

Оптимізоване рішення

Друге рішення, яке розглянемо, є більш складним, але ефективним за швидкістю виконання. Воно використовує три цикли та більше пам’яті, але працює значно швидше за попереднє рішення. Нижче наведений код цього рішення:

```rust
impl Solution {
    pub fn rotate(nums: &mut Vec<i32>, k: i32) {
        let k: usize = k as usize;
        let length = nums.len();
        let mut n: usize = 1;
        while (((n * length - k) as i32) < 0) {
            n += 1;
        }
        let mut padding: usize = n * length - k;
        let mut res = Vec::with_capacity(length);
        for i in 0..length {
            res.push(nums[(i + padding) % length]);
        }
        for i in 0..length {
            nums[i] = res[i];
        }
    }
}
```

```rust

impl Solution {

pub fn rotate(nums: &mut Vec<i32>, k: i32) {

let k: usize = k as usize;

let length = nums.len();

let mut n: usize = 1;

while (((n * length - k) as i32) < 0) {

n += 1;

}

let mut padding: usize = n * length - k;

let mut res = Vec::with_capacity(length);

for i in 0..length {

res.push(nums[(i + padding) % length]);

}

for i in 0..length {

nums[i] = res[i];

}

```

Це рішення використовує більше пам’яті, але працює значно швидше за попереднє, оскільки не має такої великої кількості операцій зміни вектора. Воно використовує три цикли для визначення нового індексу для кожного елементу вектора та зберігає результат у новому векторі, який потім копіюється назад до вихідного вектора.

Висновок

Хоча просте рішення з одним циклом є більш зрозумілим і зручним для реалізації, воно працює значно повільніше за оптимізоване рішення з трьома циклами. У випадках, коли швидкість виконання є критичним чинником, варто вибрати оптимізоване рішення з меншою кількістю операцій зміни вектора та більшою швидкістю виконання.

Copy code