¿Cuál es la forma más rápida de buscar cadenas en Objective-C?

Estoy implementando una especie de autocompletado para una aplicación de iOS. Los datos que estoy usando para los valores de autocompletar son un archivo de texto separado por comas con aproximadamente 100.000 cadenas. Esto es lo que estoy haciendo ahora:¿Cuál es la forma más rápida de buscar cadenas en Objective-C?

leer el archivo de texto, y crear un NSArray con 100.000 NSString.
A medida que el usuario escribe, haga [array containsObject:text]

Seguramente hay una manera mejor/más rápido para hacer esto de búsqueda. ¿Alguna idea?

Fuente

2012-07-20 user1007895

Puede intentar omita las cadenas que ni siquiera coinciden con la primera letra, no tiene sentido buscar manzanas o yogur si su palabra es cebra. No estoy seguro de la mejor manera de implementar esto, ¿quizás una matriz multidimensional? La primera dimensión podría ser la primera letra, la segunda segunda letra, etc., hasta que aparezca la tercera o la cuarta letra, entonces podría contener el resto de la palabra. –

Si no necesita ordenar, creo que los conjuntos son más rápidos al verificar si contiene un objeto o no. Sin embargo, todavía no está optimizado para cuerdas.Probablemente deberías buscar cosas como árboles binarios, etc. si necesitas crear un código personalizado, el enfoque general sería similar sin importar la plataforma/idioma con el que estés trabajando. –

Hay * siempre * una manera más rápida. ¿Estás viendo retraso en tu UI? He hecho exactamente lo mismo para autocompletar (con una matriz de entrada más pequeña) y no tuve ningún retraso visible, a pesar del ingenioso algoritmo de búsqueda. – kubi

¡Absolutamente, lo hay! Sin embargo, no está "en Objective-C": lo más probable es que necesites codificarlo tú mismo.

La idea es convertir su lista de cadenas en suffix tree, una estructura de datos que le permite buscar por prefijo muy rápidamente. La búsqueda de posibles terminaciones en un árbol de sufijos es muy rápida, pero la estructura en sí misma no es fácil de construir. Una búsqueda rápida en Internet reveló que no hay una implementación disponible en el Objetivo C, pero es posible que pueda port an implementation in another language, use a C implementation, o incluso que escriba la suya propia si no está especialmente presionado por el tiempo.

Quizás un enfoque más fácil sería ordenar las cadenas alfabéticamente y ejecutar una búsqueda binaria en el prefijo que se ha ingresado hasta el momento. Aunque no es tan eficiente como un árbol de sufijos, el método de matriz ordenada será aceptable para cadenas de 100K, ya que se llega al punto correcto en menos de diecisiete cheques.

Fuente

2012-07-20 20:42:34 dasblinkenlight

+1 para señalar Objective-C es C y no debe temer bajar a C cuando se analizan las tareas de rendimiento intensivo :) También pondré en segundo lugar el árbol binario que probablemente sea el más fácil de implementar. – Taum

+1 encanta su respuesta – Omarj

NDTrie (https://github.com/nathanday/ndtrie) y PJTernarySearchTree (https://github.com/peakji/PJTernarySearchTree) son precisamente esto en Objective-C! –

La más simple es probablemente la búsqueda binaria. Ver -[NSArray indexOfObject:inSortedRange:options:usingComparator:].

En particular, me gustaría probar algo como esto:

pre-ordenar la matriz que se guarda en el fichero de
cuando se carga la matriz, posiblemente @selector(compare:) (si está preocupado al respecto ser accidentalmente sin clasificar o cambiar el orden de clasificación Unicode para algunos casos extremos). Esto debería ser aproximadamente O (n) suponiendo que la matriz ya está ordenada en su mayoría.
para encontrar la primera coincidencia potencial, [array indexOfObject:searchString inSortedRange:(NSRange){0,[array count]} options:NSBinarySearchingInsertionIndex|NSBinarySearchingFirstEqual usingComparator:@selector(compare:)]
caminar por la matriz hasta que las entradas ya no contienen searchString que como prefijo. Es posible que desee hacer comparaciones/diacrítica/ancho insensibles caso para determinar si se trata de un prefijo (NSAnchoredSearch | NSCaseInsensitiveSearch | NSDiacriticInsensitiveSearch | NSWidthInsensitiveSearch)

Esto no puede "correctamente" manejar todas las configuraciones regionales (en turco, en particular), pero tampoco sustituirá a compare: con localizedCompare:, ni será un plegado ingenuo. (Tiene solo 9 líneas de longitud, pero tomó aproximadamente un día de trabajo para hacerlo bien y tiene alrededor de 40 líneas de código y 200 líneas de prueba, por lo que probablemente no debería compartirlo aquí).

Fuente

2012-07-20 20:59:14

¿Cuál es la forma más rápida de buscar cadenas en Objective-C?

Respuesta

Cuestiones relacionadas