Обзор алгоритмов поиска Rust

Обзор алгоритмов поиска Rust

Алгоритмы поиска и их реализация в Rust, языке системного программирования, разработанном для обеспечения безопасности, параллелизма и производительности.

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

По мере изучения этого руководства вы можете узнать следующее:

1. Уникальная особенность Rust
2. Подробные пояснения и примеры кода
3. Анализ производительности и методы оптимизации

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

use std::cmp::Ordering;
pub fn binary_search<T: Ord>(item: &T, arr: &[T]) -> Option<usize> {
    let mut is_asc = true;
    if arr.len() > 1 {
        is_asc = arr[0] < arr[arr.len() - 1];
    }
    let mut left = 0;
    let mut right = arr.len();
    while left < right {
        let mid = left + (right - left) / 2;
        if is_asc {
            match item.cmp(&arr[mid]) {
                Ordering::Less => right = mid,
                Ordering::Equal => return Some(mid),
                Ordering::Greater => left = mid + 1,
            }
        } else {
            match item.cmp(&arr[mid]) {
                Ordering::Less => left = mid + 1,
                Ordering::Equal => return Some(mid),
                Ordering::Greater => right = mid,
            }
        }
    }
    None
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn empty() {
        let index = binary_search(&"a", &[]);
        assert_eq!(index, None);
    }
    #[test]
    fn one_item() {
        let index = binary_search(&"a", &["a"]);
        assert_eq!(index, Some(0));
    }
    #[test]
    fn search_strings_asc() {
        let index = binary_search(&"a", &["a", "b", "c", "d", "google", "zoo"]);
        assert_eq!(index, Some(0));
        let index = binary_search(&"google", &["a", "b", "c", "d", "google", "zoo"]);
        assert_eq!(index, Some(4));
    }
    #[test]
    fn search_strings_desc() {
        let index = binary_search(&"a", &["zoo", "google", "d", "c", "b", "a"]);
        assert_eq!(index, Some(5));
        let index = binary_search(&"zoo", &["zoo", "google", "d", "c", "b", "a"]);
        assert_eq!(index, Some(0));
        let index = binary_search(&"google", &["zoo", "google", "d", "c", "b", "a"]);
        assert_eq!(index, Some(1));
    }
    #[test]
    fn search_ints_asc() {
        let index = binary_search(&4, &[1, 2, 3, 4]);
        assert_eq!(index, Some(3));
        let index = binary_search(&3, &[1, 2, 3, 4]);
        assert_eq!(index, Some(2));
        let index = binary_search(&2, &[1, 2, 3, 4]);
        assert_eq!(index, Some(1));
        let index = binary_search(&1, &[1, 2, 3, 4]);
        assert_eq!(index, Some(0));
    }
    #[test]
    fn search_ints_desc() {
        let index = binary_search(&4, &[4, 3, 2, 1]);
        assert_eq!(index, Some(0));
        let index = binary_search(&3, &[4, 3, 2, 1]);
        assert_eq!(index, Some(1));
        let index = binary_search(&2, &[4, 3, 2, 1]);
        assert_eq!(index, Some(2));
        let index = binary_search(&1, &[4, 3, 2, 1]);
        assert_eq!(index, Some(3));
    }
    #[test]
    fn not_found() {
        let index = binary_search(&5, &[1, 2, 3, 4]);
        assert_eq!(index, None);
        let index = binary_search(&5, &[4, 3, 2, 1]);
        assert_eq!(index, None);
    }
}

В этом коде на Rust реализован алгоритм бинарного поиска для упорядоченного массива значений. Процесс выглядит следующим образом:

1. Сигнатура функции binary_search‹T: Ord›(item: &T, arr: &[T]) -> Option‹usize› указывает на то, что функция принимает два параметра: ссылку на искомый элемент и срез массива для поиска. in. Функция возвращает параметр ‹usize›, который может иметь значение Some(index), если элемент найден по заданному индексу, или None, если он не найден.
2. Чтобы определить, отсортирован ли массив по возрастанию или по убыванию, функция сначала проверяет, содержит ли массив более одного элемента.
3. Левая и правая переменные инициализируются начальным и конечным индексами массива.
4. Массив многократно просматривается с использованием цикла while. Пока левый индекс меньше правого, цикл выполняется.
5. Во время цикла функция вычисляет средний индекс, находя среднюю точку между левым и правым.
6. Когда массив отсортирован в порядке возрастания, выражение соответствия проверяет, является ли искомый элемент меньше, равен или больше элемента в середине индекса. При установке справа на середину поиск ограничивается левой половиной массива, если она меньше среднего элемента. В этом случае средний индекс возвращается как значение Some, если он равен среднему элементу. При установке для левого значения mid + 1 поиск ограничивается правой половиной массива, если он больше среднего элемента.
7. В порядке убывания используется одно и то же выражение соответствия, но варианты «меньше» и «больше» меняются местами. Поиск в нисходящем массиве следует логике, противоположной поиску в восходящем массиве.
8. По завершении цикла while без нахождения элемента функция возвращает None.
9. В код также включены несколько тестовых случаев, проверяющих различные входные массивы и элементы. Assert_eq! используется в тестах. Используя этот макрос, вы можете убедиться, что выходные данные функции соответствуют вашим ожиданиям.

