Python inversé indice efficacité

Question

J'écris du code Python pour mettre en œuvre certains des concepts que j'ai récemment appris, liés à des index inversés/listes de messages. Je suis relativement nouveau à Python et j'ai quelques difficultés à comprendre son efficacité dans certains cas.

En théorie, la création d'un index inversé d'un ensemble de documents D, chacun avec un identifiant unique doc_id devrait impliquer:

1. Parsing/effectuer une analyse lexicale de chaque document D
2. suppression de termes courants, l'exécution découlant etc.
3. Création d'une liste de toutes les paires (word,doc_id)
4. tri de la liste
5. doublons se condensant dans {word:[set_of_all_doc_ids]} (index inversé)

étape 5 est souvent réalisée en ayant un dictionnaire contenant le mot avec des méta-données (fréquence de terme, décalages d'octets) et un pointeur vers la liste des messages (liste de documents, il se produit in) . La liste d'écritures est souvent mise en œuvre en tant que structure de données qui permet une insertion aléatoire efficace, c'est-à-dire une liste chaînée. Mon problème est que Python est un langage de plus haut niveau, et l'utilisation directe de choses comme les pointeurs de mémoire (et donc les listes liées) semble être hors de portée. J'optimise avant le profilage car pour des ensembles de données très volumineux, il est déjà connu que l'efficacité doit être maximisée pour conserver toute sorte de capacité à calculer l'index dans un délai raisonnable.

Plusieurs autres messages existent ici sur SO à propos des index inversés Python et, comme MY implémentation actuelle, ils utilisent des clés de mappage de dictionnaires pour les listes (ou ensembles). Faut-il s'attendre à ce que cette méthode ait des performances similaires à celles d'un langage permettant le codage direct de pointeurs vers des listes chaînées?

Answer 1

Il y a un certain nombre de choses à dire:

1. Si accès aléatoire est nécessaire pour une mise en œuvre de liste particulière, une liste chaînée est pas optimale (quel que soit le langage de programmation utilisé). Pour accéder à l'élément ith de la liste, une liste chaînée vous oblige à parcourir tout le chemin de l'élément 0 à l'élément ith. Au lieu de cela, la liste devrait être stockée comme un bloc continu (ou plusieurs gros blocs s'il est très long). Les listes Python [...] sont stockées de cette façon, donc pour commencer, une liste Python devrait être assez bonne.

2. En Python, toute cessiona = b d'un objet b qui ne soit pas un type de données de base (tels que int ou float), est réalisée en interne par passer un pointeur et incrémenter le compteur de référence -b . Donc, si b est une liste ou un dictionnaire (ou une classe définie par l'utilisateur, d'ailleurs), cela n'est en principe pas très différent de passer un pointeur en C ou C++.

3. Cependant, il y a évidemment une surcharge causée par a) le comptage des références et b) l'enlèvement des ordures. Si la mise en œuvre est à des fins d'étude, c.-à-d.pour mieux comprendre les concepts d'indexation inversée, je ne m'inquiéterais pas de cela. Mais pour une implémentation sérieuse et hautement optimisée, l'utilisation de Python pur (plutôt que, par exemple, C/C++ intégré dans Python) n'est pas conseillée. Comme vous optimisez l'implémentation de votre liste d'écritures, vous verrez probablement le besoin de: a) faire des insertions aléatoires, b) le garder trié et c) le garder compressé - tout en même temps. À ce stade, la liste Python standard ne sera plus suffisante, et vous pouvez envisager d'implémenter une représentation de liste plus optimisée dans C/C++ et l'incorporer dans Python. Cependant, même alors, coller à Python pur serait probablement possible. Par exemple. vous pouvez utiliser une grande chaîne pour implémenter la liste et utiliser itertools et buffer pour accéder à des parties spécifiques d'une manière qui est, dans une certaine mesure, similaire à l'arithmétique du pointeur.

4. Une chose que vous devez toujours garder à l'esprit lorsqu'ils traitent avec les chaînes en Python est que, malgré ce que je dit plus haut au sujet des opérations d'affectation, le substring opération text[i:j] consiste à créer une réelle (profonde) copie la sous-chaîne, plutôt que d'incrémenter simplement un nombre de références. Cela peut être évité en utilisant le type de données buffer mentionné ci-dessus.

Answer 2

Vous pouvez voir le code et la documentation pour l'index inversé en Python à: http://www.ssiddique.info/creation-of-inverted-index-and-use-of-ranking-algorithm-python-code.html

Bientôt, je vais coder en C++ ..