diff options
author | Denys Vlasenko <vda.linux@googlemail.com> | 2021-09-07 22:51:42 +0200 |
---|---|---|
committer | Denys Vlasenko <vda.linux@googlemail.com> | 2021-09-07 22:51:42 +0200 |
commit | 6a9b3f7acfaa7365515f1eb70427d5ddd687c162 (patch) | |
tree | cf8f15c4e8f4a1acadc5b14557238396be4c9962 /coreutils | |
parent | 574b9c446da11baaf89551f09f951d6523eff731 (diff) | |
download | busybox-w32-6a9b3f7acfaa7365515f1eb70427d5ddd687c162.tar.gz busybox-w32-6a9b3f7acfaa7365515f1eb70427d5ddd687c162.tar.bz2 busybox-w32-6a9b3f7acfaa7365515f1eb70427d5ddd687c162.zip |
shuf: add a TODO, code shrink
function old new delta
shuf_main 501 500 -1
Signed-off-by: Denys Vlasenko <vda.linux@googlemail.com>
Diffstat (limited to 'coreutils')
-rw-r--r-- | coreutils/shuf.c | 24 |
1 files changed, 14 insertions, 10 deletions
diff --git a/coreutils/shuf.c b/coreutils/shuf.c index 50483a25e..3def3d80f 100644 --- a/coreutils/shuf.c +++ b/coreutils/shuf.c | |||
@@ -44,21 +44,25 @@ | |||
44 | */ | 44 | */ |
45 | static void shuffle_lines(char **lines, unsigned numlines, unsigned outlines) | 45 | static void shuffle_lines(char **lines, unsigned numlines, unsigned outlines) |
46 | { | 46 | { |
47 | unsigned i; | ||
48 | unsigned r; | ||
49 | char *tmp; | ||
50 | |||
51 | srand(monotonic_us()); | 47 | srand(monotonic_us()); |
52 | 48 | ||
53 | for (i = numlines - 1; outlines > 0; i--, outlines--) { | 49 | while (outlines != 0) { |
54 | r = rand(); | 50 | char *tmp; |
51 | unsigned r = rand(); | ||
55 | /* RAND_MAX can be as small as 32767 */ | 52 | /* RAND_MAX can be as small as 32767 */ |
56 | if (i > RAND_MAX) | 53 | if (numlines > RAND_MAX) |
57 | r ^= rand() << 15; | 54 | r ^= rand() << 15; |
58 | r %= i + 1; | 55 | r %= numlines; |
59 | tmp = lines[i]; | 56 | //TODO: the above method is seriously non-uniform when numlines is very large. |
60 | lines[i] = lines[r]; | 57 | //For example, with numlines of 0xf0000000, |
58 | //values of (r % numlines) in [0, 0x0fffffff] range | ||
59 | //are more likely: e.g. r=1 and r=0xf0000001 both map to 1, | ||
60 | //whereas only one value, r=0xefffffff, maps to 0xefffffff. | ||
61 | numlines--; | ||
62 | tmp = lines[numlines]; | ||
63 | lines[numlines] = lines[r]; | ||
61 | lines[r] = tmp; | 64 | lines[r] = tmp; |
65 | outlines--; | ||
62 | } | 66 | } |
63 | } | 67 | } |
64 | 68 | ||