Best shuffle: Difference between revisions
Content added Content deleted
(Improved D version) |
(Improved D version) |
||
Line 307: | Line 307: | ||
enum size_t NCHAR = cast(size_t)char.max + 1; |
enum size_t NCHAR = cast(size_t)char.max + 1; |
||
enum size_t MAX_VLA_SIZE = 1024; |
enum size_t MAX_VLA_SIZE = 1024; |
||
immutable size_t len = txt.length; |
|||
if (len == 0) |
if (len == 0) |
||
return; |
return; |
||
Line 330: | Line 330: | ||
if ((len * size_t.sizeof) < MAX_VLA_SIZE) |
if ((len * size_t.sizeof) < MAX_VLA_SIZE) |
||
ptr1 = cast(size_t*)alloca(len * size_t.sizeof); |
ptr1 = cast(size_t*)alloca(len * size_t.sizeof); |
||
size_t[] ndx1 = (ptr1 == null) ? new size_t[len] : ptr1[0 |
size_t[] ndx1 = (ptr1 == null) ? new size_t[len] : ptr1[0..len]; |
||
for (size_t ch = 0, i = 0; ch < NCHAR; ch++) |
for (size_t ch = 0, i = 0; ch < NCHAR; ch++) |
||
if (counts[ch]) |
if (counts[ch]) |
||
Line 343: | Line 343: | ||
if ((len * size_t.sizeof) < MAX_VLA_SIZE) |
if ((len * size_t.sizeof) < MAX_VLA_SIZE) |
||
ptr2 = cast(size_t*)alloca(len * size_t.sizeof); |
ptr2 = cast(size_t*)alloca(len * size_t.sizeof); |
||
size_t[] ndx2 = (ptr2 == null) ? new size_t[len] : ptr2[0 |
size_t[] ndx2 = (ptr2 == null) ? new size_t[len] : ptr2[0..len]; |
||
for (size_t i = 0, n = 0, m = 0; i < len; i++) { |
for (size_t i = 0, n = 0, m = 0; i < len; i++) { |
||
ndx2[i] = ndx1[n]; |
ndx2[i] = ndx1[n]; |
||
Line 354: | Line 354: | ||
// how long can our cyclic groups be? |
// how long can our cyclic groups be? |
||
immutable size_t grp = 1 + (len - 1) / fmax; |
|||
// how many of them are full length? |
// how many of them are full length? |
||
immutable size_t lng = 1 + (len - 1) % fmax; |
|||
// rotate each group |
// rotate each group |
||
for (size_t i = 0, j = 0; i < fmax; i++) { |
for (size_t i = 0, j = 0; i < fmax; i++) { |
||
immutable size_t first = ndx2[j]; |
|||
immutable size_t glen = grp - (i < lng ? 0 : 1); |
|||
foreach (size_t k; 1 .. glen) |
foreach (size_t k; 1 .. glen) |
||
ndx1[j + k - 1] = ndx2[j + k]; |
ndx1[j + k - 1] = ndx2[j + k]; |
||
Line 380: | Line 380: | ||
auto shuf = txt.dup; |
auto shuf = txt.dup; |
||
bestShuffle(txt, shuf); |
bestShuffle(txt, shuf); |
||
immutable nequal = count!q{a[0] == a[1]}(zip(txt, shuf)); |
|||
writefln("%s, %s, (%d)", txt, shuf, nequal); |
writefln("%s, %s, (%d)", txt, shuf, nequal); |
||
} |
} |