统计单词 - 简书

统计单词

君子不器 ㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤㅤ -- 论语

伊始

来源：题目来自于陶老师的码农花园课程；

陶老师经常说同一道题目，我们需要通过尝试不同的方法去解答来达到练习的效果

问题描述

一个文本文件，假定里面都是由空格分隔的英文单词。单词的数量和最长长度不确定，但系统的内存一定够用
输入：文件名
输出：输出出现次数最多的前20个单词
备注
1. 文件总单词个数小于20，则输出所有单词
2. 相同次数的单词可随意输出，只要输出单词个数达到20即可
3. 空格可以是一个或多个

Solutions

话不多说，这里我们直接给出几个解法供大家参考

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;

接口设计

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

基础功能

在给出我们几个解法前，我们先实现一些我们认为的基础功能，供各个解法复用

打开文件

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

统计词频

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来保存词频键值对，然后按照词频进行排序即可

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来保存词频的value和key，利用反向迭代器来获取次数最多的单词

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()) // 利用反向迭代器构建stream 流
      | map_([](const auto& p) { return p.second; })
      | limit(min(OUT_WORD_NUM, words.size()))
      | to_vector();
}

解法三

在解法二的基础上，我们可以指定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

其实还有很多种解法，陶老师给出了7个版本，有兴趣的读者可以多多尝试不同的解法

After

最后，写个测试函数将我们的结果打印出来就可以了

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

延申讨论

需求变更

变更1

如果不是输出的个数不是20，而是由用户指定个数呢？
变更2

次数相同，按照字典序（升序或者降序）输出
变更3

次数相同，按照字符串在文件里第一次出现的顺序输出
变更4

加入单词间的分隔符除了空格还有','和’.'等其它指定的字符集
……

应对变化

问：对于复杂的需求变化，我们需要做一个大而全的设计吗？充分考虑未来的变化吗？甚至提前实现一些未来可能出现变化点？

我们的认为是，不需要；我们提倡用简单来应对变化（抗变化），而不去用大设计去预测或者实现变化；

对于未来，我们的态度是：“预测未来，绝不是实现未来”

End

独乐乐不如众乐乐，持续学习，共同进步

最后编辑于：2022.03.27 17:44:01