Re: The Alphanum Algorithm for Lua
[
Date Prev][
Date Next][
Thread Prev][
Thread Next]
[
Date Index]
[
Thread Index]
- Subject: Re: The Alphanum Algorithm for Lua
- From: Nick Gammon <nick@...>
- Date: Sat, 7 Jun 2008 12:38:54 +1000
The only problem with the version shown earlier is that the chunking
is done for every comparison. A quick test shows that for a table of
70 items you might be calling the chunk routine 800 times.
The variant below does a chunking pass once, storing the results in a
temporary table as an upvalue, and then uses that for the comparison.
In my timing test it was about 4 times faster.
------
function alphanum (t)
assert (type (t) == "table", "Must pass table to be sorted to
alphanum")
local function chunkString(str)
local c = {}
for a, b in tostring (str):gmatch("(%d*)(%D*)") do
if a ~= "" then c[#c+1] = tonumber(a) end
if b ~= "" then c[#c+1] = b end
end
return c
end
local chunks = {}
-- build temporary table of the keys
for i=1, #t do
chunks [t [i]] = chunkString (t [i])
end
return function (a, b) -- return our sort comparison function
-- lookup chunked information from previously-built table
local achunks = chunks [a]
local bchunks = chunks [b]
for i = 1, math.min (#achunks, #bchunks) do
local as, bs = achunks [i], bchunks [i]
-- if one is a string, make them both strings
if type (as) == "string" or type (bs) == "string" then
as = (tostring (as)):upper ()
bs = (tostring (bs)):upper ()
end -- at least one is a string
-- if they are equal, move onto the next chunk
if as ~= bs then
return as < bs
end -- if
end -- for each chunk
-- still equal? the one with fewer chunks compares less
return #achunks < #bchunks
end -- sort function
end -- alphanum
-- Example:
t={
"z18.doc","z19.doc","z2.doc","z16.doc","z17.doc",
"z1.doc","z101.doc","z102.doc","z11.doc","z12.doc",
"z13.doc","z14.doc","z15.doc","z20.doc","z3.doc",
"z4.doc","z5.doc","z6.doc","z10.doc","z100.doc",
"z7.doc","z8.doc","z9.doc",
}
table.sort(t, alphanum (t))
for i=1, #t do
print(t[i])
end