g*****1
发帖数: 998 | 1 一个大概200M的csv file，几百万行，
每行格式一样，我用stringstream和getline读每一行，然后把这行信息(几个varialbe
)存入一个自己写的class object,然后把它push到stl的priority queue,然后做点小计
算。
现在的问题是太慢了，好几个小时没出结果。 请问有哪些地方我做的不对或者要改进
的，让这个过程快一些？ |
j*a
发帖数: 14423 | 2 priority queue这里慢了吧，200m个值啊
varialbe
【在 g*****1 的大作中提到】
: 一个大概200M的csv file，几百万行，
: 每行格式一样，我用stringstream和getline读每一行，然后把这行信息(几个varialbe
: )存入一个自己写的class object,然后把它push到stl的priority queue,然后做点小计
: 算。
: 现在的问题是太慢了，好几个小时没出结果。 请问有哪些地方我做的不对或者要改进
: 的，让这个过程快一些？
|
X****r
发帖数: 3557 | 3 The standard answer is to run a profiler on it (either
with a smaller data set or make it terminate earlier),
then you know what takes all these time.
varialbe
【在 g*****1 的大作中提到】
: 一个大概200M的csv file，几百万行，
: 每行格式一样，我用stringstream和getline读每一行，然后把这行信息(几个varialbe
: )存入一个自己写的class object,然后把它push到stl的priority queue,然后做点小计
: 算。
: 现在的问题是太慢了，好几个小时没出结果。 请问有哪些地方我做的不对或者要改进
: 的，让这个过程快一些？
|
S*********g
发帖数: 5298 | 4 你觉得很大的可能是，你push到priority queue里的时候花了大量的时间
push的complexity是 O(log n)
你花的总时间是 sum _{n=1}^N log(n) ~ N log N - N
如果每一步你花1ms,那么100万个记录对应的是 13815秒 = 3.8小时
varialbe
【在 g*****1 的大作中提到】
: 一个大概200M的csv file，几百万行，
: 每行格式一样，我用stringstream和getline读每一行，然后把这行信息(几个varialbe
: )存入一个自己写的class object,然后把它push到stl的priority queue,然后做点小计
: 算。
: 现在的问题是太慢了，好几个小时没出结果。 请问有哪些地方我做的不对或者要改进
: 的，让这个过程快一些？
|
g*****1
发帖数: 998 | 5 恩，这个确实太费时了，
不知道有别的办法快一些的吗
【在 S*********g 的大作中提到】
: 你觉得很大的可能是，你push到priority queue里的时候花了大量的时间
: push的complexity是 O(log n)
: 你花的总时间是 sum _{n=1}^N log(n) ~ N log N - N
: 如果每一步你花1ms,那么100万个记录对应的是 13815秒 = 3.8小时
:
: varialbe
|
P********e
发帖数: 2610 | 6 你计算complexity是用什么表达方式阿？
sum _...
小计
改进
【在 S*********g 的大作中提到】
: 你觉得很大的可能是，你push到priority queue里的时候花了大量的时间
: push的complexity是 O(log n)
: 你花的总时间是 sum _{n=1}^N log(n) ~ N log N - N
: 如果每一步你花1ms,那么100万个记录对应的是 13815秒 = 3.8小时
:
: varialbe
|
l*y
发帖数: 21010 | 7 这个有错？
【在 P********e 的大作中提到】
: 你计算complexity是用什么表达方式阿？
: sum _...
:
: 小计
: 改进
|
g*****1
发帖数: 998 | 8 是不是stl的priority queue用了vector?
如果自己实现priority queue会不会好些？
【在 S*********g 的大作中提到】
: 你觉得很大的可能是，你push到priority queue里的时候花了大量的时间
: push的complexity是 O(log n)
: 你花的总时间是 sum _{n=1}^N log(n) ~ N log N - N
: 如果每一步你花1ms,那么100万个记录对应的是 13815秒 = 3.8小时
:
: varialbe
|
S*********g
发帖数: 5298 | 9 latex .......
【在 P********e 的大作中提到】
: 你计算complexity是用什么表达方式阿？
: sum _...
:
: 小计
: 改进
|
S*********g
发帖数: 5298 | 10 这个是C++标准定义的complexity
【在 g*****1 的大作中提到】
: 是不是stl的priority queue用了vector?
: 如果自己实现priority queue会不会好些？
|
|
|
g*****g
发帖数: 34805 | 11 对C++的IO类不熟，但直觉就是你的buffering太小。开个大缓冲区，
把东西读进来再处理，会好很多。如果读一行disk IO一次，就会很慢。
varialbe
【在 g*****1 的大作中提到】
: 一个大概200M的csv file，几百万行，
: 每行格式一样，我用stringstream和getline读每一行，然后把这行信息(几个varialbe
: )存入一个自己写的class object,然后把它push到stl的priority queue,然后做点小计
: 算。
: 现在的问题是太慢了，好几个小时没出结果。 请问有哪些地方我做的不对或者要改进
: 的，让这个过程快一些？
|
p***o
发帖数: 1252 | 12 你要是不愿意帖code, 还是先profile一下搞清楚为啥慢把, 猜来猜去都不靠谱。
【在 g*****1 的大作中提到】
: 是不是stl的priority queue用了vector?
: 如果自己实现priority queue会不会好些？
|
p***o
发帖数: 1252 | 13 不至于，缺省的没那么慢。
【在 g*****g 的大作中提到】
: 对C++的IO类不熟，但直觉就是你的buffering太小。开个大缓冲区，
: 把东西读进来再处理，会好很多。如果读一行disk IO一次，就会很慢。
:
: varialbe
|
y**b
发帖数: 10166 | 14 使用流迭代器是不是会快一些？通常一个一个push进容器的效率不如给出一个迭代器范
围。
ifstream in("your_file");
istream_iterator in_iter(in);
istream_iterator eof;
priority_queue pq(in_iter, eof);
当然your_class需要重载输入操作符>>
varialbe
【在 g*****1 的大作中提到】
: 一个大概200M的csv file，几百万行，
: 每行格式一样，我用stringstream和getline读每一行，然后把这行信息(几个varialbe
: )存入一个自己写的class object,然后把它push到stl的priority queue,然后做点小计
: 算。
: 现在的问题是太慢了，好几个小时没出结果。 请问有哪些地方我做的不对或者要改进
: 的，让这个过程快一些？
|
p***o
发帖数: 1252 | 15 input iterator怎么可能更快 ...
【在 y**b 的大作中提到】
: 使用流迭代器是不是会快一些？通常一个一个push进容器的效率不如给出一个迭代器范
: 围。
: ifstream in("your_file");
: istream_iterator in_iter(in);
: istream_iterator eof;
: priority_queue pq(in_iter, eof);
: 当然your_class需要重载输入操作符>>
:
: varialbe
|
p***o
发帖数: 1252 | 16 帮你猜一把：把所有的priority_queue换成set看看，估计是你的class比较大，
vector里copy来copy去耗掉了太多时间。
【在 p***o 的大作中提到】
: 你要是不愿意帖code, 还是先profile一下搞清楚为啥慢把, 猜来猜去都不靠谱。
|
y**b
发帖数: 10166 | 17 为什么呢？
【在 p***o 的大作中提到】
: input iterator怎么可能更快 ...
|
g*****1
发帖数: 998 | 18 谢谢各位，我需要学的太多，你们说的profiling我根本没用过。
这里要模拟数据一条一条进入，来一条处理一个，所以只能一个个push。
不过目前我自己觉得有一个问题是因为每行我都push into heap,所以隔一段要主动
resize一下。可是具体怎么做我还没研究。不过刚看到一个"You cannot directly access the underlying container to modify the capacity. You can however change the container that is used internally to a std::deque. The std::deque container might be slightly slower (not in big-O notation) than a vector, but growing it is much faster as it does not need to relocate all existing elements."
我再研下profiling看看 |
p***o
发帖数: 1252 | 19 你把priority_queue换成set看看
access the underlying container to modify the capacity. You can however
change the container that is used internally to a std::deque. The std::deque
container might be slightly
【在 g*****1 的大作中提到】
: 谢谢各位，我需要学的太多，你们说的profiling我根本没用过。
: 这里要模拟数据一条一条进入，来一条处理一个，所以只能一个个push。
: 不过目前我自己觉得有一个问题是因为每行我都push into heap,所以隔一段要主动
: resize一下。可是具体怎么做我还没研究。不过刚看到一个"You cannot directly access the underlying container to modify the capacity. You can however change the container that is used internally to a std::deque. The std::deque container might be slightly slower (not in big-O notation) than a vector, but growing it is much faster as it does not need to relocate all existing elements."
: 我再研下profiling看看
|
a******d
发帖数: 191 | 20 Very likely inserting into priority queue involves rebalancing etc
unnecessarily in the middle. Try use an array (if possible) or vector or set
(if only this works), then construct the priority queue this it. |
|
|
y**b
发帖数: 10166 | 21 简单测试了一下，读一千万个记录(每个记录是一个int)、80MB大小的文件，
无论是用vector还是priority_queue,
无论是读一行push一次，还是给出一个区间构造容器，
无论是采用int直接放入容器还是用该int构造某个简单class(重载>>,<<,<)放入容器，
都在10秒以内。
比较有趣的，用区间构造容器比读一行push一次慢20%左右, why?
再就是priority_queue对数据顺序比较敏感，
递增序列用8秒(同样情况vector为1.22秒)，
递减序列用2秒(同样情况vector为1.22秒)，这个好理解，优先队列要比呀比。
还有就是比较了一下读入并放入vector(1.22秒)和读入但不放入vector(1.17秒),
可见放入vector容器只用了0.05秒，很快，而放入优先队列要花费更多时间。
我把源码和makefile放这里，大家有空玩玩：
https://sites.google.com/site/forconvenience/Home/reader.tar，
1. 1write生成数据文件，可以改动记录数，生成常数系列、递增系列、递减系列。
2. 2read采用区间读入，可以改动元素类型(int或datastore)，可以选择向量或优先队
列，可以选择验证读入结果。
3. 3read1采用一次读一行，也可以改动元素类型(int或datastore)，可以选择向量或优
先队列，可以选择验证读入结果。
lz的问题难以直接回答，可能该class非常复杂而导致耗时？没有profiling只能猜测。
access the underlying container to modify the capacity. You can however
change the container that is used internally to a std::deque. The std::deque
container might be slightly
【在 g*****1 的大作中提到】
: 谢谢各位，我需要学的太多，你们说的profiling我根本没用过。
: 这里要模拟数据一条一条进入，来一条处理一个，所以只能一个个push。
: 不过目前我自己觉得有一个问题是因为每行我都push into heap,所以隔一段要主动
: resize一下。可是具体怎么做我还没研究。不过刚看到一个"You cannot directly access the underlying container to modify the capacity. You can however change the container that is used internally to a std::deque. The std::deque container might be slightly slower (not in big-O notation) than a vector, but growing it is much faster as it does not need to relocate all existing elements."
: 我再研下profiling看看
|
r********3
发帖数: 2998 | 22 用buffered来读。 才200M的csv文件，以现在的硬盘速度，应该在10-20秒内就可以读
完并存入内存对象。
varialbe
【在 g*****1 的大作中提到】
: 一个大概200M的csv file，几百万行，
: 每行格式一样，我用stringstream和getline读每一行，然后把这行信息(几个varialbe
: )存入一个自己写的class object,然后把它push到stl的priority queue,然后做点小计
: 算。
: 现在的问题是太慢了，好几个小时没出结果。 请问有哪些地方我做的不对或者要改进
: 的，让这个过程快一些？
|
D*******a
发帖数: 3688 | 23 maybe faster to read everything and sort. 200m fits in memory easily.
varialbe
【在 g*****1 的大作中提到】
: 一个大概200M的csv file，几百万行，
: 每行格式一样，我用stringstream和getline读每一行，然后把这行信息(几个varialbe
: )存入一个自己写的class object,然后把它push到stl的priority queue,然后做点小计
: 算。
: 现在的问题是太慢了，好几个小时没出结果。 请问有哪些地方我做的不对或者要改进
: 的，让这个过程快一些？
|
P********e
发帖数: 2610 | 24 晕，弄点通俗易懂的。不然也没办法看你说的对不对阿。。。。
【在 S*********g 的大作中提到】
: latex .......
|
N*****m
发帖数: 42603 | 25 还有比这个更通俗易懂的么？
【在 P********e 的大作中提到】
: 晕，弄点通俗易懂的。不然也没办法看你说的对不对阿。。。。
|
P********e
发帖数: 2610 | 26 有趣。
【在 N*****m 的大作中提到】
: 还有比这个更通俗易懂的么？
|
j*a
发帖数: 14423 | 27 上phd的写纸很多都上latex
【在 P********e 的大作中提到】
: 晕，弄点通俗易懂的。不然也没办法看你说的对不对阿。。。。
|
f*****Q
发帖数: 1912 | 28 re
int length;
char * fileBuffer;
ifstream is;
is.open ("xxx.csv", ios::binary );
is.seekg (0, ios::end);
length = is.tellg();
buffer = new char [length];
is.seekg (0, ios::beg);
is.read (fileBuffer,length);
然后就对着fileBuffer干好了。
【在 r********3 的大作中提到】
: 用buffered来读。 才200M的csv文件，以现在的硬盘速度，应该在10-20秒内就可以读
: 完并存入内存对象。
:
: varialbe
|
P********e
发帖数: 2610 | 29 咱早就不弄了，明摆的不让不懂latex的人看懂。
我们这种学了算法的都看不懂，难道这个版要求phd学历？
【在 j*a 的大作中提到】
: 上phd的写纸很多都上latex
|
j*a
发帖数: 14423 | 30 不会啊 但是人家习惯了那种表达方式 不要理解为别的什么
【在 P********e 的大作中提到】
: 咱早就不弄了，明摆的不让不懂latex的人看懂。
: 我们这种学了算法的都看不懂，难道这个版要求phd学历？
|
|
|
L***n
发帖数: 6727 | 31 latex 对数学公式的表达方式基本上就是一个人念公式念出声的表达方式，
基本上不会有其他方式比这个更简明了（可能troff eqn好一点点，更接近
人类语言，但是也更verbose, 这俩基本上没啥本质区别），除了tex和troff，
还有其他什么更简明的写数学公式的方式么？
【在 P********e 的大作中提到】
: 咱早就不弄了，明摆的不让不懂latex的人看懂。
: 我们这种学了算法的都看不懂，难道这个版要求phd学历？
|
P********e
发帖数: 2610 | 32 好吧，我没明白为什么这么长一个公式，不过不知道是不是因为表达方式的不一样。
【在 L***n 的大作中提到】
: latex 对数学公式的表达方式基本上就是一个人念公式念出声的表达方式，
: 基本上不会有其他方式比这个更简明了（可能troff eqn好一点点，更接近
: 人类语言，但是也更verbose, 这俩基本上没啥本质区别），除了tex和troff，
: 还有其他什么更简明的写数学公式的方式么？
|
c*******w
发帖数: 23 | 33 You can try run multiple processes. First process read csv file from record
1 to 100k, 2nd process read from record 100001 thru 200k, etc. |
l*****z
发帖数: 2305 | 34 read a chunk of that file and then do the processing job. |
d*********8
发帖数: 2192 | 35 file IO 肯定不是问题，才200M
应该是PUSH的问题。
你是否在PUSH时进行了比较，查找，插入？这是大头。
如果是的话，先不改代码，把文件SORT一下看看是否好点。 |
g*****1
发帖数: 998 | 36 文件不能sort,因为要模拟每行数据在不同时间点进来。所以要一个个push。
刚才学习了下用profile，发现耗时最多的是我自定义的class中的2个member function
,都是用来获取data member数值的。
因为push的时候用了自定义的一个比较 bool operator<(const oneOrder &a, const
oneOrder &b)，这个里面大量的用到了上面的2个member function
其实我这个class很简单，除了data member就是get member value function了,是不是
有点为了用class而用?是不是根本就因该弄成一个简单的struct,直接读数据，不要什
么member function
【在 d*********8 的大作中提到】
: file IO 肯定不是问题，才200M
: 应该是PUSH的问题。
: 你是否在PUSH时进行了比较，查找，插入？这是大头。
: 如果是的话，先不改代码，把文件SORT一下看看是否好点。
|
a****l
发帖数: 8211 | 37 这是火上浇油。
record
【在 c*******w 的大作中提到】
: You can try run multiple processes. First process read csv file from record
: 1 to 100k, 2nd process read from record 100001 thru 200k, etc.
|
n****n
发帖数: 568 | 38 我们写过类似的project,文件比这个还要大，全部读进来也就几分钟。你试着把文件先
全部读近。
varialbe
function,都是用来获取data member数值的。
oneOrder &b)，这个里面大量的用到了上面的2个member function
【在 g*****1 的大作中提到】
: 一个大概200M的csv file，几百万行，
: 每行格式一样，我用stringstream和getline读每一行，然后把这行信息(几个varialbe
: )存入一个自己写的class object,然后把它push到stl的priority queue,然后做点小计
: 算。
: 现在的问题是太慢了，好几个小时没出结果。 请问有哪些地方我做的不对或者要改进
: 的，让这个过程快一些？
|
x*******1
发帖数: 28835 | 39 Looks like design a I/O middleware.
use buffer class? avoid frequent I/O. batch request?
200 M can be fit into a laptop's memory. not big deal. |
