由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
Programming版 - 天,如何能让程序转得快点?有包子。
相关主题
how to read a sentence into a vector of string?how to skip the last empty lines in ifstream?
读取数据求教请教用c++读取large file怎么可以快一些?
关于文件读取的C++ 问题?请教一个C++的问题
[合集] 如何能让这个程序快一点呢?太慢了C++ 在 windows 上 结果正确, 在 linux 上结果总是不一样,怎
C++读文本文件怎么判断换行?C++ string类输入数据的问题
一个很诡异的ifstream问题,求助~~C++ string to int Problem
如何让这个cur变量正确指向新地址贡献一c++面试题
how to use cin as default ifstream?istream_iterator问题
相关话题的讨论汇总
话题: std话题: string话题: boost话题: s1话题: s2
进入Programming版参与讨论
1 (共1页)
t***q
发帖数: 418
1
天,如何能让程序转得快点?
原帖在这里:
http://www.mitbbs.com/article_t0/Programming/31381809.html
主要是要做 title matching.
有两个 file, file A 162283 行 X 12 列。 File B 3695 行 X 6 列。用 A 的 第五
列和 B的第四列进行比较, 对 B 的第四列的每一行, 从 A的 那 162283 行中 找出
与之最相似的那一行。A 的第五列和 B 的第四列都是些影视作品的 title, 是一些长
短不一的 string. 我用的是 Levenshtein algorithm 算每一对string 的相似度,再
把相似度排序,从高到低,找出相似度最大的那一个 string, 也就是影视作品的
title, 加到 file B 对应的那一个title 那一行。再加入一个从file A 出来的对应的
一个id, 到 file B 里。算相似度前,我先对每个title 组成的string做预处理,去掉
“:”,”-“,”season”,”episode “ , 等一些词。减少matching 的误差。
但就这样一个程序,我先用 python, 一个程序要跑很长时间,才出结果,再用c++ 没
想到用的时间更长。程序如下:
Python:
import csv
import re
import difflib
import operator
import Levenshtein
import datetime
import glob
import os
import fnmatch
a=[]
with open("D:\A.txt","rb") as f:
for row in f:
a.append(row.split("t"))
f.close()

