代码之家 › 专栏 › 技术社区 › Sergey Stadnik

你将如何使这个开关语句尽可能快?

switch-statement optimization c#

Sergey Stadnik · 技术社区 · 5 年前

2009-12-04更新 :有关此处发布的许多建议的分析结果,请参阅下面的内容!

问题

考虑以下非常无害、非常直接的方法,它使用 switch 返回已定义枚举值的语句:

public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
    if (ActivCode == null) return MarketDataExchange.NONE;

    switch (ActivCode) {
        case "": return MarketDataExchange.NBBO;
        case "A": return MarketDataExchange.AMEX;
        case "B": return MarketDataExchange.BSE;
        case "BT": return MarketDataExchange.BATS;
        case "C": return MarketDataExchange.NSE;
        case "MW": return MarketDataExchange.CHX;
        case "N": return MarketDataExchange.NYSE;
        case "PA": return MarketDataExchange.ARCA;
        case "Q": return MarketDataExchange.NASDAQ;
        case "QD": return MarketDataExchange.NASDAQ_ADF;
        case "W": return MarketDataExchange.CBOE;
        case "X": return MarketDataExchange.PHLX;
        case "Y": return MarketDataExchange.DIRECTEDGE;
    }

    return MarketDataExchange.NONE;
}

我的同事和我今天讨论了一些关于如何使这个方法更快速的想法,我们提出了一些有趣的修改,事实上,这些修改极大地提高了它的性能(当然,按比例来说)。我很想知道其他人能想到哪些我们可能没有想到的优化。

马上,让我做一个简短的免责声明:这是为了乐趣和不推动整个“优化还是不优化”的辩论。也就是说,如果你把自己算在那些信奉“过早优化是万恶之源”的人当中,请注意我在一家高频交易公司工作,在那里一切需要以尽可能快的速度运行——是否为瓶颈。所以,即使我把这个贴在上面乐趣这也不仅仅是浪费时间。

另一个简短的提示:我对两种答案感兴趣——假设每个输入都是有效的活动代码(在 转换 上面的陈述),而那些没有。我是几乎可以肯定的是,做出第一个假设可以进一步提高速度;不管怎样,这对我们来说的确是如此。但我知道无论哪种方法都有改进的可能。

结果

好吧,事实证明,迄今为止最快的解决方案(我已经测试过)来自Jo_o Angelo,他的建议实际上非常简单,但非常聪明。我和我的同事设计的解决方案(在尝试了几种方法之后,其中许多方法在这里也被考虑在内)排在第二位;我本来打算发布它,但结果马克·兰索姆提出了完全相同的想法,所以只要看看他的答案就行了!

自从我运行这些测试以来,其他一些用户甚至发布了更新思想。。。我会在适当的时候测试它们,当我还有几分钟的空闲时间的时候。

我在两台不同的机器上运行了这些测试:我家的个人电脑(一台双核Athlon,4 GB RAM运行Windows 7 64位)和我的开发机器(一台双核Athlon,2 GB RAM运行Windows XP SP3)。显然,时代是不同的;然而, 相对的 时间,意思,每个方法与其他方法相比,都是一样的。也就是说,在这两台机器上,最快的是最快的。

现在来看结果。(我在下面发布的时间来自我的家庭计算机。)

但首先,作为参考——原始switch语句:
1000000次运行:98.88 ms
平均:0.09888微秒

迄今为止最快的优化:

