2011-02-08 13 views
6

¿Cuál es el método más rápido para verificar los sufijos de cadena en C#?Comprobación rápida del sufijo de cadena en C# (.NET 4.0)?

Necesito comprobar cada cadena en una lista grande (desde 5000 a 100000 elementos) para un término en particular. El término está garantizado de no estar incrustado en la cadena. En otras palabras, si la cadena contiene el término, estará al final de la cadena. La cadena también se garantiza que es más larga que el sufijo. La información cultural no es importante.

Estos son cómo los diferentes métodos realizaron contra 100000 cuerdas (la mitad de ellos tienen el sufijo):

1. Substring Comparison - 13.60ms 
2. String.Contains - 22.33ms 
3. CompareInfo.IsSuffix - 24.60ms 
4. String.EndsWith - 29.08ms 
5. String.LastIndexOf - 30.68ms 

Estos son tiempos promedio. [Editar] Se olvidó de mencionar que las cadenas también se ponen en listas separadas, pero esto no es importante. Sin embargo, se agrega al tiempo de ejecución.

En mi sistema la comparación de subcadenas (extraer el final de la cadena utilizando el método String.Substring y compararlo con el término del sufijo) es consistentemente el más rápido cuando se prueba contra 100000 cadenas. El problema con el uso de la comparación de subcadenas es que Garbage Collection puede ralentizarlo considerablemente (más que los otros métodos) porque String.Substring crea cadenas nuevas. El efecto no es tan malo en .NET 4.0 como en 3.5 e inferior, pero sigue siendo notable. En mis pruebas, String.Substring se comportó consistentemente más lento en series de 12000-13000 cadenas. Obviamente, esto diferirá entre sistemas e implementaciones.

[EDIT] código de referencia: http://pastebin.com/smEtYNYN

[EDIT] Código de FlyingStreudel corre rápido, pero la recomendación de utilizar en conjunción con EndsWith StringComparison.Ordinal de Jon Skeet parece ser la mejor opción.

+3

Sin comentarios sobre lo que está haciendo .NET, pero si necesita probar la misma cadena para muchos sufijos, puede ser aconsejable construir un árbol de sufijos: http://en.wikipedia.org/wiki/Suffix_tree – mquander

Respuesta

18

Si ese es el tiempo necesario para comprobar 100.000 cadenas, ¿realmente importa?

Personalmente, utilizaría string.EndsWith con el argumento de que es el más descriptivo: dice exactamente lo que está tratando de probar.

Sospecho algo del hecho de que parece estar funcionando peor ... si pudieras publicar tu código de referencia, sería muy útil. (En particular, realmente no debería tener que hacer tanto trabajo como string.Contains.)

¿Ha intentado especificar una coincidencia ordinal? Eso puede hacer que sea mucho más rápido:

if (x.EndsWith(y, StringComparison.Ordinal)) 

Por supuesto, usted no debe hacer eso a menos que desee una comparación ordinal - esperas partidos culturalmente sensibles? (Los desarrolladores tienden a no considerar este tipo de cosas, y yo muy me incluyo firmemente en esa categoría.)

+0

En este el rendimiento del caso es un problema debido a cómo se usa la aplicación (maneja múltiples conjuntos de datos). – ilitirit

+0

@ilitirit: ¿Cuál es tu velocidad objetivo? ¿Qué tan rápido es lo suficientemente rápido?29ms para 100,000 cuerdas me suena bastante rápido. ¿Con qué frecuencia necesita su aplicación hacer esto? –

+0

En realidad es más rápido que 29ms pero las cadenas se colocan en listas diferentes, lo que se suma a la sobrecarga. La cultura no es importante porque las cadenas son esencialmente nombres de archivo generados por máquina. Estoy de acuerdo en que la diferencia en la velocidad no es mucho más de 1 iteración, pero esto opera en varios conjuntos (no estoy seguro de cuántos, depende de la hora del día/mes, etc.). Tendré que preguntarle a los poderes acerca de sus métricas de rendimiento. – ilitirit

0

