c# - formulario 1 banco de la republica
¿Cómo harías esta declaración de cambio lo más rápido posible? (21)
ACTUALIZACIÓN 2009-12-04 : para obtener un perfil de los resultados de varias de las sugerencias publicadas aquí, ¡consulte más abajo!
La pregunta
Considere el siguiente método muy sencillo e inofensivo, que utiliza una instrucción switch para devolver un valor enum definido:
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;
}
Mi colega y yo discutimos algunas ideas hoy acerca de cómo hacer que este método sea más rápido, y se nos ocurrieron algunas modificaciones interesantes que de hecho mejoraron su rendimiento bastante significativamente (proporcionalmente hablando, por supuesto). Me interesaría saber qué tipo de optimizaciones puede imaginar cualquier otra persona que no se nos haya ocurrido.
Inmediatamente, permítanme ofrecer un rápido descargo de responsabilidad: esto es por diversión , y no para impulsar todo el debate "para optimizar o no optimizar". Dicho esto, si se considera uno de los que creen dogmáticamente que "la optimización prematura es la raíz de todo mal", tenga en cuenta que trabajo para una empresa comercial de alta frecuencia, donde todo debe funcionar lo más rápido posible: cuello de botella. o no. Entonces, aunque estoy publicando esto en SO por diversión , tampoco es una gran pérdida de tiempo.
Una nota más rápida: me interesan dos tipos de respuestas: las que suponen que cada entrada será un ActivCode válido (una de las cadenas en la declaración de switch anterior) y aquellas que no lo hacen. Estoy casi seguro de que hacer la primera suposición permite más mejoras de velocidad; de todos modos, lo hizo por nosotros. Pero sé que las mejoras son posibles de cualquier manera.
Los resultados
Bueno, resulta que la solución más rápida hasta ahora (que he probado) provino de João Angelo, cuya sugerencia fue en realidad muy simple, pero extremadamente inteligente. La solución que mi compañero de trabajo y yo habíamos ideado (después de probar varios enfoques, muchos de los cuales también se pensaron aquí) quedó en segundo lugar; Iba a publicarlo, pero resulta que a Mark Ransom se le ocurrió la misma idea, ¡así que solo revisa su respuesta!
Desde que realicé estas pruebas, otros usuarios han publicado ideas aún más nuevas ... Las probaré a su debido tiempo, cuando tenga unos minutos más de sobra.
Realicé estas pruebas en dos máquinas diferentes: mi computadora personal en casa (un Athlon de doble núcleo con 4 Gb de RAM con Windows 7 de 64 bits) y mi máquina de desarrollo en el trabajo (un Athlon de doble núcleo con 2 Gb de RAM con Windows XP) SP3). Obviamente, los tiempos fueron diferentes; sin embargo, los tiempos relativos , es decir, la forma en que cada método se comparó con cualquier otro método, fueron los mismos. Es decir, el más rápido fue el más rápido en ambas máquinas, etc.
Ahora para los resultados. (Los horarios que publico a continuación corresponden a la computadora de mi casa).
Pero primero, para referencia, la declaración de cambio original:
1000000 carreras: 98.88 ms
Promedio: 0.09888 microsegundos
Las optimizaciones más rápidas hasta el momento:
La idea de João Angelo de asignar valores a las enumeraciones en función de los códigos hash de las cadenas ActivCode y luego
ActivCode.GetHashCode()directamenteActivCode.GetHashCode()enMarketDataExchange:
1000000 carreras: 23,64 ms
Promedio: 0.02364 microsegundos
Aumento de velocidad: 329.90%La idea de mi colega y de mí de
ActivCode[0]en unainty recuperar elMarketDataExchangeadecuado de una matriz inicializada al inicio (esta misma idea fue sugerida por Mark Ransom):
1000000 carreras: 28,76 ms
Promedio: 0.02876 microsegundos
Aumento de velocidad: 253.13%La idea de
ActivCode.GetHashCode()deActivCode.GetHashCode()la salida deActivCode.GetHashCode()lugar deActivCode:
1000000 ejecuciones: 34.69 ms
Promedio: 0.03469 microsegundos
Aumento de velocidad: 185.04%La idea, sugerida por varios usuarios, incluidos Auraseer, tster y kyoryu, de
ActivCode[0]lugar deActivCode:
1000000 carreras: 36.57 ms
Promedio: 0.03657 microsegundos
Aumento de velocidad: 174.66%La idea de Loadmaster de usar el hash rápido,
ActivCode[0] + ActivCode[1]*0x100:
1000000 carreras: 39.53 ms
Promedio: 0.03953 microsegundos
Aumento de velocidad: 153.53%Usando una tabla hash (
Dictionary<string, MarketDataExchange>), como lo sugieren muchos:
1000000 ejecuciones: 88.32 ms
Promedio: 0.08832 microsegundos
Aumento de velocidad: 12.36%Usando una búsqueda binaria:
1000000 ejecuciones: 1031 ms
Promedio: 1.031 microsegundos
Aumento de velocidad: ninguno (empeorado)
Permítanme decir que ha sido realmente genial ver cuántas ideas diferentes tenían las personas sobre este simple problema. Esto fue muy interesante para mí, y estoy muy agradecido con todos los que han contribuido y hecho una sugerencia hasta el momento.
- Evite todas las comparaciones de cadenas.
- Evita mirar a más de un personaje (nunca)
- Evitar if-else, ya que quiero que el compilador pueda optimizar lo mejor posible
- Intenta obtener el resultado en un solo salto de interruptor
código:
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;
}
}
¿Tiene alguna estadística sobre qué cadenas son más comunes? Para que esos puedan ser verificados primero?
+1 para usar un diccionario. No necesariamente para la optimización, pero sería más limpio.
Probablemente usaría constantes para las cuerdas también, aunque dudo que te compre algo en cuanto al rendimiento.
Cambie el interruptor para activar el HashCode () de las cadenas.
Cambie la memoria por la velocidad rellenando previamente una tabla de índice para aprovechar la aritmética del puntero simple.
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;
}
}
Haga el enum basado en bytes para ahorrar un poco de espacio.
public enum MarketDataExchange : byte
{
NBBO, AMEX, BSE, BATS, NSE, CHX, NYSE, ARCA,
NASDAQ, NASDAQ_ADF, CBOE, PHLIX, DIRECTEDGE, NONE
}
Coloque las cajas en una estructura ordenada con acceso no lineal (como una tabla hash). El interruptor que tienes tendrá un tiempo lineal.
Con una entrada válida podría usar
if (ActivCode.Length == 0)
return MarketDataExchange.NBBO;
if (ActivCode.Length == 1)
return (MarketDataExchange) (ActivCode[0]);
return (MarketDataExchange) (ActivCode[0] | ActivCode[1] << 8);
Desordenado pero usando una combinación de ifs anidados y codificación difícil podría vencer al optimizador: -
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;
}
}
}
}
Esto obtiene la función correcta con tres o cuatro comparaciones. ¡Ni siquiera pensaría en hacer esto de verdad a menos que se espere que tu código corra varias veces por segundo!
Además lo otimise para que solo se produzcan comparaciones de un solo carácter. por ejemplo, reemplace ''<"BT"'' con ''> = "B"'' - ¡cada vez más rápido y aún menos legible!
Extrapolaría la respuesta de tster a "cambiar una función hash personalizada", suponiendo que el generador de códigos creara una tabla de búsqueda, o - en su defecto - construyera la tabla de búsqueda yo mismo.
La función hash personalizada debe ser simple, por ejemplo:
(int)ActivCode[0]*2 + ActivCode.Length-1
Esto requeriría una tabla de 51 elementos, que se guardan fácilmente en caché L1, bajo las siguientes suposiciones:
- Los datos de entrada ya deben ser validados
- cadena vacía debe ser manejada sepsately
- no hay códigos de dos caracteres que comiencen con el mismo personaje
- agregar nuevos casos es difícil
la caja vacía de cadenas podría incorporarse si pudiera usar un acceso inseguro a ActivCode[0] produciendo el terminador ''/ 0''.
Lo pondría en el diccionario en lugar de usar una declaración de cambio. Dicho esto, puede que no haga la diferencia. O podría ser. Consulte las limitaciones de la declaración de cambio C # - ¿por qué? .
Perdóname si encuentro algo mal aquí, estoy extrapolando mi conocimiento de C ++. Por ejemplo, si toma ActivCode [0] de una cadena vacía, en C ++ obtendrá un carácter cuyo valor es cero.
Cree una matriz bidimensional que inicialice una vez; la primera dimensión es la longitud del código, la segunda es un valor de carácter. Complete con el valor de enumeración que desea devolver. Ahora toda tu función se convierte en:
public static MarketDataExchange GetMarketDataExchange(string ActivCode) {
return LookupTable[ActivCode.Length][ActivCode[0]];
}
Por suerte para ti, todos los códigos de dos caracteres son únicos en la primera letra en comparación con los otros códigos de dos caracteres.
Puede obtener una aceleración leve ordenando los códigos según cuáles sean los más utilizados.
Pero estoy de acuerdo con Cletus: la mejor aceleración que se me ocurre sería utilizar un mapa hash con mucho espacio (para que no haya colisiones).
Rodaría mi propia función hash rápida y usaría una declaración de cambio entero para evitar comparaciones de cadenas:
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;
}
Mis pruebas muestran que esto es aproximadamente 4.5 veces más rápido que el código original.
Si C # tuviera un preprocesador, usaría una macro para formar las constantes de caso.
Esta técnica es más rápida que utilizar una tabla hash y, desde luego, es más rápida que el uso de comparaciones de cadenas. Funciona para cadenas de hasta cuatro caracteres con entradas de 32 bits y hasta 8 caracteres con longitudes de 64 bits.
Si los valores de enumeración son arbitrarios, podrías hacer esto ...
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;
}
}
... si quieres volverte loco, también puedes usar una llamada insegura con apuntadores como lo señala Pavel Minaev ... La versión de lanzamiento puro anterior es más rápida que esta versión insegura.
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
}
Si sabe con qué frecuencia se muestran los distintos códigos, los más comunes deben ir en la parte superior de la lista, por lo que se realizan menos comparaciones. Pero supongamos que no tienes eso.
Suponer que ActivCode siempre es válido, por supuesto, acelerará las cosas. No es necesario que pruebe la cadena vacía o nula, y puede dejar fuera una prueba desde el final del interruptor. Es decir, prueba todo excepto Y, y luego devuelve DIRECTEDGE si no se encuentra ninguna coincidencia.
En lugar de encender toda la cadena, encienda su primera letra. Para los códigos que tienen más letras, realice una segunda prueba dentro de la caja del interruptor. Algo como esto:
switch(ActivCode[0])
{
//etc.
case ''B'':
if ( ActivCode.Length == 1 ) return MarketDataExchange.BSE;
else return MarketDataExchange.BATS;
// etc.
}
Sería mejor si pudieras regresar y cambiar los códigos para que sean todos caracteres individuales, porque nunca necesitarías más de una prueba. Mejor aún sería usar el valor numérico de la enumeración, por lo que simplemente puede emitir en lugar de tener que cambiar / traducir en primer lugar.
Suponiendo que cada entrada será un ActivCode válido, que puede cambiar los valores de enumeración y altamente acoplado a la implementación de 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();
}
Todas sus cadenas tienen como máximo 2 caracteres de largo, y ASCII, por lo que podemos usar 1 byte por carácter. Además, lo más probable es que nunca puedan tener /0 en ellos ( string .NET permite caracteres nulos incrustados, pero muchas otras cosas no). Con esa suposición, podemos anular todas las cadenas para que sean exactamente 2 bytes cada una, o un 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
Ahora que tenemos un entero único en un rango relativamente corto (64K), podemos usar una tabla de búsqueda:
MarketDataExchange[] lookup = {
MarketDataExchange.NBBO,
MarketDataExchange.NONE,
MarketDataExchange.NONE,
...
/* at index 0x041 */
MarketDataExchange.AMEX,
MarketDataExchange.BSE,
MarketDataExchange.NSE,
...
};
Ahora, obtener el valor dado a una cadena es:
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];
}
Un par de pensamientos aleatorios, que pueden no ser todos aplicables juntos:
¿Enciende el primer carácter de la cadena, en lugar de la cadena misma, y haces un subinterruptor para las cadenas que pueden contener más de una letra?
Un hashtable ciertamente garantizaría la recuperación de O (1), aunque podría no ser más rápido para un menor número de comparaciones.
No use cadenas, use enums o algo así como un flyweight en su lugar. Usar cuerdas en este caso parece un poco frágil de todos modos ...
Y si realmente necesita que sea lo más rápido posible, ¿por qué no lo está escribiendo en ensamblaje? :)
Utilizaría un diccionario para los pares de valores clave y aprovecharía el tiempo de búsqueda O (1).
Can we cast the ActivCode to int and then use int in our case statements?
Use la longitud del código para crear un valor único a partir de ese código en lugar de usar GetHashCode (). Resulta que no hay colisiones si usa la primera letra del código desplazado por la longitud del código. Esto reduce el costo de dos comparaciones, un índice de matriz y un cambio (en promedio).
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),
}