Search optimization for if statements in C#

[kolleamm]

I have a program that searches out string types.. Here is what I have so far -

C# language.

if(word.Contains "Hello")
{...}
else
if(word.Contains "Bye")
{...}
else
if(word.Contains "Yes")
{...}
...
I plan to add more and more of those if statements as my program advances. Would organizing these if statements in categories be worth it performance wise if I were to have thousands of them?

Here the program checks the first letter first in order to access different groups of ifs.

if(word[0] = 'a')
{
all if starting with 'a'
}
else
if(word[0] = 'b')
{
all if starting with 'b'
}
else
...

Thanks in advance

 

[rbelli1]

Can the word variable be made to contain just the single word only? If so you could populate a hash map with the target words associated with the function. That would make the search relatively fast for an arbitrarily large set of words.

BoB

 

[kolleamm]

The software is designed to describe catagories of statements from text, and a statement can have more than 1 category, therefore an equal sign won't work.

Here's an example - I say "yes"

response properties = ,yes,to_accept,

if response_property.Contains( yes)
{
do something
}
else

if response_property.Contains( to_accept)
{
do something else
}

 

[Svein]

Here the program checks the first letter first in order to access different groups of ifs.

if(word[0] = 'a')
{
all if starting with 'a'
}
else
if(word[0] = 'b')
{
all if starting with 'b'
}
else
...

Or more concisely:

switch (word[0]) {
case 'a':...
  break;
case 'b':...
  break;
...
else
...
}

 

[kolleamm]

Not bad I should really use switch

 

[jim mcnamara]

Look up branch prediction:
https://en.wikipedia.org/wiki/Branch_predictor
https://en.wikipedia.org/wiki/Branch_target_predictor

You should read the articles in the order listed- the second one directly deals with your question. Both arise from the same problem: fetching code to execute in advance so things run quickly.

 

[newjerseyrunner]

Here is what I would do in this situation. I would use callbacks and a map (maybe called a dictionary in C#?)

This is pseudocode, but you'll see what I mean:

static Dictionary map;
if (map.isEmpty()){
   map["hello"] = helloCallback;
   map["bye"] = byeCallback;
   map["yes"] = yesCallback;
}
DictionaryIterator i = map.find(word);
if (i.isValid()){
   callbackType call = i.value();
   call(data);
}



function helloCallback(data){
   //Behavior goes here
}

The dictionary is probably using a red/black tree, which is O(log n) in most cases.

 

[kolleamm]

Here is what I would do in this situation. I would use callbacks and a map (maybe called a dictionary in C#?)

This is pseudocode, but you'll see what I mean:

static Dictionary map;
if (map.isEmpty()){
   map["hello"] = helloCallback;
   map["bye"] = byeCallback;
   map["yes"] = yesCallback;
}
DictionaryIterator i = map.find(word);
if (i.isValid()){
   callbackType call = i.value();
   call(data);
}



function helloCallback(data){
   //Behavior goes here
}

The dictionary is probably using a red/black tree, which is O(log n) in most cases.

Interesting, so if I understand correctly a map is basically an array with string indexes?

So instead of --- array[ int ] = value,
its -- array[ string ] = value

 

[newjerseyrunner]

Yes, you can think of it like that. Some higher level languages actually use them interchangeably (php/javascript.)

Looks like in C# you have Dictionary and SortedDictionary at your disposal, I would research them.

 

[kolleamm]

I will definitely look into them. Would you say this would help out performance wise? Or would it just help simplify the code?

 

[newjerseyrunner]

Both. If you do things as a long list of if statements, that's a O(n) algorithm, but the maps use trees internally, so finding the correct function for your string would actually be easier.

 

[kolleamm]

Both. If you do things as a long list of if statements, that's a O(n) algorithm, but the maps use trees internally, so finding the correct function for your string would actually be easier.

Thanks for the help I will definitely implement it into my program.

 

[Pepper Mint]

You can also apply polymorphism for your Response class like so, which I think will help increase your program clarity or readability.

 interface IBase
    {
        void React();
    }
    class Derived_No : IBase
    {
        public void React()
        {
            Console.WriteLine("Reaction against No");
        }
    }
    class Derived_Yes : IBase
    {
        public void React()
        {
            Console.WriteLine("Reaction against Yes");
        }
    }

    class Program
    {
        private static Dictionary<string, IBase> dic;
        static void Main(string[] args)
        {
            dic = new Dictionary<string, IBase>();
            IBase child1 = new Derived_No();
            dic.Add("No", child1);
            IBase child2 = new Derived_Yes();
            dic.Add("Yes", child2);
            while (true)
            {
                string val = Console.ReadLine();
                dic[val].React();
            }
        }
    }

 

[D H]

The dictionary is probably using a red/black tree, which is O(log n) in most cases.

Probably not. C# has a SortedDictionary and a Dictionary. These have in common the concept of a container that maps keys to values. The implementations tend to be very different. A SortedDictionary uses a binary search tree, which a Dictionary typically uses a hash table.

As an aside, C++ missed the mark originally by specifying the much less useful binary search tree in std::map and failing to specify the much more useful hash table. (This was rectified in C++11, which provides std::unordered_map.) Python, perl, javascript, and PHP only provide hash tables, natively.

Typical lookup and insertion times in a hash table are O(1), so very good. The worst case performance is O(n), but this only happens when the hash function is notoriously bad. Binary search trees are typically much slower than hash tables.

Note that using a hash table was suggested in post #2 by @rbelli1.

 

[Jaeusm]

Kolleamm, it appears that you've never studied data structures and algorithms. It's really worth your while to do so if you're going to do programming of any kind. Actually, I think it's extremely important for any programmer to learn the material. There are several good books on the subject, but my favorite is "Algorithms" by Robert Sedgewick. It has a nice balance of practical implementation issues and theory. The only prerequisite is knowledge of object oriented programming.

 

[kolleamm]

Thanks for the suggestions everyone. I will definitely look into reading that book. I do know how to program in fact I've written many successful programs, however in terms of organization and efficiency they could be improved. My programs generally revolve around if,for,while statements and not other structures such as switch, but I would love to learn them.

 

[rbelli1]

Data structures and algorithms is one of the least captivating classes I encountered in college. It is also one of the most useful. Almost everything more complicated then a for loop is built up the eponymous structures.

BoB

 

[newjerseyrunner]

Data structures and algorithms is one of the least captivating classes I encountered in college. It is also one of the most useful.

Quoted for truthfulness. It was the most boring and grueling courses I took, but it was probably one of the only classes that taught me something that I didn't already know.

 

[rbelli1]

And knowledge that will be pretty much necessary in any programming field.

BoB

 

[D H]

Quoted for truthfulness. It was the most boring and grueling courses I took, but it was probably one of the only classes that taught me something that I didn't already know.

Many undergraduate majors have weed out classes. This is one of the CS weed out classes. I liked those weed out classes. I took organic chemistry, abstract algebra, data structures & algorithms, classical electromagnetism, and aircraft flight dynamics and made a B or an A in each.

My boring and grueling classes were the ones that did not challenge me in the least and where it was obvious from day one that I wouldn't be learning a thing in that class. I received Fs in a couple of underwater basket weaving classes. All you had to do was show up to the lectures and discussion sections and you pretty much had a guaranteed B. (Details: 2 Fs and 3As in one semester! My advisor was flabbergasted when he saw that the two Fs were in classes that were guaranteed Bs and the three As were in weed out classes. I was asked to take a semester off for that.)