¿Has probado el acceso directo? Es decir, puede hacer que un bucle esté atento a cadenas similares, podría ser más rápido que crear una subcadena y tener el mismo comportamiento.

int i,j; 
foreach(String testing in lists){ 
    i=0; 
    j=0; 
    int ok=1; 
    while(ok){ 
     i = testing.lenght - PATTERN.lenght; 
     if(i>0 && i<testing.lenght && testing[i] != PATTERN[j]) 
     ok = 0; 
     i++; 
     j++; 
    } 
    if(ok) return testing; 
} 

Además, si se trata de cadenas grandes, puede intentar usar hashs.

+0

Esto generalmente es una muy mala idea. Siempre debe usar las rutinas de Framework para la búsqueda de cadenas, o corre el riesgo de tener problemas debido a las rarezas de Unicode (combinación de caracteres, etc.). A menos que, por supuesto, 1) la velocidad sea más importante que la precisión, y 2) solo trabajará con caracteres ingleses. – erikkallen

+0

La idea de usar hashes no es probable que ayude; generar hashes requiere leer toda la cadena. Comparar hashes requiere leer solo tantos caracteres como sea necesario para descubrir que no hay coincidencia. – Brian

+0

por hash, i significa hashes en las subcadenas. Pero después de pensar que es claramente una mala forma de hacerlo. – ykatchou

4

No sé qué tan rápido es esto, pero esto es lo que haría?

static bool HasSuffix(string check, string suffix) 
{ 
    int offset = check.Length - suffix.Length; 
    for (int i = 0; i < suffix.Length; i++) 
    { 
     if (check[offset + i] != suffix[i]) 
     { 
      return false; 
     } 
    } 
    return true; 
} 

edición: OOPS x2

edición: Así que escribí mi propio punto de referencia ... sí cuenta esto? Ejecuta 25 ensayos de evaluación de un millón de cadenas y toma el promedio de la diferencia en el rendimiento. El puñado de veces que lo ejecuté fue consistentemente dando como resultado que CharCompare fue más rápido en ~ 10-40ms por encima de un millón de registros. Así que ese es un aumento enormemente sin importancia en la eficiencia (.000000001s/call) :) En general, dudo que importe el método que implemente.

class Program 
{ 
    volatile static List<string> strings; 
    static double[] results = new double[25]; 
    static void Main(string[] args) 
    { 
     strings = new List<string>(); 
     Random r = new Random(); 
     for (int rep = 0; rep < 25; rep++) 
     { 
      Console.WriteLine("Run " + rep); 
      strings.Clear(); 
      for (int i = 0; i < 1000000; i++) 
      { 
       string temp = ""; 
       for (int j = 0; j < r.Next(3, 101); j++) 
       { 
        temp += Convert.ToChar(
         Convert.ToInt32(
         Math.Floor(26 * r.NextDouble() + 65))); 
       } 
       if (i % 4 == 0) 
       { 
        temp += "abc"; 
       } 
       strings.Add(temp); 
      } 
      OrdinalWorker ow = new OrdinalWorker(strings); 
      CharWorker cw = new CharWorker(strings); 
      if (rep % 2 == 0) 
      { 
       cw.Run(); 
       ow.Run(); 
      } 
      else 
      { 
       ow.Run(); 
       cw.Run();      
      } 
      Thread.Sleep(1000); 
      results[rep] = ow.finish.Subtract(cw.finish).Milliseconds; 
     } 
     double tDiff = 0; 
     for (int i = 0; i < 25; i++) 
     { 
      tDiff += results[i]; 
     } 
     double average = tDiff/25; 
     if (average < 0) 
     { 
      average = average * -1; 
      Console.WriteLine("Char compare faster by {0}ms average", 
       average.ToString().Substring(0, 4)); 
     } 
     else 
     { 
      Console.WriteLine("EndsWith faster by {0}ms average", 
       average.ToString().Substring(0, 4)); 
     } 

    } 
} 



class OrdinalWorker 
{ 
    List<string> list; 
    int count; 
    public Thread t; 
    public DateTime finish; 
    public OrdinalWorker(List<string> l) 
    { 
     list = l; 
    } 

