Наверное, вы не так поняли. Задача называется binary_search и состоит из ввода/вывода + сортировку массива A + поиск значений из массива B в массиве A. В таблице честно указана асимптотика задачи O(N logN).
Хотя нехорошо, что сортировка, занимающая O(N logN), может занимать больше времение, чем основная деятельность программы, описанная в ее названии (тут мы имеем O(M logN), где M — кол-во элементов в массиве B). Возможно, в следующей ревизии статьи и кода, я буду подавать на вход программы уже отсортированные данные.
Спасибо большое за замечания! Я исправлю код в репозитории и в статье.
Насчет возврата -1 из binary_search, как так получилось: изначально в задаче в онлайн курсе было такое требование (возвращать -1, индексация с 1), изначально я решал данную задачу на C++ и, недостаточно подумав, переписал так же на Rust. Действительно, лучше возвращать Option, а при записи результата делать unwrap_or(-1)
1. Согласен, как только доберусь до машинки, на которой проводил замеры, соберу данные по clang. Постараюсь взять clang такой версии, чтобы версия LLVM совпадала с Rust.
2. Я измеряю не время вызова функций — это действительно сложная история и есть много готовых решений. Я измеряю полное время выполнения программы. Я отказался от программы time, т.к. она под Mac os x не выдавала результат с нужной мне точностью. Программа measure, на которую вы указали, — это лишь попытка обойти это ограничение и иметь возможность проводить замеры на Linux & Mac os x.
Интуитивно — оптимизированные до упора программы должны дать примерно одинаковое быстродействие
Спасибо за эту мысль. Я ее не смог высказать в статье.
Действительно, всегда можно получить оптимальный машинный код на компилируемом языке, хотя бы ассемблерными вставками. Статья же призвана показать, какую производительность можно достичь, используя идиоматический подход и высокоуровневые конструкции того, или иного языка.
Мы ведь хотим писать быстро, и чтоб работало быстро, а не зависать над ассемблером и профилировщиком :)
На всякий случай повторю, что цель статьи не в том, чтобы сказать, что Rust быстрее C++, а сказать, что Rust не медленней C++.
Код для C++ не представлен, чтобы не раздувать размер статьи. Код доступен на github, там же вы можете оценить корявость кода и флаги компиляции. Если у вас будут объективные замечания к коду — я обязательно их учту. Флаги: g++ -std=c++11 -O2 -o main_cpp main.cpp rustc -O --crate-name main_rust main.rs
Rust компилирует в LLVM код, как и clang, поэтому оптимизации, заложенные в LLVM, должны работать и там, и тут.
У Rust система типов дает оптимизатору дополнительные гарантии по владению памяти, что потенциально может привести к более оптимизированному коду.
O(N logN).Хотя нехорошо, что сортировка, занимающая
O(N logN), может занимать больше времение, чем основная деятельность программы, описанная в ее названии (тут мы имеемO(M logN), где M — кол-во элементов в массивеB). Возможно, в следующей ревизии статьи и кода, я буду подавать на вход программы уже отсортированные данные.Насчет возврата -1 из
binary_search, как так получилось: изначально в задаче в онлайн курсе было такое требование (возвращать -1, индексация с 1), изначально я решал данную задачу наC++и, недостаточно подумав, переписал так же наRust. Действительно, лучше возвращатьOption, а при записи результата делатьunwrap_or(-1)2. Я измеряю не время вызова функций — это действительно сложная история и есть много готовых решений. Я измеряю полное время выполнения программы. Я отказался от программы time, т.к. она под Mac os x не выдавала результат с нужной мне точностью. Программа measure, на которую вы указали, — это лишь попытка обойти это ограничение и иметь возможность проводить замеры на Linux & Mac os x.
Можно было брать больше прогонов, но дисперсия времени выполнении была невелика.
Спасибо за эту мысль. Я ее не смог высказать в статье.
Действительно, всегда можно получить оптимальный машинный код на компилируемом языке, хотя бы ассемблерными вставками. Статья же призвана показать, какую производительность можно достичь, используя идиоматический подход и высокоуровневые конструкции того, или иного языка.
Мы ведь хотим писать быстро, и чтоб работало быстро, а не зависать над ассемблером и профилировщиком :)
Этот комментарий нам никак не поможет, напишите конкретное место и как его улучшить.
Код для C++ не представлен, чтобы не раздувать размер статьи. Код доступен на github, там же вы можете оценить корявость кода и флаги компиляции. Если у вас будут объективные замечания к коду — я обязательно их учту. Флаги:
g++ -std=c++11 -O2 -o main_cpp main.cpprustc -O --crate-name main_rust main.rsRustкомпилирует вLLVMкод, как иclang, поэтому оптимизации, заложенные в LLVM, должны работать и там, и тут.У Rust система типов дает оптимизатору дополнительные гарантии по владению памяти, что потенциально может привести к более оптимизированному коду.