首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》混合操作

关灯直达底部

在之前的边栏“编码对性能的影响”中,设计者不得不考虑同时发生的多个乘法操作。并不是每个操作都能够被优化。事实上,优化一个操作将会降低另外一个操作的执行性能。例如,考虑这样一个数据结构,包含两个操作op1和op2。假设这个数据结构能够有A和B两种方法实现。基于这个讨论的目的,知道这个数据结构或者各个方法是不重要的。我们构建下列两种情景:

小数据集

数据集大小n为1000,然后混合执行2000次op1操作和3000次op2操作。

大数据集

数据集大小n为100 000,然后混合执行200 000次op1操作和300 000次op2操作。

表2-6包含了两个实现A和B在两个数据集上的预期性能。表中的第一列是A实现在n=1000的数据集上执行op1的平均花费时间,大概为0.008毫秒,第二列和第三列的数据也是类似的。最后一列是执行的总时间。因此,对于在n=1000的数据集上,我们期望A实现需要花费2000*0.008+3000*0.001=16+3=19毫秒,虽然B实现在小数据集上初始表现要好于A实现,但是在问题规模扩大了两个数量级之后,我们发现结果出现了戏剧性的变化,A实现适应了变化,而B实现表现得不尽如人意。