今天給大家介紹下并行編程在實際場景中的應用

給定一篇文章A，從備選的1000份文章中找出和文章A相似度最高的一篇。如果相似度大于50%，則認為該文章有抄襲嫌疑，将文章提取出來進行人工篩查。而且效率要足夠高。

這裡請大家暫停10分鐘，思考下如果換做是你，你将如何實現這個需求。

我來講下方法，如果大家有更好的想法，小豆君希望大家在評論區讨論。每個人積極交換思想，才能碰撞出更亮的火花。

在數據分析中，有個叫做餘弦相似度的概念

其公式為：

餘弦相似度公式

其中，a·b表示向量點積

向量點積

||a||*||b||表示：

距離乘積

舉例：

• 文章A内容：中國人民都愛喝牛奶
• 文章B内容：我們中國百姓都喜歡喝牛奶
• 文章C内容：外國人不喜歡牛奶

然後将三篇文章做成一個矩陣表格，其中每個單元格的數字表示這個字在文章中出現的次數

字矩陣

那麼

• A·B=6 (A和B對應每列相乘再求和)
• sqrt(A^2)=3
• sqrt(B^2)=3.46
• cos(A,B)=6/(3*3.46)=0.58

你可以嘗試求一下cos(A,C)，我這裡就不給答案了，你可以将答案寫到評論區。

故文章A與B的餘弦相似度為0.58

解釋：

餘弦相似度實際上是兩個向量之間的夾角餘弦值，夾角越小越相似。在用點積除以距離時，實際上是将它們進行了歸一化處理，這時我們就不需要考慮向量的長度了。

在取點積時，如果乘數中有0，則相當于是将彼此間互不包含的字符去掉了，這會使得整個分子變小，而分子變小，餘弦值減小，角度增大，其相似度也就增大了。當餘弦值為0時，角度為90度，說明它們之間不包含任何相同的文字了。

通過上面的解釋，你應該已經弄懂了什麼是餘弦相似度了。接下來我們用代碼實現之

上代碼：

#include <QDebug> //獲取字符串a和字符串b每個字的出現次數 QMap<QString, QList<int> > get_dict(const QString& a, const QString& b) { QMap<QString, QList<int> > dict; QList<int> empty_list; //空的一位列表，索引0為a的字符次數，索引1為b的字符次數 empty_list.append(0); empty_list.append(0); //找到所有的字，并初始化為空列表 foreach (const QString& v, a b) { if (!dict.contains(v)) { dict[v] = empty_list; } } //計算a中字符出現次數 foreach (const QString& v, a) { if (dict.contains(v)) { dict[v][0] =1; } } //計算b中字符出現次數 foreach (const QString& v, b) { if (dict.contains(v)) { dict[v][1] = 1; } } return dict; } double cos_ab(const QString& a, const QString& b) { int ab = 0; //點積 int a_distance2 = 0; //a距離平方 int b_distance2 = 0; //b距離平方 QMap<QString, QList<int> > dict = get_dict(a, b); QMapIterator<QString, QList<int> > i(dict); while (i.hasNext()) { i.next(); const QList<int>& v = i.value(); ab = v[0]*v[1]; a_distance2 = v[0]*v[0]; b_distance2 = v[1]*v[1]; } double s_a = sqrt(a_distance2); double s_b = sqrt(b_distance2); return ab/(s_a*s_b); } int main() { double result = cos_ab(QString("中國人民都愛喝牛奶"), QString("我們中國百姓都喜歡喝牛奶")); qDebug() << result; }

以上，我們已經解決了比較文章相似度的問題了，但需求是需要從1000篇文章中進行篩選，所以我們要充分發揮計算機的資源，盡快找出相似度最高的文章，所以需要用到多線程。

在Qt中，QtConcurrent提供了并行處理方案。

上代碼：

#include <QApplication> #include <QDebug> #include <QTextStream> #include <QFile> #include <QDir> #include <qtconcurrentmap.h> // 查找指定目錄下的所有文件，并指定過濾條件，返回文件路徑列表 QStringList find_files(const QString &startDir, QStringList filters) { QStringList names; QDir dir(startDir); foreach (QString file, dir.entryList(filters, QDir::Files)) names = startDir '/' file; foreach (QString subdir, dir.entryList(QDir::AllDirs | QDir::NoDotAndDotDot)) names = find_files(startDir '/' subdir, filters); return names; } // 讀取文件中的所有内容 QString read_file(const QString& file) { QFile f(file); f.open(QIODevice::ReadOnly); return f.readAll(); } // 餘弦函數代理，用于在mappedReduced中計算餘弦相似度 double cos_ab_proxy(const QString& file) { static QString src = read_file("./src.txt"); // 存放原始文件内容，"中國人民都愛喝牛奶" QString compare = read_file(file); // 讀取被比較的文件内容 double res = cos_ab(src, compare); qDebug() <<QString("原字符串[%1] 被比較字符串[%2] 相似度[%3]").arg(src).arg(compare).arg(res); return res; } // 對計算後的餘弦相似度進行處理，找出最大的餘弦相似度 void reduce(double &result, double calc_result) { if (result < calc_result) { result = calc_result; } } int main(int argc, char** argv) { QApplication app(argc, argv); // 查找files目錄下的所有txt文件，并返回文件路徑列表。1.txt (我們中國百姓都喜歡喝牛奶) 2.txt (外國人不喜歡牛奶) QStringList files = find_files("./files/", QStringList() << "*.txt"); double result = QtConcurrent::mappedReduced(files, cos_ab_proxy, reduce); qDebug() << "最高相似度為：" << result; }

輸出結果：

并行計算結果

使用QtConcurrent編寫的程序可以根據可用的處理器内核數自動調整線程數來加快計算速度，那麼當部署到核數更多的機器上時，計算速度将自動提高。

QtConcurrent::mappedReduced函數，第一個參數是一個序列，它會将序列中的每一個元素分别傳遞給cos_ab_proxy函數作為參數，然後将cos_ab_proxy的結果傳遞給reduce，作為reduce的入參。reduce的結果将是整個函數的返回值。

你可以嘗試增加文本和文件數量，當數量越來越多時，就會體現出并行計算的優勢。

此處小豆君計算文本之間的相似度，是很初級的。因為中國是漢字，這裡隻計算的漢字之間的相似度，實際應計算詞語相似度，過濾掉特殊符号，标點符号等。還需要處理同一種詞語或詞義的不同形式。這個留給後面我們進行探索。

最後留一個問題，本代碼中，并沒有返回是哪篇文章相似度最高，大家可以思考下應該怎麼做。

喜歡本文的大家就點個贊吧，同時也歡迎關注

知乎号：小豆君編程分享

小豆君編程分享（關注後，可加入小豆君交流群進行學習交流，也可第一時間看到最新文章）

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!