Jo_o Angelo的想法是根据activcode字符串的散列代码为枚举赋值,然后直接对其进行大小写 ActivCode.GetHashCode() 到 MarketDataExchange :
1000000次运行:23.64 ms
平均:0.02364微秒
提速:329.90%
我的同事和我的铸造想法 ActivCode[0] 到 int 并检索适当的 市场数据交换 从启动时初始化的数组(Mark Ransom提出了完全相同的想法):
1000000次运行:28.76 ms
平均:0.02876微秒
提速:253.13%
TSter开启 activcode.gethashcode()。 而不是 ActivCode :
1000000次运行:34.69 ms
平均:0.03469微秒
提速:185.04%
一些用户(包括auraseer、tster和kyoryu)建议打开 激活码〔0〕 而不是 活动代码 :
1000000次运行:36.57 ms
平均:0.03657微秒
提速:174.66%
LoadMaster使用快速哈希的想法, ActivCode[0] + ActivCode[1]*0x100 :
1000000次运行:39.53 ms
平均:0.03953微秒
提速:153.53%
使用哈希表( Dictionary<string, MarketDataExchange> ,正如许多人所建议的:
1000000次运行:88.32 ms
平均:0.08832微秒
提速:12.36%
使用二进制搜索:
1000000次运行:1031 ms
平均:1.031微秒
提速:无(性能恶化)

我只想说,看到人们对这个简单的问题有多少不同的想法真的很酷。这对我来说非常有趣,我非常感谢迄今为止所有做出贡献和提出建议的人。

21 回复 | 直到 12 年前

João Angelo 15 年前

假设每个输入都是有效的 ActivCode ,可以更改枚举值并高度耦合到 GetHashCode 实施:

enum MarketDataExchange
{
    NONE,
    NBBO = 371857150,
    AMEX = 372029405,
    BSE = 372029408,
    BATS = -1850320644,
    NSE = 372029407,
    CHX = -284236702,
    NYSE = 372029412,
    ARCA = -734575383,
    NASDAQ = 372029421,
    NASDAQ_ADF = -1137859911,
    CBOE = 372029419,
    PHLX = 372029430,
    DIRECTEDGE = 372029429
}

public static MarketDataExchange GetMarketDataExchange(string ActivCode)
{
    if (ActivCode == null) return MarketDataExchange.NONE;

    return (MarketDataExchange)ActivCode.GetHashCode();
}

David R Tribble 15 年前

我将滚动自己的fast hash函数并使用integer switch语句来避免字符串比较:

int  h = 0;  

// Compute fast hash: A[0] + A[1]*0x100
if (ActivCode.Length > 0)
    h += (int) ActivCode[0];
if (ActivCode.Length > 1)
    h += (int) ActivCode[1] << 8;  

// Find a match
switch (h)
{
    case 0x0000:  return MarketDataExchange.NBBO;        // ""
    case 0x0041:  return MarketDataExchange.AMEX;        // "A"
    case 0x0042:  return MarketDataExchange.BSE;         // "B"
    case 0x5442:  return MarketDataExchange.BATS;        // "BT"
    case 0x0043:  return MarketDataExchange.NSE;         // "C"
    case 0x574D:  return MarketDataExchange.CHX;         // "MW"
    case 0x004E:  return MarketDataExchange.NYSE;        // "N"
    case 0x4150:  return MarketDataExchange.ARCA;        // "PA"
    case 0x0051:  return MarketDataExchange.NASDAQ;      // "Q"
    case 0x4451:  return MarketDataExchange.NASDAQ_ADF;  // "QD"
    case 0x0057:  return MarketDataExchange.CBOE;        // "W"
    case 0x0058:  return MarketDataExchange.PHLX;        // "X"
    case 0x0059:  return MarketDataExchange.DIRECTEDGE;  // "Y"
    default:      return MarketDataExchange.NONE;
}

我的测试表明 快4.5倍 而不是原始代码。

如果C有一个预处理器,我将使用宏来形成case常量。

这种技术比使用哈希表更快,当然也比使用字符串比较更快。它最多可用于4个32位整数的字符串,最多可用于8个64位长字符的字符串。

Auraseer 15 年前

如果您知道各种代码出现的频率,那么更常见的代码应该放在列表的顶部,这样做的比较就更少了。但我们假设你没有。

假设activcode总是有效的,当然会加快速度。您不需要测试空字符串或空字符串,并且可以在开关的末尾留下一个测试。也就是说,测试除y之外的所有内容,如果没有找到匹配项,则返回DirecteEdge。

不要打开整个字符串,而是打开它的第一个字母。对于字母较多的代码,在开关盒内进行第二次测试。像这样:

switch(ActivCode[0])
{
   //etc.
   case 'B':
      if ( ActivCode.Length == 1 ) return MarketDataExchange.BSE; 
      else return MarketDataExchange.BATS;
      // etc.
}

如果您可以返回并更改代码,使它们都是单个字符,那就更好了,因为这样您就不需要进行多个测试。更好的方法是使用枚举的数值,因此您可以简单地强制转换,而不必首先切换/转换。

justinlatimer 15 年前

我将使用一个字典作为键值对,并利用O(1)查找时间。

quip 15 年前

您有关于哪些字符串更常见的统计数据吗?所以可以先检查一下吗?

Courtney D 15 年前

如果输入有效,则可以使用

if (ActivCode.Length == 0)
    return MarketDataExchange.NBBO;

if (ActivCode.Length == 1)
    return (MarketDataExchange) (ActivCode[0]);

return (MarketDataExchange) (ActivCode[0] | ActivCode[1] << 8);

tster 15 年前

将开关更改为打开字符串的hashcode()。

peterchen 15 年前

我推断tster对“切换自定义哈希函数”的答复,假设代码生成器创建了一个查找表,或者——失败了——自己构建了一个查找表。

自定义哈希函数应该很简单,例如:

(int)ActivCode[0]*2 + ActivCode.Length-1

在以下假设下,这需要一个51个元素的表,很容易保存在一级缓存中:

必须已验证输入数据
空字符串必须单独处理
没有两个字符代码以相同的字符开头
添加新案例是 坚硬的

如果可以使用不安全的访问 ActivCode[0] 正在生成\0'终止符。

Haacked 15 年前

请原谅,如果我在这里出错了,我从我的C++知识中推断出来。例如,如果你使用一个空字符串的ActudioC[0 ],在C++中得到一个值为零的字符。

创建一个二维数组,初始化一次;第一个维度是代码的长度,第二个维度是字符值。用要返回的枚举值填充。现在您的整个功能变成:

public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
    return LookupTable[ActivCode.Length][ActivCode[0]];
}

