Anagrammes du groupe Leetcode

Nov 23 2020

Lien ici

Je vais inclure une solution en Python et C ++ et vous pourrez en examiner une. Je suis surtout intéressé par la révision du code C ++, une chose que j'ai récemment commencé à apprendre; ceux qui ne connaissent pas C ++ peuvent consulter le code Python. Les deux solutions partagent une logique similaire, la révision s'appliquera donc à toutes.


Énoncé du problème

Étant donné un tableau de chaînes de chaînes, regroupez les anagrammes. Vous pouvez renvoyer la réponse dans n'importe quel ordre. Un anagramme est un mot ou une phrase formé en réorganisant les lettres d'un mot ou d'une phrase différent, en utilisant généralement toutes les lettres originales exactement une fois.

Exemple:

Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]

Les deux solutions impliquent la création d'un mappage des caractères de mot classés par ordre alphabétique au mot correspondant et chaque mot rencontré qui correspond, est ajouté au groupe correspondant. Et comme il a été suggéré plus tôt dans mes articles précédents de ne pas se fier aux statistiques de leetcode car elles sont inexactes, j'ai chronométré les solutions c ++ et python pour 1000000 d'exécutions sur le même ensemble de mots pour voir ce qui se passe. Étonnamment, la solution python surpasse la solution c ++ presque par 2x. Les temps résultants ~ = 10, 20 secondes pour python et c ++ respectivement lorsqu'ils sont exécutés sur mon i5 2,7 GHZ mbp. Étant donné que les deux implémentations sont presque similaires, C ++ ne devrait-il pas être 10 fois plus rapide que Python?

group_anagrams.py

from collections import defaultdict
from time import perf_counter


def group(words):
    groups = defaultdict(lambda: [])
    for word in words:
        groups[tuple(sorted(word))].append(word)
    return groups.values()


def time_grouping(n, words):
    print(f'Calculating time for {n} runs ...')
    t1 = perf_counter()
    for _ in range(n):
        group(words)
    print(f'Time: {perf_counter() - t1} seconds')


if __name__ == '__main__':
    w = [
        'abets',
        'baste',
        'beats',
        'tabu',
        'actress',
        'casters',
        'allergy',
        'gallery',
        'largely',
    ]
    print(list(group(w)))
    time_grouping(1000000, w)

Résultats:

[['abets', 'baste', 'beats'], ['tabu'], ['actress', 'casters'], ['allergy', 'gallery', 'largely']]
Calculating time for 1000000 runs ...
Time: 8.801584898000002 seconds

group_anagrams.h

#ifndef LEETCODE_GROUP_ANAGRAMS_H
#define LEETCODE_GROUP_ANAGRAMS_H

#include <vector>
#include <string>

std::vector<std::vector<std::string>> get_groups(const std::vector<std::string> &words);

#endif //LEETCODE_GROUP_ANAGRAMS_H

group_anagrams.cpp

#include "group_anagrams.h"
#include <algorithm>
#include <chrono>
#include <iostream>
#include <map>


std::vector<std::vector<std::string>>
get_groups(const std::vector<std::string> &words) {
    std::map<std::string, std::vector<std::string>> word_groups;
    std::vector<std::vector<std::string>> groups;
    for (const auto &word: words) {
        auto sorted_word = word;
        std::sort(sorted_word.begin(), sorted_word.end());
        if (word_groups.contains(sorted_word)) {
            word_groups[sorted_word].push_back(word);
        } else {
            word_groups[sorted_word] = {word};
        }
    }
    groups.reserve(word_groups.size());
    for (auto const &imap: word_groups)
        groups.push_back(imap.second);
    return groups;
}


int main() {
    std::vector<std::string> words{
            "abets", "baste", "beats", "tabu", "actress", "casters", "allergy",
            "gallery", "largely"
    };
    auto groups = get_groups(words);
    for (const auto &group: groups) {
        for (const auto &word: group)
            std::cout << word << ' ';
        std::cout << '\n';
    }
    size_t n_times{1000000};
    std::cout << "\nCalculating time for " << n_times << " runs ..." << '\n';
    auto t1 = std::chrono::high_resolution_clock::now();
    while (n_times > 0) {
        get_groups(words);
        n_times--;
    }
    auto t2 = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::seconds>(
            t2 - t1).count();
    std::cout << duration << " seconds";
}

Résultats:

abets baste beats 
tabu 
actress casters 
allergy gallery largely 

Calculating time for 1000000 runs ...
22 seconds

Réponses

1 user673679 Nov 23 2020 at 09:20

C ++

    if (word_groups.contains(sorted_word)) {
        word_groups[sorted_word].push_back(word);
    } else {
        word_groups[sorted_word] = {word};
    }

containseffectue une recherche du mot dans word_groups. Puis operator[]fait cette même recherche une deuxième fois.

Nous pouvons remplacer ce qui précède par juste:

    word_groups[sorted_word].push_back(word);

( operator[]insère une valeur construite par défaut (c'est-à-dire vide vector<std::string>) si elle n'est pas présente dans la carte).


Nous n'avons pas besoin de copier la word_groupscarte dans un vecteur pour la renvoyer get_groups(). Nous pouvons simplement renvoyer la carte elle-même.

Ensuite, dans la fonction principale, nous l'itérons avec:

for (const auto &group: groups) { // group is a pair (.first is the key, .second is the values)
    for (const auto &word: group.second)
        ...

Nous n'avons pas besoin de stocker la chaîne elle-même dans la carte, nous pouvons stocker l'index de la chaîne dans le vecteur d'entrée. (ie map<string, vector<std::size_t>>).