Comment implémenter un dictionnaire "avec un tuple Python" comme clé en C++?

Question

J'ai actuellement du code python que je voudrais porter en C++ car il est actuellement plus lent que je ne le voudrais. Le problème est que j'utilise un dictionnaire dans lequel la clé est un tuple composé d'un objet et d'une chaîne (par exemple (obj, "mot")). Comment diable puis-je écrire quelque chose de similaire en C++? Peut-être que mon algorithme est horrible et qu'il y a un moyen de le rendre plus rapide sans avoir recours au C++?

L'algorithme entier ci-dessous pour des raisons de clarté. Le dictionnaire "post_score" est le problème.

def get_best_match_best(search_text, posts): 
    """ 
    Find the best matches between a search query "search_text" and any of the 
    strings in "posts". 

    @param search_text: Query to find an appropriate match with in posts. 
    @type search_text: string 
    @param posts: List of candidates to match with target text. 
    @type posts: [cl_post.Post] 
    @return: Best matches of the candidates found in posts. The posts are ordered 
    according to their rank. First post in list has best match and so on. 
    @returntype: [cl_post.Post] 
    """ 
    from math import log 

    search_words = separate_words(search_text) 
    total_number_of_hits = {} 
    post_score = {} 
    post_size = {} 
    for search_word in search_words: 
     total_number_of_hits[search_word] = 0.0 
     for post in posts: 
      post_score[(post, search_word)] = 0.0 
      post_words = separate_words(post.text) 
      post_size[post] = len(post_words) 
      for post_word in post_words: 
       possible_match = abs(len(post_word) - len(search_word)) <= 2 
       if possible_match: 
        score = calculate_score(search_word, post_word) 
        post_score[(post, search_word)] += score 
        if score >= 1.0: 
         total_number_of_hits[search_word] += 1.0 

    log_of_number_of_posts = log(len(posts)) 
    matches = [] 
    for post in posts: 
     rank = 0.0 
     for search_word in search_words: 
      rank += post_score[(post, search_word)] * \ 
        (log_of_number_of_posts - log(1.0 + total_number_of_hits[search_word])) 
     matches.append((rank/post_size[post], post)) 
    matches.sort(reverse=True) 
    return [post[1] for post in matches] 

Answer 1

map<pair<..., string>, ...> si vous êtes sur l'utilisation hellbent C++ pour cela.

Answer 2

pour une fois, vous appelez separ_words (post.text) pour chaque mot-search dans search_words. Vous devez appeler separ_words une seule fois pour chaque post dans posts.

C'est, plutôt que:

for search_word in search_words: 
    for post in posts: 
     # do heavy work 

vous devriez plutôt avoir:

for post in posts: 
    # do the heavy works 
    for search_word in search_words: 
     ... 

Si, comme je le soupçonnais, que separate_words font beaucoup de manipulations de cordes, ne pas oublier que la chaîne les manipulations sont relativement chères en python puisque la chaîne est immuable.

Une autre amélioration que vous pouvez faire, c'est que vous n'avez pas besoin de comparer chaque mot de search_words avec chaque mot de post_words. Si vous conservez le tableau search_words et post_words en fonction de la longueur du mot, vous pouvez utiliser une technique de fenêtre glissante. En effet, search_word ne correspondra à un post_word que si la différence de longueur est inférieure à 2, alors il suffit de vérifier la différence de longueur de la fenêtre, en réduisant ainsi le nombre de mots à vérifier, par exemple:

search_words = sorted(search_words, key=len) 
g_post_words = collections.defaultdict(list) # this can probably use list of list 
for post_word in post_words: 
    g_post_words[len(post_word)].append(post_word) 

for search_word in search_words: 
    l = len(search_word) 
    # candidates = itertools.chain.from_iterable(g_post_words.get(m, []) for m in range(l - 2, l + 3)) 
    candidates = itertools.chain(g_post_words.get(l - 2, []), 
           g_post_words.get(l - 1, []), 
           g_post_words.get(l , []), 
           g_post_words.get(l + 1, []), 
           g_post_words.get(l + 2, []) 
           ) 
    for post_word in candidates: 
     score = calculate_score(search_word, post_word) 
     # ... and the rest ... 

(ce code ne fonctionnera probablement pas tel quel, c'est juste pour illustrer l'idée)