幸运的是,与其他两个字符代码相比,所有两个字符代码在第一个字母中都是唯一的。

cletus 7 年前

我会把它放在字典里,而不是使用switch语句。尽管如此,这可能不会有什么不同。或者可能。见 C# switch statement limitations - why? .

tster 15 年前

避免所有字符串比较。
避免看超过一个字符(任何时候)
避免其他情况,因为我希望编译器能够尽可能优化
尝试在一次切换跳跃中获得结果

代码:

public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
    if (ActivCode == null) return MarketDataExchange.NONE;
    int length = ActivCode.Length;
    if (length == 0) return MarketDataExchange.NBBO;

    switch (ActivCode[0]) {
        case 'A': return MarketDataExchange.AMEX;
        case 'B': return (length == 2) ? MarketDataExchange.BATS : MarketDataExchange.BSE;
        case 'C': return MarketDataExchange.NSE;
        case 'M': return MarketDataExchange.CHX;
        case 'N': return MarketDataExchange.NYSE;
        case 'P': return MarketDataExchange.ARCA;
        case 'Q': return (length == 2) ? MarketDataExchange.NASDAQ_ADF : MarketDataExchange.NASDAQ;
        case 'W': return MarketDataExchange.CBOE;
        case 'X': return MarketDataExchange.PHLX;
        case 'Y': return MarketDataExchange.DIRECTEDGE;
        default:  return MarketDataExchange.NONE;
    }
}

R Samuel Klatchko 15 年前

通过预先填充索引表来利用简单的指针算法来交换内存以提高速度。

public class Service 
{
    public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
    {
        int x = 65, y = 65;
        switch(ActivCode.Length)
        {
            case 1:
                x = ActivCode[0];
                break;
            case 2:
                x = ActivCode[0];
                y = ActivCode[1];
                break;
        }
        return _table[x, y];
    }

    static Service()
    {
        InitTable();
    }

    public static MarketDataExchange[,] _table = 
        new MarketDataExchange['Z','Z'];

    public static void InitTable()
    {
        for (int x = 0; x < 'Z'; x++)
            for (int y = 0; y < 'Z'; y++)
                _table[x, y] = MarketDataExchange.NONE;

        SetCell("", MarketDataExchange.NBBO);
        SetCell("A", MarketDataExchange.AMEX);
        SetCell("B", MarketDataExchange.BSE);
        SetCell("BT", MarketDataExchange.BATS);
        SetCell("C", MarketDataExchange.NSE);
        SetCell("MW", MarketDataExchange.CHX);
        SetCell("N", MarketDataExchange.NYSE);
        SetCell("PA", MarketDataExchange.ARCA);
        SetCell("Q", MarketDataExchange.NASDAQ);
        SetCell("QD", MarketDataExchange.NASDAQ_ADF);
        SetCell("W", MarketDataExchange.CBOE);
        SetCell("X", MarketDataExchange.PHLX);
        SetCell("Y", MarketDataExchange.DIRECTEDGE);
    }

