• 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

```