Двоичный поиск рекурсивный

use std::cmp::Ordering;
pub fn binary_search_rec<T: Ord>(
    list_of_items: &[T],
    target: &T,
    left: &usize,
    right: &usize,
) -> Option<usize> {
    if left >= right {
        return None;
    }
    let is_asc = list_of_items[0] < list_of_items[list_of_items.len() - 1];
    let middle: usize = left + (right - left) / 2;
    if is_asc {
        match target.cmp(&list_of_items[middle]) {
            Ordering::Less => binary_search_rec(list_of_items, target, left, &middle),
            Ordering::Greater => binary_search_rec(list_of_items, target, &(middle + 1), right),
            Ordering::Equal => Some(middle),
        }
    } else {
        match target.cmp(&list_of_items[middle]) {
            Ordering::Less => binary_search_rec(list_of_items, target, &(middle + 1), right),
            Ordering::Greater => binary_search_rec(list_of_items, target, left, &middle),
            Ordering::Equal => Some(middle),
        }
    }
}
#[cfg(test)]
mod tests {
    use super::*;
    const LEFT: usize = 0;
    #[test]
    fn fail_empty_list() {
        let list_of_items = vec![];
        assert_eq!(
            binary_search_rec(&list_of_items, &1, &LEFT, &list_of_items.len()),
            None
        );
    }
    #[test]
    fn success_one_item() {
        let list_of_items = vec![30];
        assert_eq!(
            binary_search_rec(&list_of_items, &30, &LEFT, &list_of_items.len()),
            Some(0)
        );
    }
    #[test]
    fn success_search_strings_asc() {
        let say_hello_list = vec!["hi", "olá", "salut"];
        let right = say_hello_list.len();
        assert_eq!(
            binary_search_rec(&say_hello_list, &"hi", &LEFT, &right),
            Some(0)
        );
        assert_eq!(
            binary_search_rec(&say_hello_list, &"salut", &LEFT, &right),
            Some(2)
        );
    }
    #[test]
    fn success_search_strings_desc() {
        let say_hello_list = vec!["salut", "olá", "hi"];
        let right = say_hello_list.len();
        assert_eq!(
            binary_search_rec(&say_hello_list, &"hi", &LEFT, &right),
            Some(2)
        );
        assert_eq!(
            binary_search_rec(&say_hello_list, &"salut", &LEFT, &right),
            Some(0)
        );
    }
    #[test]
    fn fail_search_strings_asc() {
        let say_hello_list = vec!["hi", "olá", "salut"];
        for target in &["adiós", "你好"] {
            assert_eq!(
                binary_search_rec(&say_hello_list, target, &LEFT, &say_hello_list.len()),
                None
            );
        }
    }
    #[test]
    fn fail_search_strings_desc() {
        let say_hello_list = vec!["salut", "olá", "hi"];
        for target in &["adiós", "你好"] {
            assert_eq!(
                binary_search_rec(&say_hello_list, target, &LEFT, &say_hello_list.len()),
                None
            );
        }
    }
    #[test]
    fn success_search_integers_asc() {
        let integers = vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90];
        for (index, target) in integers.iter().enumerate() {
            assert_eq!(
                binary_search_rec(&integers, target, &LEFT, &integers.len()),
                Some(index)
            )
        }
    }
    #[test]
    fn success_search_integers_desc() {
        let integers = vec![90, 80, 70, 60, 50, 40, 30, 20, 10, 0];
        for (index, target) in integers.iter().enumerate() {
            assert_eq!(
                binary_search_rec(&integers, target, &LEFT, &integers.len()),
                Some(index)
            )
        }
    }
    #[test]
    fn fail_search_integers() {
        let integers = vec![0, 10, 20, 30, 40, 50, 60, 70, 80, 90];
        for target in &[100, 444, 336] {
            assert_eq!(
                binary_search_rec(&integers, target, &LEFT, &integers.len()),
                None
            );
        }
    }
    #[test]
    fn success_search_string_in_middle_of_unsorted_list() {
        let unsorted_strings = vec!["salut", "olá", "hi"];
        assert_eq!(
            binary_search_rec(&unsorted_strings, &"olá", &LEFT, &unsorted_strings.len()),
            Some(1)
        );
    }
    #[test]
    fn success_search_integer_in_middle_of_unsorted_list() {
        let unsorted_integers = vec![90, 80, 70];
        assert_eq!(
            binary_search_rec(&unsorted_integers, &80, &LEFT, &unsorted_integers.len()),
            Some(1)
        );
    }
}