    private static void SetCell(string s, MarketDataExchange exchange)
    {
        char x = 'A', y = 'A';
        switch(s.Length)
        {
            case 1:
                x = s[0];
                break;
            case 2:
                x = s[0];
                y = s[1];
                break;
        }
        _table[x, y] = exchange;
    }
}

使枚举字节基于以节省一些空间。

public enum MarketDataExchange : byte
{
    NBBO, AMEX, BSE, BATS, NSE, CHX, NYSE, ARCA, 
    NASDAQ, NASDAQ_ADF, CBOE, PHLIX, DIRECTEDGE, NONE
}

Matthew Whited 7 年前

如果枚举值是任意的,则可以执行此操作…

public static MarketDataExchange GetValue(string input)
{
    switch (input.Length)
    {
        case 0: return MarketDataExchange.NBBO;
        case 1: return (MarketDataExchange)input[0];
        case 2: return (MarketDataExchange)(input[0] << 8 | input[1]);
        default: return MarketDataExchange.None;
    }
}

…如果你想彻底疯掉,你也可以用不安全的指针调用,如 Pavel Minaev … 上面的纯强制转换版本比这个不安全的版本快。

unsafe static MarketDataExchange GetValue(string input)
{
    if (input.Length == 1)
        return (MarketDataExchange)(input[0]);
    fixed (char* buffer = input)
        return (MarketDataExchange)(buffer[0] << 8 | buffer[1]);
}

public enum MarketDataExchange
{
    NBBO = 0x00, //
    AMEX = 0x41, //A
    BSE = 0x42, //B
    BATS = 0x4254, //BT
    NSE = 0x43, //C
    CHX = 0x4D57, //MW
    NYSE = 0x4E, //N
    ARCA = 0x5041, //PA
    NASDAQ = 0x51, //Q
    NASDAQ_ADF = 0x5144, //QD
    CBOE = 0x57, //W
    PHLX = 0x58, //X
    DIRECTEDGE = 0x59, //Y

    None = -1
}

Josh 15 年前

+1.使用字典。不一定要优化,但会更干净。

我可能也会对字符串使用常量,尽管我怀疑这会为您带来性能方面的任何好处。

James Anderson 15 年前

混乱,但使用嵌套的ifs和硬编码的组合可能会击败乐观主义者:

   if (ActivCode < "N") {
         // "" to "MW"
         if (ActiveCode < "BT") {
            // "" to "B"
            if (ActiveCode < "B") {
                // "" or "A"
                if (ActiveCode < "A") {
                      // must be ""
                     retrun MarketDataExchange.NBBO;
                } else {
                     // must be "A"
                    return MarketDataExchange.AMEX;
                }
            } else {
                // must be "B"
                return MarketDataExchange.BSE;
            }
         } else {
            // "BT" to "MW"
            if (ActiveCode < "MW") {
                // "BT" or "C"
                if (ActiveCode < "C") {
                      // must be "BT"
                     retrun MarketDataExchange.NBBO;
                } else {
                     // must be "C"
                    return MarketDataExchange.NSE;
                }
            } else {
            // must be "MV"
                return MarketDataExchange.CHX;
            }
         }
    } else {
        // "N" TO "Y"
         if (ActiveCode < "QD") {
            // "N" to "Q"
            if (ActiveCode < "Q") {
                // "N" or "PA"
                if (ActiveCode < "PA") {
                      // must be "N"
                     retrun MarketDataExchange.NYSE;
                } else {
                     // must be "PA"
                    return MarketDataExchange.ARCA;
                }
            } else {
                // must be "Q"
                return MarketDataExchange.NASDAQ;
            }
         } else {
            // "QD" to "Y"
            if (ActiveCode < "X") {
                // "QD" or "W"
                if (ActiveCode < "W") {
                      // must be "QD"
                     retrun MarketDataExchange.NASDAQ_ADF;
                } else {
                     // must be "W"
                    return MarketDataExchange.CBOE;
                }
            } else {
            // "X" or "Y"
                if (ActiveCode < "Y") {
                      // must be "X"
                     retrun MarketDataExchange.PHLX;
                } else {
                     // must be "Y"
                    return MarketDataExchange.DIRECTEDGE;
                }
            }
         }
    }

