Skip to content

Instantly share code, notes, and snippets.

@kostya kostya/result forked from c910335/result
Last active Nov 7, 2016

Embed
What would you like to do?
some sort benchmarks
======== random 2097152 =============
(0.185) 2097152 elements with original quick sort
(0.135) 2097152 elements with intro sort
(0.142) 2097152 elements with std::sort in cpp
(0.267) 2097152 elements with qsort in c
======== seq 2097152 =============
(0.047) 2097152 elements with original quick sort
(0.021) 2097152 elements with intro sort
(0.025) 2097152 elements with std::sort in cpp
(0.076) 2097152 elements with qsort in c
======== rotated_seq 2097152 =============
(0.065) 2097152 elements with original quick sort
(0.123) 2097152 elements with intro sort
(0.044) 2097152 elements with std::sort in cpp
(0.081) 2097152 elements with qsort in c
======== reversed 2097152 =============
(0.047) 2097152 elements with original quick sort
(0.198) 2097152 elements with intro sort
(0.018) 2097152 elements with std::sort in cpp
(0.096) 2097152 elements with qsort in c
======== rotated_reversed 2097152 =============
(0.047) 2097152 elements with original quick sort
(0.197) 2097152 elements with intro sort
(0.118) 2097152 elements with std::sort in cpp
(0.102) 2097152 elements with qsort in c
======== random 4194304 =============
(0.379) 4194304 elements with original quick sort
(0.282) 4194304 elements with intro sort
(0.296) 4194304 elements with std::sort in cpp
(0.552) 4194304 elements with qsort in c
======== seq 4194304 =============
(0.097) 4194304 elements with original quick sort
(0.044) 4194304 elements with intro sort
(0.053) 4194304 elements with std::sort in cpp
(0.160) 4194304 elements with qsort in c
======== rotated_seq 4194304 =============
(0.131) 4194304 elements with original quick sort
(0.311) 4194304 elements with intro sort
(0.263) 4194304 elements with std::sort in cpp
(0.170) 4194304 elements with qsort in c
======== reversed 4194304 =============
(0.095) 4194304 elements with original quick sort
(0.425) 4194304 elements with intro sort
(0.038) 4194304 elements with std::sort in cpp
(0.200) 4194304 elements with qsort in c
======== rotated_reversed 4194304 =============
(0.100) 4194304 elements with original quick sort
(0.425) 4194304 elements with intro sort
(0.318) 4194304 elements with std::sort in cpp
(0.202) 4194304 elements with qsort in c
======== random 8388608 =============
(0.789) 8388608 elements with original quick sort
(0.596) 8388608 elements with intro sort
(0.612) 8388608 elements with std::sort in cpp
(1.148) 8388608 elements with qsort in c
======== seq 8388608 =============
(0.201) 8388608 elements with original quick sort
(0.097) 8388608 elements with intro sort
(0.110) 8388608 elements with std::sort in cpp
(0.341) 8388608 elements with qsort in c
======== rotated_seq 8388608 =============
(0.280) 8388608 elements with original quick sort
(0.285) 8388608 elements with intro sort
(0.133) 8388608 elements with std::sort in cpp
(0.355) 8388608 elements with qsort in c
======== reversed 8388608 =============
(0.204) 8388608 elements with original quick sort
(0.905) 8388608 elements with intro sort
(0.081) 8388608 elements with std::sort in cpp
(0.418) 8388608 elements with qsort in c
======== rotated_reversed 8388608 =============
(0.211) 8388608 elements with original quick sort
(0.880) 8388608 elements with intro sort
(0.755) 8388608 elements with std::sort in cpp
(0.428) 8388608 elements with qsort in c
======== random 16777216 =============
(1.651) 16777216 elements with original quick sort
(1.238) 16777216 elements with intro sort
(1.297) 16777216 elements with std::sort in cpp
(2.484) 16777216 elements with qsort in c
======== seq 16777216 =============
(0.418) 16777216 elements with original quick sort
(0.188) 16777216 elements with intro sort
(0.224) 16777216 elements with std::sort in cpp
(0.706) 16777216 elements with qsort in c
======== rotated_seq 16777216 =============
GC Warning: Repeated allocation of very large block (appr. size 67112960):
May lead to memory leak and poor performance.
(0.615) 16777216 elements with original quick sort
(1.723) 16777216 elements with intro sort
(1.128) 16777216 elements with std::sort in cpp
(0.729) 16777216 elements with qsort in c
======== reversed 16777216 =============
(0.413) 16777216 elements with original quick sort
(1.871) 16777216 elements with intro sort
(0.181) 16777216 elements with std::sort in cpp
(0.923) 16777216 elements with qsort in c
======== rotated_reversed 16777216 =============
GC Warning: Repeated allocation of very large block (appr. size 67112960):
May lead to memory leak and poor performance.
(0.443) 16777216 elements with original quick sort
(1.815) 16777216 elements with intro sort
(1.008) 16777216 elements with std::sort in cpp
(0.895) 16777216 elements with qsort in c
// g++ -c -O3 -o sort.o sort.cpp
#include <cstdlib>
#include <algorithm>
extern "C" void std_sort(int *array, int size) {
std::sort(array, array + size);
}
require "benchmark"
class Array
def intro_sort!
Array.intro_sort!(@buffer, @size)
self
end
protected def self.intro_sort!(a, n)
return if n < 2
quick_sort!(a, n, Math.log2(n).to_i * 2)
insertion_sort!(a, n)
end
protected def self.quick_sort!(a, n, d)
while n > 16
if d == 0
heap_sort!(a, n)
return
end
d -= 1
shift_median!(a, n)
c = partition!(a, n)
quick_sort!(c, n - (c - a), d)
n = c - a
end
end
protected def self.heap_sort!(a, n)
(n / 2).downto 0 do |p|
heapify!(a, p, n)
end
while n > 1
n -= 1
a.value, a[n] = a[n], a.value
heapify!(a, 0, n)
end
end
protected def self.heapify!(a, p, n)
v, c = a[p], p
while c < (n - 1) / 2
c = 2 * (c + 1)
c -= 1 if a[c] < a[c - 1]
break unless v < a[c]
a[p] = a[c]
p = c
end
if n & 1 == 0 && c == n / 2 - 1
c = 2 * c + 1
if v < a[c]
a[p] = a[c]
p = c
end
end
a[p] = v
end
protected def self.shift_median!(a, n)
b, c = a + n / 2, a + n - 1
if a.value < b.value
if b.value < c.value
a.value, b.value = b.value, a.value
elsif a.value < c.value
a.value, c.value = c.value, a.value
end
elsif a.value < c.value
return
elsif b.value < c.value
a.value, c.value = c.value, a.value
else
a.value, b.value = b.value, a.value
end
end
protected def self.partition!(a, n)
v, l, r = a.value, a + 1, a + n
loop do
while l.value < v
l += 1
end
r -= 1
while v < r.value
r -= 1
end
return l unless l < r
l.value, r.value = r.value, l.value
l += 1
end
end
protected def self.insertion_sort!(a, n)
(1...n).each do |i|
l = a + i
v = l.value
p = l - 1
while l > a && v < p.value
l.value = p.value
l, p = p, p - 1
end
l.value = v
end
end
end
@[Link(ldflags: "#{__DIR__}/sort.o")]
lib StdSort
fun std_sort(array : Int32*, size : Int32) : Void
fun qsort(array : Void*, size : LibC::SizeT, elm_size : LibC::SizeT, cmp : (Void*, Void*) -> Int32)
end
def generate_array(size, style)
case style
when :random
random = Random.new
a = Array(Int32).new(size)
size.times do
a << random.next_int
end
a
when :seq
Array(Int32).new(size) { |i| i }
when :rotated_seq
Array(Int32).new(size) { |i| i }.rotate(rand(size))
when :reversed
Array(Int32).new(size) { |i| i }.reverse
when :rotated_reversed
Array(Int32).new(size) { |i| i }.reverse.rotate(rand(size))
else
raise "unknown style #{style}"
end
end
def report(msg)
t = Time.now
s = 0_64
yield || 0
puts "(#{"%.3f" % {(Time.now - t).to_f}}) #{msg}"
end
size = 2097152
while size <= 16_777_216
[:random, :seq, :rotated_seq, :reversed, :rotated_reversed].each do |style|
puts "======== #{style} #{size} ============="
a = generate_array(size, style)
b, c, d = a.dup, a.dup, a.dup
report("#{size} elements with original quick sort") do
a.sort!
end
report("#{size} elements with intro sort") do
b.intro_sort!
end
report("#{size} elements with std::sort in cpp") do
StdSort.std_sort(c, size)
end
report("#{size} elements with qsort in c") do
StdSort.qsort(d, size, sizeof(Int32), -> (x : Void*, y : Void*){
x.as(Int32*).value - y.as(Int32*).value
})
end
end
size *= 2
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.