lua-misc/test_binary_heap.lua at master · kinbei/lua-misc · GitHub

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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
local binary_heap = require "binary_heap"

local math_random = math.random
local table_sort, table_remove = table.sort, table.remove

-- tests -----------------------------------------------------------------------

local function test_heap_write(h)
  io.write("Pretty-printing heap:\n")
  for i = 1, 20 do
    h:insert(math_random(100))
  end
  h:write()
  io.write("\n")
end


local function test_heap_integrity(h, runs, insert_count, pop_count, range)
  runs = runs or 200
  insert_count = insert_count or 100
  pop_count = pop_count or 50
  range = range or 10000
  local cmp = h.comparison
  local size = 0
  local low

  io.write("Testing heap integrity...\n")
  for i = 1,runs do
    for j = 1,math_random(insert_count) do
      h:insert(math_random(range), nil)
      size = size + 1
      if not h:check() then
        io.write("\n")
        h:write()
        error("Heap check failed after insertion")
      end
      if size % 10 == 0 then io.write("Step: ", i, "/", runs, ": Heap size: ", size,".     \r") end
    end
    low = 0
    for j = 1,math.min(size, math_random(pop_count)) do
      local r = h:pop()
      size = size - 1
      if cmp(r, low) then
        io.write("\n")
        h:write()
        error(string.format("Popped %d after %d", r, low))
      end
      low = r
      if not h:check() then
        io.write("\n")
        h:write()
        error("Heap check failed after pop")
      end
      if size % 10 == 0 then io.write("Step: ", i, "/", runs, ": Heap size: ", size,".     \r") end
    end
  end
  io.write("\n")
  low = 0
  while not h:empty() do
    local r = h:pop()
    size = size - 1
    if cmp(r, low) then
      io.write("\n")
      h:write()
      error(string.format("Popped %d after %d", r, low))
    end
    low = r
    if not h:check() then
      io.write("\n")
      h:write()
      error("Heap check failed while clearing")
    end
    if size % 10 == 0 then io.write("Clearing: Heap size: ", size,".     \r") end
  end
  io.write("\nDone.\n")
end


local function test_heap_speed(h, name, runs, insert_count, pop_count, range)
  runs = runs or 100
  insert_count = insert_count or 10000
  pop_count = pop_count or 7500
  pop_count = math.min(pop_count, insert_count)
  range = range or 10000

  io.write(("Testing %s speed...\n"):format(name))
  local start = os.clock()
  for i = 1,runs do
    io.write("Step: ", i, "/", runs, ".\r")
    for j = 1,insert_count do
      h:insert(math_random(range), nil)
    end
    for j = 1,pop_count do
      h:pop()
    end
  end
  io.write("\nClearing heap.\n")
  while not h:empty() do
    h:pop()
  end

  local elapsed = os.clock() - start
  io.write("Done.  Elapsed time ", elapsed, " seconds (", elapsed / (insert_count * runs), " s/insert+pop).\n")
end


local function test_sort_queue_speed(runs, insert_count, pop_count, range)
  runs = runs or 100
  insert_count = insert_count or 10000
  pop_count = pop_count or 7500
  pop_count = math.min(pop_count, insert_count)
  range = range or 10000

  local function cmp(a, b) return a.key < b.key end

  h = {}

  io.write("Testing sorted queue speed...\n")
  local start = os.clock()
  for i = 1,runs do
    io.write("Step: ", i, "/", runs, ".\r")
    for j = 1,insert_count do
      h[#h+1] = { key=math_random(range), value=nil }
    end
    table_sort(h, cmp)
    for j = 1,pop_count do
      table_remove(h)
    end
  end
  io.write("\nClearing heap.\n")
  while h[1] do
    table_remove(h)
  end

  local elapsed = os.clock() - start
  io.write("Done.  Elapsed time ", elapsed, " seconds (", elapsed / (insert_count * runs), " s/insert+pop).\n")
end


--test_heap_write(binary_heap:new(function(k1, k2) return k1 > k2 end))
--test_heap_integrity(binary_heap:new())
--test_heap_speed(binary_heap:new(), "binary heap")
--test_sort_queue_speed()

local h = binary_heap:new()
local begin_t = os.clock()
local end_t = os.clock()

h:insert(1, { test = "test" } )
h:insert(1, { test = "test" } )
h:insert(3, { test = "test" } )
h:insert(1, { test = "test" } )
h:insert(2, { test = "test" } )
h:insert(5, { test = "test" } )

end_t = os.clock()
print( string.format("insert use %s", end_t - begin_t  ) )

begin_t = os.clock()
while not h:empty() do
	local n, t = h:pop()
	print(n, t.test)
end
end_t = os.clock()
print( string.format("pop use %s", end_t - begin_t  ) )