In article <[EMAIL PROTECTED]>,
Michael W Thelen <[EMAIL PROTECTED]> writes:
> * Ton Hospel <[EMAIL PROTECTED]> [2003-08-30 14:39]:
>> > Also to be added: an edge testcase with everything at max:
>> > full length input string, all 10 transforms full length.
>>
>> I guess I was being too subtle with that last sentence.
>> Several solution build a repeated s/// string, and then eval that.
>> leading to a 127*128*(2*80+5)=26822400 char string.
>
> Just to be clear, what exactly do those numbers represent?
127*128: maximum number of repeats possible, so the minimum multiplier you
can safely use
2*80+5 = s/string_of_80/string_of_80/;
and I forgot to write the factor 10 (10 transforms), but i had accounted
for it in the result.
This almost 30M string will then go into the interpreter which will blow
it up by a factor of about 10 on my machine.
>
>> The rules guarantee you a "a few million" entries in a datastructure,
>> and 27 million is a lot more than that. In actuallity evalling such a
>> string uses bout 360M real memory on my perl, again clearly too much.
>>
>> So i think a lot of solutions have to be rejected.
>
> Mine was one of the solutions that creates a repeated s/// string and then
> evals it. I didn't realize how slow they were until I started creating some
> pathological tests on my own and then discovered version 9 of the test suite
> about an hour before the end of the contest. :) And memory usage never even
> crossed my mind. It may be that these solutions eventually have to be
> rejected, but if so, I'd like to talk about why. I'm a little embarrassed (or
> should I be proud?) at having my solution be one of those that prompts a
> discussion of the rules, but I suppose it had to be discussed sometime.
>
> I guess it isn't clear to me how to interpret rules 12 and 13 of the generic
> rules, and how they should be applied. I interpreted rule 12 to mean that your
> program can use up to 2**32 bytes (about 4GB) of memory - basically, that it
> must not require infinite amounts of memory and that 2**32 bytes is an upper
> limit.
No. Rule 12 says you have *definitely less* than 4G (which guarantees
that 32-bit addressing will work), but it doesnt say how low. Your
interpretation is exactly backward. If you could use up to 4G it would say
"memory is >= 2**32" or "memory = 2**32"
.
>
> But rule 13 seems to say using 2GB of memory is too much. It also says that
The 2Gb is meant as an example that you can't just assume arbitrary amounts
of memory.
> you can make data structures of "a few million entries", and that "@a=(1)x1e6"
> is okay, but "@a=(1)x1e8" is not. In this particular contest, the line seems
> to be thin. Creating a data structure of five million entries ("@a=(1)x5e6")
This is meant to say that you may make working data of a few million "units",
and it tries not to use any terms of real memory (which varies a lot
depending on which perl it is. I've seen real memory used by a big "map"
vary by more than a factor 100 (more than 300M real memory difference)).
Yes, it's not a very exact measure. I don't know how to formulate an
objective exact limit which wouldn't spoil the fun. Real memory use is
out (due to that the *same* perl version does proper memory cleanup on
map or not depending on the exact compilation flags. Also the size of
the basic perl structures vary quite a bit in 32- versus 64-bit perl).
I could say "no more than exactly one million 'units'", but then next
golf may make using e.g. a 2**20 array very natural, which would be just
over the limit.
So that's why it has this formulation. You get to build data of a
few million "thingies", and leave the meaning of "few" and "thingies"
open for discussion in the edge cases.
> uses 117M on my system. In contrast, my 49 solution uses 129M of memory to
> solve test 24 (the big one) from test suite v9. Is it too much? If so, why?
> My 47 solution uses 229M. Is that too much? We should probably clarify
> exactly how much is too much.
This represents the real maximum case with the minimal short multiplier:
perl -wle '$_="s/". "a" x 80 . "/" . "b" x 80 . "/;";$_ x= 2e4*10; eval'
This uses 364M on my perl 5.8.0
The rules try to avoid using real memory. But even then your 5e6 is already
pushing "a few million", and this uses about 3 times as much. That's clearly
over the edge.
If you were just building a 26 million char string, we'd have a bit edge
case of the rules (since you could defend that an array entry is about 40
bytes, so 1 million of an array is about equivalent of a plain string of
40M) and I wouldn't know in which direction to decide.
But here it next goes into the interpreter that blows it up again, so
it's clearly the 26 (million) that has to be matched agains "a few (million)".
26 is a lot more than "a few" to my mind, so I say "invalid".
As a rule of the thumb, if your program uses more than 64M real and the input
size isn't in the millions, start thinking if you are breaking the memory
rules.
>
> Anyway, whatever we decide about rejecting solutions, I had fun on this hole!
> It's good to be golfing again.
>
Indeed, it seemed like a good hole, I was sorry to have missed it.
But it also was a very messy hole, so I'm glad I'm not the judge on
this one :-)
