Re: Perl Idioms Explained: && and || "Short Circuit" operators

[hardburn]

Now you know why Perl doesn't have a switch statement . . .

It should still get one, since the advantage of C switches it that they have O(1) efficency, whereas most of the equivilent idioms in Perl have O(n) worst-case time. <UPDATE>Actually, the one posted above always runs in O(n) time.</UPDATE> <UPDATE2>Oops, that update wasn't quite true. Thanks demerphq.</UPDATE2> You can get O(1) time using a hash table that stores subroutine refs, but then you make implementing fall-through a lot harder.

Fortunatly, we're getting a real switch in Perl6.

[demerphq]

Im very confused about this node. How does C's switch statement offer O(1) time? Im wracking my brain to see how this could be done without becoming hopelessly inefficient. Also your update is confusing too, the switch like code posted drops out of the loop once a condition has been met. I suppose strictly speaking a series of conditionals can be described as O(N), but this deosnt seem to match up with the spirit of your usage.

[BrowserUk]

Now you've confused me:)

Doesn't O(1) (in this case) mean that a condition is only tested once with the C-switch statement. Whereas the implementation shown in the OP, all tests from 0 to N where N is the met condition's lexical position within the group, hence worst case O(N) if the last case is the one chosen?

It was this bit of your post that confused me

...Im wracking my brain to see how this could be done without becoming hopelessly inefficient....

---

Examine what is said, not who speaks.
"Efficiency is intelligent laziness." -David Dunham
"Think for yourself!" - Abigail
Hooray!

[demerphq]

Well, what I mean is that I dont see how in C the conditional is only evaluated once. I dont know enough about how C implements a case statement to say for sure But i dont see how a case statement could be implemented in such a way without adding a lot of code to the statement, which would potentially be far more expensive than converting it to a series of conditionals. For instance something like this

switch (val) {
  case 1 : handle_case1; break;
  case 2 : handle_case2; break;
  case 5 : handle_case5;
  case 10: handle_case10;
  default: handle_default; 
}

I would guess would get converted to something like

if (val == 1) {
  handle_case1;
} elsif (val == 2) {
  handle_case2;
} else {
  if (val == 5) {
    goto CASE5;
  } elsif (val == 10) {
    goto CASE10;
  } else {
    goto DEFAULT;
  }
CASE5:   handle_case5;
CASE10:  handle_case10;
DEFAULT: handle_default;
}

Or something like it. I just dont see how it could be handled otherwise. Perhaps the fact that it only operates on ints means that there is a neater optimisation. But if you extend switch to handle strings as it does in pascal then I think the situation becomes even more difficult.

Thanks to the CB for clarifying that switch only handles ints. That issue may make my ruminations on this invalid. I dont know. Id be interested to hear from someone that does. As I said, this issue confuses me. :-)

[fletcher_the_dog]

C switch statements create an internal jump table that is more or less like a hash so that they can skip testing cases that are are going to fail, this makes them O(1). For example in the following switch statement if 'test' equals 'c' the code jumps right to case 'c', it doesn't test to see if 'test' equals 'a' or 'b':

switch(test){
  case 'a':
   # do something
  case 'b':
   # do something else
  case 'c':
   # do something else
}

This of course means that the possible cases (but not the test value) are static and must be known at compile time which decreases flexibilty but increases speed.

[demerphq]

Im still confused how this works. :-) How does it map discontiguous values into a jump table without doing a lot of work?

[pg]

It is correct to say C's switch is O(1).

Theoritically speaking, BrowserUK is also wrong when he said O(1) means test once. However he had something in () said "in this case", which made himself "politically" right ;-)

Strictly speaking, O(1) means that the cost is a constant, not a function of any variable, thus it is considered ideal, as the cost is 100% predictable. The complexity (worst scenario cost) of the switch statement is determined at the coding time, not base on the input data at execution time.

C's switch statement falls into this category. I personally believe that there is a benefit to have it in Perl.

[kelan]

Indeed if having an execution of O(1) is switch's primary benefit, that will not be present in Perl6's switch, except perhaps in primitive uses. C's switches must have constant case labels to facilitate the chicanery it uses for producing O(1) behavior. Perl6 will not enforce constants as the "labels". From what I understand, you'll be able to use any Perl expression you wish as a label. Therefore, each one will need to be evaluated, at runtime, to find the correct one. I think in this case, the benefit to the switch statement for Perl would be its conciseness over using chained if/elses.