君子不器 ?????????????????????????? -- 論語(yǔ)

伊始

• 來(lái)源：題目來(lái)自于陶老師的碼農(nóng)花園課程；

  陶老師經(jīng)常說(shuō)同一道題目，我們需要通過(guò)嘗試不同的方法去解答來(lái)達(dá)到練習(xí)的效果

問(wèn)題描述

• 一個(gè)文本文件，假定里面都是由空格分隔的英文單詞。單詞的數(shù)量和最長(zhǎng)長(zhǎng)度不確定，但系統(tǒng)的內(nèi)存一定夠用
• 輸入：文件名
• 輸出：輸出出現(xiàn)次數(shù)最多的前20個(gè)單詞
• 備注
  1. 文件總單詞個(gè)數(shù)小于20，則輸出所有單詞
  2. 相同次數(shù)的單詞可隨意輸出，只要輸出單詞個(gè)數(shù)達(dá)到20即可
  3. 空格可以是一個(gè)或多個(gè)

Solutions

話不多說(shuō)，這里我們直接給出幾個(gè)解法供大家參考

Before

• 定義

  using Words = std::vector<std::string>;  // output type
  using WordFreqs = map<string, int>; // for count word freq
  
  constexpr std::size_t OUT_WORD_NUM = 20;
  

• 接口設(shè)計(jì)

  Words count_word(const std::string& file);
  

• 基礎(chǔ)功能

  在給出我們幾個(gè)解法前，我們先實(shí)現(xiàn)一些我們認(rèn)為的基礎(chǔ)功能，供各個(gè)解法復(fù)用

  1. 打開文件

  std::ifstream open_file(const std::string& file) {
    return std::ifstream{file};
  }
  

  2. 統(tǒng)計(jì)詞頻

  WordFreqs count_word_freq(const std::string& file) {
    auto in = open_file(file);
    map<string, int> words;
    string word;
    while (in >> word) {
      ++words[word];
    }
    return words;
  }
  

解法一

• 使用vector來(lái)保存詞頻鍵值對(duì)，然后按照詞頻進(jìn)行排序即可

  Words count_word_1(const WordFreqs& freqs) {
    vector<pair<string, int>> words{begin(freqs), end(freqs)};
    auto out_nums = min(OUT_WORD_NUM, words.size());
  
    std::partial_sort(begin(words), begin(words) + out_nums, end(words),
                      [](auto& x, auto& y) { return x.second > y.second; });
  
    return copy_range<Words>(words | sliced(0, out_nums) | transformed([](const auto& p) { return p.first; }));
  }
  

解法二

• 使用multimap來(lái)保存詞頻的value和key，利用反向迭代器來(lái)獲取次數(shù)最多的單詞

  auto revers_k_v(const WordFreqs& freqs) {
    return copy_range<multimap<int, string>>(freqs | transformed([](const auto& p) {
      return make_pair(p.second, p.first);
    }));
  }
  
  Words count_word_2(const WordFreqs& freqs) {
    return MakeStream::from(freqs.rbegin(), freqs.rend()) // 利用反向迭代器構(gòu)建stream 流
        | map_([](const auto& p) { return p.second; })
        | limit(min(OUT_WORD_NUM, words.size()))
        | to_vector();
  }
  

解法三

在解法二的基礎(chǔ)上，我們可以指定multimap的比較器，就不需要使用反向迭代器了；

// 傳入greater比較器
auto revers_k_v(const WordFreqs& freqs) {
  return copy_range<multimap<int, string, greater<>>>(freqs | transformed([](const auto& p) {
    return make_pair(p.second, p.first);
  }));
}

Words count_word_3(const WordFreqs& freqs) {
  return MakeStream::from(freqs)
      | map_([](const auto& p) { return p.second; })
      | limit(min(OUT_WORD_NUM, freqs.size()))
      | to_vector();
}

解法n

其實(shí)還有很多種解法，陶老師給出了7個(gè)版本，有興趣的讀者可以多多嘗試不同的解法

After

最后，寫個(gè)測(cè)試函數(shù)將我們的結(jié)果打印出來(lái)就可以了

string file = "input.txt";
auto words = count_word(file);
copy(begin(words), end(words), ostream_iterator<string>(cout, " "));

延申討論

需求變更

• 變更1

  如果不是輸出的個(gè)數(shù)不是20，而是由用戶指定個(gè)數(shù)呢？

• 變更2

  次數(shù)相同，按照字典序（升序或者降序）輸出

• 變更3

  次數(shù)相同，按照字符串在文件里第一次出現(xiàn)的順序輸出

• 變更4

  加入單詞間的分隔符除了空格還有','和’.'等其它指定的字符集

• ……

應(yīng)對(duì)變化

• 問(wèn)：對(duì)于復(fù)雜的需求變化，我們需要做一個(gè)大而全的設(shè)計(jì)嗎？充分考慮未來(lái)的變化嗎？甚至提前實(shí)現(xiàn)一些未來(lái)可能出現(xiàn)變化點(diǎn)？

  我們的認(rèn)為是，不需要；我們提倡用簡(jiǎn)單來(lái)應(yīng)對(duì)變化（抗變化），而不去用大設(shè)計(jì)去預(yù)測(cè)或者實(shí)現(xiàn)變化；

  對(duì)于未來(lái)，我們的態(tài)度是：“預(yù)測(cè)未來(lái)，絕不是實(shí)現(xiàn)未來(lái)”

End

獨(dú)樂(lè)樂(lè)不如眾樂(lè)樂(lè)，持續(xù)學(xué)習(xí)，共同進(jìn)步