-
Notifications
You must be signed in to change notification settings - Fork 1
/
boosted-insertion-sort.benchmark.fs
109 lines (75 loc) · 2.83 KB
/
boosted-insertion-sort.benchmark.fs
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
\ galope/boosted-insertion-sort.benchmark.fs
\ This file is part of Galope
\ http:https://programandala.net/en.program.galope.html
\ Last modified: 201807251834
\ See change log at the end of the file.
\ Authors:
\ Hans Bezemer (?), 2014
\ Marcos Cruz (programandala.net) adapted the code to Galope, 2018.
\ ==============================================================
\ Credit
0 [if]
Message-Id: <[email protected]>
From: Hans Bezemer
Subject: Does anyone know this sorting routine??
Newsgroups: comp.lang.forth
Date: Sun, 13 Apr 2014 14:45:13 +0200
It's a kind of boosted insertion sort. On my machine/compiler the results
are rather dramatic - compared to a vanilla insertion sort. Please clarify
if you can. As usual, compatible with Wil Baden's QSORT:
Hans Bezemer
Message-Id: <[email protected]>
From: Hans Bezemer
Subject: Re: Does anyone know this sorting routine??
Newsgroups: comp.lang.forth
Date: Mon, 14 Apr 2014 16:10:38 +0200
[then]
\ ==============================================================
\ Requirements
require ./boosted-insertion-sort.fs \ `boosted-insertion-sort`
require ./insertion-sort.fs \ `insertion-sort`
\ ==============================================================
[undefined] th [if]
: th ( a1 u -- a2 ) cells + ;
[then]
variable seed
32767 constant max-rand
\ Maximum random number.
: (random) ( n1 n2 -- n3 )
seed @ * + dup seed ! 16 rshift max-rand and ;
: random ( -- n ) 12345 1103515245 (random) ;
: randomize ( -- ) random seed ! ;
: choose ( n1 n2 -- n3 ) random * max-rand 1+ / ;
randomize
1000 constant /array
/array cells buffer: array
: fill-array ( -- )
/array 0 do max-rand choose array i th ! loop ;
: .array ( -- )
/array 0 do array i th ? loop cr ;
synonym ticks utime
: elapsed ( ud1 -- ud2 ) ticks 2swap d- ;
: timer ( ud -- ) elapsed ud. ;
fill-array cr ." Insertion sort:"
ticks array /array insertion-sort timer cr
fill-array cr ." Boosted insertion sort:"
ticks array /array boosted-insertion-sort timer cr
\ array! cr ." Circle sort:"
\ ticks array /array (circle-sort) timer cr
\ .Benchmark results (in microseconds) with 100000 items
\ |===
\ | Date | items | insertion-sort | boosted-insertion-sort | Notes
\
\ | 2014 | 100 000 | 112 448 573 | 502 108 | (1)
\ | 2018-07-23 | 100 000 | 538 090 404 | 3 124 079 | (2)
\ | 2018-07-23 | 100 000 | 478 182 675 | 2 658 325 | (2) Stack operations optimized
\ | 2018-07-24 | 1 000 | 46 858 | 8 275 | (2)
\ |===
\ Notes:
\
\ (1) By Hans Bezemer. Running on 4tH. Unknown machine.
\ (2) Running on Gforth 0.7.9_20171005 on a Raspberry Pi 2.
\ ==============================================================
\ Change log
\ 2018-07-25: Extract from <boosted-insertion-sort.fs>. Simplify the
\ timer.