c++ - 通过多线程判断每个字符在一个文件中出现了多少次

Question

我的代码。我写了我可以。现在需要你的帮助。告诉我怎么了。我如何屏蔽尽可能多的符号？我不知道如何正确地做，我看书。但仍然没有解决

void TextThread(std::string str)
{
  std::ifstream text(str);
  if (!text)
    std::cout << "No open file" << "\n";

  std::istream_iterator<char> input(text);
  std::istream_iterator<char> output;

  std::vector<char> symvol(input, output);

  unsigned maxThreadCount = std::thread::hardware_concurrency();
  const std::size_t minLength = symvol.size() / maxThreadCount;
  const std::size_t modulo = symvol.size() % maxThreadCount;

  std::vector<std::size_t> results;
  results.reserve(maxThreadCount);

  std::vector<std::thread> threads;
  threads.reserve(maxThreadCount - 1);

  for (std::size_t i = 0; i < modulo; ++i)
    results.emplace_back(minLength + 1);

  if (minLength > 0)
  {
     for (std::size_t i = modulo; i < maxThreadCount; ++i)
        results.emplace_back(minLength);
  }
  for (std::size_t i = 1; i < threads.size(); ++i)
    threads.emplace_back(threads[i - 1] + 1, threads[i - 1] + threads[i]);

  std::for_each(threads.begin(), threads.end(), 
   std::mem_fn(&std::thread::join));


  for (unsigned int i = 0; i < symvol.size(); ++i)
    std::cout << symvol[i] << "\n";
}


int main()
{
  TextThread("D:\\text.txt");
  return 0;
}

更新:我会在屏幕上显示所有字符

void TextThread(std::string str)
 {
   std::ifstream text(str);
   if (!text)
    std::cout << "No open file" << "\n";

  std::istream_iterator<char> input(text);
  std::istream_iterator<char> output;

  std::vector<char> symvol(input, output);
  for (unsigned int i = 0; i < symvol.size(); ++i)
    std::cout << symvol[i] << "\n";
 }

UPD2:

像你一样做。它仍然与多线程有关

 using Symbol = std::array<size_t, 256>;
 Symbol  CountSymbol(std::vector<char> const& data) 
 {
    Symbol countSymbol{};
    for (unsigned char ch : data) 
        countSymbol[ch] += 1;
    return countSymbol;
 }


 Symbol SymbolFile(std::string const& fname) 
 {
   std::ifstream text(fname);

   if (!text)
      throw std::runtime_error("No open file");

   std::vector<char> const data(std::istreambuf_iterator<char>{text}, {});
     return CountSymbol(data);
 }

 int main() 
 {
    Symbol  symbol = SymbolFile("D:\\text.txt");
    for (int ch = 0; ch <= 255; ++ch) 
    {
       if (symbol[ch]) 
       {
           if (std::isprint(ch))
            std::cout << "Character '" << char(ch) << "' occurs " << 
        symbol[ch] << " times\n";
           else
               std::cout << "Character #" << ch << " occurs " << symbol[ch] 
        << " times\n";
       }
    }
}