    public void Run() 
    { 
     t = new Thread(() => { 
      string suffix = "abc"; 
      for (int i = 0; i < list.Count; i++) 
      { 
       count = (list[i].EndsWith(suffix, StringComparison.Ordinal)) ? 
        count + 1 : count; 
      } 
      finish = DateTime.Now; 
     }); 
     t.Start(); 
    } 
} 

class CharWorker 
{ 
    List<string> list; 
    int count; 
    public Thread t; 
    public DateTime finish; 
    public CharWorker(List<string> l) 
    { 
     list = l; 
    } 

    public void Run() 
    { 
     t = new Thread(() => 
     { 
      string suffix = "abc"; 
      for (int i = 0; i < list.Count; i++) 
      { 
       count = (HasSuffix(list[i], suffix)) ? count + 1 : count; 
      } 
      finish = DateTime.Now; 
     }); 
     t.Start(); 
    } 

    static bool HasSuffix(string check, string suffix) 
    { 
     int offset = check.Length - suffix.Length; 
     for (int i = 0; i < suffix.Length; i++) 
     { 
      if (check[offset + i] != suffix[i]) 
      { 
       return false; 
      } 
     } 
     return true; 
    } 
} 
+0

Sería interesante ver si el optimizador elimina las comprobaciones fuera de límites en los dos accesos de cadena. –

+1

Me sorprendería que la implementación incorporada de 'EndsWith' no se pareciera demasiado a esto, aunque sospecho que probablemente sea' extern' -ed y/o 'inseguro' (y probablemente esté algo obstaculizado por el conocimiento de la cultura etc. también). – LukeH

+0

Er, así que supongo que esto supone que una cadena que se va a verificar nunca es más corta que el sufijo. Eso es un poco redundante teniendo en cuenta que una cadena más corta que el sufijo nunca podría contener el sufijo. – FlyingStreudel

13

Jon tiene toda la razón; esto no es potencialmente una comparación de manzanas a manzanas porque los diferentes métodos de cuerda tienen diferentes valores predeterminados para la sensibilidad cultera. Esté muy seguro de que está obteniendo la semántica de comparación que pretende en cada uno.

Además de la respuesta de Jon, agregaría que la pregunta relevante no es "¿cuál es la más rápida?" sino más bien "¿qué es demasiado lento?" ¿Cuál es su objetivo de rendimiento para este código? El método más lento aún encuentra el resultado en menos tiempo del que le toma a un proyector de películas avanzar al siguiente fotograma, y ​​obviamente eso no es notorio para los humanos. Si tu objetivo es que la búsqueda sea instantánea para el usuario, entonces ya terminaste; cualquiera de esos métodos funciona Si su objetivo es que la búsqueda tome menos de un milisegundo, ninguno de esos métodos funcionará; todos son órdenes de magnitud demasiado lentos. ¿Cuál es el presupuesto?

+4

+1 para "que es demasiado lento" muy bien redirige los pensamientos a la pregunta del presupuesto. –

0

No pretendo ser un experto en esta área, sin embargo me sentí obligado a al menos perfilar esto hasta cierto punto (sabiendo muy bien que mi escenario ficticio diferirá sustancialmente del suyo) y esto es lo que se le ocurrió:

parece, al menos para mí, EndsWith está a la cabeza con LastIndexOf viniendo constantemente en segundo lugar, algunos horarios son:

SubString: 00:00:00.0191877 
Contains:  00:00:00.0201980 
CompareInfo: 00:00:00.0255181 
EndsWith:  00:00:00.0120296 
LastIndexOf: 00:00:00.0133181 

Estos fueron recogidos de procesamiento de 100.000 cuerdas donde apareció el sufijo deseado en todos cadenas y para mí simplemente se hace eco de la respuesta de Jon (donde el beneficio es a la vez la velocidad y la descriptividad). Y el código utilizado para llegar a estos resultados:

class Program 
{ 
    class Profiler 
    { 
     private Stopwatch Stopwatch = new Stopwatch(); 

     public TimeSpan Elapsed { get { return Stopwatch.Elapsed; } } 

