2

IO 一般都慢, 但是这里不考虑 IO 那部分. 而是创建什么数据类型, 对数据做什么样的操作, 或者其他行为? 以及有没有相关的文档可以参照?

照顾一下题主请用 Go, JavaScript, C 或者 Haskell 当中的例子吧..

题叶 16.4k
2014-09-16 提问
2 个回答
2

已采纳
  1. 用Haskell怎么举例?你知道sum [1..10]空间复杂度是多少?
  2. 用C语言的不是都会点汇编什么的吗,直接gcc -S看汇编分析啊。
  3. Golang很会照顾人,特地设计了slice这种东西。
  4. 我只想说,JavaScript中(Sparse)Array和Object几乎是同一种东西,不要上当。

传统的编译型语言,对于什么情况下会复制数据,甚至标准库中某些函数的复杂度,语言本身都有定义,如C、C++、Golang。而像JS这样的语言,如果规范中没有要求(通常也不要求)某个操作的复杂度是O(n)还是O(1),那就只能听随解释器了。至于像Haskell这样的非严格求值的语言嘛~等我读过GHC再说吧。


比如说吧,ECMAScript语言没有规定Array#sort使用哪种算法排序,Google v8Webkit JavaScriptCore都进行了权衡,根据Array大小、是否是SparseArray,选择使用不同的排序算法。有人发现v8在排序超大数组时性能不理想 ,这种性能问题当然不是语言自身固有的,甚至也不是v8引擎固有的,因为说不定人家下个版本就优化了啊。以前都有说法,拼接String用Array#join性能更好,可后来人家优化了,这方法反而效率变低了。以前我以为Array[P]一定Object[P]速度更快,但考虑下Array.prototype[9]="Whatz!",嗯,还是打消这种想当然吧。

好像在前年有一阵Hash Collision Denial Of Service恐慌。这种性能问题,如果不针对具体解释器、具体算法库考虑的话,单从语言层面,是不会注意到HashMap Get操作会这么容易就变成O(n)的。对于Haskell,我目前除了知道一点foldrfoldl之类的性能上的固有差别,其它的都无力分析了。写C语言嘛还要考虑性能问题,难道不就应该自动脑补成汇编,考虑的不应该是哪里会有Cache Thrashing、哪里编译器做不了指令级并行优化?和语言自身就更无关系啦。


想起了这个项目:https://github.com/codemix/fast.js
Optimized for Chrome v8 engine.Faster user-land reimplementations for several common builtin native JavaScript functions.
里面解释了为什么Native函数反而低效的原因。

0
  1. 了解数据结构(建议学习下redis背后的数据结构,看看哪些是o(1),哪些是o(n)的)
  2. 了解排序,查找算法

撰写答案

你可能感兴趣的

推广链接