¿Qué algoritmo utiliza .Net para buscar un patrón en una cadena?

Estoy estudiando algoritmos de búsqueda de cadenas ahora y me pregunto qué algoritmo se utiliza para .NET String.Contains function por ejemplo. Reflector muestra que esta función se usa pero no tengo idea de lo que significa su nombre.¿Qué algoritmo utiliza .Net para buscar un patrón en una cadena?

private static extern int InternalFindNLSStringEx(IntPtr handle, string localeName, int flags, string source, int sourceCount, int startIndex, string target, int targetCount);

Fuente

2010-04-06 Hun1Ahpu

posible duplicado de [¿Cómo funciona String.Contains?] (Http://stackoverflow.com/questions/3769519/how-does-string-contains-work) –

Es solo la implementación ingeniosa de búsqueda de cadenas mediante un ciclo anidado sobre el texto y el patrón, con el tiempo de ejecución O (n · m).

En particular, MSDN no especifica el rendimiento de este método, por lo que no es seguro asumir un mejor rendimiento.

Además, la mayoría de patrones avanzados métodos de búsqueda son muy especializados para determinados tipos de cadena y si bien no son mejores algoritmos de búsqueda de propósito general, la aplicación de una en String.IndexOf es algo así como una optimización innecesaria.

La razón es simple: si requiere una búsqueda de patrones eficiente, entonces implementará la suya de todos modos, adaptada a medida para adaptarse a sus datos particulares. Por lo tanto, no es necesario implementar algo sofisticado en la biblioteca de propósito general.

A partir de 2016 (con el código fuente CLR Core ahora disponible), la aplicación sigue utilizando un bucle anidado ingenuo. Esto se implementa en NewApis::IndexOfString y NewApis::FastIndexOfString, que se llaman (a través de InternalFindNLSStringEx) desde las funciones String.Contains y String.IndexOf administradas.

Fuente

2010-04-06 10:48:57

Gracias por una respuesta razonable. – Hun1Ahpu

No podría estar menos de acuerdo; ¿por qué implementaría su propia búsqueda general de cadenas si ya hay una en la biblioteca? Además, los algoritmos de búsqueda de cadenas son excepciones, ya que existe Boyer-Moore que es tan agradable (todo pro no con) que se considera referencia estándar. Lo que quiero decir es que generalmente elegir un algoritmo para una biblioteca puede ser muy difícil, pero con cadenas no esperaría que se usara nada menos en ninguna biblioteca que valga la pena. Por favor corrígeme si estoy equivocado. – Unreason

@Unreason: en la mayoría de las aplicaciones, simplemente no importa. El uso de 'Buscar' para cualquier cosa que no sean tareas triviales da como resultado una complicada lógica y un exceso de código de todos modos. Es mejor usar expresiones regulares o un analizador. Donde * haz * necesitas usar el patrón de búsqueda y donde importa, rara vez lidias con Unicode. A menudo es altamente especializado como secuencias de ADN. Y * por supuesto * no lo programa usted mismo; usa bibliotecas listas para usar. Pero estos son especializados y no pertenecen a un marco general como el .NET framework. –

¿Por qué utilizar el reflector cuando el source code está disponible?

Fuente

2010-04-06 10:45:29

Que todavía no muestra ningún código nativo/interno, como lo hace este método. – leppie

Es cierto, solo el código .Net está disponible, erf –

Estaba intentando usar el código fuente pero no me muestra el algoritmo. ¿Estoy haciendo algo mal o no hay forma de ver la implementación real? – Hun1Ahpu

No pude encontrar ese trozo de método, pero mi mejor opción es que sea un plegado de casos específico local para búsquedas que no distinguen entre mayúsculas y minúsculas.

Fuente

2010-04-06 10:48:58 leppie

¿Qué algoritmo utiliza .Net para buscar un patrón en una cadena?

Respuesta

Cuestiones relacionadas