Справочник функций

Ваш аккаунт

Войти через: 
Забыли пароль?
Регистрация
Информацию о новых материалах можно получать и без регистрации:
RSS
ВКонтакте

Почтовая рассылка

Подписчиков: -1
Последний выпуск: 19.06.2015

switch vs hashtable

Microsoft .NET Framework
273
26 марта 2007 года
3A3-968M
1.2K / / 22.12.2005
Есть такой код:
Свернуть исходник 
Код:
[SIZE=2][COLOR=#0000ff][FONT=Courier New]public [/FONT][/COLOR][/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]void [/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New]NextToken()[/FONT]
[FONT=Courier New]{[/FONT]
[/SIZE][SIZE=2][COLOR=#008000][FONT=Courier New]//...[/FONT]
[/COLOR][/SIZE][SIZE=2][/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]  char[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New] c = CurrentChar;[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]  switch[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New] (c)[/FONT]
[FONT=Courier New]  {[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]    case[/COLOR][/SIZE][SIZE=2] [/SIZE][SIZE=2][COLOR=#800000]'a'[/COLOR][/SIZE][SIZE=2]: AHandler(); [/SIZE][SIZE=2][COLOR=#0000ff]return[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New];[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]    case[/COLOR][/SIZE][SIZE=2] [/SIZE][SIZE=2][COLOR=#800000]'%'[/COLOR][/SIZE][SIZE=2]: PrecentHandler(); [/SIZE][SIZE=2][COLOR=#0000ff]return[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New];[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]    case[/COLOR][/SIZE][SIZE=2] [/SIZE][SIZE=2][COLOR=#800000]'#'[/COLOR][/SIZE][SIZE=2]: SharpHandler(); [/SIZE][SIZE=2][COLOR=#0000ff]return[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New];[/FONT]
[/SIZE][SIZE=2][COLOR=#008000][FONT=Courier New]    //...[/FONT]
[/COLOR][/SIZE][SIZE=2][FONT=Courier New]  }[/FONT]
[FONT=Courier New]}[/FONT]
[/SIZE]

И таких case-выражений достаточно много - около 20. Метод NextToken срабатывает при обработке каждого символа в строке. Но у меня есть другой вариант реализации через хэш-таблицу:
Свернуть исходник 
Код:
[SIZE=2][COLOR=#0000ff][FONT=Courier New]delegate [/FONT][/COLOR][/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]void [/COLOR][/SIZE][SIZE=2][COLOR=#008080]CharHandler[/COLOR][/SIZE][SIZE=2]([/SIZE][SIZE=2][COLOR=#0000ff]char[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New] c);[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]private [/COLOR][/SIZE][SIZE=2][COLOR=#008080]Dictionary[/COLOR][/SIZE][SIZE=2]<[/SIZE][SIZE=2][COLOR=#0000ff]char[/COLOR][/SIZE][SIZE=2], [/SIZE][SIZE=2][COLOR=#008080]CharHandler[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New]> charHandlers;[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]private [/COLOR][/SIZE][SIZE=2][COLOR=#0000ff]void [/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New]Initialize()[/FONT]
[FONT=Courier New]{[/FONT]
[FONT=Courier New]  charHandlers = [/FONT][/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]new [/COLOR][/SIZE][SIZE=2][COLOR=#008080]Dictionary[/COLOR][/SIZE][SIZE=2]<[/SIZE][SIZE=2][COLOR=#0000ff]char[/COLOR][/SIZE][SIZE=2], [/SIZE][SIZE=2][COLOR=#008080]CharHandler[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New]>();[/FONT]
[FONT=Courier New]  charHandlers.Add([/FONT][/SIZE][FONT=Courier New][SIZE=2][COLOR=#800000]'a'[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New], AHandler);[/FONT]
[FONT=Courier New]  charHandlers.Add([/FONT][/SIZE][FONT=Courier New][SIZE=2][COLOR=#800000]'%'[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New], PrecentHandler);[/FONT]
[FONT=Courier New]  charHandlers.Add([/FONT][/SIZE][FONT=Courier New][SIZE=2][COLOR=#800000]'#'[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New], SharpHandler);[/FONT]
[/SIZE][SIZE=2][COLOR=#008000][FONT=Courier New]  //..[/FONT]
[/COLOR][/SIZE][FONT=Courier New][SIZE=2]}
[/SIZE][/FONT]

Т.е. теперь на каждый символ в табицу заносим обрабочик. Теперь метода NextToken выглядит так:
 
Код:
[SIZE=2][COLOR=#0000ff][FONT=Courier New]public [/FONT][/COLOR][/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]void [/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New]NextToken()[/FONT]
[FONT=Courier New]{[/FONT]
[/SIZE][SIZE=2][COLOR=#008000][FONT=Courier New]  //...[/FONT]
[/COLOR][/SIZE][SIZE=2][/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]  char[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New] c = CurrentChar;[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]  if[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New] (charHandlers.ContainsKey(c))[/FONT]
[FONT=Courier New]    charHandlers[c](c);[/FONT]
[FONT=Courier New]}[/FONT]
[/SIZE]

Ну кто что думает по этому поводу? Какой из методов будет более производительным?
По порядку
Сначала полезные
Сначала решения

4 ответа

5
26 марта 2007 года
hardcase
4.5K / / 09.08.2005
Сам ответил что лучше пользовать хэш-таблицу, но написал тест, который показал, что switch оказался круче :D
(8 секунд против 14)

Всё это при количестве символов 90'000'000
Можно сделать вывод - пофиг какой вариант выбрать. В то время как хэш-таблицу проще сопровождать.

Вот код:
Свернуть исходник 
Код:
using System;
using System.Collections.Generic;
using System.Text;

namespace ConsoleApplication1 {
    class Program {

        static char[] chars = new char[] { 'a', 'b', 'c', '#', 'd', '$', '&', '%' , '*', '8', '?',
            '(', ')', '@', '^', '!', '~', 't', 'k', ':', '"', '=', '-', '+', '1', '2', '4' };

        static IEnumerable<char> SequenceOfChars(long count) {            
            Random rnd = new Random();
            int randMax = chars.Length;
            for (int i = 0; i < count; i++) {
                yield return chars[rnd.Next(randMax)];
            }
        }

        delegate void CharHandler(char c);

        static Dictionary<char, CharHandler> hash = new Dictionary<char, CharHandler>();

        static void DoChar(char c) {

        }

        delegate void MesureExecutionTimeCallback();
        static void MesureExecutionTime(string operationName, MesureExecutionTimeCallback callback) {
            Console.WriteLine("Operation '{0}' started....", operationName);
            DateTime startTime = DateTime.Now;
            callback();
            DateTime endTime = DateTime.Now;
            TimeSpan span = endTime - startTime;
            Console.WriteLine("Operation '{0}' completed in {1} seconds", operationName, span.TotalSeconds);
        }

        static void Main(string[] args) {
            // заполняем хэш
            foreach (char c in chars) {
                hash.Add(c, DoChar);
            }

            int charCount = 90000000;

            // проверяем switch блок
            MesureExecutionTime("Switch construction", delegate {
               foreach(char c in SequenceOfChars(charCount))
                   switch (c) {
                       case 'a': DoChar(c); break;
                       case 'b': DoChar(c); break;
                       case 'c': DoChar(c); break;
                       case '#': DoChar(c); break;
                       case 'd': DoChar(c); break;
                       case '$': DoChar(c); break;
                       case '&': DoChar(c); break;
                       case '%': DoChar(c); break;
                       case '*': DoChar(c); break;
                       case '8': DoChar(c); break;
                       case '?': DoChar(c); break;
                       case '(': DoChar(c); break;
                       case ')': DoChar(c); break;
                       case '@': DoChar(c); break;
                       case '^': DoChar(c); break;
                       case '!': DoChar(c); break;
                       case '~': DoChar(c); break;
                       case 't': DoChar(c); break;
                       case 'k': DoChar(c); break;
                       case ':': DoChar(c); break;
                       case '"': DoChar(c); break;
                       case '=': DoChar(c); break;
                       case '-': DoChar(c); break;
                       case '+': DoChar(c); break;
                       case '1': DoChar(c); break;
                       case '2': DoChar(c); break;
                       case '4': DoChar(c); break;
                   }
            });

            //проверяем hash-вариант
            MesureExecutionTime("Hash table", delegate {
                foreach (char c in SequenceOfChars(charCount))
                    hash[c](c);
            });

            Console.WriteLine("Test completed");
            Console.ReadLine();
        }
    }
}
273
26 марта 2007 года
3A3-968M
1.2K / / 22.12.2005
Странно. Ведь процедура инициализации хэш-таблицы проходит только один раз перед перебором всей строки, а switch работает каждый раз при встрече символа....
5
26 марта 2007 года
hardcase
4.5K / / 09.08.2005
Да ничего не странно. Компилятор не дурак - он для switch наверняка строит таблицу переходов, отсюда некоторый выигрышь в скорости - так по крайней мере dcc32 в отношении Делфей делает.
273
28 марта 2007 года
3A3-968M
1.2K / / 22.12.2005
Ну компилер Delphi генерит native-код, так что его в данном контексте рассматривать нельзя. Ну посмотрим, что же нам генерит компилер C#. Имеется код:
 
Код:
[SIZE=2][COLOR=#0000ff][FONT=Courier New]public [/FONT][/COLOR][/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]void [/COLOR][/SIZE][SIZE=2]NextToken([/SIZE][SIZE=2][COLOR=#0000ff]char[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New] c)[/FONT]
[FONT=Courier New]{[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]  switch[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New] (c)[/FONT]
[FONT=Courier New]  {[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]    case[/COLOR][/SIZE][SIZE=2] [/SIZE][SIZE=2][COLOR=#800000]'a'[/COLOR][/SIZE][SIZE=2]: [/SIZE][SIZE=2][COLOR=#008080]Console[/COLOR][/SIZE][SIZE=2].WriteLine([/SIZE][SIZE=2][COLOR=#800000]"Alpha char"[/COLOR][/SIZE][SIZE=2]); [/SIZE][SIZE=2][COLOR=#0000ff]return[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New];[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]    case[/COLOR][/SIZE][SIZE=2] [/SIZE][SIZE=2][COLOR=#800000]'#'[/COLOR][/SIZE][SIZE=2]: [/SIZE][SIZE=2][COLOR=#008080]Console[/COLOR][/SIZE][SIZE=2].WriteLine([/SIZE][SIZE=2][COLOR=#800000]"Sharp Char"[/COLOR][/SIZE][SIZE=2]); [/SIZE][SIZE=2][COLOR=#0000ff]return[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New];[/FONT]
[/SIZE][FONT=Courier New][SIZE=2][COLOR=#0000ff]    case[/COLOR][/SIZE][SIZE=2] [/SIZE][SIZE=2][COLOR=#800000]'?'[/COLOR][/SIZE][SIZE=2]: [/SIZE][SIZE=2][COLOR=#008080]Console[/COLOR][/SIZE][SIZE=2].WriteLine([/SIZE][SIZE=2][COLOR=#800000]"Quest handler"[/COLOR][/SIZE][SIZE=2]); [/SIZE][SIZE=2][COLOR=#0000ff]return[/COLOR][/SIZE][/FONT][SIZE=2][FONT=Courier New];[/FONT]
[FONT=Courier New]  }[/FONT]
[FONT=Courier New]}[/FONT]
[/SIZE]

На выходе компилятора получим:
Свернуть исходник 
Код:
[SIZE=3][FONT=Courier New][SIZE=2].method public hidebysig instance void NextToken(char c) cil managed[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]{[/SIZE][/FONT]
[FONT=Courier New][SIZE=2][COLOR=green]// Code size 60 (0x3c)[/COLOR][/SIZE][/FONT]
[FONT=Courier New][SIZE=2].maxstack [COLOR=blue]2[/COLOR][/SIZE][/FONT]
[FONT=Courier New][SIZE=2].locals init ([0] char CS$4$0000)[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0000: nop[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0001: ldarg.1[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0002: stloc.0[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0003: ldloc.0[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0004: ldc.i4.s 35[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0006: beq.s IL_0021[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0008: ldloc.0[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0009: ldc.i4.s [COLOR=blue]63[/COLOR][/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_000b: beq.s IL_002e[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_000d: ldloc.0[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_000e: ldc.i4.s [COLOR=blue]97[/COLOR][/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0010: beq.s IL_0014[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0012: br.s IL_003b[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0014: ldstr [COLOR=blue]"Alpha char"[/COLOR][/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0019: call void [mscorlib]System.Console::WriteLine(string)[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_001e: nop[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_001f: br.s IL_003b[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0021: ldstr [COLOR=blue]"Sharp Char"[/COLOR][/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0026: call void [mscorlib]System.Console::WriteLine(string)[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_002b: nop[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_002c: br.s IL_003b[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_002e: ldstr [COLOR=blue]"Quest handler"[/COLOR][/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0033: call void [mscorlib]System.Console::WriteLine(string)[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0038: nop[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_0039: br.s IL_003b[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]IL_003b: ret[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]}[/SIZE][/FONT]
[/SIZE]

Видим тупое последовательное сравнение. Это случилось, так как слишком мало в коде case-конструкций, было бы побольше, компилятор выдал бы нечто такое:
 
Код:
[SIZE=3][SIZE=3][/SIZE][SIZE=2][FONT=Courier New]IL_006b: [/FONT][FONT=Courier New]ldc.i4.s [COLOR=blue]9[/COLOR][/FONT][/SIZE]
[/SIZE][SIZE=3][FONT=Courier New][SIZE=2]IL_006c: switch ( [/SIZE][/FONT]
[FONT=Courier New][SIZE=2]  IL_017d,[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]  IL_01b0,[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]  IL_016c,[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]  IL_018e,[/SIZE][/FONT]
[FONT=Courier New][SIZE=2]  IL_019f)[/SIZE][/FONT]
...
[/SIZE]

Т.е. он строит switch-таблицу с метками на которые переведётся управление, если значение загруженное в стэк будет равно 9 ну и т.д...
Значит управление программой перейдёт на нужную метку всегда за одно сравнение.
Реклама на сайте | Обмен ссылками | Ссылки | Экспорт (RSS) | Контакты
Добавить статью | Добавить исходник | Добавить хостинг-провайдера | Добавить сайт в каталог