如何演示算法的bigO成本？ [英] How to demonstrate bigO cost of algorithms?

问题描述

嗨 -


我正在学习算法，我想编写一个python程序，

计算实际的运行时间。


我想在我的程序中增加一个名为n的全局变量，所以

我可以看到问题大小和
$ b $之间的关系b步数。


这是我笨拙的尝试实现这个：


def qsort（ll）：

尝试：

全球n

n + = len（ll）

打印将％d添加到％d。 ％（len（ll），n）

print"递增n到％d。 ％n

除外：

通过

如果len（ll）== 0：

返回[]

p = ll [0]

left = [x代表l的x，如果x< p]

mid = [如果x == p，则x为x in ll]

right = [x，如果x> x则x为ll p]

返回qsort（左）+ mid + qsort（右）


我没有得到我希望的结果。我预计在

程序完成后，我会得到结果


len（ll）* math.log（len（ll），2）


因为除了最糟糕的情况之外，快速排序的大O是nlogn。


我想为mergesort编写类似的函数，bubblesort，以及所有

数据结构类中涵盖的其他基本算法。


欢迎所有帮助。


-

赠送和免费赠送东西： http://freecycle.org

Hi -

I''m studying algorithms and I want to write a python program that
calculates the actual runtimes.

I want to increment up some global variable called n in my program so
that I can see the relationship between the size of the problem and the
number of steps.

Here''s my clumsy attempt to implement this:

def qsort(ll):
try:
global n
n += len(ll)
print "adding %d to %d." % (len(ll), n)
print "incrementing up n to %d." % n
except:
pass
if len(ll) == 0:
return []
p = ll[0]
left = [x for x in ll if x < p]
mid = [x for x in ll if x == p]
right = [x for x in ll if x > p]
return qsort(left) + mid + qsort(right)

I''m not getting the results I hoped for. I expected that after the
program is finished, I would get results near

len(ll) * math.log(len(ll), 2)

since the big O for quicksort is nlogn for all but the worst case.

I''d like to write similar functions for mergesort, bubblesort, and all
the other basic algorithms covered in data structures classes.

All help is welcome.

--
Give and take free stuff: http://freecycle.org

推荐答案

Rusty Shackleford写道：

Rusty Shackleford wrote:

嗨 -

我是学习算法，我想编写一个python程序来计算实际的运行时间。

我想在我的程序中增加一个名为n的全局变量，以便我可以看到问题的大小与步数之间的关系。

[snipped]

Hi -

I''m studying algorithms and I want to write a python program that
calculates the actual runtimes.

I want to increment up some global variable called n in my program so
that I can see the relationship between the size of the problem and the
number of steps.

Here''s my clumsy attempt to implement this:

[snipped]

那个丑陋的try-except块是什么？它似乎只是隐藏

潜在的错误。


无论如何，如果你只测试基于比较的排序算法，那么

为什么不创建一个新类（可能通过子类化内置函数）和

实现一个__cmp__方法，该方法在调用时递增全局。

这样你就可以得到一个精确的计数比较的数量。


干杯，

Brian

What is that ugly try-except block for? All it seems to do is hide
potential errors.

Anyway, if you are only testing comparison-base sorting algorithms then
why not create a new class (maybe by subclassing a builtin) and
implement a __cmp__ method that increments a global whenever called.
That way you will get an exact count of the number of comparisons.

Cheers,
Brian

周三，2004年6月2日15:40:12 GMT，Rusty Shackleford

< [e-mail]>在comp.lang.python中声明了以下内容：

On Wed, 02 Jun 2004 15:40:12 GMT, Rusty Shackleford
<[e-mail]> declaimed the following in comp.lang.python:

嗨 -

我正在研究算法，我想写一个
计算实际运行时间。


看一看Python Library Manual的10.10节（呃，

需要Python 2.3+）。这应该直接让你获得运行时间。

我想在我的程序中增加一个名为n的全局变量，以便我可以看到问题的大小与
步数。

这是我笨拙的尝试实现这个：

