Leetcodeグループのアナグラム
PythonとC ++のソリューションを含めますが、レビューすることができます。私は最近学び始めたC ++コードのレビューに主に興味があります。C ++を知らない人は、Pythonコードを確認できます。どちらのソリューションも同様のロジックを共有しているため、レビューはすべてに適用されます。
問題文
文字列strsの配列が与えられた場合、アナグラムをグループ化します。回答は任意の順序で返すことができます。アナグラムは、別の単語またはフレーズの文字を再配置することによって形成される単語またはフレーズであり、通常、すべての元の文字を1回だけ使用します。
例：
Input: strs = ["eat","tea","tan","ate","nat","bat"]
Output: [["bat"],["nat","tan"],["ate","eat","tea"]]
どちらのソリューションも、アルファベット順に並べられた単語文字から対応する単語へのマッピングを作成することを含み、一致する各単語が対応するグループに追加されます。また、以前の投稿で、leetcodeの統計が不正確であるために依存しないことが提案されていたため、同じ単語セットで1,000,000回実行するようにc ++とpythonの両方のソリューションのタイミングを調整して、何が表示されるかを確認しました。驚いたことに、PythonソリューションはC ++ソリューションをほぼ2倍上回っています。私のi52.7 GHZ mbpで実行した場合、結果として得られる時間は、PythonとC ++でそれぞれ〜= 10、20秒です。両方の実装がほぼ類似していることを考えると、c ++はPythonの10倍高速であるべきではありませんか？
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)
結果：
[['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";
}
結果：
abets baste beats
tabu
actress casters
allergy gallery largely
Calculating time for 1000000 runs ...
22 seconds
回答
C ++
if (word_groups.contains(sorted_word)) {
word_groups[sorted_word].push_back(word);
} else {
word_groups[sorted_word] = {word};
}
contains内の単語を検索しword_groupsます。次にoperator[]、同じ検索をもう一度実行します。
上記を次のように置き換えることができます。
word_groups[sorted_word].push_back(word);
（マップに存在しない場合はoperator[]、デフォルトで作成された値（つまり空vector<std::string>）を挿入します）。
word_groupsマップをベクトルにコピーしてから返す必要はありませんget_groups()。マップ自体を返すだけです。
次に、メイン関数で次のように繰り返します。
for (const auto &group: groups) { // group is a pair (.first is the key, .second is the values)
for (const auto &word: group.second)
...
文字列自体をマップに保存する必要はありません。文字列のインデックスを入力ベクトルに保存できます。（すなわちmap<string, vector<std::size_t>>）。