fra*_*a66 8 c complexity-theory big-o memset
我和一些朋友讨论了一段代码,我们讨论了在C中使用memset函数,如果我们初始化一个大小为N的数组,这个函数的Big-O表示法的顺序是什么？
R..*_*R.. 16
在您可以直接访问页表并且以分层方式存储的系统上,memset可以O(log n)通过将整个虚拟地址映射替换为使用给定字节值填充的单个页面的写入时复制来实现..但是请注意,如果您将来要对对象进行任何修改,那么正常的O(n)成本memset将被推迟到页面错误,以便在修改页面时实例化单独的页面副本.
Eri*_*hil 12
您询问了复杂性,但您可能打算询问性能.
用符号O(n)表示的复杂性是与算法中的操作数量如何随着问题大小增长而被迫增长有关的概念.O(n)表示必须执行与输入大小成比例的一些步骤.它没有说明这个比例是多少.memset是O(n).O(n 2)表示必须执行与n 2成比例的一些步骤.memset不是O(n 2),因为设置2n个字节的工作量只是n个字节的两倍,而不是工作量的四倍.
您可能对memset的性能更感兴趣,因为memset的库版本比您可能编写的C版本执行得更快.
库版本执行速度更快,因为它使用专门的指令.最常见的现代处理器具有允许它们在一条指令中将16字节写入存储器的指令.库实现者用汇编语言或接近它的东西编写memset等关键函数,因此他们可以访问所有这些指令.
用C语言编写时,编译器很难利用这些指令.例如,指向您正在设置的内存的指针可能不会与16个字节的倍数对齐.memset作者将编写测试指针的代码,并为每种情况分支到不同的代码,目标是单独设置一些字节,然后使用一个对齐的指针,这样他们就可以使用存储16字节的快速指令.时间.这只是库编写器在编写memset等例程时要处理的许多复杂问题之一.
由于这些复杂性,编译器无法轻松采用memset的C实现并将其转换为专家编写的快速代码.当编译器在C代码中看到一次写入一个字节的循环时,它通常会生成一次写入一个字节的汇编语言.优化器变得越来越聪明,但复杂性限制了它们允许执行的程度以及它们可以执行多少操作而无需生成大量代码来处理可能很少发生的情况.