Re: The Alphanum Algorithm for Lua

["Andrew Wilson" <agrwagrw@...>]

Thanks for the improvement, my original version had a couple of big
errors issues which you've fixed as well,  that the other version
fixed too... anyway optimization is like a potato chip it's hard to
have just one ;)   AGRW

On Fri, Jun 6, 2008 at 7:38 PM, Nick Gammon <nick@gammon.com.au> wrote:
> 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
>
>
>
>