Project Euler Problem 35 #シェル芸 - jarp,
の seq のはなし。
Project Euler Problem 35 #シェル芸 - jarp,
そもそも最初から奇数だけ扱えばいいのでseqで奇数指定する。
% time (seq 1 2 999999|grep -v '[024568]'|wc -l)
5460
0.31s user 0.00s system 111% cpu 0.280 total
なぜか遅くなった。佐藤さんの調査によるとGNU coreutils seqは +1だけ最適化してるという話で、なかなか興味深い。
ということでソースを読んでみた。
/* seq - print sequence of numbers to standard output.
Copyright (C) 1994-2016 Free Software Foundation, Inc.
(略)
/* Written by Ulrich Drepper. */
あ、うるりっひの名前が!
ソースコード上での登場順は違うけどまず判定部分はこう
int
main (int argc, char **argv)
{
(略)
/* If the following hold:
- no format string, [FIXME: relax this, eventually]
- integer start (or no start)
- integer end
- increment == 1 or not specified [FIXME: relax this, eventually]
then use the much more efficient integer-only code. */
if (all_digits_p (argv[optind])
&& (n_args == 1 || all_digits_p (argv[optind + 1]))
&& (n_args < 3 || (STREQ ("1", argv[optind + 1])
&& all_digits_p (argv[optind + 2])))
&& !equal_width && !format_str && strlen (separator) == 1)
{
char const *s1 = n_args == 1 ? "1" : argv[optind];
char const *s2 = argv[optind + (n_args - 1)];
if (seq_fast (s1, s2))
return EXIT_SUCCESS;
/* Upon any failure, let the more general code deal with it. */
}
if ((isfinite (first.value) && first.precision == 0)
&& step.precision == 0 && last.precision == 0
&& 0 <= first.value && step.value == 1 && 0 <= last.value
&& !equal_width && !format_str && strlen (separator) == 1)
{
char *s1;
char *s2;
if (asprintf (&s1, "%0.Lf", first.value) < 0)
xalloc_die ();
if (! isfinite (last.value))
s2 = xstrdup ("inf"); /* Ensure "inf" is used. */
else if (asprintf (&s2, "%0.Lf", last.value) < 0)
xalloc_die ();
if (*s1 != '-' && *s2 != '-' && seq_fast (s1, s2))
{
IF_LINT (free (s1));
IF_LINT (free (s2));
return EXIT_SUCCESS;
}
free (s1);
free (s2);
/* Upon any failure, let the more general code deal with it. */
}
if (format_str == NULL)
format_str = get_default_format (first, step, last);
print_numbers (format_str, layout, first.value, step.value, last.value);
return EXIT_SUCCESS;
}
すべてが数字(==整数)で、増分が1で、
出力の幅を揃えない、書式指定がない、区切りは1バイト…というところ?
二つめの判定は削ったところも見ないと正確にはわからんけど、
大体同じようなものっぽい。
んで、その「高速」なほうがこれ
/* Print all whole numbers from A to B, inclusive -- to stdout, each
followed by a newline. If B < A, return false and print nothing.
Otherwise, return true. */
static bool
seq_fast (char const *a, char const *b)
{
bool inf = STREQ (b, "inf");
/* Skip past any leading 0's. Without this, our naive cmp
function would declare 000 to be larger than 99. */
a = trim_leading_zeros (a);
b = trim_leading_zeros (b);
size_t p_len = strlen (a);
size_t q_len = inf ? 0 : strlen (b);
/* Allow for at least 31 digits without realloc.
1 more than p_len is needed for the inf case. */
size_t inc_size = MAX (MAX (p_len + 1, q_len), 31);
/* Copy input strings (incl NUL) to end of new buffers. */
char *p0 = xmalloc (inc_size + 1);
char *p = memcpy (p0 + inc_size - p_len, a, p_len + 1);
char *q;
char *q0;
if (! inf)
{
q0 = xmalloc (inc_size + 1);
q = memcpy (q0 + inc_size - q_len, b, q_len + 1);
}
else
q = q0 = NULL;
bool ok = inf || cmp (p, p_len, q, q_len) <= 0;
if (ok)
{
/* Reduce number of fwrite calls which is seen to
give a speed-up of more than 2x over the unbuffered code
when printing the first 10^9 integers. */
size_t buf_size = MAX (BUFSIZ, (inc_size + 1) * 2);
char *buf = xmalloc (buf_size);
char const *buf_end = buf + buf_size;
char *bufp = buf;
/* Write first number to buffer. */
bufp = mempcpy (bufp, p, p_len);
/* Append separator then number. */
while (inf || cmp (p, p_len, q, q_len) < 0)
{
*bufp++ = *separator;
incr (&p, &p_len);
/* Double up the buffers when needed for the inf case. */
if (p_len == inc_size)
{
inc_size *= 2;
p0 = xrealloc (p0, inc_size + 1);
p = memmove (p0 + p_len, p0, p_len + 1);
if (buf_size < (inc_size + 1) * 2)
{
size_t buf_offset = bufp - buf;
buf_size = (inc_size + 1) * 2;
buf = xrealloc (buf, buf_size);
buf_end = buf + buf_size;
bufp = buf + buf_offset;
}
}
bufp = mempcpy (bufp, p, p_len);
/* If no place for another separator + number then
output buffer so far, and reset to start of buffer. */
if (buf_end - (p_len + 1) < bufp)
{
fwrite (buf, bufp - buf, 1, stdout);
bufp = buf;
}
}
/* Write any remaining buffered output, and the terminator. */
*bufp++ = *terminator;
fwrite (buf, bufp - buf, 1, stdout);
IF_LINT (free (buf));
}
free (p0);
free (q0);
return ok;
}
通常のはこちら。
/* Actually print the sequence of numbers in the specified range, with the
given or default stepping and format. */
static void
print_numbers (char const *fmt, struct layout layout,
long double first, long double step, long double last)
{
bool out_of_range = (step < 0 ? first < last : last < first);
if (! out_of_range)
{
long double x = first;
long double i;
for (i = 1; ; i++)
{
long double x0 = x;
printf (fmt, x);
if (out_of_range)
break;
x = first + i * step;
out_of_range = (step < 0 ? x < last : last < x);
if (out_of_range)
{
/* If the number just past LAST prints as a value equal
to LAST, and prints differently from the previous
number, then print the number. This avoids problems
with rounding. For example, with the x86 it causes
"seq 0 0.000001 0.000003" to print 0.000003 instead
of stopping at 0.000002. */
bool print_extra_number = false;
long double x_val;
char *x_str;
int x_strlen;
setlocale (LC_NUMERIC, "C");
x_strlen = asprintf (&x_str, fmt, x);
setlocale (LC_NUMERIC, "");
if (x_strlen < 0)
xalloc_die ();
x_str[x_strlen - layout.suffix_len] = '\0';
if (xstrtold (x_str + layout.prefix_len, NULL, &x_val, c_strtold)
&& x_val == last)
{
char *x0_str = NULL;
if (asprintf (&x0_str, fmt, x0) < 0)
xalloc_die ();
print_extra_number = !STREQ (x0_str, x_str);
free (x0_str);
}
free (x_str);
if (! print_extra_number)
break;
}
fputs (separator, stdout);
}
fputs (terminator, stdout);
}
}
そういやこれ、GNU 形式のインデントだわ。
![「食戟のソーマ」第1巻<初回生産限定版> [Blu-ray]](http://ecx.images-amazon.com/images/I/51ezHbZmwFL._SL160_.jpg)
「食戟のソーマ」第5巻<初回生産限定版> 【イベントチケット先行購入申込券付】 [Blu-ray]![「食戟のソーマ」第5巻<初回生産限定版> 【イベントチケット先行購入申込券付】 [Blu-ray]](http://ecx.images-amazon.com/images/I/51HXOwxtanL._SL160_.jpg)
うん。アニメ(に限らないだろうけど)の
サントラは商売にならないってのは以前聞いたことがあるけどね○|￣|＿
