你这个叛逃方向不对啊 ...
很抱歉!页面已丢失,但我们可以帮助他们找到亲人...
难道不是少了个 :
为啥提交给乌云啊 ...
tweak 一下,应该能达到大约 50% 的正确率
Cython 还是略坑
from libc.stdlib cimport malloc, free
from cython import sizeof
cdef pushDown(int *h, int pos, int n):
cdef int j
while 2 * pos + 1 < n:
j = 2 * pos + 1
if (j + 1 < n) and (h[j+1] > h[j]):
j += 1
if h[pos] >= h[j]:
break
h[pos], h[j] = h[j], h[pos]
pos = j
def heapsort(int size):
cdef int i, n
cdef int *heap = <int *>malloc(sizeof(int)*size)
for i in range(size):
heap[i] = i
for i in range(size//2, -1, -1):
pushDown(heap, i, size)
for n in range(size-1, 0, -1):
heap[0], heap[n] = heap[n], heap[0]
pushDown(heap, 0, n)
for i in range(size):
assert i == heap[i], "Array not sorted"
free(heap)
#56 楼 @ShiningRay 快跑我的代码,看看结果如何
Ruby 代码主要就是 a, b = b, a
这里手工展开所以才比 Python 2.7 快了,
我去掉了个 0,实在太久了,等不起。
$ python --version
Python 2.7.5
$ python3 --version
Python 3.3.2
$ pypy --version
Python 2.7.3 (352c78d2e80f4a812ae1d8cdbe8c01a7f2e6fbc0, Aug 19 2013, 10:43:46)
[PyPy 2.1.0 with GCC 4.8.1 20130603 (Red Hat 4.8.1-1)]
$ ruby --version
ruby 2.0.0p247 (2013-06-27 revision 41674) [x86_64-linux]
$ python heapsort.py
17.9021840096
$ python3 heapsort.py
30.28932676600016
$ pypy heapsort.py
0.749085903168
$ ruby heapsort.rb
23.450000 0.010000 23.460000 ( 23.611715)
代码改成一致的实现,不能因为一边有更快的写法就用更快的写法。
from __future__ import division, unicode_literals, print_function
import timeit
try:
range = xrange
except NameError:
pass
def pushDown(h, pos, n):
while 2 * pos + 1 < n:
j = 2 * pos + 1
if j + 1 < n and h[j+1] > h[j]:
j += 1
if h[pos] >= h[j]:
break
h[pos], h[j] = h[j], h[pos]
pos = j
def heapsort(size):
heap = list(range(size))
for i in range(size//2, -1, -1):
pushDown(heap, i, size)
for n in range(size-1, 0, -1):
heap[0], heap[n] = heap[n], heap[0]
pushDown(heap, 0, n)
for i, e in enumerate(heap):
assert i == e, "Array not sorted"
if __name__ == "__main__":
print(timeit.timeit("heapsort(1000000)", setup="from __main__ import heapsort", number=1))
require 'benchmark'
def push_down(heap, pos, n)
while (2 * pos + 1) < n
j = 2 * pos + 1
if (j + 1 < n) and (heap[j + 1] > heap[j])
j += 1
end
break unless heap[pos] < heap[j]
heap[pos], heap[j] = heap[j], heap[pos]
pos = j
end
end
def heapsort(size)
heap = (0...size).to_a
(size / 2).downto(0) do |i|
push_down heap, i, size
end
(size - 1).downto(1) do |n|
heap[0], heap[n] = heap[n], heap[0]
push_down heap, 0, n
end
raise "Array not sorted" unless heap.each.with_index.all? { |element, index| element == index }
end
puts Benchmark.measure { heapsort 1000000 }
Ruby 学 Smalltalk,要让控制流以库而不是关键字的形式提供,才用了类似抛错的机制。你可以认为其实 break/return 什么的也是会 throw 的。
Rust,不像 Ruby 有 block 和 lambda 两种不同的语义。Rust 只有 lambda,并且是通过不同的返回值来实现不同的控制流,最后通过编译期对 lambda 的统一优化来消除额外的运行期开销。
这个就是 Ruby 没搞对的地方,这个就是 Rust 搞对的地方 ...
#36 楼 @skandhas 对啊,之前的 jjyr benchmark 也是类似的结果 http://ruby-china.org/topics/12688
很奇怪啊,几乎一样的实现 (Python 只是没有 direct threading),Ruby 1.9/2.0能快很多
善用邮件列表就好了,真的