Чтобы найти целевой элемент в упорядоченном массиве элементов, этот код Rust реализует алгоритм рекурсивного бинарного поиска. Процесс выглядит следующим образом:

1. Binary_search_rec‹T: Ord›(list_of_items: &[T], target: &T, left: &usize, right: &usize) -> Option‹usize› указывает, что функция принимает четыре параметра: часть упорядоченных элементов, целевой элемент для search for и две переменные usize, представляющие левую и правую границы среза. Если элемент найден по заданному индексу, функция возвращает Some(index), в противном случае возвращается None.
2. Первоначально функция проверяет, больше ли левый индекс или равен правому индексу, указывая, что часть элементов была исчерпана, но целевой элемент не найден. В этом случае функция возвращает None.
3. Проверяя, меньше ли первый элемент в срезе, чем последний элемент, функция определяет, отсортирован ли срез по возрастанию или по убыванию.
4. Средний индекс рассчитывается как середина между левым и правым.
5. Когда срез отсортирован по возрастанию, выражение соответствия проверяет, является ли целевой элемент меньше, больше или равен среднему элементу. Рекурсивный вызов binary_search_rec с тем же левым индексом и средним индексом, что и новый правый индекс, ограничивает поиск левой половиной среза, если он меньше среднего элемента. Рекурсивный вызов binary_search_rec со средним + 1 индексом в качестве нового левого индекса и тем же правым индексом ограничивает поиск правой половиной среза, если он больше, чем средний элемент. Функция возвращает Some(middle), если ее значение равно среднему элементу.
6. То же выражение соответствия используется, если срез отсортирован по убыванию, но случаи «меньше» и «больше» меняются местами. Логика поиска нисходящего среза противоположна логике поиска восходящего среза.
7. Существует несколько тестовых случаев для функции, проверяющих различные входные срезы и целевые элементы. Тесты запускаются с использованием assert_eq! Вывод функции должен соответствовать ожидаемому.

Экспоненциальный поиск

use std::cmp::Ordering;
pub fn exponential_search<T: Ord>(item: &T, arr: &[T]) -> Option<usize> {
    let len = arr.len();
    if len == 0 {
        return None;
    }
    let mut upper = 1;
    while (upper < len) && (&arr[upper] <= item) {
        upper *= 2;
    }
    if upper > len {
        upper = len
    }
    // binary search
    let mut lower = upper / 2;
    while lower < upper {
        let mid = lower + (upper - lower) / 2;
        match item.cmp(&arr[mid]) {
            Ordering::Less => upper = mid,
            Ordering::Equal => return Some(mid),
            Ordering::Greater => lower = mid + 1,
        }
    }
    None
}
#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn empty() {
        let index = exponential_search(&"a", &[]);
        assert_eq!(index, None);
    }
    #[test]
    fn one_item() {
        let index = exponential_search(&"a", &["a"]);
        assert_eq!(index, Some(0));
    }
    #[test]
    fn search_strings() {
        let index = exponential_search(&"a", &["a", "b", "c", "d", "google", "zoo"]);
        assert_eq!(index, Some(0));
    }
    #[test]
    fn search_ints() {
        let index = exponential_search(&4, &[1, 2, 3, 4]);
        assert_eq!(index, Some(3));
        let index = exponential_search(&3, &[1, 2, 3, 4]);
        assert_eq!(index, Some(2));
        let index = exponential_search(&2, &[1, 2, 3, 4]);
        assert_eq!(index, Some(1));
        let index = exponential_search(&1, &[1, 2, 3, 4]);
        assert_eq!(index, Some(0));
    }
    #[test]
    fn not_found() {
        let index = exponential_search(&5, &[1, 2, 3, 4]);
        assert_eq!(index, None);
    }
}

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

