简单列表效率问题 [英] simple list efficiency question
问题描述
我的程序收到了几百万个数据项,我希望
将它们存储在列表中,每个项目被插入
列表中的任何位置。任何性能提示,以便我的程序运行正常吗?
我已经检查了STL,并考虑过使用矢量,设置,列表,
deque和map 。我不知道这些东西是如何实现的,所以不确定
哪个最好用,或者我应该实现另一个数据结构。
也许可以使用它们中的任何一个或全部没有什么大问题。
我只是担心如果我浪费精力与他们一起编码然后找到我需要实现别的东西,因为它运行如此慢。我是新手
使用c ++,所以在我开始学习如何编写
之前先了解它会很不错。
感谢您的帮助。
jason
您好,
杰森 < JA *********** @ btinternet.com>写道:
我的程序收到了几百万个数据项,我希望将它们存储在一个列表中,每个项目都插入到
清单。任何性能提示,以便我的程序运行正常?
我已经检查了STL,并考虑过使用矢量,设置,列表,
deque和map。我不知道这些东西是如何实现的,所以不确定哪个最好用,或者我应该实现另一个数据结构。
也许任何或所有这些都可以使用而没有大问题。
如果我理解正确,您希望以分类的
方式存储这些对象。对于一个像几百万这样的数字,我的猜测就是你可以将它们存放在一个向量中并且在它们全部读完之后将它们全部读出来。
对它们进行排序。因为排序是(如果对象是
进入的顺序并不太糟糕)N * log(N)操作,这不应该花费很长时间。此外,很难想象你
可能比N * log(N)更快。
祝你好运,
Chris Dams
ch****@gamow.sci。 kun.nl (Chris Dams)写道:
如果我理解正确,你想以有条件的方式存储这些对象。对于几百万这样的数字,我的猜测是你可以将它们存储在一个向量中,然后将它们全部读入后对它们进行排序。因为排序是(如果对象进入的顺序不是太糟糕)N * log(N)操作,这不应该过长。此外,很难想象你可能比N * log(N)更快。
忘了提一下如果你使用矢量你不要忘记
使用合理的数字调用.reserve()方法。
Chris Dams写道:
你好,
杰森 < JA *********** @ btinternet.com>写道:
我的程序收到了几百万个数据项,我希望将它们存储在一个列表中,每个项目都插入到
清单。任何性能提示,以便我的程序运行正常?
我已经检查了STL,并考虑过使用矢量,设置,列表,
deque和map 。我不知道这些东西是如何实现的,所以不确定哪个最好用,或者我应该实现另一个数据结构。
也许任何或所有这些都可以使用而没有大问题。
如果我理解正确,您希望以分类的方式存储这些对象。对于几百万这样的数字,我的猜测是你可以将它们存储在一个向量中,然后将它们全部读入后对它们进行排序。因为排序是(如果对象进入的顺序不是太糟糕)N * log(N)操作,这不应该过长。此外,很难想象你可能比N * log(N)更快。
我也会用地图交叉检查。
-
Karl Heinz Buchegger
kb * *****@gascad.at
Hi,
I have a few million data items being received by my program and I wish to
store them in a list, with each item being inserted in any position in the
list. Any performance tips so that my program runs ok?
I have checked out the STL and have thought of using vector, set, list,
deque and map. I dont know how these things are implemented so not sure
which is best to use or if i should implement another data structure.
Perhaps any or all of them can be used with no big problem.
I am just worried in case I waste effort coding with them and then finding i
need to implement something else because it runs so slow. I''m a novice
using c++ so it would be nice to know up front before I start learning how
to write it.
Thanks for your help.
jason
Hello,
"Jason" <ja***********@btinternet.com> writes:
I have a few million data items being received by my program and I wish to
store them in a list, with each item being inserted in any position in the
list. Any performance tips so that my program runs ok? I have checked out the STL and have thought of using vector, set, list,
deque and map. I dont know how these things are implemented so not sure
which is best to use or if i should implement another data structure.
Perhaps any or all of them can be used with no big problem.
If I understand correctly you want to store these objects in a sorted
fashion. For a number like a few million my guess would be that you can
get away with storing them in a vector and after they are all read in
sorting them. Because sorting is (if the order in which the objects are
coming in is not too bad) an N*log(N) operation this should not take
prohibitively long. Furthermore, it is difficult to imagine that you
could be faster than N*log(N).
Good luck,
Chris Dams
ch****@gamow.sci.kun.nl (Chris Dams) writes:
If I understand correctly you want to store these objects in a sorted
fashion. For a number like a few million my guess would be that you can
get away with storing them in a vector and after they are all read in
sorting them. Because sorting is (if the order in which the objects are
coming in is not too bad) an N*log(N) operation this should not take
prohibitively long. Furthermore, it is difficult to imagine that you
could be faster than N*log(N).
Forgot to mention that if you use a vector you should not forget to
call the .reserve() method with a sensible number.
Chris Dams wrote:
Hello,
"Jason" <ja***********@btinternet.com> writes:I have a few million data items being received by my program and I wish to
store them in a list, with each item being inserted in any position in the
list. Any performance tips so that my program runs ok?
I have checked out the STL and have thought of using vector, set, list,
deque and map. I dont know how these things are implemented so not sure
which is best to use or if i should implement another data structure.
Perhaps any or all of them can be used with no big problem.
If I understand correctly you want to store these objects in a sorted
fashion. For a number like a few million my guess would be that you can
get away with storing them in a vector and after they are all read in
sorting them. Because sorting is (if the order in which the objects are
coming in is not too bad) an N*log(N) operation this should not take
prohibitively long. Furthermore, it is difficult to imagine that you
could be faster than N*log(N).
I would cross check with a map also.
--
Karl Heinz Buchegger
kb******@gascad.at
这篇关于简单列表效率问题的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!