Идиоматические способы использования кортежей и std::tie
Я пытаюсь реализовать модульный мультипликативный обратный , используя расширенный алгоритм Евклида на C++. В Python код для этого краткий и идиоматический, в нем используется распаковка кортежей:
def inv_modulo(a: int, b: int) -> int:
_s, s = 1, 0
_t, t = 0, 1
while a % b != 0:
q, r = divmod(a, b)
_s, s = s, _s - q * s
_t, t = t, _t - q * t
a, b = b, r
return s
Я хочу воспроизвести это поведение на C++ и написал следующий код:
long long inv_modulo(long long a, long long b) {
long long old_s = 1, s = 0;
long long old_t = 0, t = 1;
while (a % b != 0) {
auto [q, r] = std::lldiv(a, b);
std::tie(old_s, s) = std::make_tuple(s, old_s - q * s);
std::tie(old_t, t) = std::make_tuple(t, old_t - q * t);
std::tie(a, b) = std::make_tuple(b, r);
}
return s;
}
У меня есть три конкретных вопроса по поводу этой реализации:
- Эквивалентен ли этот код C++ показанному коду Python?
- Считается ли этот код идиоматическим в программировании на C++?
- Существует ли снижение производительности при написании кода таким способом по сравнению с другим подходом, например использованием временных переменных для промежуточных этапов вычислений?
Спасибо, думаю, это то, что я действительно искал! Если вы хотите опубликовать свое решение, я приму его!
Для тривиальных типов, таких как целочисленные типы, если и есть накладные расходы, они будут небольшими; но для нетривиальных типов (таких как std::string), если они не оптимизированы, существуют дополнительные копии.
1. да 2. Я бы сказал нет, но код меня устраивает. 3. Дополнительные копии, связанные с дополнительным кортежем (по сравнению с множественным простым присвоением) (полагаясь на то, что оптимизатор устранит накладные расходы).
Будет ли std::exchange создавать дополнительные копии?
Это работает, но я бы просто использовал std::div в C++; он имеет перегрузки для всех целочисленных типов со знаком, больших int. И я бы использовал std::int64_t для фиксированного размера на разных платформах или std::intmax_t для использования самого большого поддерживаемого целого числа со знаком. std::tie не популярен среди программистов C++, но ваш вариант использования мне нравится. Правая часть должна быть std::tuple-, как и std::make_tuple. Но начиная с C++17, вы можете просто сделать std::tuple{a,b} и получить тот же результат.
@Red.Wave: tuple{a, b} даже лучше с гарантированным порядком оценки (std::tuple{string1 + string2, std::move(string1)} (хотя порядок параметров очень важен и может быть не «естественным» порядком :-/)
Целочисленные типы являются фундаментальными типами данных. Поэтому они также тривиальны. Это делает их первыми кандидатами для всех видов оптимизации. Не беспокойтесь об оптимизации, если она делает то, что должна. Проверьте разборку, чтобы узнать о ее работоспособности.
Ответы 2
AFAIK, std::tie изначально был разработан для точно такого же использования; как левая часть задания, хотя позже могли появиться и другие полезные случаи. Идиома хорошо иллюстрирует относительность во фрагменте ОП:
- структурированная привязка для разделения значений, подобных кортежу.
std::tieслева от заданияstd::tupleконструктор (илиstd::make_tupleдля более старых версий стандарта) в правой части задания.
std::tie создает временный кортеж ссылок на элементы, которые необходимо назначить из другого кортежа.
Основными задачами каждой программы являются функциональность и читаемость. Проблемы оптимизации возникают только после тщательного сравнительного анализа.
Это краткое изложение того, что @Jarod42 сказал в комментариях. Я ждал, пока он опубликует ответ, чтобы принять его, но, поскольку этого не произошло, вот ответ на мой вопрос.
- Да, этот код эквивалентен коду Python, показанному выше.
- Нет, это не идиоматический способ написания кода на C++, но, судя по комментариям, он не будет беспокоить многих разработчиков C++.
- Для тривиальных типов это, вероятно, можно оптимизировать, но для нетривиальных типов у нас есть дополнительная копия при создании кортежа, и мы полагаемся на компилятор для оптимизации.
Он также отметил, что в моем случае можно использовать std::exchange из C++14. Это мой рефакторинг кода после комментариев.
std::int64_t inv_modulo(std::int64_t a, std::int64_t b) {
std::int64_t old_s = 1, s = 0;
std::int64_t old_t = 0, t = 1;
while (a % b != 0) {
auto div_result = std::div(a, b);
old_s = std::exchange(s, old_s - div_result.quot * s);
old_t = std::exchange(t, old_t - div_result.quot * t);
a = std::exchange(b, div_result.rem);
}
return s;
}
структурное связывание немного рискованно. Обратите внимание, что std::lldiv_t имеет неопределенный порядок полей :(. См. документацию.
Почему С++????? :'( Я обновил код, чтобы удалить структурную привязку, так лучше?
Для этого конкретного случая (назначение old, current, new_value) существует std::exchange (C++14). (
old_s = std::exchange(s, old_s - q * s))