|
精华帖 (12) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2009-05-15
最后修改：2009-05-15
night_stalker 写道 比 fib 速度请用 C，循环用 goto。C 写的单线程算法就打翻 VM 语言好多个核了。
这不一定，选对了算法javascrpit都会比C快. 首先，单线程的尾递归也好循环也好,最快也是O(n)的，而且无法并行运算. 但是吧fib(n)转换为 0 1 1 1 矩阵的n次幂,那么就可以并行计算,而且不光是并行计算,本身的单线程算法就可以从循环的o(n)下降为o(log(n)). |
| 返回顶楼 | |
|
发表时间：2009-05-16
Trustno1 写道 night_stalker 写道 比 fib 速度请用 C，循环用 goto。C 写的单线程算法就打翻 VM 语言好多个核了。
这不一定，选对了算法javascrpit都会比C快. 首先，单线程的尾递归也好循环也好,最快也是O(n)的，而且无法并行运算. 但是吧fib(n)转换为 0 1 1 1 矩阵的n次幂,那么就可以并行计算,而且不光是并行计算,本身的单线程算法就可以从循环的o(n)下降为o(log(n)). 这个好， 这是我看的一本薄 algorithms 书中第一章章末的一道习题 提到用matrix来算fib。 |
| 返回顶楼 | |
|
发表时间：2009-05-16
Trustno1 写道 这不一定，选对了算法javascrpit都会比C快. 首先，单线程的尾递归也好循环也好,最快也是O(n)的，而且无法并行运算. 但是吧fib(n)转换为 0 1 1 1 矩阵的n次幂,那么就可以并行计算,而且不光是并行计算,本身的单线程算法就可以从循环的o(n)下降为o(log(n)). 如果都是矩阵乘，那么 C 的单线程算法还是能打翻很多虚拟机语言的多核算法…… |
| 返回顶楼 | |
|
发表时间：2009-05-16
night_stalker 写道 Trustno1 写道 这不一定，选对了算法javascrpit都会比C快. 首先，单线程的尾递归也好循环也好,最快也是O(n)的，而且无法并行运算. 但是吧fib(n)转换为 0 1 1 1 矩阵的n次幂,那么就可以并行计算,而且不光是并行计算,本身的单线程算法就可以从循环的o(n)下降为o(log(n)). 如果都是矩阵乘，那么 C 的单线程算法还是能打翻很多虚拟机语言的多核算法…… 矩阵与矩阵比 矩阵与递归比 矩阵与并行矩阵乘比 你说的是那个? |
| 返回顶楼 | |
|
发表时间：2009-05-16
单线程矩阵乘 和 并行矩阵乘比。
只要 cpu 的个数有限，仅仅改成并行不能降低算法复杂度。 |
| 返回顶楼 | |
|
发表时间：2009-05-16
night_stalker 写道 单线程矩阵乘 和 并行矩阵乘比。
只要 cpu 的个数有限，仅仅改成并行不能降低算法复杂度。 比如Axum理论上的CPU是无限的，因为可以通过网络扩展。 |
| 返回顶楼 | |
|
发表时间：2009-05-16
最后修改：2009-05-16
night_stalker 写道 单线程矩阵乘 和 并行矩阵乘比。
只要 cpu 的个数有限，仅仅改成并行不能降低算法复杂度。 当幂充分大的时候,这个幂起码可以分成4个通道来做. 从复杂度上来说，可以是1/4的.当然从数量及来说，是不可能降的更低了. |
| 返回顶楼 | |
|
发表时间：2009-05-17
Chat Room无疑是ERLANG的强项了。
|
| 返回顶楼 | |
|
发表时间：2009-05-18
night_stalker 写道 比 fib 速度请用 C，循环用 goto。C 写的单线程算法就打翻 VM 语言好多个核了。
不过聊天室的 concurrency 和 parallel 真的没什么联系…… 瓶颈不在 cpu，在 io 和锁。所以 C 算得快也没多大帮助。 赞一个，计算机设计就是一个主要的原因就是合理利用IO，从cpu的缓存，到内存，操作系统级别的缓存，应用级别的缓存，硬盘级别的缓存，无一不是用来提高IO的。合理的IO也需要合理的锁设计，要不成单线程了，最坏的就是死锁。 个人感觉： 现在cpu是很快了，除了视频编解码和图像处理外外，其他应用主要是IO处理上跟不上，不在cpu的处理能力上 |
| 返回顶楼 | |
|
发表时间：2009-05-19
再出一个并行算法的题.
有一个庞大的数组,数组每一个元素都是随机数,现在求这个数组每一个元素的前向和,即p[n]=p[1]+....+p[n-1].要求算法的复杂度小于单线程最快算法的复杂度. |
| 返回顶楼 | |