UPD3

 #include "stdafx.h"
 #include <iostream>
 #include <fstream>
 #include <iterator>
 #include <algorithm>
 #include <string>
 #include <vector>
 #include <unordered_map>
 #include <thread>
 #include <cctype>
 #include <clocale>
 #include <numeric>

 std::vector<std::pair<std::size_t, std::size_t>> GenerateIntervals(const 
       std::vector<char>& text)
 {
     std::size_t maxThreadCount = std::thread::hardware_concurrency();
     const std::size_t minLength = text.size() / maxThreadCount;
     const std::size_t modulo = text.size() % maxThreadCount;

     std::vector<std::size_t> intervalLengthPerThread;
     intervalLengthPerThread.reserve(maxThreadCount);

     for (std::size_t i = 0; i < modulo; ++i)
    intervalLengthPerThread.emplace_back(minLength + 1);

if (minLength > 0)
{
    for (std::size_t i = modulo; i < maxThreadCount; ++i)
        intervalLengthPerThread.emplace_back(minLength);
}

std::vector<std::pair<std::size_t, std::size_t>> intervals;
intervals.reserve(intervalLengthPerThread.size());

intervals.emplace_back(0, 0 + intervalLengthPerThread[0] - 1);
for (std::size_t i = 1; i < intervalLengthPerThread.size(); ++i)
    intervals.emplace_back(intervals[i - 1].second + 1, intervals[i - 1].second + intervalLengthPerThread[i]);

return intervals;
}

 void BuildHistogram(const std::pair<std::size_t, std::size_t>& textRange, 
 const std::vector<char>& text, std::unordered_map<char, std::size_t>& 
  histogram)
 {
    for (std::size_t i = textRange.first; i < textRange.second; ++i) 
        ++histogram[text[i]];
 }

 std::vector<char> ReadDataFromFile(const std::string& pathToFile)
{
std::ifstream stream(pathToFile);

if (!stream) 
{
    std::vector<char> result;
    std::cout << "Can not open file" << "\n";
    return result;
}

std::istream_iterator<char> it(stream);
std::istream_iterator<char> itEnd;

std::vector<char> text(it, itEnd);
}

 int main() 
 {
auto text = ReadDataFromFile("D:\\text.txt");

const auto textIntervals = GenerateIntervals(text);
const auto usedThreadCount = textIntervals.size();

std::vector<std::unordered_map<char, size_t>> histograms(usedThreadCount);
std::vector<std::thread> threads(usedThreadCount);

for (std::size_t i = 0; i < usedThreadCount; ++i)
    threads[i] = std::thread(BuildHistogram, std::cref(textIntervals[i]), text, std::ref(histograms[i]));

for (std::size_t i = 0; i < usedThreadCount; ++i)
    threads[i].join();

std::unordered_map<char, size_t> histogram;
for (const auto& hist : histograms)
{
    for (const auto& pair : hist)
        histogram[pair.first] += pair.second;
}

for (int ch = 0; ch < 256; ++ch) 
{
    if (text[ch]) 
    {
        std::cout << "Character '" << char(ch) << "' occurs " << text[ch] << " times\n";
    }
}
return 0;

Answer 1

我会在这里提供帮助，因为你迷路了。

目标

我认为你想要一个直方图，比如:

std::array<size_t, 256> histo;

这里，每个元素对应输入字符的整数值(比如a是97)。

下面是简单的实现:

using Histo = std::array<size_t, 256>;

Histo histogram(std::vector<char> const& data) {
    Histo histo {}; // value initialize, makes sure all elements are 0

    for (auto ch : data) {
        histo[ch] += 1;
    }

    return histo;
}

Note There's a very subtle thing here where I convert the character to unsigned char (could also say uint8_t). This is because some platforms will have char be signed and that leads to errors when indexing histo[ch] or when comparing (e.g. ch <= 255 would always be true).

您可以像这样对文件的内容进行操作:

Histo histogram_file(std::string const& fname) {
    std::ifstream text(fname);

    if (!text)
        throw std::runtime_error("No open file");

    std::vector<char> const data(std::istreambuf_iterator<char>{text}, {});
    return histogram(data);
}

Note The use of istreambuf_iterator does not skip whitespace (as istreambuf_iterator does by default, see http://en.cppreference.com/w/cpp/io/manip/skipws).

现场演示

简单代码 Live On Coliru

#include <thread>
#include <vector>
#include <string>
#include <fstream>
#include <iostream>
#include <iterator>

using Histo = std::array<size_t, 256>;

Histo histogram(std::vector<char> const& data) {
    Histo histo {}; // value initialize, makes sure all elements are 0

    for (unsigned char ch : data) {
        histo[ch] += 1;
    }

    return histo;
}


Histo histogram_file(std::string const& fname) {
    std::ifstream text(fname);

    if (!text)
        throw std::runtime_error("No open file");

    std::vector<char> const data(std::istreambuf_iterator<char>{text}, {});
    return histogram(data);
}

int main() {
    Histo histo = histogram_file("main.cpp");
    for (int ch = 0; ch <= 255; ++ch) {
        if (histo[ch]) {
            if (std::isprint(ch))
                std::cout << "Character '" << char(ch) << "' occurs " << histo[ch] << " times\n";
            else
                std::cout << "Character #" << ch << " occurs " << histo[ch] << " times\n";
        }
    }
}

打印类似的东西

Character #10 occurs 41 times
Character ' ' occurs 224 times
Character '!' occurs 1 times
Character '"' occurs 16 times
Character '#' occurs 7 times
...
Character 'x' occurs 3 times
Character 'y' occurs 1 times
Character 'z' occurs 2 times
Character '{' occurs 9 times
Character '}' occurs 9 times

使其线程化

要分发工作，我们必须调用 histogram对于 vector 数据的一部分。让我们稍微修改我们的函数来实现这一点:

template <typename Iterator> // could just use `char const*` but let's not
Histo histogram(Iterator begin, Iterator end) {
    Histo histo {}; // value initialize, makes sure all elements are 0

    for (auto it = begin; it != end; ++it) {
        histo[*it] += 1;
    }

    return histo;
}

Histo histogram(std::vector<char> const& data) {
    return histogram(data.begin(), data.end());
}

如您所见，我们可以将“旧”签名直接转发到新的、更灵活的界面。当然你可以对 char const* 挑剔。直接并具有完全相同的代码，但如果输入与 vector 有任何不同，它就无法正常工作。或者如果它变成了 std::deque<unsigned char>等等

并发

我们希望将工作分成相等的 block :

using It = std::vector<char>::const_iterator;

// calculate chunk size
auto chunk = data.size() / num_threads;
if (chunk*num_threads < data.size()) chunk += 1;

Note that the last chunk could be extend (

因为你不能(有用地)分享 Histo所有线程之间的对象(同步访问的成本将远远超过并发处理的任何速度优势)，我们必须有 Histo每个线程。

让我们先笨拙地手动操作:

////////////////////////////////////////////
// start chunk threads
struct worker_t {
    Histo local; // histogram per thread
    std::thread th;

    void run(It begin, It end) {
        local = histogram(begin, end);
    }
};
std::vector<worker_t> workers(num_threads);

现在我们可以开始了 run在每个工作实例上，传递计算的子范围:

int i = 0;
for (auto& w : workers) {
    auto begin = data.begin()+chunk*i,
         end   = std::min(begin + chunk, data.end());
    w.th = std::thread(&worker_t::run, std::ref(w), begin, end);
    ++i;
}

等待与合并

////////////////////////////////////////////
// wait for completion
for (auto& w : workers) {
    if (w.th.joinable())
        w.th.join();
};

这几乎是您已经拥有的。

////////////////////////////////////////////
// merge results
Histo histo;
for (auto& w : workers) {
    merge_into(histo, w.local);
}

return histo;

注意编写你想阅读的代码，然后再实现更多细节的习惯。在这种情况下，我们仍然定义了 merge_into :

void merge_into(Histo& into, Histo const& part) {
    for (auto& p : part)
        into[p.first] += p.second;
}

体力劳动者演示

以上 Live On Coliru 和 MSVC on RexTester

#include <thread>
#include <vector>
#include <string>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>

using Histo = std::map<char, size_t>;

void merge_into(Histo& into, Histo const& part) {
    for (auto& p : part)
        into[p.first] += p.second;
}

template <typename Iterator> // could just use `char const*` but let's not
Histo histogram(Iterator begin, Iterator end) {
    Histo histo {}; // value initialize, makes sure all elements are 0

    for (auto it = begin; it != end; ++it) {
        histo[*it] += 1;
    }

    return histo;
}

Histo histogram(std::vector<char> const& data) {
    return histogram(data.begin(), data.end());
}

Histo parallel_histo(std::vector<char> const& data, size_t num_threads = std::thread::hardware_concurrency()) {
    using It = std::vector<char>::const_iterator;

    // calculate chunk size
    auto chunk = data.size() / num_threads;
    if (chunk*num_threads < data.size()) chunk += 1;

    ////////////////////////////////////////////
    // start chunk threads
    struct worker_t {
        Histo local; // histogram per thread
        std::thread th;

        void run(It begin, It end) {
            local = histogram(begin, end);
        }
    };
    std::vector<worker_t> workers(num_threads);

    int i = 0;
    for (auto& w : workers) {
        auto begin = data.begin()+chunk*i,
             end   = std::min(begin + chunk, data.end());
        w.th = std::thread(&worker_t::run, std::ref(w), begin, end);
        ++i;
    }

    ////////////////////////////////////////////
    // wait for completion
    for (auto& w : workers) {
        if (w.th.joinable())
            w.th.join();
    };

    ////////////////////////////////////////////
    // merge results
    Histo histo;
    for (auto& w : workers) {
        merge_into(histo, w.local);
    }

    return histo;
}

Histo histogram_file(std::string const& fname) {
    std::ifstream text(fname);

    if (!text)
        throw std::runtime_error("No open file");

    return parallel_histo({std::istreambuf_iterator<char>{text}, {}});
}

int main() {
    Histo histo = histogram_file("main.cpp");
    for (int ch = 0; ch <= 255; ++ch) {
        if (histo[ch]) {
            if (std::isprint(ch))
                std::cout << "Character '" << char(ch) << "' occurs " << histo[ch] << " times\n";
            else
                std::cout << "Character #" << ch << " occurs " << histo[ch] << " times\n";
        }
    }
}

打印与之前相同的输出。

不那么笨拙

分配接受输入和生成结果的任务的“标准库”是使用 std::async它可以简单地返回结果。它并不完美，但工作量少得多:

Live On Coliru

Histo parallel_histo(std::vector<char> const& data, size_t num_threads = std::thread::hardware_concurrency()) {
    // calculate chunk size
    auto chunk = data.size() / num_threads;
    if (chunk*num_threads < data.size()) chunk += 1;

    ////////////////////////////////////////////
    // start tasks
    std::vector<std::future<Histo> > tasks(num_threads);

    int i = 0;
    for (auto& t : tasks) {
        auto begin = data.begin()+chunk*i,
             end   = std::min(begin + chunk, data.end());

        t = std::async([=,&data] { return histogram(begin, end); });
    }

    Histo histo;
    for (auto& t : tasks) {
        merge_into(histo, t.get());
    }

    return histo;
}

禅师

当然，如果你真的了解标准库，你就会使用它(c++17):

#include <atomic>
#include <execution>
#include <algorithm>

using Histo = std::vector<std::atomic_size_t>;

Histo histogram(std::vector<char> const& data) {
    Histo histo(256);
    std::for_each(std::execution::par_unseq, data.begin(), data.end(), [&histo](unsigned char ch) { ++histo[ch]; });
    return histo;
}

Histo histogram_file(std::string const& fname) {
    std::ifstream text(fname);

    if (!text)
        throw std::runtime_error("No open file");

    return histogram({std::istreambuf_iterator<char>{text}, {}});
}

遗憾的是您还不能使用它，因为没有编译器供应商实际(完全)实现它。