Leetcode grup anagramları

Question

Buraya bağlantı

Python ve C ++ 'da bir çözüm ekleyeceğim ve bir tane inceleyebilirsiniz. Çoğunlukla, yeni öğrenmeye başladığım bir şey olan C ++ kodunu gözden geçirmekle ilgileniyorum; C ++ 'yı bilmeyenler Python kodunu inceleyebilirler. Her iki çözüm de benzer mantığı paylaşır, bu nedenle inceleme herhangi biri için geçerli olacaktır.

---

Sorun bildirimi

Bir dizi dizge verildiğinde, anagramları birlikte gruplayın. Cevabı herhangi bir sırayla iade edebilirsiniz. Bir Anagram, farklı bir kelime veya cümlenin harflerinin yeniden düzenlenmesiyle, tipik olarak tüm orijinal harflerin tam olarak bir kez kullanılmasıyla oluşturulan bir kelime veya ifadedir.

Misal:

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

Her iki çözüm de alfabetik olarak sıralanan kelime karakterlerinden karşılık gelen kelimeye bir eşleme oluşturmayı içerir ve bir eşleşme olan karşılaşılan her bir kelime ilgili gruba eklenir. Ve önceki yazılarımda daha önce yanlış oldukları için leetcode istatistiklerine güvenmemem önerildiğinden, ne olduğunu görmek için aynı kelime grubu üzerinde hem c ++ hem de python çözümlerini 1.000.000 çalıştırma için zamanladım. Şaşırtıcı bir şekilde, python çözümü c ++ çözümünden neredeyse 2 kat daha iyi performans gösteriyor. İ5 2.7 GHZ mbp'mde çalıştırıldığında elde edilen süreler sırasıyla python ve c ++ için ~ = 10, 20 saniye. Her iki uygulamanın da neredeyse benzer olduğu göz önüne alındığında, c ++ python'dan 10 kat daha hızlı olmamalı mı?

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)

Sonuçlar:

[['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";
}

Sonuçlar:

abets baste beats 
tabu 
actress casters 
allergy gallery largely 

Calculating time for 1000000 runs ...
22 seconds

Answer 1

C ++

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

containsiçindeki kelimeyi arar word_groups. Sonra operator[]aynı aramayı ikinci kez yapar.

Yukarıdakileri sadece şu şekilde değiştirebiliriz:

    word_groups[sorted_word].push_back(word);

( haritada yoksa operator[]varsayılan olarak oluşturulmuş bir değer (yani boş vector<std::string>) ekler ).

---

Döndürmek için word_groupsharitayı bir vektöre kopyalamamıza gerek yok get_groups(). Haritanın kendisini iade edebiliriz.

Daha sonra ana işlevde şu şekilde yineleriz:

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

---

Dizenin kendisini haritada saklamamıza gerek yok, dizenin dizinini girdi vektöründe saklayabiliriz. (yani map<string, vector<std::size_t>>).