可以将文章内容翻译成中文,广告屏蔽插件可能会导致该功能失效(如失效,请关闭广告屏蔽插件后再试):
问题:
Let say I have a switch statement as below
switch(alphabet) {
case "f":
//do something
break;
case "c":
//do something
break;
case "a":
//do something
break;
case "e":
//do something
break;
}
Now suppose I know that the frequency of having Alphabet
e is highest followed by a, c and f respectively. So, I just restructured the case
statement order and made them as follows:
switch(alphabet) {
case "e":
//do something
break;
case "a":
//do something
break;
case "c":
//do something
break;
case "f":
//do something
break;
}
Will the second switch
statement be faster than the first switch
statement? If yes and if in my program I need to call this switch
statement say many times, will that be a substantial improvement? Or if not in any how can I use my frequency knowledge to improve the performance?
回答1:
Not so much that you should be concerned. It's certainly not something that can be predicted.
With string case labels, the compiler actually uses an internal hash table that maps the strings to indexes in a jump-table. So the operation is actually O(1) - independent of the number of labels.
For integer labels, then I believe the actual code that is generated depends on the number of labels and whether the numbers are consecutive (or "almost" consecutive). If they're consecutive (1, 2, 3, 4, ...) then they'll just be transformed into a jump table. If there's a lot of them, then the Hashtable+jump table (like with strings) will be used. If there's only a few labels and they're not table to be immediately transformed into a jump table, only then will be transformed into a series of if..then..else statements.
In general, though, you should write code so that you can read it, not so that the compiler can produce "faster" code.
(Note my description above is an implementation detail of how the C# compiler works internally: you shouldn't rely on it always working like that -- in fact, it might not even work exactly like that now, but at least it's the general idea).
回答2:
It depends on how the compiler implements the switch statement.
First, you can't arbitrarily permute the order; if you have one case block
in a C-like language (C, C++, C#, Java, ...), and that case block does not
terminate in break, you can't rearrange the cases because the absence of
the break means the compiler must implement fall-through to the next case.
If we ignore this special situation, you can permute the rest of the cases.
If the number of cases is small, the compiler may implement the case tests
by a sequences of compares. If the number of cases is modest, it may construct
a balanced binary tree from the cases. If the number of cases is large, most
compilers implement an indexed branch on the switch value if it is from
a dense set. If parts of the set of case values is dense, and parts are
not, the compiler may partition the cases into groups using a binary tree
to select which dense set, and an indexed jump within the dense set.
(In fact, the compiler may technically do anything that passes control to the
appropriate case, but most often it is one of the above).
You can see that order may matter, or it may not, depending on how the compiler
implements the switch. For most good compilers, it does not matter much.
回答3:
They have the same performance for a relatively small set of values. I tried checking the assembly code of C program before, the compiler creates a jump table out of all the values you have in your switch statement.
But if the case values are too many, it's a safe bet that they will degenerate to if
else if
, so putting your case 'E' on top would surely speed things up.
It's also applicable in C#, C# also produces a jump table for switch statements with a small set, albeit for adjacent values only. So it's O(1), there's no multiple testing even if the first values doesn't match.
回答4:
I think the way switch case do is it will loop over all the cases from top to bottom to find some match. If it matches, it stops there.
So, if you made changes to prioritize the frequency cases, the answer is yes, it can help somehow with performance. But I believe that it will not help much.