最近、複雑なミュータブル ラムダを標準アルゴリズムに渡す人を見てきました。これらの使用法は通常、1 つの考え方から来ています。可変ラムダを使用して複雑なロジックを保持するよりも?"この考えの両方の前提が間違っていると思います。まず、「生のループがない」ことは定説ではなく理想として扱われるべきです。ユースケースに応じて、いつでもニーズに合わせてアルゴリズムを作成できます。
私は次のツイートでこの考えを表明しました:
この投稿では、この考えを少し拡張しようとします。
可変ラムダは <algorithms> の美しさを破壊します
<algorithm> を使用する理由 ?それは「エレガント」または「モダン」だからですか?それとも「一部の専門家がそう言った」からですか? ?"どちらも <algorithm> を好む恐ろしい理由です オーバーループ。私にとっては、<algorithm> 次の利点があります:
- 変化しにくい状態
- 宣言的
- 意思表示
- 既知の正しい実装
変更可能なラムダはそれらすべてを破壊します。まず、STL アルゴリズムは変更可能な状態を小さな関数にカプセル化します。それにもかかわらず、必要なのは mutable だけです。 アルゴリズムがすべての変更可能なロジックをカプセル化できなかった場合のラムダ。2 つ目は、変更可能な状態と複雑な制御フローが戻ってきたため、実装を宣言型と呼ぶことはできなくなりました。3 つ目は、アルゴリズムを実行するためにラムダ内に複雑なロジックを拡張する必要があるためです。タスク, アルゴリズムは私たちの意図を表現していません.4 つ目, アルゴリズムは私たちの意図を表現していないため, たとえアルゴリズム自体が正しいとしても, 私たち自身の 理解しにくい バグルアーがまだある可能性があります. コード。
LeetCode の例
Yacob Cohen-Arazi による LeetCode Two Sum 問題の次の C++ ソリューションを見てみましょう。問題は次のように表現されます:"与えられた整数の配列 nums および整数 target 、合計がターゲットになるような 2 つの数値のインデックスを返します。 " そして LeetCode は twoSum の型シグネチャを提供します 変更できない機能。
std::vector<int> twoSum(std::vector<int>& nums, int target) {
int idx1{}, idx2{};
auto process_and_lookup(
[m = std::unordered_map<int, int>(),
i = 0, target, &idx1, &idx2]
(const auto item) mutable {
auto iter = m.find(target - item);
if (iter == cend(m)) {
m[item] = i++;
return false;
}
idx1 = iter->second;
idx2 = i;
return true;
});
auto iter = std::find_if(
cbegin(nums), cend(nums), process_and_lookup);
assert(iter != cend(nums));
return {idx1, idx2};
}
このバージョンは長く、乱雑で、読みにくいです。また、5 つの変更可能な状態 m も含まれています。 、 idx1 、 idx2 、 i 、および target target でも 基本的に同じロジックを実行している、私が書いたループ バージョンを次に示します。
std::vector<int> twoSum(std::vector<int>& nums, int target) {
std::unordered_map<int, int> nums_map;
const int size = static_cast<int>(nums.size());
for (int i = 0; i < size; ++i) {
const auto item = nums[i];
const auto iter = nums_map.find(target - item);
if (iter != nums_map.end()) {
return {iter->second, i};
}
nums_map.emplace(item, i);
}
throw std::runtime_error{"No solution exist"};
}
このループ バージョンは短く、理解しやすく、変更可能な状態が 2 つだけ含まれています:マップ nums_map インデックス i .
<algorithm> std::find_if のため、バージョンはここにひどく着陸します この問題の意図と一致しません。std::find_if シングルを見つけます しかし、私たちの状況では、述語に一致する 2 つの要素を一緒に見つける必要があります。その結果、この問題に対して十分な有用な機能を提供しませんが、代わりに障害となります。私はこの種の <algorithm> 抽象化反転アンチパターンのインスタンスを使用します。抽象化がタスクに適していないため、抽象化が非表示にする実装の詳細を再実装し始めます。この種の使用法は、コードを読みにくくし、潜在的な非-わずかなランタイム コストであり、バグが発生する可能性が高くなります。<algorithm> ヘッダーはすべての逆境に対処しようとしますが、変更可能なラムダを使用することで、関数の対応するループよりも悪い状況に陥ります。
別の例:述語を満たすまで内積を計算します
Dima Savin が難しい問題を教えてくれます:
この問題を STL アルゴリズムで解決するのは困難です。STL アルゴリズムは順番に構成するように設計されているためです。ループ バージョンで見られるように、反復中に複数のインターリーブされたロジックが存在します。
したがって、ループ バージョンを開始点として使用します。Dima は、インデックスが見つからなかった場合に何が起こるかを指定していないため、i の最終結果を返します。 、これは最後の要素に 1 を加えたインデックスである必要があります:
template <std::input_iterator Itr, std::input_iterator Itr2, class T>
auto inner_product_till(
Itr first1, Itr last1, Itr2 first2, const T upper_bound)
-> std::size_t
{
T acc{};
std::size_t i = 0;
for (; first1 != last1; ++first1, ++first2, ++i) {
acc = std::move(acc) + *first1 * *first2;
if (acc > upper_bound) { return i; }
}
return i;
}
このバージョンは確かに理想的ではありません.4 つの可変状態 first1 が含まれています. 、 first2 、 i 、および acc にもかかわらず、ループ内のロジックは単純であり、まともな C++ プログラマーなら誰でもこのコードを比較的短時間で理解できるはずです。
私はこのバージョンに満足しています.最初に「生のループなし」のイデオロギーを提案した人物であるショーンの親でさえ、関数「生のループ」にうまくカプセル化されたこの種の単純なループを考慮しません.
std::find + ただし、変更可能なラムダ バージョンは、ループ バージョンよりも確実に劣っています。このバージョンには、同じ量の変更可能な状態が含まれており、この種のラムダを多用するスタイルのプログラミングに慣れている人でも、非常に読みにくくなっています。
template <std::input_iterator Itr, std::input_iterator Itr2, class T>
auto inner_product_till(
Itr first1, Itr last1, Itr2 first2, const T upper_bound)
-> std::size_t
{
std::size_t i = 0;
std::find_if(first1, last1,
[acc = T{}, first2, upper_bound, &i]
(const T& elem) mutable {
acc = std::move(acc) + elem * *first2;
if (acc > upper_bound) return true;
++first2;
++i;
return false;
});
return i;
}
少し戻って、ここで達成しようとしているロジックについて考えてみます.2 つのインターリーブ ステップを見つけることができます.最初に、これまでに出会った要素に対して内積を実行する必要があります.2 番目に、この計算された内積が積が upper_bound より大きい .「インターリーブ」部分を無視すると、std::transform を使用できます と std::partial_sum 最初のステップと std::find_if を実行する 2 番目のステップを実行するには:
template <std::input_iterator Itr, std::input_iterator Itr2, class T>
auto inner_product_till(
Itr first1, Itr last1, Itr2 first2, const T upper_bound)
-> std::size_t
{
std::vector<T> products;
std::transform(first1, last1, first2, std::back_inserter(products),
std::multiplies<T>{});
std::partial_sum(products.begin(), products.end(),
products.begin());
const auto result = std::find_if(products.begin(), products.end(),
[&](T e) { return e > upper_bound; });
return std::distance(products.begin(), result);
}このバージョンは私の思考の流れに最も近いですが、余分なヒープメモリを割り当て、必要のない結果を熱心に計算するため、非常に非効率的でもあります.遅延範囲ビューはパフォーマンスの問題を解決します.範囲が数値アルゴリズムをサポートしている場合は、次のコードを書く可能性があります:
template <std::input_range Range, class T>
auto inner_product_till(Range r1, Range r2, const T upper_bound)
-> std::size_t
{
return std::ranges::distance(
std::view::transform(r1, r2, std::multiplies<T>{})
| std::view::partial_sum
| std::view::take_while([&](T e) { return e > upper_bound; }));
);
}
このバージョンは素晴らしいです。早期に割り当ても終了もしないので、理論的には、生のループ バージョンや変更可能なラムダ バージョンと同じくらい効率的です。残念ながら、<numeric> のアルゴリズムはどれも header は C++20 の範囲に含まれます。その結果、std::view::partial_sum になります。 ただし、range-v3 ライブラリにはこれらの機能がすべて含まれています。
独自のアルゴリズムを書くことを恐れないでください
この問題を解決するもう 1 つの方法は、独自のアルゴリズムを作成することです。たとえば、上記の例では、独自の view::partial_sum を作成できます。 アダプタを表示してください。
このコードの一部を再利用する必要がある場合は、後でいつでもアルゴリズムを拡張できるため、アルゴリズムは実際には非常に汎用的である必要はありません。アルゴリズムの開始点は、単に「ループを関数に抽出する」ことです。 id="fnref-2">2
また、興味深いのは、上記の inner_product_till は STL 互換のアルゴリズムです。そして、それを抽象化の最低レベルの 1 つとして扱うことができます。十分にテストされ、高速で、適切に動作する場合、内部でループや他のアルゴリズムを使用するかどうかを誰が気にしますか? std::inner_product ほど一般的ではありません ,しかし、必要に応じて、いつでも初期値とプラス/乗算バイナリ演算をパラメータとして追加できます.
std::generate での可変ラムダの使用について ?
std::generate の使い方が多い 変更可能なラムダを「ジェネレータ」関数として使用します。たとえば、次のコードは、再帰関係
この再帰関係は、単純に近い形式
int seq[20];
std::generate(std::begin(seq), std::end(seq),
[x = 0]() mutable {
return std::exchange(x, x * 2 + 1);
});
std::generate のこの種の「ジェネレーター」使用法 変更可能なラムダは一般的であり、前の例とは異なり、問題ないと思います。
ループを使用する場合と比較して、このバージョンには利点があります。同等のループ バージョンと比較して、可変変数 x のスコープ はラムダのスコープ内にあるように制約されています。また、変数 (特に変更可能) のスコープをできるだけ小さくするように努める必要があります。それでも、ループを明示的な中括弧のペアで囲んで同様の効果を得ることができます:
int seq[20];
{
int x = 1;
for (auto& elem: seq) {
elem = std::exchange(x, x * 2 + 1);
}
}変更可能なラムダを STL アルゴリズムに渡す代替手段を検討してください
すべてを要約すると、変更可能なラムダを std::generate 以外の STL アルゴリズムに渡すと思います または std::generate_n 避けるべきアンチパターンです。いくつかの選択肢があります。場合によっては、より優れたアルゴリズムに切り替えることができます。単純なループを使用する方が良い場合もあります。また、タスクを達成するためにカスタマイズされたアルゴリズムを作成できる場合もあります。