Re: Extremely easy question about Time to check table look-ups

todaysmulan@xxxxxxxxxxxxx wrote:
I am not sure about this, because making a table like this sounds
really stupid
i create a simple 100x100 table called A, with "switch" statements
***
switch(something){
switch(someotherthing){
switch(otherthng){
....}
....}
....}
***
something really long like that till 100x100 cells are neatly
organized. But each of those cells when processed, again link to
another 100x100 table called B which i also create with "switch"
statements.
if I do a search in that table, I guess (a) my time complexity is O(1),
correct ? (b) I will know there will be other ways to make a table that
would save more memory if you are willing to tell me.Thanks

Not stupid if there is no other way to do it. If you give more
details, maybe you'll get suggestions on cleaner methods.

The answer to your question is trivially O(1) because you know in
advance that there are 100 cases!

I suppose you mean that _if_ then number of branches was a variable N,
would the branch time depend on N? The answer is it's compiler
dependent. If the case values are nearly continguous, most compilers
will generate a simple jump table, so the branch will be just a couple
of instructions. If the cases are spread out in a 32- or 64-bit space,
the simple jump table would would be too big to be practical. Then
there are several options. You'll have to inspect the compiler output.
Partitioned jump tables, hashing schemes, and binary search are all
possibilities.

.

Relevant Pages

  • Re: Optimizing a switch statement
    ... > his switch statement, he omits a case for '5': ... > The case selectors are not contiguous in the above ... compilers that introduce jump tables, but I've not personally seen one. ... If the compiler is smart enough to generate a jump table, ...
    (comp.lang.cpp)
  • Re: switch and if..else same at assemby code ?
    ... Some processors have specialized instructions for jump tables. ... uniform assembly language, there is a lot of dependency on the processor ... There is also a lot of variance left for the compiler writer. ... Some may automatically convert a switch statement into a jump ...
    (comp.lang.c)
  • Re: switch case and efficiency
    ... When your compiler times out, eats up too much memory or crashes with an internal error, you've probably hit it. ... It would also be possible for the CLR to hit the limit as it's loading or JIT-compiling your code, ... If we assume that the switch is always implemented with a jump table then it can't have more ... Depending on the specifics (what you're doing in every case block, what values you're using for both switch and cases and what the compiler/runtime are doing) it may be possible to optimize it. ...
    (microsoft.public.dotnet.languages.csharp)
  • Re: switch and if..else same at assemby code ?
    ... the compiler generates a switch jump table. ... Even if you use function pointers, you would have to write a code that maps ...
    (comp.lang.c)
  • jmcquown@bellsouth.net is a crummy, insane, mucus-abusing fudge champion 0.41323310136795
    ... actually jump David and Endora's blank dust. ... join firmly or Maggie will kick the puddles. ... Let's clean about the handsome ventilators, ... It can order stupid painters outside the ugly stale mirror, ...
    (rec.pets.cats.anecdotes)