diff options
author | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2015-11-25 10:48:57 -0200 |
---|---|---|
committer | Roberto Ierusalimschy <roberto@inf.puc-rio.br> | 2015-11-25 10:48:57 -0200 |
commit | 5936eb16d8d6224b0b3605abb77e90ddf1ccc0db (patch) | |
tree | 7a295ca88800087a8f91d3c0759dc74a107043ba /ltablib.c | |
parent | 7dc3ca7b8ee87d5264f7edb2a1ad425a34048aa1 (diff) | |
download | lua-5936eb16d8d6224b0b3605abb77e90ddf1ccc0db.tar.gz lua-5936eb16d8d6224b0b3605abb77e90ddf1ccc0db.tar.bz2 lua-5936eb16d8d6224b0b3605abb77e90ddf1ccc0db.zip |
randomness in 'table.sort' used only when needed (big imbalance in
partition result) + small refactoring
Diffstat (limited to 'ltablib.c')
-rw-r--r-- | ltablib.c | 111 |
1 files changed, 73 insertions, 38 deletions
@@ -1,5 +1,5 @@ | |||
1 | /* | 1 | /* |
2 | ** $Id: ltablib.c,v 1.86 2015/11/20 12:30:20 roberto Exp roberto $ | 2 | ** $Id: ltablib.c,v 1.89 2015/11/24 16:54:32 roberto Exp roberto $ |
3 | ** Library for Table Manipulation | 3 | ** Library for Table Manipulation |
4 | ** See Copyright Notice in lua.h | 4 | ** See Copyright Notice in lua.h |
5 | */ | 5 | */ |
@@ -231,24 +231,68 @@ static int unpack (lua_State *L) { | |||
231 | ** ======================================================= | 231 | ** ======================================================= |
232 | */ | 232 | */ |
233 | 233 | ||
234 | |||
235 | /* | ||
236 | ** Produce a "random" 'unsigned int' to randomize pivot choice. This | ||
237 | ** macro is used only when 'sort' detects a big imbalance in the result | ||
238 | ** of a partition. (If you don't want/need this "randomness", ~0 is a | ||
239 | ** good choice.) | ||
240 | */ | ||
241 | #if !defined(l_randomizePivot) /* { */ | ||
242 | |||
243 | #include <time.h> | ||
244 | |||
245 | /* size of 'e' measured in number of 'unsigned int's */ | ||
246 | #define sof(e) (sizeof(e) / sizeof(unsigned int)) | ||
247 | |||
248 | /* | ||
249 | ** Use 'time' and 'clock' as sources of "randomness". Because we don't | ||
250 | ** know the types 'clock_t' and 'time_t', we cannot cast them to | ||
251 | ** anything without risking overflows. A safe way to use their values | ||
252 | ** is to copy them to an array of a known type and use the array values. | ||
253 | */ | ||
254 | static unsigned int l_randomizePivot (void) { | ||
255 | clock_t c = clock(); | ||
256 | time_t t = time(NULL); | ||
257 | unsigned int buff[sof(c) + sof(t)]; | ||
258 | unsigned int i, rnd = 0; | ||
259 | memcpy(buff, &c, sof(c) * sizeof(unsigned int)); | ||
260 | memcpy(buff + sof(c), &t, sof(t) * sizeof(unsigned int)); | ||
261 | for (i = 0; i < sof(buff); i++) | ||
262 | rnd += buff[i]; | ||
263 | return rnd; | ||
264 | } | ||
265 | |||
266 | #endif /* } */ | ||
267 | |||
268 | |||
269 | /* arrays larger than 'RANLIMIT' may use randomized pivots */ | ||
270 | #define RANLIMIT 100u | ||
271 | |||
272 | |||
234 | static void set2 (lua_State *L, unsigned int i, unsigned int j) { | 273 | static void set2 (lua_State *L, unsigned int i, unsigned int j) { |
235 | lua_seti(L, 1, i); | 274 | lua_seti(L, 1, i); |
236 | lua_seti(L, 1, j); | 275 | lua_seti(L, 1, j); |
237 | } | 276 | } |
238 | 277 | ||
278 | |||
279 | /* | ||
280 | ** Return true iff value at stack index 'a' is less than the value at | ||
281 | ** index 'b' (according to the order of the sort). | ||
282 | */ | ||
239 | static int sort_comp (lua_State *L, int a, int b) { | 283 | static int sort_comp (lua_State *L, int a, int b) { |
240 | if (!lua_isnil(L, 2)) { /* function? */ | 284 | if (lua_isnil(L, 2)) /* no function? */ |
285 | return lua_compare(L, a, b, LUA_OPLT); /* a < b */ | ||
286 | else { /* function */ | ||
241 | int res; | 287 | int res; |
242 | lua_pushvalue(L, 2); | 288 | lua_pushvalue(L, 2); /* push function */ |
243 | lua_pushvalue(L, a-1); /* -1 to compensate function */ | 289 | lua_pushvalue(L, a-1); /* -1 to compensate function */ |
244 | lua_pushvalue(L, b-2); /* -2 to compensate function and 'a' */ | 290 | lua_pushvalue(L, b-2); /* -2 to compensate function and 'a' */ |
245 | lua_call(L, 2, 1); | 291 | lua_call(L, 2, 1); /* call function */ |
246 | res = lua_toboolean(L, -1); | 292 | res = lua_toboolean(L, -1); /* get result */ |
247 | lua_pop(L, 1); | 293 | lua_pop(L, 1); /* pop result */ |
248 | return res; | 294 | return res; |
249 | } | 295 | } |
250 | else /* a < b? */ | ||
251 | return lua_compare(L, a, b, LUA_OPLT); | ||
252 | } | 296 | } |
253 | 297 | ||
254 | 298 | ||
@@ -293,39 +337,26 @@ static unsigned int partition (lua_State *L, unsigned int lo, | |||
293 | 337 | ||
294 | 338 | ||
295 | /* | 339 | /* |
296 | ** Choose a "random" pivot in the middle part of the interval [lo, up]. | 340 | ** Choose an element in the middle (2nd-3th quarters) of [lo,up] |
297 | ** (If you don't want/need this "randomness", (lo+up)/2 is an excellent | 341 | ** "randomized" by 'rnd' |
298 | ** choice.) | ||
299 | */ | 342 | */ |
300 | #if !defined(l_sortpivot) | 343 | static unsigned int choosePivot (unsigned int lo, unsigned int up, |
301 | /* Use 'time' and 'clock' as sources of "randomness" */ | 344 | unsigned int rnd) { |
302 | #include <time.h> | ||
303 | |||
304 | #define szi (sizeof(unsigned int)) | ||
305 | #define sof(e) (sizeof(e)/szi) | ||
306 | |||
307 | static unsigned int choosePivot (unsigned int lo, unsigned int up) { | ||
308 | clock_t c = clock(); | ||
309 | time_t t = time(NULL); | ||
310 | unsigned int buff[sof(c) + sof(t)]; | ||
311 | unsigned int r4 = (unsigned int)(up - lo) / 4u; /* range/4 */ | 345 | unsigned int r4 = (unsigned int)(up - lo) / 4u; /* range/4 */ |
312 | unsigned int p, i, h = 0; | 346 | unsigned int p = rnd % (r4 * 2) + (lo + r4); |
313 | memcpy(buff, &c, sof(c) * szi); | ||
314 | memcpy(buff + sof(c), &t, sof(t) * szi); | ||
315 | for (i = 0; i < sof(buff); i++) | ||
316 | h += buff[i]; | ||
317 | p = h % (r4 * 2) + (lo + r4); | ||
318 | lua_assert(lo + r4 <= p && p <= up - r4); | 347 | lua_assert(lo + r4 <= p && p <= up - r4); |
319 | return p; | 348 | return p; |
320 | } | 349 | } |
321 | 350 | ||
322 | #define l_sortpivot(lo,up) choosePivot(lo,up) | ||
323 | #endif | ||
324 | |||
325 | 351 | ||
326 | static void auxsort (lua_State *L, unsigned int lo, unsigned int up) { | 352 | /* |
353 | ** QuickSort algorithm (recursive function) | ||
354 | */ | ||
355 | static void auxsort (lua_State *L, unsigned int lo, unsigned int up, | ||
356 | unsigned int rnd) { | ||
327 | while (lo < up) { /* loop for tail recursion */ | 357 | while (lo < up) { /* loop for tail recursion */ |
328 | unsigned int p; /* Pivot index */ | 358 | unsigned int p; /* Pivot index */ |
359 | unsigned int n; /* to be used later */ | ||
329 | /* sort elements 'lo', 'p', and 'up' */ | 360 | /* sort elements 'lo', 'p', and 'up' */ |
330 | lua_geti(L, 1, lo); | 361 | lua_geti(L, 1, lo); |
331 | lua_geti(L, 1, up); | 362 | lua_geti(L, 1, up); |
@@ -335,10 +366,10 @@ static void auxsort (lua_State *L, unsigned int lo, unsigned int up) { | |||
335 | lua_pop(L, 2); /* remove both values */ | 366 | lua_pop(L, 2); /* remove both values */ |
336 | if (up - lo == 1) /* only 2 elements? */ | 367 | if (up - lo == 1) /* only 2 elements? */ |
337 | return; /* already sorted */ | 368 | return; /* already sorted */ |
338 | if (up - lo < 100u) /* small interval? */ | 369 | if (up - lo < RANLIMIT || rnd == 0) /* small interval or no randomize? */ |
339 | p = (lo + up)/2; /* middle element is a good pivot */ | 370 | p = (lo + up)/2; /* middle element is a good pivot */ |
340 | else /* for larger intervals, it is worth a random pivot */ | 371 | else /* for larger intervals, it is worth a random pivot */ |
341 | p = l_sortpivot(lo, up); | 372 | p = choosePivot(lo, up, rnd); |
342 | lua_geti(L, 1, p); | 373 | lua_geti(L, 1, p); |
343 | lua_geti(L, 1, lo); | 374 | lua_geti(L, 1, lo); |
344 | if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ | 375 | if (sort_comp(L, -2, -1)) /* a[p] < a[lo]? */ |
@@ -360,14 +391,18 @@ static void auxsort (lua_State *L, unsigned int lo, unsigned int up) { | |||
360 | p = partition(L, lo, up); | 391 | p = partition(L, lo, up); |
361 | /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ | 392 | /* a[lo .. p - 1] <= a[p] == P <= a[p + 1 .. up] */ |
362 | if (p - lo < up - p) { /* lower interval is smaller? */ | 393 | if (p - lo < up - p) { /* lower interval is smaller? */ |
363 | auxsort(L, lo, p - 1); /* call recursively for lower interval */ | 394 | auxsort(L, lo, p - 1, rnd); /* call recursively for lower interval */ |
395 | n = p - lo; /* size of smaller interval */ | ||
364 | lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ | 396 | lo = p + 1; /* tail call for [p + 1 .. up] (upper interval) */ |
365 | } | 397 | } |
366 | else { | 398 | else { |
367 | auxsort(L, p + 1, up); /* call recursively for upper interval */ | 399 | auxsort(L, p + 1, up, rnd); /* call recursively for upper interval */ |
400 | n = up - p; /* size of smaller interval */ | ||
368 | up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ | 401 | up = p - 1; /* tail call for [lo .. p - 1] (lower interval) */ |
369 | } | 402 | } |
370 | } /* tail call auxsort(L, lo, up) */ | 403 | if ((up - lo) / 128u > n) /* partition too imbalanced? */ |
404 | rnd = l_randomizePivot(); /* try a new randomization */ | ||
405 | } /* tail call auxsort(L, lo, up, rnd) */ | ||
371 | } | 406 | } |
372 | 407 | ||
373 | 408 | ||
@@ -379,7 +414,7 @@ static int sort (lua_State *L) { | |||
379 | if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ | 414 | if (!lua_isnoneornil(L, 2)) /* is there a 2nd argument? */ |
380 | luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */ | 415 | luaL_checktype(L, 2, LUA_TFUNCTION); /* must be a function */ |
381 | lua_settop(L, 2); /* make sure there are two arguments */ | 416 | lua_settop(L, 2); /* make sure there are two arguments */ |
382 | auxsort(L, 1, (unsigned int)n); | 417 | auxsort(L, 1, (unsigned int)n, 0u); |
383 | } | 418 | } |
384 | return 0; | 419 | return 0; |
385 | } | 420 | } |