CODEWITHSUNDEEP
performanceswitch-statement
user2875404
user2875404

Reputation: 3218

What's the most efficient way of combining switch/if statements

This question doesn't address any programming language in particular but of course I'm happy to hear some examples.

Imagine a big number of files, let's say 5000, that have all kinds of letters and numbers in it. Then, there is a method that receives a user input that acts as an alias in order to display that file. Without having the files sorted in a folder, the method(s) need to return the file name that is associated to the alias the user provided.

So let's say user input "gd322" stands for the file named "k4e23", the method would look like

  if(input.equals("gd322")){
            return "k4e23";
                           }

Now, imagine having 4 values in that method:

switch(input){ 
case gd322: return fw332;
case g344d: return 5g4gh;
case s3red: return 536fg;
case h563d: return h425d;
  } //switch on string, no break, no string indicators, ..., pls ignore the syntax, it's just pseudo

Keeping in mind we have 5000 entries, there are probably more than just 2 entries starting with g. Now, if the user input starts with 's', instead of wasting CPU cycles checking all the a's, b's, c's, ..., we could also make another switch for this, which then directs to the 'next' methods like this:

 switch(input[0]){ //implying we could access strings like that 
    case a: switchA(input);
    case b: switchB(input);
// [...]
    case g: switchG(input);
    case s: switchS(input);
      }

So the CPU doesn't have to check on all of them, but rather calls a method like this:

switchG(String input){

 switch(input){
   case gd322: return fw332;
   case g344d: return 5g4gh;
  // [...]

  }

Is there any field of computer science dealing with this? I don't know how to call it and therefore don't know how to search for it but I think my thoughts make sense on a large scale. Pls move the thread if it doesn't belong here but I really wanna see your thoughts on this.

EDIT: don't quote me on that "5000", I am not in the situation described above and I wanted to talk about this completely theoretical, it could also be 3 entries or 300'000, maybe even less or more

Upvotes: 1

Views: 44

Answers (4)

Michel Billaud
Michel Billaud

Reputation: 1826

Yes the problem is known and solved since decades. Hash functions.

Basically you have a set of values (here strings like "gd322", "g344d") and you want to know if some other value v is among them.

The idea is to put the strings in a big array, at an index calculated from their values by some function. Given a value v, you'll compute an index the same way, and check whether the value v is here or not. Much faster than checking the whole array.

Of course there is a problem with different values falling at the same place : collisions. Some magic is needed then : perfect hash functions whose coefficients are tweaked so values from the initial set don't cause any collisions.

Upvotes: 1

Bergi
Bergi

Reputation: 664247

Is there any field of computer science dealing with this?

Yes, the science of efficient data structures. Well, isn't that what CS is all about? :-)

The algorithm you described resembles a trie. It wouldn't be statically encoded in the source code with switch statements, but would use dynamic lookups in a structure loaded from somewhere and stuff, but the idea is the same.

Upvotes: 1

GolezTrol
GolezTrol

Reputation: 116100

Interesting, but I don't think you can give a generic answer. It all depends on how the code is executed. Many compilers will have all kinds of optimizations, in the if and switch, but also in the way strings are compared.

That said, if you have actual (disk) files with those lists, then reading the file will probably take much longer than processing it, since disk I/O is very slow compared to memory access and CPU processing.

And if you have a list like that, you may want to build a hash table, or simply a sorted list/array in which you can perform a binary search. Sorting it also takes time, but if you have to do many lookups in the same list, it may be well worth the time.

Upvotes: 1

davidjh78
davidjh78

Reputation: 71

If you have 5000 options, you're probably better off hashing them than having hard-coded if / switch statements. In c++ you could also use std::map to pair a function pointer or other option handling information with each possible option.

Upvotes: 1

Related Questions