Untitled

a guest
Nov 1st, 2018
321
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. function test_tableremove(mylist)
2.     for i=#mylist,1,-1 do
3.         if mylist[i] == 13 then
4.             table.remove(mylist, i)
5.         end
6.     end
7. end -- func
8.
9. function test_mitch(mylist)
10.     -- NOTE: This is a messy, hardcoded version of my algorithm, for test-purposes.
11.     -- Go to https://stackoverflow.com/a/53038524/8874388 for the actual, clean version.
12.     local j, n = 1, #mylist;
13.
14.     for i=1,n do
15.         local value = mylist[i]
16.         if value ~= 13 then -- Keep everything except "13"
17.             -- Move i's kept value to j's position, if it's not already there.
18.             if (i ~= j) then
19.                 mylist[j] = mylist[i];
20.                 mylist[i] = nil;
21.             end
22.             j = j + 1; -- Increment position of where we'll place the next kept value.
23.         else -- Delete "13"
24.             mylist[i] = nil;
25.         end
26.     end
27. end
28.
29. function build_tables(howMany)
30.     local ofs = {}
31.     for i=1,howMany do
32.         ofs[i*50] = true;
33.     end
34.
35.     local tables = {}
36.     for i=1, 1 do
37.       tables[i] = {}
38.       for j=1, 2000000 do -- 2 million items
39.         tables[i][j] = (ofs[j] and 13 or 100) -- put a "13" (deleted) in the slots to be deleted, otherwise "100" (kept)
40.       end
41.     end
42.
43.     return tables
44. end
45.
46. function time_func(func, name, howMany)
47.     local tables = build_tables(howMany)
48.     time0 = os.clock()
49.     for i=1, #tables do
50.         func(tables[i])
51.     end
52.     time1 = os.clock()
53.     print(string.format("[%13s] elapsed time (deleting %.0f items): %.3f\n", name, howMany, time1 - time0))
54. end
55.
56. -- The number below (i) controls how many items that will need to be deleted from the array.
57. -- This test checks if table.remove() is ever faster if you only need to remove a few entries.
58. -- The test arrays contain 2 million items, and the items that need to be removed at all at the start,
59. -- hence triggering the need to re-index the subsequent array entries.
60. for i=1,6 do
61.     time_func(test_mitch, "mitch", i)
62.     time_func(test_tableremove, "table.remove", i)
63. end
64.
65.
66. --[[
67.
68. LuaJIT 2.0.5 -- Copyright (C) 2005-2017 Mike Pall. http://luajit.org/
69. JIT: ON CMOV SSE2 SSE3 SSE4.1 fold cse dce fwd dse narrow loop abc sink fuse
70.
71. [        mitch] elapsed time (deleting 1 items): 0.008
72.
73. [ table.remove] elapsed time (deleting 1 items): 0.010
74.
75. [        mitch] elapsed time (deleting 2 items): 0.008
76.
77. [ table.remove] elapsed time (deleting 2 items): 0.019
78.
79. [        mitch] elapsed time (deleting 3 items): 0.008
80.
81. [ table.remove] elapsed time (deleting 3 items): 0.022
82.
83. [        mitch] elapsed time (deleting 4 items): 0.008
84.
85. [ table.remove] elapsed time (deleting 4 items): 0.028
86.
87. [        mitch] elapsed time (deleting 5 items): 0.008
88.
89. [ table.remove] elapsed time (deleting 5 items): 0.031
90.
91. [        mitch] elapsed time (deleting 6 items): 0.008
92.
93. [ table.remove] elapsed time (deleting 6 items): 0.039
94.
95.
96.
97. Lua 5.3.4  Copyright (C) 1994-2017 Lua.org, PUC-Rio
98.
99. + \$ lua test.lua
100. [        mitch] elapsed time (deleting 1 items): 0.306
101.
102. [ table.remove] elapsed time (deleting 1 items): 0.121
103.
104. [        mitch] elapsed time (deleting 2 items): 0.309
105.
106. [ table.remove] elapsed time (deleting 2 items): 0.164
107.
108. [        mitch] elapsed time (deleting 3 items): 0.313
109.
110. [ table.remove] elapsed time (deleting 3 items): 0.237
111.
112. [        mitch] elapsed time (deleting 4 items): 0.326
113.
114. [ table.remove] elapsed time (deleting 4 items): 0.262
115.
116. [        mitch] elapsed time (deleting 5 items): 0.326
117.
118. [ table.remove] elapsed time (deleting 5 items): 0.304
119.
120. [        mitch] elapsed time (deleting 6 items): 0.334
121.
122. [ table.remove] elapsed time (deleting 6 items): 0.341
123.
124.
125.
126. ]]--