b=[]
with open("B.txt","rb") as k:
for row in k:
b.append(row.split("t"))
k.close()
dd={}
ee={}
my_list=[]
for i in range(len(a)):
ff={}
# max_value=0
for j in range(len(b)):
s1=re.sub(r',',' ',a[i][3])
s1=s1.lower()
s2=re.sub(r',',' ',b[j][4])
s2=s2.lower()
s1=re.sub(r'series',' ',s1)
s1=re.sub(r'episode',' ',s1)
s2=re.sub(r'series',' ',s2)
s2=re.sub(r'episode',' ',s2)
s1=re.sub(r'season',' ',s1)
s2=re.sub(r'season',' ',s2)
s1=re.sub(r'"',' ',s1)
s2=re.sub(r'"',' ',s2)
s1=re.sub(r'-',' ',s1)
s2=re.sub(r'-',' ',s2)
s2=re.sub(r':',' ',s2)
s1=re.sub(r':',' ',s1)
s1=re.sub(r' ','',s1)
s2=re.sub(r' ','',s2)
d=float(Levenshtein.ratio(s1,s2))
ff[b[j][4]+"t"+str(b[j][11])]=d
# max_value=float(max(max_value,d))
qq="t".join(a[i])
dd[qq]=max(ff.iteritems(),key=operator.itemgetter(1))[0]
my_list.append([qq.strip()+"t"+dd[qq]])
datestr=datetime.date.today().strftime("%y%m%d")
filename="good2_codes_{}".format(datestr)+'.txt'
File=open("C”+filename,'w')
for item in my_list:
File.write(str(item[0])+"n")
File.close()
C++:
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
size_t uiLevenshteinDistance (const std::string &s1, const std::string &s2)
{ const size_t m(s1.size());
const size_t n(s2.size());
if(m==0) return n;
if(n==0) return m;

size_t *costs=new size_t[n+1];
for(size_t k=0;k<=n;k++) costs[k]=k;

size_t i=0;
for (std::string::const_iterator it1=s1.begin(); it1!=s1.end();++it1,++i)
{costs[0]=i+1;
size_t corner=i;
size_t j=0;
for(std::string::const_iterator it2=s2.begin();it2!=s2.end();++it2,++j)
{
size_t upper=costs[j+1];
if(*it1==*it2)
{
costs[j+1]=corner;
}
else
{ size_t t(upper costs[j+1]=(costs[j] }
corner=upper;
}
}
size_t result=costs[n];
delete [] costs;
return result;
}
int main()
{
std::vector lines;
std::ifstream file("A.txt");
std::string line;
while (std::getline(file,line)) {
lines.push_back(line);
}
std::vector foxs;
std::ifstream file1("B.txt");
std::string fox;
while (std::getline(file1,fox)) {
foxs.push_back(fox);
}
boost::unordered_map hashtable1;
for (int i=0; i< (int) lines.size(); i++)
{ boost::unordered_map hashtable;
for (int j=0; j<(int) foxs.size(); j++)
{
std::string str=lines[i];
std::vector tokens;
boost::split(tokens,str,boost::algorithm::is_any_of("t"));
std::string str1=foxs[j];
std::vector tokens1;
boost::split(tokens1,str1,boost::algorithm::is_any_of("t"));
std::string s1=tokens[3];
std::string s2=tokens1[4];
boost::algorithm::to_lower(s1);
boost::algorithm::to_lower(s2);
boost::replace_all(s1,",","");
boost::replace_all(s2,",","");
boost::replace_all(s1,"-","");
boost::replace_all(s2,"-","");
boost::replace_all(s1,"season","");
boost::replace_all(s2,"season","");
boost::replace_all(s1,"episode","");
boost::replace_all(s2,"episode","");
boost::replace_all(s1,"series","");
boost::replace_all(s2,"series","");
// size_t f = s1.find(",");
// s1.replace(f, std::string(",").length(),"");
// size_t f1=s2.find(",");
// s2.replace(f1, std::string(",").length(),"");
// size_t f2 = s1.find("season");
// s1.replace(f2, std::string("season").length(),"");
// size_t f3=s2.find("season");
// s2.replace(f3, std::string(",").length(),"");
// size_t f4 = s1.find("episode");
// s1.replace(f4, std::string("episode").length(),"");
// size_t f5=s2.find("episode");
// s2.replace(f5, std::string("episode").length(),"");
// size_t f6 = s1.find("series");
// s1.replace(f6, std::string("series").length(),"");
// size_t f7=s2.find("series");
// s2.replace(f7, std::string("series").length(),"");
s1.erase(remove( s1.begin(), s1.end(), '"' ),s1.end());
s2.erase(remove( s2.begin(), s2.end(), '"' ),s2.end());
//size_t f10 = s1.find("-");
// s1.replace(f10, std::string("-").length(),"");
// size_t f11=s2.find("-");
// s2.replace(f11, std::string("-").length(),"");
boost::replace_all(s1," ","");
boost::replace_all(s2," ","");
float k,k2,k3;
k=float (std::max(s1.size(),s2.size()));
k2=float ( uiLevenshteinDistance(s1,s2));
k3=1-k2/k;
hashtable.insert(make_pair(tokens1[4]+"t"+(std::string)tokens1[11],k3));
}
float max=0;
std::string max_key;
for (auto itr=hashtable.begin(); itr !=hashtable.end(); itr++)
{
if ((*itr).second>max)
{
max=(*itr).second;
max_key=(*itr).first;
}
}
hashtable1.insert(make_pair(lines[i],max_key));
}
for (auto itr1=hashtable1.begin(); itr1 !=hashtable1.end(); itr1++)
cout << (*itr1).first << "t" << (*itr1).second << endl;
return 0;
}
天,为什么要用这么长的时间?
我周末要跑12个file B, 每一个file B 都有 4000 行左右,对应一个 file A 162283
行 X 12 列. 今天下午回家从5:30开始run 一个程序, run 到 8 点都没有结束。为
什么这样一个程序都这么耗时?谁来帮帮我,写一个快一点的程序。多谢。有大包子!
t***q
发帖数: 418
2
我的电脑2.60 ghz,应该不会慢呀。天,为什么?

【在 t***q 的大作中提到】
: 天,如何能让程序转得快点?
: 原帖在这里:
: http://www.mitbbs.com/article_t0/Programming/31381809.html
: 主要是要做 title matching.
: 有两个 file, file A 162283 行 X 12 列。 File B 3695 行 X 6 列。用 A 的 第五
: 列和 B的第四列进行比较, 对 B 的第四列的每一行, 从 A的 那 162283 行中 找出
: 与之最相似的那一行。A 的第五列和 B 的第四列都是些影视作品的 title, 是一些长
: 短不一的 string. 我用的是 Levenshtein algorithm 算每一对string 的相似度,再
: 把相似度排序,从高到低,找出相似度最大的那一个 string, 也就是影视作品的
: title, 加到 file B 对应的那一个title 那一行。再加入一个从file A 出来的对应的

c***d
发帖数: 996
3
先把每行call algorithm用的时间打印出来看看, 如果是外面调用的算法慢, 看看
cpu usage是不是单cpu 高, 数据没有dependency就分开一百块分开算, 最后聚合个
结果。

【在 t***q 的大作中提到】
: 天,如何能让程序转得快点?
: 原帖在这里:
: http://www.mitbbs.com/article_t0/Programming/31381809.html
: 主要是要做 title matching.
: 有两个 file, file A 162283 行 X 12 列。 File B 3695 行 X 6 列。用 A 的 第五
: 列和 B的第四列进行比较, 对 B 的第四列的每一行, 从 A的 那 162283 行中 找出
: 与之最相似的那一行。A 的第五列和 B 的第四列都是些影视作品的 title, 是一些长
: 短不一的 string. 我用的是 Levenshtein algorithm 算每一对string 的相似度,再
: 把相似度排序,从高到低,找出相似度最大的那一个 string, 也就是影视作品的
: title, 加到 file B 对应的那一个title 那一行。再加入一个从file A 出来的对应的

c******n
发帖数: 4965
4
高级的办法是用suffix trie

【在 t***q 的大作中提到】
: 天,如何能让程序转得快点?
: 原帖在这里:
: http://www.mitbbs.com/article_t0/Programming/31381809.html
: 主要是要做 title matching.
: 有两个 file, file A 162283 行 X 12 列。 File B 3695 行 X 6 列。用 A 的 第五
: 列和 B的第四列进行比较, 对 B 的第四列的每一行, 从 A的 那 162283 行中 找出
: 与之最相似的那一行。A 的第五列和 B 的第四列都是些影视作品的 title, 是一些长
: 短不一的 string. 我用的是 Levenshtein algorithm 算每一对string 的相似度,再
: 把相似度排序,从高到低,找出相似度最大的那一个 string, 也就是影视作品的
: title, 加到 file B 对应的那一个title 那一行。再加入一个从file A 出来的对应的

c********g
发帖数: 449
5
不改变你的算法,用基本的技巧来 改变/优化 一下你的C++程序的实现可提高一些效
率:
1.在循环体内尽量不要定义数组和变量,要使用的数组和 变量 尽量在循环外边定义。
2.在循环体内尽量不要调用函数,要尽量直接使用 程序模块 即将函数直接体嵌入循环
内。
3.循环体内的计算要优化
a*********a
发帖数: 3656
6
any operation on items in lines are repeated many times.
these should be done out side of the inner loop over foxs and cached.

for (int i=0; i< (int) lines.size(); i++)
{ boost::unordered_map hashtable;
for (int j=0; j<(int) foxs.size(); j++)
{
std::string str=lines[i];
std::vector tokens;
boost::split(tokens,str,boost::algorithm::is_any_of("t"));

【在 t***q 的大作中提到】
: 我的电脑2.60 ghz,应该不会慢呀。天,为什么?
t***q
发帖数: 418
7
多谢大家,包子已发。通过这个project 和大家的帮助学了不少东西。以后慢慢聊。多
谢!
m********2
发帖数: 89
8
内存不够了吧?a可以换成iterable?

【在 t***q 的大作中提到】
: 天,如何能让程序转得快点?
: 原帖在这里:
: http://www.mitbbs.com/article_t0/Programming/31381809.html
: 主要是要做 title matching.
: 有两个 file, file A 162283 行 X 12 列。 File B 3695 行 X 6 列。用 A 的 第五
: 列和 B的第四列进行比较, 对 B 的第四列的每一行, 从 A的 那 162283 行中 找出
: 与之最相似的那一行。A 的第五列和 B 的第四列都是些影视作品的 title, 是一些长
: 短不一的 string. 我用的是 Levenshtein algorithm 算每一对string 的相似度,再
: 把相似度排序,从高到低,找出相似度最大的那一个 string, 也就是影视作品的
: title, 加到 file B 对应的那一个title 那一行。再加入一个从file A 出来的对应的

t***q
发帖数: 418
9
多谢。能不能进一步指点一下。怎么换成 iterable? 我也在考虑内存的问题。如果那
个大的file 行数很多的话,读进去不是要out of memory 了,那该怎么办?听说用
hash table?怎么用呢?多谢!发包子!

【在 m********2 的大作中提到】
: 内存不够了吧?a可以换成iterable?
B***i
发帖数: 724
10
还是对A 做一下index吧
可以的话,用solr存储一下A, 然后用 B 的title做query 来search solr.
包子拿来。
相关主题
一个很诡异的ifstream问题,求助~~how to skip the last empty lines in ifstream?
如何让这个cur变量正确指向新地址请教用c++读取large file怎么可以快一些?
how to use cin as default ifstream?请教一个C++的问题
进入Programming版参与讨论
N********n
发帖数: 8363
11
把原始数据拆成N块。各分块并行计算出MAX之后再汇总找出众MAX之中的MAX。
最基本的DIVIDE & CONQUER & AGGREGATE思路。具体编程要看你的硬件是
MULTI-CORE,MULTI-CPU还是MULTI-SERVER。另外也要看你的编译器针对硬
件生成并行代码的能力,总之关键在并行。
S*A
发帖数: 7142
12
这个问题用 suffix tree 不能有什么大的帮助吧。

【在 c******n 的大作中提到】
: 高级的办法是用suffix trie
g*****g
发帖数: 34805
13
Elastic Search is your friend. With A being indexed, you can expect
subsecond query performance for each title from B. If you run a cluster, you
can keep the performance even if you have hundreds of concurrent queries.
If you want to go with a lighter approach, it's still obviously your problem
can be solved by multi-threading and clustering.
t***q
发帖数: 418
14
多谢大家的回复。我把string processing 那步变简单了,只是将string都换成 lower
case,其他的替换都没变,程序耗时从原先的十几小时,变成了两小时。看来是string
processing 耗时。
我觉得主要是循环那步有问题。多谢!
t***q
发帖数: 418
15
把 c++ 程序改成这样,快了许多,虽说程序不work,但至少说明,应该在算distance
之前就把 string processing 都做了:
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
size_t uiLevenshteinDistance(const std::string &s1, const std::string &s2)
{
const size_t m(s1.size());
const size_t n(s2.size());
if(m == 0) return n;
if(n == 0) return m;
size_t *costs = new size_t[n + 1];
for(size_t k = 0; k <= n; k++) costs[k] = k;
size_t i = 0;
for(std::string::const_iterator it1 = s1.begin(); it1 != s1.end(); ++it1
, ++i)
{
costs[0] = i + 1;
size_t corner = i;
size_t j = 0;
for(std::string::const_iterator it2 = s2.begin(); it2 != s2.end(); +
+it2, ++j)
{
size_t upper = costs[j + 1];
if(*it1 == *it2)
{
costs[j + 1] = corner;
}
else
{
size_t t(upper costs[j + 1] = (costs[j] }
corner = upper;
}
}
size_t result = costs[n];
delete[] costs;
return result;
}
int main()
{
std::vector lines;
std::ifstream file("A.txt");
std::string line;
while(std::getline(file, line)) {
lines.push_back(line);
}
std::vector foxs;
std::ifstream file1("B.txt");
std::string fox;
while(std::getline(file1, fox)) {
foxs.push_back(fox);
}
boost::unordered_map hashtable1;
std::vector tokens;
std::vector s1s;
for(int i = 0; i < (int)lines.size(); i++)
{
std::string str = lines[i];
boost::split(tokens, str, boost::algorithm::is_any_of("t"));
std::string s1 = tokens[3];
boost::algorithm::to_lower(s1);
boost::replace_all(s1, ",", "");
boost::replace_all(s1, "-", "");
boost::replace_all(s1, "season", "");
boost::replace_all(s1, "episode", "");
boost::replace_all(s1, "series", "");
s1.erase(remove(s1.begin(), s1.end(), '"'), s1.end());
boost::replace_all(s1, " ", "");
s1s.push_back(s1);
}
std::vector tokens1;
std::vector s2s;
for(int j = 0; j < (int)foxs.size(); j++)
{
std::string str1 = foxs[j];
boost::split(tokens1, str1, boost::algorithm::is_any_of("t"));
std::string s2 = tokens1[4];
boost::algorithm::to_lower(s2);
boost::replace_all(s2, ",", "");
boost::replace_all(s2, "-", "");
boost::replace_all(s2, "season", "");
boost::replace_all(s2, "episode", "");
boost::replace_all(s2, "series", "");
s2.erase(remove(s2.begin(), s2.end(), '"'), s2.end());
boost::replace_all(s2, " ", "");
s2s.push_back(s2);
}
for(int i = 0; i< (int)lines.size(); i++)
{
boost::unordered_map hashtable;
for(int j = 0; j<(int)foxs.size(); j++)
{
float k, k2, k3;
k = float(std::max(s1s[i].size(), s2s[j].size()));
k2 = float(uiLevenshteinDistance(s1s[i], s2s[j]));
k3 = 1 - k2 / k;
hashtable.insert(make_pair(tokens1[4] + "t" + (std::string)
tokens1[11], k3));
}
float max = 0;
std::string max_key;
for(auto itr = hashtable.begin(); itr != hashtable.end(); itr++)
{
if((*itr).second>max)
{
max = (*itr).second;
max_key = (*itr).first;
}
}
hashtable1.insert(make_pair(lines[i], max_key));
}
for(auto itr1 = hashtable1.begin(); itr1 != hashtable1.end(); itr1++)
cout << (*itr1).first << "t" << (*itr1).second << endl;
return 0;
}

lower
string

【在 t***q 的大作中提到】
: 多谢大家的回复。我把string processing 那步变简单了,只是将string都换成 lower
: case,其他的替换都没变,程序耗时从原先的十几小时,变成了两小时。看来是string
: processing 耗时。
: 我觉得主要是循环那步有问题。多谢!

c********g
发帖数: 449
16
good job! :-)
1 (共1页)
进入Programming版参与讨论
相关主题
istream_iterator问题C++读文本文件怎么判断换行?
python gc question一个很诡异的ifstream问题,求助~~
A problem on string parsing (using either grep or perl)如何让这个cur变量正确指向新地址
问一个C++ set和unordered_set iterator的问题how to use cin as default ifstream?
how to read a sentence into a vector of string?how to skip the last empty lines in ifstream?
读取数据求教请教用c++读取large file怎么可以快一些?
关于文件读取的C++ 问题?请教一个C++的问题
[合集] 如何能让这个程序快一点呢?太慢了C++ 在 windows 上 结果正确, 在 linux 上结果总是不一样,怎
相关话题的讨论汇总
话题: std话题: string话题: boost话题: s1话题: s2