     public void Start() 
     { 
      Reset(); 
      Stopwatch.Start(); 
     } 

     public void Stop() 
     {    
      Stopwatch.Stop(); 
     } 

     public void Reset() 
     { 
      Stopwatch.Reset(); 
     } 
    } 

    static string suffix = "_sfx"; 
    static Profiler profiler = new Profiler(); 
    static List<string> input = new List<string>(); 
    static List<string> output = new List<string>(); 

    static void Main(string[] args) 
    { 
     GenerateSuffixedStrings(); 

     FindStringsWithSuffix_UsingSubString(input, suffix); 
     Console.WriteLine("SubString: {0}", profiler.Elapsed); 

     FindStringsWithSuffix_UsingContains(input, suffix); 
     Console.WriteLine("Contains:  {0}", profiler.Elapsed); 

     FindStringsWithSuffix_UsingCompareInfo(input, suffix); 
     Console.WriteLine("CompareInfo: {0}", profiler.Elapsed); 

     FindStringsWithSuffix_UsingEndsWith(input, suffix); 
     Console.WriteLine("EndsWith:  {0}", profiler.Elapsed); 

     FindStringsWithSuffix_UsingLastIndexOf(input, suffix); 
     Console.WriteLine("LastIndexOf: {0}", profiler.Elapsed); 

     Console.WriteLine(); 
     Console.WriteLine("Press any key to exit..."); 
     Console.ReadKey(); 
    } 

    static void GenerateSuffixedStrings() 
    { 
     for (var i = 0; i < 100000; i++) 
     { 
      input.Add(Guid.NewGuid().ToString() + suffix); 
     } 
    } 

    static void FindStringsWithSuffix_UsingSubString(IEnumerable<string> strings, string suffix) 
    { 
     output.Clear(); 
     profiler.Start(); 
     foreach (var s in strings) 
     { 
      if(s.Substring(s.Length - 4) == suffix) 
       output.Add(s); 
     } 
     profiler.Stop(); 
    } 

    static void FindStringsWithSuffix_UsingContains(IEnumerable<string> strings, string suffix) 
    { 
     output.Clear(); 
     profiler.Start(); 
     foreach (var s in strings) 
     { 
      if (s.Contains(suffix)) 
       output.Add(s); 
     } 
     profiler.Stop(); 
    } 

    static void FindStringsWithSuffix_UsingCompareInfo(IEnumerable<string> strings, string suffix) 
    { 
     var ci = CompareInfo.GetCompareInfo("en-GB"); 
     output.Clear(); 
     profiler.Start(); 
     foreach (var s in strings) 
     { 
      if (ci.IsSuffix(s, suffix)) 
       output.Add(s); 
     } 
     profiler.Stop(); 
    } 

    static void FindStringsWithSuffix_UsingEndsWith(IEnumerable<string> strings, string suffix) 
    { 
     output.Clear(); 
     profiler.Start(); 
     foreach (var s in strings) 
     { 
      if (s.EndsWith(suffix)) 
       output.Add(s); 
     } 
     profiler.Stop(); 
    } 

    static void FindStringsWithSuffix_UsingLastIndexOf(IEnumerable<string> strings, string suffix) 
    { 
     output.Clear(); 
     profiler.Start(); 
     foreach (var s in strings) 
     { 
      if (s.LastIndexOf(suffix) == s.Length - 4) 
       output.Add(s); 
     } 
     profiler.Stop(); 
    } 
} 

EDIT:

Como se ha comentado, he tratado esto de nuevo con sólo algunas de las cadenas que tienen un sufijo aplicado y estos son los resultados:

SubString: 00:00:00.0079731 
Contains:  00:00:00.0243696 
CompareInfo: 00:00:00.0334056 
EndsWith:  00:00:00.0196668 
LastIndexOf: 00:00:00.0229599 

El método generador de secuencia se actualiza como sigue, para producir las cadenas:

static void GenerateSuffixedStrings() 
    { 
     var nxt = false; 
     var rnd = new Random();    
     for (var i = 0; i < 100000; i++) 
     { 
      input.Add(Guid.NewGuid().ToString() + 
       (rnd.Next(0, 2) == 0 ? suffix : string.Empty)); 
     } 
    } 

