# | User | Rating |
---|---|---|
1 | tourist | 3985 |
2 | jiangly | 3741 |
3 | jqdai0815 | 3682 |
4 | Benq | 3529 |
5 | orzdevinwang | 3526 |
6 | ksun48 | 3489 |
7 | Radewoosh | 3483 |
8 | Kevin114514 | 3442 |
9 | ecnerwala | 3392 |
9 | Um_nik | 3392 |
# | User | Contrib. |
---|---|---|
1 | cry | 166 |
2 | atcoder_official | 163 |
3 | Um_nik | 162 |
3 | maomao90 | 162 |
5 | adamant | 157 |
5 | -is-this-fft- | 157 |
5 | djm03178 | 157 |
8 | awoo | 155 |
9 | TheScrasse | 154 |
10 | Dominater069 | 153 |
Name |
---|
Great blog! Thank you so much. I wish I could upvote twice.
Glad that you liked the blog. I'm planning to write some more C++ blogs too.
I use it in non-recursive get in dsu
while(i != p[i]) i = exchange(p[i], v);
Just curious, do you really need
sz
to be mutable? Seems like it is not necessaryYes, but i don't want to break one line of code
Nice example!
Just want to put the function signature of
std::exchange
here. I think I understand better after I know its signature.Yeah, in retrospect it seems that I should have put it in the blog for people who know about templates.
I think,
copy_c_string
should be implemented aswhile (*output++ = *input++);
in order to terminate the copied string with '\0' in the output.Yeah, my bad, somewhere I had switched from copying arrays to C strings. The example holds for both, and this one liner shows the true power of null-terminated strings (not that I would use null-terminated strings anywhere given that std::string exists). Updated the blog, since now the algorithm can be used to concatenate multiple strings.
We can also use
std::tie(a, b) = std::make_pair(b, a + b)
Similar to python, very readable.The only problem with this piece of code is too many copies, std::exchange is faster on larger structs. Definitely more readable though, to the extent that I had used this as an explanation for the functionality of std::exchange.
Oh! I see
From this blog post, I learned that extended gcd can be implemented non-recursively (or at least with no backtracking).
I found it a bit surprising that most people implement extended GCD recursively, given that recursion is not very obvious (at least to me), and each step of extended GCD is just manipulating coefficients so that the equation is true before and after the operations that replace arguments with their new values.
I think it's just because it was done recursively on emaxx, and from then on we do it exactly that way.
An important thing to keep in mind is that most things in your code aren't bottlenecking the performance, and this gets more true the more complex your code gets, so how exactly you write them (as opposed to what logic you implement) is almost irrelevant. You shouldn't overoptimise or worry about maximum performance ahead of time. Just write something that's not slow (good algorithm and follow basic patterns like processing inner array in inner loop), check if it's good enough and move on. Your writing time is more valuable than the resulting program's time.
It's useful to know these things just in case you find out that your code isn't good enough and you need hardcore optimisations, or if you're writing a performance-critical library that's going to be reused.
I'm not sure where performance comes into discussion here. That is unless it is an argument for using i++ instead of ++i, targeted towards people who use ++i because of performance claims, which have been debunked in the blog too, except for the cases where the operators are defined for a class and can have potentially different behaviour.
Also, I believe that when writing code, readability becomes quite important as the code becomes more and more complex. So expressing intent through code properly can prevent you from having bugs in the first place as well as help you catch bugs.
If you're referring to the topic of the blog and didn't bother reading the content, it was more about getting rid of temporaries because they make code uglier, rather than performance considerations, since the compiler will generate the same code most of the time.
Yeah, I was referring to those performance claims you addressed at the start — even if they were true, it almost doesn't matter.
Regarding readability of code, it's not all that much about exact implementation, since the definition
void copy_c_string(const char* input, char* output)
offers much more info about what that code is supposed to do than the function body itself. When the code is structured like this, implementation of individual building blocks will need to be read less, and the most readable code is one where you don't need to look into extra details at all.Ah, that makes more sense.
Regarding whether it is important to implement it properly — well, if it is write-once read-never code, then it makes sense to only have good names (and short functions like this) and not care about quality of implementation so much as long as it just works. Maybe this was not a very good example given how short it was, but in both longer functions (complicated functionality) as well as code that needs to be maintained (for example, during refactoring), having a harder-to-modify-incorrectly implementation is more preferable in general — in fact this is why functional code is seen as cleaner.
This might only be partially true for competitive programming, where we optimize for writing once and not for maintaining, but is something that should be kept in mind in general.
Some other examples taken from code I wrote in the past