29 июл 2022 в 01:05

Стоит ли использовать Rust при изучении алгоритмов?

Ожидает приглашения

Я решил изучить книгу И. В. Романовского "Алгоритмы решения экстремальных задач". В силу своего почтенного возраста (у меня издание 1977 года), все примеры в книге приведены с использованием языков программирования Algol 60 и Algol 68. В то же время, недавно я начал знакомиться с языком программирования Rust. Что если по мере чтения книги портировать примеры кода с Algol на Rust и, тем самым, убить двух зайцев: опробовать примеры из книги и попрактиковаться в написании кода на Rust? Однако портирование первого же примера заставило поразмыслить, а так ли хороша задумка.

Задача

Описание задачи, содержащей первый нетривиальный отрывок кода, звучит следующим образом:

Пусть требуется перебрать все подмножества 1:n, т. е. множества целых чисел от 1 до n. Каждое такое множество A можно задать его _характеристическим вектором_ chi[1:n], где $chi[i] = \delta(i \in A)$ . В свою очередь каждый такой вектор можно рассматривать как двоичную запись некоторого натурального числа, и перебрать все такие векторы можно, перебрав все числа от 0 до $2^{n} - 1$ (т. е. все элементы множества $0:2^{n} - 1$ ). Описание алгоритма выглядит так:
1. Использовать имеющийся вектор chi.
2. Положить целое число i равным 1.
3. Если i > n, то перейти к п. 6.
4. Если chi[i]=0, то положить chi[i] равным 1 и перейти к п. 1.
5. Положить chi[i] равным 0, увеличить i на 1 и перейти к п. 3.
6. Завершить вычисления.

Решение на Algol 60

procedure subsets (n, use);
	value n; integer n; procedure use;
begin
	integer i; integer array chi[1:n];
  for i := 1 step 1 until n do chi[i] := 0;
mk: use(chi);
  for i := 1 step 1 until n do
  	if chi[i] = 1 then chi[i] := 0
    else begin chi[i] := 1; go to mk end
end

Решение на Rust

Первая проблема, с которой мы сталкиваемся при портировании на Rust заключается в том, что размерность массива в Rust должна быть известна во время компиляции. Поэтому придется вместо массива использовать тип Vec<T>. Далее, метки в Rust разрешены только на циклах, поэтому используем дополнительный бесконечный цикл loop с break в конце. Наконец, чтобы передать в функцию код, использующий вектор, параметризуем функцию параметром типа F и потребуем, чтобы он реализовывал трейт Fn(&[u8]). Почему функция принимает слайс &[u8] вместо вектора? Для того чтобы не передать владение вектором в вызываемый код. Итак, получился следующий порт:

fn subsets<F>(n: usize, f: F) where F: Fn(&[u8]) {
    let mut chi: Vec<u8> = Vec::with_capacity(n);
    for _ in 0..n {
        chi.push(0)
    }
    'mk: loop {
        f(&chi);
        for i in 0..n {
            if chi[i] == 1 {
                chi[i] = 0
            } else {
                chi[i] = 1;
                continue 'mk
            }
        }
        break
    }
}

fn main() {
    subsets(4, |chi| println!("{:?}", chi))
}

Код работает, однако линтер нам намекает, что код не идеоматичен и неплохо было бы использовать итераторы вместо доступа по индексу.

consider using an iterator: <item> (rustic-clippy)
main.rs 8 18 warning clippy::needless_range_loop the loop variable i is only used to index chi (rustic-clippy)

Воспользуемся советом. Обратим внимание, что нам нужно будет изменять значения во время итерации и значит тип элемента должен быть &mut u8. Заодно также используем макрос vec! для инициализации вектора.

fn subsets<F>(n: usize, f: F) where F: Fn(&[u8]) {
    let mut chi: Vec<u8> = vec![0; n];
    'mk: loop {
        f(&chi);
        for elem in &mut chi {
            if *elem == 1 {
                *elem = 0
            } else {
                *elem = 1;
                continue 'mk
            }
        }
        break
    }
}

fn main() {
    subsets(4, |chi| println!("{:?}", chi));
}

Заключение

Итак, оправдано ли было здесь использование Rust? В качестве головоломки для начинающего изучать Rust, да. Как язык для изучения алгоритмов, пожалуй нет. Слишком много всего нужно знать, чтобы реализовать простейший код. Судите сами: семантика передачи владения, мутабельные и иммутабельные ссылки, указатели, параметры типа, трейты, макросы для литералов коллекций. Так "куда христианину податься", какой современный язык использовать для изучения алгоритмов? Си - слишком низкоуровневой, Java - слишком ООП и многословен, Python - слишком много сахара. Получается что сейчас, как и много лет назад, лучшим языком для изучения алгоритмов будет язык из семейства Algol? Из современных диалектов это, пожалуй, Free Pascal и Zonnon. А как считаете вы?

Теги:

Хабы: