std :: list和std :: set之间的因子50.000？ [英] factor 50.000 between std::list and std::set?

问题描述

如果我有一个带有1.000.000元素的已排序的std :: list，则需要1.000.000

操作来查找值为1.000.000的元素（需要迭代器

通过整个列表。


相比之下，如果我有一个带有1.000.000元素的std :: set，那么只需要
需要大约lg 1.000.000 = 20次操作！在这种情况下，

差异是否真的是1.000.000 / 20 = 50.000？

解决方案

< blockquote> desktop写道：

如果我有一个带有1.000.000元素的已排序的std :: list，则需要1.000.000

操作查找元素值= 1.000.000（需要迭代器

整个列表）。


相比之下，如果我有一个std :: set with 1.000.000元素只会

需要大约lg 1.000.000 = 20次操作！在这种情况下，

差异是否真的是1.000.000 / 20 = 50.000？

是的。现在做同样的练习，但寻找第一个元素。

的差异并不是那么戏剧化，但它就在那里。


-


- Pete

Roundhouse Consulting，Ltd。（ www.versatilecoding.com ）

标准C ++库扩展：教程和
参考的作者。 （ www.petebecker.com/tr1book ）

desktop写道：

如果我有一个带有1.000.000元素的排序std :: list需要1.000.000

操作找到值为1.000.000的元素（需要迭代器

整个列表）。


相比之下，如果我有一个标准::设置1.000.000元素只会

需要大约lg 1.000.000 = 20次操作！在这种情况下，

差异是否真的是1.000.000 / 20 = 50.000？

是的。列表是线性搜索，也就是找到元素的O（N）。具有对数时间搜索O（log N）所需的集合是
。所以指定的时间

非常有意义。

Pete Becker写道：

desktop写道：

>如果我有一个带有1.000.000元素的已排序的std :: list，则需要使用
1.000.000操作来查找元素value = 1.000.000（需要在整个列表中使用迭代器）。

相比之下，如果我有一个带有1.000.000元素的std :: set它只会
大约需要1.000.000 = 20次操作！真的可以吗？在这种情况下差异是1.000.000 / 20 = 50.000的因素吗？

是的。现在做同样的练习，但寻找第一个元素。

的差异并不是那么显着，但它就在那里。

在排序列表中，它需要恒定的时间。但是在设置中它可能会花费20美元来执行20次操作，除非你使用某种类型的标题总是有指向最小值和最大值的
指针。但在上一个例子中，仍然有一个因子50.000似乎是超自然的！

If I have a sorted std::list with 1.000.000 elements it takes 1.000.000
operations to find element with value = 1.000.000 (need to iterator
through the whole list).

In comparison, if I have a std::set with 1.000.000 element it will only
take approx lg 1.000.000 = 20 operations! Can it really be true that the
difference is a factor of 1.000.000/20 = 50.000 in this case?

解决方案

desktop wrote:

If I have a sorted std::list with 1.000.000 elements it takes 1.000.000
operations to find element with value = 1.000.000 (need to iterator
through the whole list).

In comparison, if I have a std::set with 1.000.000 element it will only
take approx lg 1.000.000 = 20 operations! Can it really be true that the
difference is a factor of 1.000.000/20 = 50.000 in this case?

Yes. Now do the same exercise, but look for the first element. The
difference isn''t as dramatic, but it''s there.

--

-- Pete
Roundhouse Consulting, Ltd. (www.versatilecoding.com)
Author of "The Standard C++ Library Extensions: a Tutorial and
Reference." (www.petebecker.com/tr1book)

desktop wrote:

If I have a sorted std::list with 1.000.000 elements it takes 1.000.000
operations to find element with value = 1.000.000 (need to iterator
through the whole list).

In comparison, if I have a std::set with 1.000.000 element it will only
take approx lg 1.000.000 = 20 operations! Can it really be true that the
difference is a factor of 1.000.000/20 = 50.000 in this case?

Yes. A list is a linear search, aka O(N) to find an element. A set is
required to have logarithmic time search O(log N). So a times specified
make perfect sense.

Pete Becker wrote:

desktop wrote:

>If I have a sorted std::list with 1.000.000 elements it takes
1.000.000 operations to find element with value = 1.000.000 (need to
iterator through the whole list).

In comparison, if I have a std::set with 1.000.000 element it will
only take approx lg 1.000.000 = 20 operations! Can it really be true
that the difference is a factor of 1.000.000/20 = 50.000 in this case?

Yes. Now do the same exercise, but look for the first element. The
difference isn''t as dramatic, but it''s there.

Well in a sorted list it takes constant time. But in the set it might
take 20 operations, unless you use some kind of header that always have
pointers to min and max. But still a factor 50.000 seems supernatural in
the previous example!

这篇关于std :: list和std :: set之间的因子50.000？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！