CppCon 2019: Conor Hoekstra, “Algorithm Intuition (part 2 of 2)”

preview_player
Показать описание



Data structure intuition is something that develops naturally for most software developers. In all languages, we rely heavily on standard containers and collections. Need fast insertion/lookup? Hashmap. Need a sorted data structure that stores unique values? Set. Duplicate values? Multiset. And so on.

However, most software developers don't develop algorithm intuition quite as easily. Algorithms aren't taught as widely as data structures are, and aren't relied on as heavily. This talk aims to introduce some STL algorithms, show how they are commonly used, and show how by developing intuition about them (+ a little help from lambdas), you can unlock their true potential.

Conor Hoekstra
Amazon
Software Development Engineer
San Francisco Bay Area

Conor is extremely passionate about programming languages, algorithms and beautiful code. He spent 5 years in Canada working on a large-scale C++ codebase. In 2018, he moved down to Silicon Valley and has spent the last year working for Amazon using C++, Java, Python, Go, Perl and more. He is in the midst of falling in love with Haskell and functional programming. He also has a YouTube channel where he covers solutions to competitive programming problems and more.


*-----*
*-----*
Рекомендации по теме
Комментарии
Автор

That's actually pretty nice to see that someone researching at Nvidia can make such mistakes. Because Hoekstra's talks inspired me to try and write that specific idea: Sum((x-mean)^2 / (n-1)) in algorithms and I couldn't figure it out without a couple of phases.

In haskell I got it with
. sqrt
. (/x -> x / fromIntegral (length array - 1))
. sum
. map (^2)
. map (subtract mean)
where
mean = sum / fromIntegral (length array)

But I wonder how to write it in C++ the same way. I suppose the two maps can be written in one lambda in C++, do fold, but then I suppose the division is another lambda though and things start getting ugly, especially considering the mean has to be calculated as well.

Yupppi
Автор

I think that the naming and default operations for inner_product, accumulate and partial_sum can be justified since they belong to <numeric>. I don't see why reduce, transform (or many others) should belong in <numeric> and not <algorithm>.

edgarmendez
Автор

long long int solveF(std::vector<long long int>& v){
long long int backDrop = std::reduce(v.cbegin(), v.cend());
partial_sum(cbegin(v), cend(v), begin(v), [](auto a, auto b){return std::max(a, b);});
return std::reduce(cbegin(v), cend(v)) - backDrop;
}
looks more appropriate whenever your accumulates don't sum over the largest int.

And, while writing this, I realize that we don't need to modify inplace the input vector. This code flows out automatically:
long long int solves(const std::vector<long long int>& v){
long long int waterLevel = 0;
std::reduce(v.cbegin(), v.cend(), 0ll,
[&waterLevel](auto a, auto b){auto c = std::max(a, b);
waterLevel += c; return c;});
return waterLevel - std::reduce(cbegin(v), cend(v));
}
is the capture an antipattern? Does it come from the lack of possibility to pipe the two reduces (max and plus) in C++17?
Thx for answers to the last two questions.

davidefichera