[Date Prev][Date Next][Thread Prev][Thread Next]
[Date Index]
[Thread Index]
- Subject: Re: Stable sort for Lua 4.1?
- From: Roberto Ierusalimschy <roberto@...>
- Date: Mon, 02 Jul 2001 10:54:36 -0300
About mergesort x quicksort:
> 1. It's simpler (which although it's not of interest to the user, may be to
> the Lua developers). For example, it could be implemented non-recursively,
> thus improving memory requirements (the current Quicksort is recursive,
> though only on the smaller partition).
That would be a big plus, if it reflects in implementation size. The
recursiveness of quicksort doesn't seem to be a problem, as it needs at
most twenty levels (less than 1Kbyte of stack) to sort 10^6 elements.
> 2. It's guaranteed best case (O(NlogN), although the constant factor may be
> higher than for quicksort; [...]
That would need some testing. Moving elements is also critical in Lua.
Why don't you try? If the result is smaller than the current implementation
(quite probable) and with a comparable performance, we can adopt it. (I
would even accept a small performance penalty for a smaller and stable
algorithm.) (Just in case, I am sending attached the standard tests for
sorting in Lua.)
-- Roberto
PS:
> You can also find versions of Mergesort which have a linear best-case time,
Where?
print"verificando sort"
function check (a, f)
f = f or function (x,y) return x<y end;
for n=getn(a),2,-1 do
assert(not f(a[n], a[n-1]))
end
end
a = {"Jan", "Feb", "Mar", "Apr", "May", "Jun", "Jul", "Aug", "Sep",
"Oct", "Nov", "Dec"}
sort(a)
check(a)
limit = 30000
if _soft then limit = 5000 end
a = {}
for i=1,limit do
a[i] = random()
end
local x = clock()
sort(a)
print(format("Sorting %d elements in %.2f sec.", limit, clock()-x))
check(a)
x = clock()
sort(a)
print(format("Re-sorting %d elements in %.2f sec.", limit, clock()-x))
check(a)
a = {}
for i=1,limit do
a[i] = random()
end
x = clock(); i=0
sort(a, function(x,y) i=i+1; return y<x end)
print(format("Invert-sorting other %d elements in %.2f sec., with %i comparisons",
limit, clock()-x, i))
check(a, function(x,y) return y<x end)
sort{} -- array vazio
a.n = 2
sort(a) -- so' 2 primeiros elementos
assert(a[1] <= a[2] and a.n == 2)
for i=3,limit-1 do
assert(a[i] >= a[i+1])
end
a = {n=limit}
x = clock();
sort(a, function(x,y) return nil end)
print(format("Sorting %d equal elements in %.2f sec.", limit, clock()-x))
check(a, function(x,y) return nil end)
for i,v in a do assert (i=='n' and v==limit) end
a = {"álo", "\0first :-)", "alo", "then this one", "45", "and a new"}
sort(a)
check(a)
sort(a, function (x, y)
dostring(format("a[%q] = ''", x))
collectgarbage()
return x<y
end)
tt = newtag()
a = {}
for i=1,10 do a[i] = {val=random(100)}; settag(a[i], tt); end
f = function (a,b) return a.val < b.val end
settagmethod(tt, 'lt', f)
sort(a)
check(a, f)
print"OK"