1. Сигнатура функции exponential_search‹T:Ord›(item: &T, arr: &[T]) -> Option‹usize› указывает на то, что функция принимает два параметра: ссылку на целевой элемент для поиска и ссылку на срез заказанных товаров. Если элемент найден по заданному индексу, функция возвращает Some(index), в противном случае — None.
2. Первоначально функция проверяет, имеет ли входной массив нулевую длину. Он возвращает None, если это так.
3. Итеративно удваивает значение upper до тех пор, пока оно не превысит длину массива или значение в arr[upper] не станет больше или равно целевому значению.
4. Чтобы избежать ошибки индекса за пределами, верхний теперь устанавливается на длину массива, если он превышает длину массива.
5. Затем выполняется бинарный поиск между индексами нижний = верхний/2 и верхний. Каждый раз, когда выполняется итерация, вычисляется середина средней точки и целевой элемент сравнивается с элементом в arr[mid]. Функция продолжает работу с левой половиной массива, если целевой элемент меньше arr[mid]. Функция продолжает работу с правой половиной массива, если она больше, чем элемент в arr[mid]. Функция возвращает Some(mid), если целевой элемент равен элементу в arr[mid].
6. Эта функция возвращает None, если бинарный поиск не находит целевой элемент в диапазоне поиска.
7. В код включено несколько тестовых случаев, проверяющих различные входные срезы и целевые элементы. Assert_eq! используется в тестах. Вывод функции должен соответствовать ожидаемому результату с помощью этого макроса.

Алгоритм поиска Фибоначчи

Одним из наиболее эффективных алгоритмов поиска отсортированных массивов является алгоритм Фибоначчи, реализованный на Rust. Согласно последовательности Фибоначчи, каждый элемент последовательности представляет собой сумму двух предыдущих элементов. Начиная с 0 и 1, первые несколько элементов: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34,…

Числа Фибоначчи используются для разделения массива на две части, и проверяется целевой элемент, в какой части. Пока элемент не будет найден или определен как отсутствующий в массиве, этот процесс повторяется.

Ниже приводится построчное объяснение кода:

use std::cmp::min;
use std::cmp::Ordering;

Этот алгоритм использует признаки std::cmp min и Ordering для сравнения.

