你会如何尽可能快地制作这个切换声明？

Question

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;
}

我和我的同事今天就如何更快地实现这个方法的几个想法进行了斗争,并且我们想出了一些有趣的修改,实际上相当显着地提高了它的性能(当然,按比例说).我有兴趣知道那里的其他人可以想到哪种优化可能没有发生在我们身上.

接下来,让我简单地提供一个快速免责声明:这是为了好玩,而不是为整个"优化或不优化"辩论提供动力.也就是说,如果你把自己视为那些教条地认为"过早优化是所有邪恶的根源"的人,请注意我在一家高频交易公司工作,一切都需要尽可能快地运行 - 瓶颈或不.因此,即使我在SO上发布这些内容以获得乐趣,也不仅仅是浪费时间.

还有一个快速说明:我对两种答案感兴趣 - 假设每个输入都是有效的ActivCode(switch上面语句中的一个字符串),而那些不是.我几乎可以肯定,做出第一个假设可以进一步提高速度; 无论如何,它为我们做了.但我知道无论哪种方式都可以改进.

---

结果

好吧,事实证明,迄今为止最快的解决方案(我已经测试过)来自JoãoAngelo,他的建议实际上非常简单,但非常聪明.我的同事和我设计的解决方案(在尝试了几种方法之后,其中许多方法也在这里被考虑过)排在第二位; 我打算发布它,但事实证明Mark Ransom提出了完全相同的想法,所以看看他的回答!

自从我运行这些测试以来,其他一些用户已经发布了更新的想法...我将在适当的时候测试它们,当我还有几分钟的时间.

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

现在结果.(我在下面发布的时间来自我的家用电脑.)

但首先,作为参考 - 原始开关语句:
1000000运行:98.88 ms
平均:0.09888微秒

到目前为止最快的优化:

1. 分配值基础上,ActivCode字符串的哈希码,然后枚举的若昂·安杰洛的想法直接壳ActivCode.GetHashCode()到MarketDataExchange:
   百万运行:23.64毫秒
   平均:0.02364微秒
   的速度增长:329.90%

2. 我的同事和我铸造的想法ActivCode[0]到int和检索适当的MarketDataExchange从启动时初始化数组(此相同的想法建议由马克赎金):
   百万运行:28.76毫秒
   平均:0.02876微秒
   的速度增长:253.13%

3. tster打开输出的想法ActivCode.GetHashCode()代替ActivCode:
   1000000次运行:34.69 ms
   平均值:0.03469微秒
   速度增加:185.04%

4. 这个想法,包括Auraseer,tster和kyoryu在内的几个用户建议,ActivCode[0]而不是ActivCode:
   1000000次运行:36.57 ms
   平均值:0.03657微秒
   速度增加:174.66%

5. Loadmaster使用快速哈希的想法ActivCode[0] + ActivCode[1]*0x100:
   1000000次运行:39.53 ms
   平均值:0.03953微秒
   速度增加:153.53%

6. 使用hashtable(Dictionary<string, MarketDataExchange>),如许多建议:
   1000000次运行:88.32 ms
   平均值:0.08832微秒
   速度增加:12.36%

7. 使用二进制搜索:
   1000000次运行:1031 ms
   平均值:1.031微秒
   速度增加:无(性能恶化)

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

Answer 1

假设每个输入都是有效的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();
}

Answer 2

我将使用自己的快速哈希函数并使用整数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常量.

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

Answer 3

如果你知道各种代码显示的频率,那么更常见的代码应该放在列表的顶部,这样就可以进行更少的比较.但是我们假设你没有那个.

假设ActivCode始终有效,当然会加快速度.您不需要测试null或空字符串,并且可以从交换机的末尾取消一个测试.也就是说,测试除Y之外的所有内容,如果找不到匹配则返回DIRECTEDGE.

而不是打开整个字符串,切换它的第一个字母.对于包含更多字母的代码,在开关盒内放置第二个测试.像这样的东西:

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

如果您可以返回并更改代码以便它们都是单个字符会更好,因为您将永远不需要多个测试.更好的是使用枚举的数值,所以你可以简单地转换而不是必须首先切换/翻译.

Answer 4

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

Answer 5

你有关于哪些字符串更常见的统计数据吗？那么可以先检查一下吗？

Answer 6

有效输入可以使用

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

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

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