你将如何尽快做出这个转换声明?

2009-12-04更新 :对于这里发布的一些build议的分析结果,请看下面!


问题

考虑以下非常无害,非常直接的方法,它使用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上,也不是浪费时间。

还有一点需要注意:我对两种答案感兴趣 – 那些假设每个input都是有效的ActivCode(上面的switch语句中的一个string),那些没有的。 我几乎可以肯定,做出第一个假设可以进一步提高速度。 无论如何,它为我们做了。 但是我知道改进是可能的。


结果

那么,事实certificate,迄今为止我所testing的最快解决scheme来自JoãoAngelo,他的build议其实非常简单,却非常聪明。 我的同事和我所devise的解决scheme(在尝试了几种方法之后,其中许多也被认为是在这里)排在第二位; 我准备发布它,但事实certificate,Mark Ransom提出了完全相同的想法,所以请查看他的答案!

自从我运行这些testing以来,其他一些用户发布了更新的想法……我将在适当的时候对其进行testing,当我还剩下几分钟的时间。

我在两台不同的机器上运行了这些testing:我家里的个人电脑(一台运行Windows 7 64位的4 Gb RAM的双核Athlon)和我的开发机器(运行Windows XP的双核Athlon 2 GB内存SP3)。 显然,时代不同, 然而, 相对的时代,也就是说,每种方法与其他方法相比,是如何相同的。 也就是说,两台机器中速度最快的是

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

但首先,供参考 – 最初的开关声明:
1000000次运行:98.88毫秒
平均值:0.09888微秒

到目前为止最快的优化:

  1. JoãoAngelo基于ActivCodestring的哈希码为枚举赋值的思路,然后将ActivCode.GetHashCode()直接ActivCode.GetHashCode()MarketDataExchange
    1000000次运行:23.64毫秒
    平均值:0.02364微秒
    提速:329.90%

  2. 我的同事和我的想法将ActivCode[0]转换为int并从启动时初始化的数组中检索相应的MarketDataExchange (这与Mark Ransombuild议的完全相同):
    1000000次运行:28.76毫秒
    平均值:0.02876微秒
    提速:253.13%

  3. tster打开ActivCode.GetHashCode()而不是ActivCode的输出的想法:
    1000000次运行:34.69毫秒
    平均值:0.03469微秒
    提速:185.04%

  4. 这个想法,由几个用户(包括Auraseer,tster和kyoryu)build议开启ActivCode[0]而不是ActivCode
    1000000次运行:36.57毫秒
    平均值:0.03657微秒
    提速:174.66%

  5. Loadmaster使用快速散列的想法, ActivCode[0] + ActivCode[1]*0x100
    1000000次运行:39.53毫秒
    平均值:0.03953微秒
    提速:153.53%

  6. 使用散列表( Dictionary<string, MarketDataExchange> ),如许多build议:
    1000000次运行:88.32毫秒
    平均值:0.08832微秒
    提速:12.36%

  7. 使用二进制search:
    1000000次运行:1031毫秒
    平均值:1.031微秒
    速度提高:无(性能恶化)

让我只是说,看到人们在这个简单的问题上有多less不同的想法真的很酷。 这对我来说非常有趣,我非常感谢迄今已经提出并提出build议的所有人。

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

我会推出自己的快速哈希函数,并使用整数切换语句来避免string比较:

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

我的testing表明,这比原来的代码4.5倍

如果C#有一个预处理器,我会使用一个macros来形成大小写常量。

这种技术比使用散列表更快,当然比使用string比较更快。 它适用于32位整数的最多四个字符的string,以及64位长的最多八个字符。

如果您知道各种代码出现的频率,那么最常见的代码应该放在列表的顶部,这样就可以减less比较次数。 但是让我们假设你没有这个。

假设ActivCode总是有效的,当然会加快速度。 您不需要testingnull或空string,并且可以从交换机末尾省略一个testing。 也就是说,testing除Y以外的所有内容,如果找不到匹配项,则返回DIRECTEDGE。

打开整个string,而不是打开它的第一个字母。 对于有更多字母的代码,请在开关盒内进行第二次testing。 像这样的东西:

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

如果你可以回去修改代码,所以它们都是单个字符会更好,因为你再也不需要多个testing了。 更好的办法是使用枚举的数值,所以你可以简单地投,而不是必须切换/翻译首先。

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

你有统计哪些string更常见? 所以这些可以先检查?

有了有效的input可以使用

 if (ActivCode.Length == 0) return MarketDataExchange.NBBO; if (ActivCode.Length == 1) return (MarketDataExchange) (ActivCode[0]); return (MarketDataExchange) (ActivCode[0] | ActivCode[1] << 8); 

改变开关打开string的HashCode()。

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

自定义散列函数应该很简单,例如:

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

这需要一个由51个元素组成的表格,可以很容易地保存在L1caching中,其条件如下:

  • input数据必须已经被validation
  • 空string必须谨慎处理
  • 没有两个字符的代码以相同的字符开始
  • 增加新的案件是困难的

如果您可以使用不安全的访问ActivCode[0]产生'\ 0'终止符,则可以合并空string大小写。

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

创build一个初始化一次的二维数组; 第一个维度是代码的长度,第二个维度是一个字符值。 填写您想要返回的枚举值。 现在你的整个function变成:

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

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

我会把它放在字典,而不是使用switch语句。 这就是说,这可能没有什么区别。 或者可能。 请参阅C#switch语句限制 – 为什么? 。

  1. 避免所有的string比较。
  2. 避免看多一个字符(永远)
  3. 避免if-else,因为我希望编译器能够优化它的最佳效果
  4. 尝试在单个开关跳转中获得结果

码:

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

通过预先填充索引表来提高速度以利用简单指针algorithm。

 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 } 

如果枚举值是任意的,你可以这样做…

 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 } 

+1使用字典。 不一定是为了优化,但它会更干净。

我可能会使用常量的string,但我怀疑这会给你什么性能明智的。

凌乱,但使用嵌套的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; } } } } 

这与三个或四个比较得到正确的function。 我甚至不会想这样做,除非你的代码片段预计每秒运行几次!

您进一步otimise它,以便只有单个字符比较发生。 例如用'> =“B”replace“<”BT“' – 这样稍微快一点,可读性就更差了!

你所有的string最多只有2个字符,而ASCII,所以我们可以使用每个字符1个字节。 而且,更可能的是,它们也永远不会出现在其中(.NET string允许embedded空字符,但许多其他的东西却不能)。 有了这个假设,我们可以将所有的string零空白,每个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, ... }; 

现在,获得一个string的值是:

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

将案例放入非线性访问的sorting结构中(如散列表)。 你有的开关将有一个线性时间。

您可以根据最常用的代码来订购代码,从而获得温和的加速。

但是我同意Cletus的观点:我能想到的最好的加速就是使用一个有足够空间的散列图(所以没有冲突)。

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

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

哈希表肯定能够保证O(1)检索,但是对于较小数量的比较,它可能不会更快。

不要使用string,使用枚举或类似flyweight的东西。 在这种情况下使用string似乎有点脆弱

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

Can we cast the ActivCode to int and then use int in our case statements?

Use the length of the code to create a unique value from that code instead of using GetHashCode() . It turns out there are no collisions if you use the first letter of the code shifted by the length of the code. This reduces the cost to two comparisons, one array index and one shift (on average).

 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), }