avatar
t*q
1
【 以下文字转载自 Programming 讨论区 】
发信人: treeq (treeq), 信区: Programming
标 题: 天,如何能让程序转得快点?有包子。
发信站: BBS 未名空间站 (Fri Feb 27 23:26:22 2015, 美东)
天,如何能让程序转得快点?
原帖在这里:
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(uppercosts[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{
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 点都没有结束。为
什么这样一个程序都这么耗时?谁来帮帮我,写一个快一点的程序。多谢。有大包子!
avatar
r*r
2
出去几次带脚架觉得很不方便,需要买个包了。
这个 Gitzo GC3100 Series 3 Tripod Bag 怎么样,好用吗?
avatar
g*7
3
gcc优化打开了吗?
avatar
G*Y
4
这个看上去不能背呀。

【在 r*********r 的大作中提到】
: 出去几次带脚架觉得很不方便,需要买个包了。
: 这个 Gitzo GC3100 Series 3 Tripod Bag 怎么样,好用吗?

avatar
t*q
5
What is gcc 优化?please give me a hint or link, thank you!

【在 g*******7 的大作中提到】
: gcc优化打开了吗?
avatar
r*r
6
背带应该有的。图上没显示吧。

【在 G**Y 的大作中提到】
: 这个看上去不能背呀。
avatar
p*r
7
你先要搞清楚,慢是因为算法本身慢,还是写得不好,或者有bug。
会做profile吗?
或者你自己可以做一个profile,就是统计出每一个routine被call了多少次,每次花了
多少时间。
然后你就有了改进的目标。
avatar
p*r
9
还可以这样实验,
file A 162 行 X 12 列,计算CPU time
file A 1622 行 X 12 列,计算CPU time
file A 16228 行 X 12 列,计算CPU time
file A 162283 行 X 12 列,计算CPU time
看看这四种情况,CPU time 变化的规律。
avatar
G*e
10
不值。淘宝上有山寨,还可以。

【在 r*********r 的大作中提到】
: 出去几次带脚架觉得很不方便,需要买个包了。
: 这个 Gitzo GC3100 Series 3 Tripod Bag 怎么样,好用吗?

avatar
m*v
11
把A用不同长度的substrings来 build index
用B的作为query,用OR search去search top k (相当于用了不同的distance算法), 再
用edit distance(也许都不用这步了)
lucene搜索是优化了得,非常快

【在 t***q 的大作中提到】
: What is gcc 优化?please give me a hint or link, thank you!
avatar
o*e
13
+1 on lucene , index b4, and query each of a5, select top x, should be
lightening fast. don't bother to write your own matching algorithm.
avatar
k*t
14
叔, 这不是. 装躺衣的都是一层FABRIC

【在 o****p 的大作中提到】
: 啊,好像是别人装躺椅的包。
avatar
l*c
15
That's a strange question.
Anyone who used GCC should know optimization -O2 or -O3 or -OS.
How did you compile your code, what's your make file?
Also improve algorithm, memory,cache.

【在 t***q 的大作中提到】
: What is gcc 优化?please give me a hint or link, thank you!
avatar
o*p
16
这不是形容词嘛。。。。。。。

【在 k****t 的大作中提到】
: 叔, 这不是. 装躺衣的都是一层FABRIC
avatar
t*q
17
多谢大家,包子已发。通过这个project 和大家的帮助学了不少东西。以后慢慢聊。多
谢!
avatar
x5
19
你们这辈分。。。

【在 k****t 的大作中提到】
: 叔, 这不是. 装躺衣的都是一层FABRIC
avatar
b*6
20
买架子不是应该带包的吗?
avatar
f*n
21
我当年买了个50刀的

【在 r*********r 的大作中提到】
: 出去几次带脚架觉得很不方便,需要买个包了。
: 这个 Gitzo GC3100 Series 3 Tripod Bag 怎么样,好用吗?

avatar
r*r
22
带的是 dust cover,不是包。

【在 b********6 的大作中提到】
: 买架子不是应该带包的吗?
avatar
i*8
23
一个包都这么贵 我还是手里拎好了
相关阅读
logo
联系我们隐私协议©2024 redian.news
Redian新闻
Redian.news刊载任何文章,不代表同意其说法或描述,仅为提供更多信息,也不构成任何建议。文章信息的合法性及真实性由其作者负责,与Redian.news及其运营公司无关。欢迎投稿,如发现稿件侵权,或作者不愿在本网发表文章,请版权拥有者通知本网处理。