def qsort（ll）：
尝试：
global n
n + = len（ll）
print将％d添加到％d。 ％（len（ll），n）
打印将n递增到％d。 ％n
除了：
传递
如果len（ll）== 0：
返回[]
p = ll [0]
left = [如果x mid = [x代表ll，如果x == p，则x =
对= [x代表x的x，如果x> p]
返回qsort（左）+ mid + qsort（右）

我没有得到我希望的结果。我预计在
程序完成后，我会得到结果

len（ll）* math.log（len（ll），2）

因为除了最坏的情况之外，快速排序的大O是nlogn。

我想为mergesort，bubblesort和所有数据覆盖的其他基本算法编写类似的函数。结构课程。

欢迎所有帮助。


- ==================================== ============== ============<
wl ***** @ ix.netcom.com | Wulfraed Dennis Lee Bieber KD6MOG<
wu******@dm.net | Bestiaria支持人员<
========================================= ========= ============<
主页：< http://www.dm.net/~wulfraed/> <
溢出页面：< http://wlfraed.home.netcom.com/> <

Hi -

I''m studying algorithms and I want to write a python program that
calculates the actual runtimes.
Take a look at section 10.10 of the Python Library Manual (uh,
requires Python 2.3+). That should get you the run-times directly.

I want to increment up some global variable called n in my program so
that I can see the relationship between the size of the problem and the
number of steps.

Here''s my clumsy attempt to implement this:

def qsort(ll):
try:
global n
n += len(ll)
print "adding %d to %d." % (len(ll), n)
print "incrementing up n to %d." % n
except:
pass
if len(ll) == 0:
return []
p = ll[0]
left = [x for x in ll if x < p]
mid = [x for x in ll if x == p]
right = [x for x in ll if x > p]
return qsort(left) + mid + qsort(right)

I''m not getting the results I hoped for. I expected that after the
program is finished, I would get results near

len(ll) * math.log(len(ll), 2)

since the big O for quicksort is nlogn for all but the worst case.

I''d like to write similar functions for mergesort, bubblesort, and all
the other basic algorithms covered in data structures classes.

All help is welcome.
-- ================================================== ============ <
wl*****@ix.netcom.com | Wulfraed Dennis Lee Bieber KD6MOG <
wu******@dm.net | Bestiaria Support Staff <
================================================== ============ <
Home Page: <http://www.dm.net/~wulfraed/> <
Overflow Page: <http://wlfraed.home.netcom.com/> <

Rusty Shackleford< [e-mail]>写在

news：sl *************** @ frank.overlook.homelinux.ne t：

Rusty Shackleford <[e-mail]> wrote in
news:sl***************@frank.overlook.homelinux.ne t:

这是我笨拙地尝试实现这个：

def qsort（ll）：
尝试：
全球n
n + = len（ll）
print将％d添加到％d。 ％（len（ll），n）
打印将n递增到％d。 ％n
除了：
传递
如果len（ll）== 0：
返回[]
p = ll [0]
left = [如果x mid = [x代表ll，如果x == p，则x =
对= [x代表x的x，如果x> p]
返回qsort（左）+ mid + qsort（右）

我没有得到我希望的结果。我预计在
程序完成后，我会得到结果

len（ll）* math.log（len（ll），2）

因为除了最糟糕的情况之外，快速排序的大O是nlogn。

Here''s my clumsy attempt to implement this:

def qsort(ll):
try:
global n
n += len(ll)
print "adding %d to %d." % (len(ll), n)
print "incrementing up n to %d." % n
except:
pass
if len(ll) == 0:
return []
p = ll[0]
left = [x for x in ll if x < p]
mid = [x for x in ll if x == p]
right = [x for x in ll if x > p]
return qsort(left) + mid + qsort(right)

I''m not getting the results I hoped for. I expected that after the
program is finished, I would get results near

len(ll) * math.log(len(ll), 2)

since the big O for quicksort is nlogn for all but the worst case.

你没有说明你在列表中传递了什么类型的对象。

你也说过你试过的''n'值有多大。你也没有说过你是如何确保你没有遇到最糟糕的表现。


Python可能不是证明这种情况的最佳语言效果。两个

的东西会影响大多数语言的排序速度：比较次数，
和复制数据项的次数，但其他因素可能会出现

与比较和移动相比较慢。它可能在这里你的比较相对较快（特别是如果你只是使用整数作为输入数据），并且时间被淹没了

函数调用开销并创建所有这些中间列表。在

这种情况​​下，您可能只需要增加列表的长度。很多。


大多数快速排序实施就地排序数据。您正在为左，中，右创建新的

列表，然后通过连接递归调用的结果再次创建新列表。这两个都涉及内存分配，并且这些列表可能需要在内存中移动，因为它们会增长。所有这些都使订单计算变得复杂。


另外，请记住，如果你的列表太长，你很可能会开始交换虚拟内存，所以你所有的那个时候走出窗外。

更不用说垃圾收集了。


如果你想得到一个符合你期望的结果，那么我认为

你最好对内部数据进行操作，也可能还要摆脱递归的
。

You don''t say what sort of objects you are passing in the list ll. Nor do
you say how large a value of ''n'' you tried. Nor have you said how you
ensured that you weren''t hitting the worst case performance.

Python may not be the best language to demonstrate this sort of effect. Two
things affect sorting speed in most languages: the number of comparisons,
and the number of times you copy data items, but other factors can come
into play when they are slow compared to the comparisons and moves. It may
well be that here your comparisons are comparatively fast (especially if
you just used integers as the input data), and the time is being swamped by
the function call overhead and creating all those intermediate lists. In
that case you may just need to increase the length of the list. A lot.

Most quicksort implementations sort the data in-place. You are creating new
lists for left, mid, right, and then again creating new lists by
concatenating the results of your recursive calls. Both of these involve
memory allocation, and the lists may need to be moved around in memory as
they grow. All of this complicates the order calculation.

Also, remember that if your lists are too long you are likely to start
swapping virtual memory, so all your times go out the window at that point.
Not to mention garbage collection.

If you want to get a result that matches your expectations, then I think
you would be best to operate on the data inplace, and probably also get rid
of the recursion.

这篇关于如何演示算法的bigO成本？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！