1/****************************************************************************
2**
3** Copyright (C) 2016 The Qt Company Ltd.
4** Contact: https://www.qt.io/licensing/
5**
6** This file is part of the examples of the Qt Toolkit.
7**
8** $QT_BEGIN_LICENSE:BSD$
9** Commercial License Usage
10** Licensees holding valid commercial Qt licenses may use this file in
11** accordance with the commercial license agreement provided with the
12** Software or, alternatively, in accordance with the terms contained in
13** a written agreement between you and The Qt Company. For licensing terms
14** and conditions see https://www.qt.io/terms-conditions. For further
15** information use the contact form at https://www.qt.io/contact-us.
16**
17** BSD License Usage
18** Alternatively, you may use this file under the terms of the BSD license
19** as follows:
20**
21** "Redistribution and use in source and binary forms, with or without
22** modification, are permitted provided that the following conditions are
23** met:
24** * Redistributions of source code must retain the above copyright
25** notice, this list of conditions and the following disclaimer.
26** * Redistributions in binary form must reproduce the above copyright
27** notice, this list of conditions and the following disclaimer in
28** the documentation and/or other materials provided with the
29** distribution.
30** * Neither the name of The Qt Company Ltd nor the names of its
31** contributors may be used to endorse or promote products derived
32** from this software without specific prior written permission.
33**
34**
35** THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
36** "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
37** LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
38** A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
39** OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
40** SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
41** LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
42** DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
43** THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
44** (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
45** OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE."
46**
47** $QT_END_LICENSE$
48**
49****************************************************************************/
50
51#include <QList>
52#include <QMap>
53#include <QTextStream>
54#include <QString>
55#include <QStringList>
56#include <QDir>
57#include <QElapsedTimer>
58#include <QApplication>
59#include <QDebug>
60
61#include <qtconcurrentmap.h>
62
63using namespace QtConcurrent;
64
65/*
66 Utility function that recursivily searches for files.
67*/
68QStringList findFiles(const QString &startDir, const QStringList &filters)
69{
70 QStringList names;
71 QDir dir(startDir);
72
73 const auto files = dir.entryList(filters, QDir::Files);
74 for (const QString &file : files)
75 names += startDir + '/' + file;
76
77 const auto subdirs = dir.entryList(QDir::AllDirs | QDir::NoDotAndDotDot);
78 for (const QString &subdir : subdirs)
79 names += findFiles(startDir + '/' + subdir, filters);
80 return names;
81}
82
83typedef QMap<QString, int> WordCount;
84
85/*
86 Single threaded word counter function.
87*/
88WordCount singleThreadedWordCount(const QStringList &files)
89{
90 WordCount wordCount;
91 for (const QString &file : files) {
92 QFile f(file);
93 f.open(QIODevice::ReadOnly);
94 QTextStream textStream(&f);
95 while (!textStream.atEnd()) {
96 const auto words = textStream.readLine().split(' ');
97 for (const QString &word : words)
98 wordCount[word] += 1;
99 }
100 }
101 return wordCount;
102}
103
104
105// countWords counts the words in a single file. This function is
106// called in parallel by several threads and must be thread
107// safe.
108WordCount countWords(const QString &file)
109{
110 QFile f(file);
111 f.open(QIODevice::ReadOnly);
112 QTextStream textStream(&f);
113 WordCount wordCount;
114
115 while (!textStream.atEnd()) {
116 const auto words = textStream.readLine().split(' ');
117 for (const QString &word : words)
118 wordCount[word] += 1;
119 }
120
121 return wordCount;
122}
123
124// reduce adds the results from map to the final
125// result. This functor will only be called by one thread
126// at a time.
127void reduce(WordCount &result, const WordCount &w)
128{
129 for (auto i = w.begin(), end = w.end(); i != end; ++i)
130 result[i.key()] += i.value();
131}
132
133int main(int argc, char** argv)
134{
135 QApplication app(argc, argv);
136 qDebug() << "finding files...";
137 QStringList files = findFiles("../../", QStringList() << "*.cpp" << "*.h");
138 qDebug() << files.count() << "files";
139
140 qDebug() << "warmup";
141 {
142 WordCount total = singleThreadedWordCount(files);
143 }
144
145 qDebug() << "warmup done";
146
147 int singleThreadTime = 0;
148 {
149 QElapsedTimer timer;
150 timer.start();
151 WordCount total = singleThreadedWordCount(files);
152 singleThreadTime = timer.elapsed();
153 qDebug() << "single thread" << singleThreadTime;
154 }
155
156 int mapReduceTime = 0;
157 {
158 QElapsedTimer timer;
159 timer.start();
160 WordCount total = mappedReduced(files, countWords, reduce);
161 mapReduceTime = timer.elapsed();
162 qDebug() << "MapReduce" << mapReduceTime;
163 }
164 qDebug() << "MapReduce speedup x" << ((double)singleThreadTime - (double)mapReduceTime) / (double)mapReduceTime + 1;
165}
166