它通过三个或四个比较得到正确的函数。我甚至不会考虑真的这样做,除非你的代码被期望每秒运行几次!

您进一步考虑它,以便只进行单个字符的比较。例如,将“<“bt”'替换为“>=b”'——速度更快,可读性更低!

Pavel Minaev 15 年前

您的所有字符串的长度最多为2个字符和ASCII,因此我们可以使用每个字符1个字节。更可能的是,他们也永远不会 \0 在其中显示(.net) string 允许嵌入空字符,但许多其他内容不允许)。有了这个假设,我们可以空填充所有字符串,使每个字符串正好为2个字节,或者 ushort :

""   -> (byte) 0 , (byte) 0   -> (ushort)0x0000
"A"  -> (byte)'A', (byte) 0   -> (ushort)0x0041
"B"  -> (byte)'B', (byte) 0   -> (ushort)0x0042
"BT" -> (byte)'B', (byte)'T'  -> (ushort)0x5442

现在我们有了一个相对较短(64K)范围内的单个整数,我们可以使用查找表:

MarketDataExchange[] lookup = {
    MarketDataExchange.NBBO, 
    MarketDataExchange.NONE, 
    MarketDataExchange.NONE, 
    ...
    /* at index 0x041 */
    MarketDataExchange.AMEX,
    MarketDataExchange.BSE,
    MarketDataExchange.NSE,
    ...
};

现在,获取给定字符串的值是:

public static unsafe MarketDataExchange GetMarketDataExchange(string s)
{
   // Assume valid input
   if (s.Length == 0) return MarketDataExchange.NBBO;

   // .NET strings always have '\0' after end of data - abuse that
   // to avoid extra checks for 1-char strings. Skip index checks as well.
   ushort hash;
   fixed (char* data = s)
   {
       hash = (ushort)data[0] | ((ushort)data[1] << 8);
   }

   return lookup[hash];
}

Nestor 15 年前

将案例放在具有非线性访问的排序结构中(如哈希表)。你的开关将有一个线性时间。

Chip Uni 15 年前

您可以根据使用最多的代码来订购代码,从而稍微加快速度。

但是我同意克莱特斯的观点:我能想到的最好的加速方法是使用一个有足够空间的散列图(这样就不会发生碰撞)。

kyoryu 15 年前

一些随机的想法,可能不完全适用于一起:

打开字符串中的第一个字符,而不是字符串本身,并为可以包含多个字母的字符串执行子开关?

哈希表当然可以保证O(1)检索,但对于较小的比较数量来说,它可能不会更快。

不要使用字符串,而是使用枚举或类似flyweight的内容。无论如何,在这种情况下使用字符串似乎有点脆弱…

如果你真的需要它尽可能快,为什么不把它写在汇编中呢?:)

indy 15 年前

我们可以将activcode强制转换为int,然后在case语句中使用int吗?

Shire 14 年前

使用代码的长度从该代码创建唯一值,而不是使用GetHashCode()。如果使用代码的第一个字母被代码的长度移动,就不会发生冲突。这将成本降低到两个比较,一个数组索引和一个移位(平均)。

public static MarketDataExchange GetMarketDataExchange(string ActivCode)
{
    if (ActivCode == null)
        return MarketDataExchange.NONE;
    if (ActivCode.Length == 0)
        return MarketDataExchange.NBBO;
    return (MarketDataExchange)((ActivCode[0] << ActivCode.Length));
}

public enum MarketDataExchange
{
    NONE = 0,
    NBBO = 1,
    AMEX = ('A'<<1),
    BSE = ('B'<<1),
    BATS = ('B'<<2),
    NSE = ('C'<<1),
    CHX = ('M'<<2),
    NYSE = ('N'<<1),
    ARCA = ('P'<<2),
    NASDAQ = ('Q'<<1),
    NASDAQ_ADF = ('Q'<<2),
    CBOE = ('W'<<1),
    PHLX = ('X'<<1),
    DIRECTEDGE = ('Y'<<1),
}