Además, esta tendencia continúa, si ninguno de la cadena tiene un sufijo:

SubString: 00:00:00.0055584 
Contains:  00:00:00.0187089 
CompareInfo: 00:00:00.0228983 
EndsWith:  00:00:00.0114227 
LastIndexOf: 00:00:00.0199328 

Sin embargo, esta brecha se acorta de nuevo cuando la asignación de una cuarta parte de las entradas de un sufijo (el primer trimestre, a continuación, la clasificación a randomise la cobertura):

SubString: 00:00:00.0302997 
Contains:  00:00:00.0305685 
CompareInfo: 00:00:00.0306335 
EndsWith:  00:00:00.0351229 
LastIndexOf: 00:00:00.0322899 

¿Conclusión?OMI, y de acuerdo con Jon, EndsWith parece el camino a seguir (basado en esta prueba limitada, de todos modos).

Además Editar:

para curar la curiosidad de Jon me encontré con algunas pruebas más en EndsWith, con y sin comparación Ordinal cadena ...

En 100.000 cuerdas con un cuarto de ellos sufijo:

EndsWith:   00:00:00.0795617 
OrdinalEndsWith:  00:00:00.0240631 

En 1,000,000 cuerdas con un cuarto de ellos sufijo:

EndsWith:   00:00:00.5460591 
OrdinalEndsWith:  00:00:00.2807860 

En 10.000.000 cuerdas con una cuarta parte de ellos con el sufijo:

EndsWith:   00:00:07.5889581 
OrdinalEndsWith:  00:00:03.3248628 

Tenga en cuenta que sólo corrió la última prueba una vez como la generación de las cuerdas demostró este portátil está en la necesidad de un reemplazo

+0

Todas sus cadenas tienen sufijos. Cuando cambio el código para que solo dé la mitad de los sufijos obtengo resultados similares a los que publiqué en mi máquina doméstica (no estoy trabajando en este momento). – ilitirit

+0

Correcto, como expliqué. Intenté esto de nuevo con sufijos aplicados 'aleatoriamente 'y obtuve conclusiones muy similares, la mayor diferencia es que, como usted mencionó,' SubString' constantemente sale en la parte superior. Todavía tendría que estar de acuerdo con Jon por la otra razón, aunque no sea la velocidad. –

+0

¿Qué sucede si usa 's.EndsWith (sufijo, StringComparison.Ordinal)'? –

6

Eché un vistazo a su código de referencia y, francamente, parece dudoso.

Está midiendo todo tipo de cosas extrañas junto con lo que quiere medir; está midiendo el costo del foreach y la adición a una lista, que pueden tener costos del mismo orden de magnitud que el que está intentando probar.

Además, no está tirando la primera carrera; recuerde, el compilador JIT va a escribir el código que llama el primer tiempo a través del ciclo, y va a estar activo y listo para pasar el segundo tiempo, por lo que sus resultados estarán sesgados; estás promediando una cosa potencialmente muy grande con muchas cosas pequeñas. En el pasado, cuando hice esto, descubrí situaciones en las que el tiempo de jit dominaba el tiempo de todo lo demás. Es eso realista? ¿Quiere decir que mide el tiempo de jit o debería considerarse como parte del promedio?

-1

Aquí hay mucha información útil. Quería señalar que si su sufijo es corto, podría ser incluso más rápido mirar los últimos caracteres individualmente. Mi versión modificada del código de referencia en cuestión está aquí: http://pastebin.com/6nNdbEvW. Da resultados de tesis:

  1. última igualdad carbón: 1,52 ms (50000)
  2. última igualdad 2 Char: 1,56 ms (50000)
  3. EndsWith utilizando StringComparison.Ordinal: 3,75 ms (50000)
  4. contiene: 11.10 m (50000)
  5. lastIndexOf: 14.85 m (50000)
  6. IsSuffix: 11,30 ms (50000)
  7. subcadena compare: 17,69 ms (50000)