But as already explained, from the point of view of complexity, this is fine as long as its usage is bound by a constant. But for small sequences they usually switch to Insertion Sort which is provably faster in very small ranges, even though it is an algorithm with O(n^2) complexity by itself. Basically, most library implementations that I've heard of use Quicksort (with some tricks, so it is O(n log(n)) even in the worst case). Another famous example is the implementation of std::sort. 10 days does matter.īTW this way of "cheating" is very common. Usually, nobody cares if something is done in 5ms or 10ms. It can easily become very difficult otherwise Allowing certain simplifications in the analysis of algorithms.This may look like cheating, and to a certain degree I can understand this reasoning, but it is important to understand that this is the very reason why complexity was introduced this way in the first place: Hence, complexity wise, it is classified as a constant algorithm, independent on n, or O(1) all three statements are equivalent. This function will always do 50 iterations or less, no matter how huge v.size() might be. "constant" or O(1)) while the actual runtime of course does depend on n: int get_max_of_first_50(std::vector const& v) Update:īased on your comments, let me give you an examples of a function that is, complexity wise, independent on n (aka. Even if that means that the actual running time does depend on the number of types, the time complexity does not. See e.g here.Īnd lastly, given what I said earlier, it is of course allowed to apply any sorts of optimizations, as long as this doesn't move the algorithm into a worse complexity class. Note however, that for a difficult distribution of cases a switch will be compiled as a binary search which is O(log n). So, an implementation using switch should be legal. This is especially likely if the cases are a subsequent number of integers, as it is the case here. So, unless the implementer knows for a fact that the compiler will optimize it into something constant, this is illegal.Ī switch will very likely be compiled to a jump table, which works in O(1). O(n)) complexity, as you correctly state. So, to actually answer your question: Using an if- else if chain exclusively will usually have linear (i.e. In particular, it is of course allowed to stay below this number C. In the case of visit this means that there is some constant C such that visit never takes more than C cpu-cycles, even for an insane number of types in the variant. So, the claim in the reddit comment is indeed correct. This being said, it's important to realize what statements like "constant time" and "does not depend on" mean when talking about complexity: In this context, both of them are just synonyms for O(1). You are confusing time complexity and running time. At least if following the standard to the letter. is legal but the optimizer (may) transforms it into 1. IMO "Constant time" means the time is constant no matter the input which for an if-elseif-chain is not the case.īut I'm not sure how this applies here. I'm asking based on a discussion on reddit where someone claimed "Constant time" again refers to the behavior in the limit. But IMO this violates the "independent of number of types" complexity mandated by the standard although it would in practice be faster. If the switch is legal, is it legal for the optimizer to convert small switches to if-elseif ladders? Again the MSVC compiler does this.Microsoft implemented it for less than 64 (or so) types. Is it legal to implement it with a switch like switch(v.index()) case I: return visitor(get(v)) ? This looks like "independent of the number of types" as control flow jumps directly to the case and it is how e.g.Would it be legal to implement std::visit as a chain of if-elseif where each check is like if(v.index() = I) return visitor(get(v)) ? It seems like it does not because dispatching to higher indices would take more checks for the index.One of the reasons is the exception state, the other was said to be the requirement of the standard that std::visit complexity does not depend on the number of types which forces implementers to use a dispatch table of function pointers which inhibits certain optimizations like inlining. It is often quoted that C++s std::variant has worse performance than variants in other languages.
0 Comments
Leave a Reply. |