Anagramas de grupo Leetcode
Enlace aquí
Incluiré una solución en Python y C ++ y puedes revisar una. Lo que más me interesa es revisar el código C ++, que es algo que comencé a aprender recientemente; aquellos que no conocen C ++ pueden revisar el código Python. Ambas soluciones comparten una lógica similar, por lo que la revisión se aplicará a cualquiera.
Planteamiento del problema
Dada una matriz de cadenas de cadenas, agrupe los anagramas. Puede devolver la respuesta en cualquier orden. Un anagrama es una palabra o frase formada reordenando las letras de una palabra o frase diferente, normalmente usando todas las letras originales exactamente una vez.
Ejemplo:
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
Ambas soluciones implican crear un mapeo de caracteres de palabras ordenados alfabéticamente a la palabra correspondiente y cada palabra encontrada que coincida se agrega al grupo correspondiente. Y como se sugirió anteriormente en mis publicaciones anteriores no confiar en las estadísticas de leetcode porque son inexactas, cronometré las soluciones de c ++ y python para 1,000,000 de ejecuciones en el mismo conjunto de palabras para ver qué surge. Sorprendentemente, la solución de Python supera en rendimiento a la solución de C ++ casi en 2x. Los tiempos resultantes ~ = 10, 20 segundos para python y c ++ respectivamente cuando se ejecutan en mi i5 2.7 GHZ mbp. Dado que ambas implementaciones son casi similares, ¿no debería C ++ ser 10 veces más rápido 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)
Resultados:
[['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";
}
Resultados:
abets baste beats
tabu
actress casters
allergy gallery largely
Calculating time for 1000000 runs ...
22 seconds
Respuestas
C ++
if (word_groups.contains(sorted_word)) {
word_groups[sorted_word].push_back(word);
} else {
word_groups[sorted_word] = {word};
}
containsrealiza una búsqueda de la palabra en word_groups. Luego operator[]hace la misma búsqueda por segunda vez.
Podemos reemplazar lo anterior con solo:
word_groups[sorted_word].push_back(word);
( operator[]inserta un valor construido por defecto (es decir, un vacío vector<std::string>) si no está presente en el mapa).
No es necesario copiar el word_groupsmapa en un vector para devolverlo get_groups(). Podemos devolver el mapa en sí.
Luego, en la función principal, la iteramos con:
for (const auto &group: groups) { // group is a pair (.first is the key, .second is the values)
for (const auto &word: group.second)
...
No necesitamos almacenar la cadena en sí en el mapa, podemos almacenar el índice de la cadena en el vector de entrada. (es decir map<string, vector<std::size_t>>).