简单算法的可扩展性

Question

我希望测试Python-gensim和lda中算法的两个实现(潜在的Dirichlet分配)的可伸缩性。大多数谷歌搜索结果都谈到网站和基于网络的应用程序的可伸缩性。

如何测试简单算法(而不是整个系统)的可伸缩性？记住什么是最好的做法？

Answer 1

看看下面的python代码，

import datetime;

s=0
VALUES = [1,10,100,1000,2000,8000]

for VALUE in VALUES:
    timebefore =  datetime.datetime.now()
    #Algorithm starts
    for i in range(VALUE):
        for j in range(VALUE):
            s+=i*j

    #Algorithm ends
    timeafter = datetime.datetime.now()    
    print('time taken for parameter:'+str(VALUE)+" is " + str(timeafter - timebefore))

上述程序的输出是

time taken for parameter:1 is 0:00:00
time taken for parameter:10 is 0:00:00
time taken for parameter:100 is 0:00:00
time taken for parameter:1000 is 0:00:00.327280
time taken for parameter:2000 is 0:00:01.285746
time taken for parameter:8000 is 0:00:21.250825

当n从1000增加到2000年(按因子2计算)时，所需时间大约增加4倍(1.285746/0.327280)。

当n从2000年改为8000(按因子4计算)时，所需时间大约增加16倍(21.250825/1.285746)。

因此，对于输入参数的n个变化，n^2所占用的时间发生了变化，由此可以推断算法的复杂性为O(n^2)。

在这种情况下，用自己的算法替换算法，并运行不同的参数来查看时间复杂性。

Answer 2

一个算法的可伸缩性取决于它的时间复杂度，对于一个简单的算法来说，它只是一个计算最大操作数的问题。对n个元素进行迭代的循环具有时间复杂度O(n)，这意味着它将像任何线性函数一样缩放，以此类推。具有嵌套循环的循环是O(n^2)。

关于更深入的解释：complexity