pub fn fibonacci_search<T: Ord>(item: &T, arr: &[T]) -> Option<usize> {

Определена общедоступная функция с именем fibonacci_search, которая принимает общий тип T, реализующий черту Ord (то есть может быть упорядоченным), и два аргумента: ссылку на искомый элемент и ссылку на искомый массив. Если элемент не найден, функция возвращает None, в противном случае возвращается его индекс.

let len = arr.len();
    if len == 0 {
        return None;
    }

Проверяется, не пуст ли массив. В этом случае функция возвращает None сразу после вызова.

let mut start = -1;

Начальное значение -1 присваивается переменной start. Он будет использоваться для отслеживания начального индекса подмассива.

let mut f0 = 0;
    let mut f1 = 1;
    let mut f2 = 1;
    while f2 < len {
        f0 = f1;
        f1 = f2;
        f2 = f0 + f1;
    }

Использование 0, 1 и 1 в качестве начальных значений для трех переменных f0, f1 и f2. Эти значения будут использоваться для генерации чисел Фибоначчи. Этот цикл вычисляет наибольшее число Фибоначчи, меньшее или равное длине массива.

while f2 > 1 {
        let index = min((f0 as isize + start) as usize, len - 1);
        match item.cmp(&arr[index]) {
            Ordering::Less => {
                f2 = f0;
                f1 -= f0;
                f0 = f2 - f1;
            }
            Ordering::Equal => return Some(index),
            Ordering::Greater => {
                f2 = f1;
                f1 = f0;
                f0 = f2 - f1;
                start = index as isize;
            }
        }
    }

Основной цикл алгоритма. Если f2 больше 1 (т. е. массив не сократился до одного элемента), он запускается. Используя числа Фибоначчи, цикл делит массив на две части и проверяет, какая часть содержит искомый элемент. Числа Фибоначчи и начальная переменная используются для расчета индексной переменной. В рамках оператора match элемент сравнивается со значением в позиции индекса в массиве с помощью функции cmp.

Алгоритм интерполяционного поиска

Алгоритм интерполяционного поиска — это эффективный алгоритм поиска равномерно распределенных отсортированных массивов, реализованный на Rust. Используя значение целевого элемента и значения первого и последнего элементов в массиве, алгоритм оценивает его положение в массиве. Диапазон поиска сужается на основе оценки.

Код поясняется построчно ниже:

pub fn interpolation_search<Ordering>(nums: &[i32], item: &i32) -> Result<usize, usize> {

Определена общедоступная функция с именем interpolation_search, которая принимает массив значений i32 (числа) и ссылку на целевой элемент (элемент). Функция возвращает тип результата: Ok(index), если элемент найден, и Err(index) в противном случае. Он включен только для согласованности с типом std::cmp::Ordering, поскольку параметр типа Ordering не используется.

// early check
    if nums.is_empty() {
        return Err(0);
    }

Проверяется, не пуст ли массив. Функция немедленно возвращает Err(0), если это так.

let mut low: usize = 0;
    let mut high: usize = nums.len() - 1;

Low и high инициализируются первой и последней позициями индекса в массиве соответственно.

while low <= high {
        if *item < nums[low] || *item > nums[high] {
            break;
        }

Это основной цикл алгоритма. Функция выполняется до тех пор, пока младший индекс меньше или равен старшему индексу, а целевой элемент находится в пределах диапазона массива. В операторе if цикл прерывается, если целевой элемент находится за пределами диапазона массива.

let offset: usize = low
            + (((high - low) / (nums[high] - nums[low]) as usize) * (*item - nums[low]) as usize);

Линейная интерполяция используется для оценки позиции индекса целевого элемента в массиве. Мы используем формулу (item — nums[low]) / (nums[high] — nums[low]), которая дает долю расстояния между первым и последним элементами массива, которое занимает целевой элемент. Чтобы получить предполагаемую позицию индекса, умножьте дробь на диапазон массива ((высокий — низкий)).

match nums[offset].cmp(item) {
            std::cmp::Ordering::Equal => return Ok(offset),
            std::cmp::Ordering::Less => low = offset + 1,
            std::cmp::Ordering::Greater => high = offset - 1,
        }

Определение того, содержится ли целевой элемент в предполагаемой позиции индекса. В этом случае Ok(смещение) будет возвращено с индексом элемента. При обновлении нижнего индекса до смещения + 1 диапазон поиска сужается до правой половины массива, если оценочное значение меньше целевого элемента. Когда оценочное значение превышает целевой элемент, диапазон поиска сужается до левой половины массива путем обновления старшего индекса до смещения -1.

}
    Err(0)

Err(0) возвращается, если цикл завершается без нахождения целевого элемента.

Чтобы убедиться, что функция работает корректно в разных сценариях, блок #[cfg(test)] содержит несколько модульных тестов. Каждый тестовый пример кратко описан ниже:

#[test]
fn returns_err_if_empty_slice() {
    let nums = [];
    assert_eq!(interpolation_search::<Ordering>(&nums, &3), Err(0));
}

Когда в качестве входных данных передается пустой массив, этот тест проверяет, возвращает ли функция Err(0).

#[test]
fn returns_err_if_target_not_found() {
    let nums = [1, 2, 3, 4, 5, 6];
    assert_eq!(interpolation_search::<Ordering>(&nums, &10), Err(0));
}

Проверяет, возвращает ли функция Err(0), когда целевой элемент отсутствует.

#[test]
fn returns_first_index() {
    let index: Result<usize, usize> = interpolation_search::<Ordering>(&[1, 2, 3, 4, 5], &1);
    assert_eq!(index, Ok(0));
}

Если целевой элемент является первым элементом массива, этот тест проверяет, возвращает ли функция правильный индекс.

#[test]
fn returns_last_index() {
    let index: Result<usize, usize> = interpolation_search::<Ordering>(&[1, 2, 3, 4, 5], &5);
    assert_eq!(index, Ok(4));
}

Когда целевой элемент является последним элементом массива, этот тест проверяет, возвращает ли функция правильный индекс.

#[test]
fn returns_middle_index() {
    let index: Result<usize, usize> = interpolation_search::<Ordering>(&[1, 2, 3, 4, 5], &3);
    assert_eq!(index, Ok(2));
}

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

Чтобы убедиться, что функция работает правильно для разных входных массивов и целевых элементов, эти модульные тесты охватывают разные сценарии.

Алгоритм поиска перехода

Эффективным алгоритмом поиска для отсортированных массивов является алгоритм поиска с переходом в Rust. Разделив массив на блоки фиксированного размера, алгоритм находит диапазон, в котором находится целевой элемент, перескакивая через эти блоки. Точное местоположение целевого элемента определяется линейным поиском после определения диапазона.

Ниже приводится построчное объяснение кода:

pub fn jump_search<T: Ord>(item: &T, arr: &[T]) -> Option<usize> {

Определение общедоступной функции jump_search, которая принимает ссылку на массив значений T (arr) и ссылку на целевой элемент (item). Функция возвращает тип Option‹usize›, который будет Some(index), если элемент найден, и None, если он не найден. Это гарантирует, что элементы в массиве упорядочены и могут сравниваться с параметром типа T: Ord.

let len = arr.len();
    if len == 0 {
        return None;
    }

Проверка пустого массива. В таком случае функция немедленно возвращает None.

let mut step = (len as f64).sqrt() as usize;
    let mut prev = 0;

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

while &arr[min(len, step) - 1] < item {
        prev = step;
        step += (len as f64).sqrt() as usize;
        if prev >= len {
            return None;
        }
    }

Это основной цикл алгоритма. Пока последний элемент текущего блока не станет меньше целевого элемента, он выполняется. Выражение min(len, step) — 1 определяет индекс последнего элемента в текущем блоке. Переменная prev обновляется до текущего блока, если последний элемент меньше целевого элемента, а переменная step увеличивается до следующего блока, если последний элемент больше целевого элемента. Функция возвращает None, если переменная prev превышает длину массива.

while &arr[prev] < item {
        prev += 1;
        if prev == min(step, len) {
            return None;
        }
    }

Как только правильный блок идентифицирован, функция выполняет линейный поиск в этом блоке, чтобы найти целевой элемент. Для каждой итерации переменная prev увеличивается на 1 до тех пор, пока текущий элемент меньше целевого элемента. Функция возвращает None, если переменная prev равна последнему элементу в блоке или массиве.

if &arr[prev] == item {
        return Some(prev);
    }
    None

Когда целевой элемент найден, функция возвращает Some(prev) с его индексом. Функция возвращает None, если целевой элемент не может быть найден.

В блоке #[cfg(test)] содержится несколько модульных тестов, чтобы убедиться, что функция работает правильно в различных сценариях. Тесты охватывают пустые массивы, массивы только с одним элементом, массивы с несколькими элементами и массивы без целевого элемента.

#[test]
fn empty() {
    let index = jump_search(&"a", &[]);
    assert_eq!(index, None);
}

Когда в качестве входных данных передается пустой массив, этот тест проверяет, возвращает ли функция None.

#[test]
fn one_item() {
    let index = jump_search(&"a", &["a"]);
    assert_eq!(index, Some(0));
}

Когда целевой элемент является единственным элементом в массиве, этот тест проверяет, возвращает ли функция Some(0).

#[test]
fn search_strings() {
    let index = jump_search(&"a", &["a", "b", "c", "d", "google", "zoo"]);
    assert_eq!(index, Some(0));
}

Когда целевой элемент присутствует в массиве строк, этот тест проверяет, возвращает ли функция правильный индекс.

#[test]
fn search_ints() {
    let index = jump_search(&4, &[1, 2, 3, 4]);
    assert_eq!(index, Some(3));
let index = jump_search(&3, &[1, 2, 3, 4]);
    assert_eq!(index, Some(2));
    let index = jump_search(&2, &[1, 2, 3, 4]);
    assert_eq!(index, Some(1));
    let index = jump_search(&1, &[1, 2, 3, 4]);
    assert_eq!(index, Some(0));
}

В этих тестах функция проверяется, возвращает ли она правильный индекс, когда целевой элемент существует в массиве целых чисел.

#[test]
fn not_found() {
    let index = jump_search(&5, &[1, 2, 3, 4]);
    assert_eq!(index, None);
}

Когда целевой элемент отсутствует в массиве, этот тест проверяет, возвращает ли функция None.

Чтобы убедиться, что функция работает правильно для разных входных массивов и целевых элементов, эти модульные тесты охватывают разные сценарии.

kth_smalest Поиск

В этом коде Rust «kth_smallest» находит k-й наименьший элемент в массиве, используя рандомизированный алгоритм быстрого выбора. Эта функция изменяет входной массив и возвращает k-й наименьший элемент в виде Option‹T›. Существует наихудшая временная сложность O (n2), но средняя временная сложность O (n).

Разберем код подробнее:

use crate::sorting::partition;
use std::cmp::{Ordering, PartialOrd};
pub fn kth_smallest<T>(input: &mut [T], k: usize) -> Option<T>
where
    T: PartialOrd + Copy,
{
    if input.is_empty() {
        return None;
    }
    let kth = _kth_smallest(input, k, 0, input.len() - 1);
    Some(kth)
}

Kth_smallest принимает изменяемую ссылку на массив «input» универсального типа «T» и положительное целое число «k». Функция возвращает None, если входной массив пуст. Вместо этого он вызывает закрытую функцию «_kth_smallest» с массивом k и индексами его первого и последнего элементов. После этого он возвращает значение Some(kth), где kth — наименьший элемент входного массива.

fn _kth_smallest<T>(input: &mut [T], k: usize, lo: usize, hi: usize) -> T
where
    T: PartialOrd + Copy,
{
    if lo == hi {
        return input[lo];
    }
let pivot = partition(input, lo as isize, hi as isize) as usize;
    let i = pivot - lo + 1;
    match k.cmp(&i) {
        Ordering::Equal => input[pivot],
        Ordering::Less => _kth_smallest(input, k, lo, pivot - 1),
        Ordering::Greater => _kth_smallest(input, k - i, pivot + 1, hi),
    }
}

Функция «_kth_smallest» рекурсивно реализует рандомизированный алгоритм быстрого выбора. Помимо тех же аргументов, что и «kth_smallest», он также принимает нижнюю границу «lo» и верхнюю границу «hi» для рассматриваемого подмассива. В базовом случае в подмассиве есть только один элемент. В этом случае функция возвращает этот элемент.

На следующем шаге функция случайным образом выбирает опорный элемент из подмассива и разбивает подмассив вокруг него. В своем конечном положении поворотный элемент делает все элементы слева от него меньше, а все элементы справа больше. Затем функция вычисляет «i», количество элементов слева от опорной точки, и сравнивает его с «k». Когда «i» равно «k», функция возвращает опорный элемент. Функция выполняет рекурсивный вызов правого подмассива, если «i» меньше «k», обновляя «k» для учета «i» меньших элементов. Левый подмассив вызывается рекурсивно, если «i» больше «k».

#[test]
fn empty() {
    let mut zero: [u8; 0] = [];
    let first = kth_smallest(&mut zero, 1);
assert_eq!(None, first);
}
#[test]
fn one_element() {
    let mut one = [1];
    let first = kth_smallest(&mut one, 1);
    assert_eq!(1, first.unwrap());
}
#[test]
fn many_elements() {
    // 0 1 3 4 5 7 8 9 9 10 12 13 16 17
    let mut many = [9, 17, 3, 16, 13, 10, 1, 5, 7, 12, 4, 8, 9, 0];
    let first = kth_smallest(&mut many, 1);
    let third = kth_smallest(&mut many, 3);
    let sixth = kth_smallest(&mut many, 6);
    let fourteenth = kth_smallest(&mut many, 14);
    assert_eq!(0, first.unwrap());
    assert_eq!(3, third.unwrap());
    assert_eq!(7, sixth.unwrap());
    assert_eq!(17, fourteenth.unwrap());
}

При наличии пустого массива «пустой» тестовый пример проверяет, возвращает ли функция None. Когда k = 1, тестовый пример one_element проверяет, возвращает ли функция одноэлементный массив только с одним элементом. Несколько значений k проверяются в тестовом примере «many_elements», чтобы гарантировать, что функция возвращает правильный наименьший элемент массива из 14 элементов. Тесты утверждают, что возвращаемые значения равны ожидаемым значениям на основе входного массива изменяемых целых чисел.

Алгоритм линейного поиска

Этот код на Rust реализует простой алгоритм линейного поиска, который возвращает индекс найденного элемента или None, если элемент не может быть найден в массиве. Требуются два аргумента: ссылка на искомый элемент и ссылка на массив. Значение, представляющее индекс найденного элемента, возвращается функцией, если элемент не найден, или None, если он не был обнаружен.

pub fn linear_search<T: PartialEq>(item: &T, arr: &[T]) -> Option<usize> {
    for (i, data) in arr.iter().enumerate() {
        if item == data {
            return Some(i);
        }
    }
None
}

Для перебора массива и повторения каждого элемента функция использует метод enumerate для поиска элемента. Для каждого элемента массива метод enumerate возвращает кортеж (i, данные), где i — индекс, а данные — элемент. Используя трейт PartialEq, функция сравнивает элемент с каждым элементом и возвращает Some(i), если есть совпадение. Функция возвращает None, если совпадений нет.

Также в код включен тестовый модуль с четырьмя тест-кейсами:

#[cfg(test)]
mod tests {
    use super::*;
#[test]
    fn search_strings() {
        let index = linear_search(&"a", &["a", "b", "c", "d", "google", "zoo"]);
        assert_eq!(index, Some(0));
    }
    #[test]
    fn search_ints() {
        let index = linear_search(&4, &[1, 2, 3, 4]);
        assert_eq!(index, Some(3));
        let index = linear_search(&3, &[1, 2, 3, 4]);
        assert_eq!(index, Some(2));
        let index = linear_search(&2, &[1, 2, 3, 4]);
        assert_eq!(index, Some(1));
        let index = linear_search(&1, &[1, 2, 3, 4]);
        assert_eq!(index, Some(0));
    }
    #[test]
    fn not_found() {
        let index = linear_search(&5, &[1, 2, 3, 4]);
        assert_eq!(index, None);
    }
    #[test]
    fn empty() {
        let index = linear_search(&1, &[]);
        assert_eq!(index, None);
    }
}

«search_strings» проверяет, правильно ли функция ищет строку в массиве строк и возвращает индекс первого вхождения. В тестовом примере «search_ints» функция проверяется на нахождение целых чисел в массиве целых чисел и на возвращение индекса первого вхождения. Когда элемент не может быть найден в массиве, тестовый пример «not_found» проверяет, возвращает ли функция None. Если массив пуст, «пустой» тестовый пример проверяет, возвращает ли функция None. Во всех тестах макрос assert_eq используется для проверки того, были ли достигнуты ожидаемые результаты.

Алгоритм быстрого выбора

Используя этот код Rust, вы можете найти k-й наименьший (или самый большой) элемент в неупорядоченном списке, используя алгоритм быстрого выбора. Используя QuickSort в качестве основы, QuickSelect делит список на две части вокруг опорного элемента, а затем рекурсивно выбирает одну часть для поиска k-го элемента.

fn partition(list: &mut [i32], left: usize, right: usize, pivot_index: usize) -> usize {
    let pivot_value = list[pivot_index];
    list.swap(pivot_index, right); // Move pivot to end
    let mut store_index = left;
    for i in left..(right + 1) {
        if list[i] < pivot_value {
            list.swap(store_index, i);
            store_index += 1;
        }
        list.swap(right, store_index); // Move pivot to its final place
    }
    store_index
}
pub fn quick_select(list: &mut [i32], left: usize, right: usize, index: usize) -> i32 {
    if left == right {
        // If the list contains only one element,
        return list[left];
    } // return that element
    let mut pivot_index = ((left + right) / 2) + 1; // select a pivotIndex between left and right
    pivot_index = partition(list, left, right, pivot_index);
    // The pivot is in its final sorted position
    match index {
        x if x == pivot_index => list[index],
        x if x < pivot_index => quick_select(list, left, pivot_index - 1, index),
        _ => quick_select(list, pivot_index + 1, right, index),
    }
}

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

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

В качестве первого шага функция устанавливает значение поворота равным значению в позиции pivot_index в массиве. В результате опорное значение заменяется значением в правом конце подмассива, эффективно перемещая опорное значение в конец.

Проходит по подмассиву, проверяя каждый элемент по опорному значению, и инициализирует переменную store_index слева. Элементы меньше точки поворота меняются местами с элементами в store_index, а store_index увеличивается, эффективно перемещая элемент влево.

Затем функция меняет опорное значение на значение в store_index, перемещая опорное значение в его окончательную отсортированную позицию, при этом все элементы слева от него меньше опорного значения, а все элементы справа от него больше или равны опорному значению. После этого возвращается store_index.

Quick_select принимает в качестве входных данных список массивов i32, самый левый и самый правый элементы подмассива и k-й наименьший элемент. Возвращается наименьший элемент подмассива.

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

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

В код также включен тестовый модуль с тремя тест-кейсами:

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn it_works() {
        let mut arr1 = [2, 3, 4, 5];
        assert_eq!(quick_select(&mut arr1, 0, 3, 1), 3);
        let mut arr2 = [2, 5, 9, 12, 16];
        assert_eq!(quick_select(&mut arr2, 1, 3, 2), 12);
        let mut arr2 = [0, 3, 8];
        assert_eq!(quick_select(&mut arr2, 0, 0, 0), 0);
    }
}

Это тестовый модуль Rust, который тестирует функцию quick_select. Атрибут #[cfg(test)] помечает модуль как тестовый модуль, что говорит Rust компилировать и запускать тесты модуля только при выполнении тестов, а не во время обычного выполнения кода.

Блок mod tests определяет тестовый модуль, а оператор use super::*; импортирует все элементы из родительского модуля (который содержит функцию quick_select) в область действия тестового модуля.

Атрибут #[test] помечает следующую функцию как тестовую, что говорит Rust скомпилировать и запустить функцию как тестовый пример. Тестовая функция называется it_works и содержит три утверждения, проверяющие поведение функции quick_select на трех различных входных массивах.

Первый тестовый пример создает массив arr1, содержащий целые числа [2, 3, 4, 5], и утверждает, что quick_select(&mut arr1, 0, 3, 1) возвращает целое число 3.

Второй тестовый пример создает массив arr2, содержащий целые числа [2, 5, 9, 12, 16], и утверждает, что quick_select(&mut arr2, 1, 3, 2) возвращает целое число 12.

Третий тестовый пример создает массив arr3, содержащий целые числа [0, 3, 8], и утверждает, что quick_select(&mut arr3, 0, 0, 0) возвращает целое число 0.

Если какое-либо из утверждений терпит неудачу, тестовый пример терпит неудачу, и Rust сообщает об ошибке вместе с ожидаемыми и фактическими значениями. Если все утверждения пройдены, тест-кейс пройден, и Rust сообщает, что тест-кейс пройден.