Requête de données de base lente

Question

Quel est le secret pour extraire des éléments correspondant aux caractères tapés dans la barre de recherche qui réagissent instantanément? Par exemple, si je tape une lettre "W" dans la barre de recherche, toutes les phrases qui contiennent une lettre "W" dans n'importe quelle position de caractère dans la phrase sont renvoyées immédiatement. Par conséquent, si une base de données de 20 000 phrases contient 500 phrases avec la lettre "W", elles apparaîtraient dès que l'utilisateur a tapé le premier caractère. Puis, lorsque des caractères supplémentaires sont tapés, la liste devient automatiquement plus courte.

Je peux envoyer des requêtes à un serveur SQL de l'iPhone et obtenir ce type de réponse, cependant, peu importe ce que nous essayons et en tenant compte des suggestions des autres utilisateurs, nous ne pouvons toujours pas obtenir un bon temps de réponse. base de données localement sur l'iPhone.

Je sais que cette performance est disponible, car il existe de nombreuses autres applications qui affichent les résultats dès que vous commencez à taper.

Veuillez noter que ce n'est pas la même chose que d'indexer tous les mots de chaque phrase, car cela ne fera qu'appeler des correspondances où le mot commence par le caractère tapé. Dans ce cas, nous recherchons des caractères dans les mots .

Answer 1

Si vous souhaitez vous éloigner de la base de données, vous pouvez utiliser un arbre de suffixes généralisé avec tous les termes de vos phrases. Vous pouvez construire dans un arbre de suffixes en temps linéaire et, je crois, l'utiliser pour trouver toutes les occurrences d'une sous-chaîne très rapidement. Le web a beaucoup de pages sur les arbres de suffixes et les tableaux de suffixes. Wikipedia est probablement un bon point de départ.

Answer 2

J'ai un schéma amusant pour vous. Vous pouvez créer un index des caractères qui existent dans chaque phrase via un entier de 32 bits. Retournez les bits [0-25] pour représenter les caractères (insensibles à la casse) a-z qui existent dans la phrase. Construire une seconde bitmap de la chaîne de requête. Vous pouvez maintenant effectuer des comparaisons via des opérations au niveau du bit (& et |) pour déterminer les correspondances. C'est très rapide et croyez-le ou non SQLite supporte réellement les opérations au niveau du bit dans les requêtes - vous pouvez même utiliser ce schéma pour aller directement à la base de données. J'ai un code de travail qui fait cela intégré dans l'une de nos applications iPhone - Alphagram.

Answer 3

Je pense que le filtrage des résultats asynchrones est la réponse. Au lieu de mettre à jour les résultats de la recherche chaque fois que l'utilisateur tape un nouveau caractère, placez la requête db sur un thread d'arrière-plan lorsque le premier caractère est tapé. Si un nouveau caractère est tapé avant la fin de la requête, annulez l'ancienne requête et commencez-en une nouvelle. Enfin, vous arriverez au point où l'utilisateur arrête de taper assez longtemps pour que la requête retourne. De cette façon, la requête elle-même ne bloque jamais la frappe de l'utilisateur. Je crois que la classe UISearchDisplayController offre ce type de recherche asynchrone, bien que ce soit à vous de décider si vous voulez utiliser cette classe ou simplement adopter le motif de conception asynchrone.