| 500. Turbo Sort [message #172599] |
Tue, 22 February 2011 02:57  |
n00m
Messages: 25
Registered: February 2011
Karma: 0
|
Junior Member |
|
|
http://www.spoj.pl/problems/TSORT/
My php code gets TimeLimitExceeded. Can it be accelerated somehow?
Just curious. No problem here with C, C++, Pascal etc.
<?php
$a = array_fill(0, 1000001, 0);
fscanf(STDIN, "%d\n", &$n);
for ($i = 0; $i < $n; ++$i) {
fscanf(STDIN, "%d\n", &$v);
++$a[$v];
}
//sort($a, SORT_NUMERIC);
for ($i = 0; $i < 1000001; ++$i) {
for ($j = 0; $j < $a[$i]; ++$j) {
echo $i."\n";
}
}
?>
|
|
|
|
| Re: 500. Turbo Sort [message #172602 is a reply to message #172599] |
Tue, 22 February 2011 03:43  |
Jerry Stuckle
Messages: 2598
Registered: September 2010
Karma: 0
|
Senior Member |
|
|
On 2/21/2011 9:57 PM, n00m wrote:
> http://www.spoj.pl/problems/TSORT/
> My php code gets TimeLimitExceeded. Can it be accelerated somehow?
> Just curious. No problem here with C, C++, Pascal etc.
>
> <?php
>
> $a = array_fill(0, 1000001, 0);
>
> fscanf(STDIN, "%d\n",&$n);
>
> for ($i = 0; $i< $n; ++$i) {
> fscanf(STDIN, "%d\n",&$v);
> ++$a[$v];
> }
>
> //sort($a, SORT_NUMERIC);
>
> for ($i = 0; $i< 1000001; ++$i) {
> for ($j = 0; $j< $a[$i]; ++$j) {
> echo $i."\n";
> }
> }
>
> ?>
There's an execution time limit (default 30 seconds) built into PHP to
prevent a runaway script from hogging the server for long periods of
time. You can change this in your php.ini file, or you can make your
code more efficient.
I've seldom run into any script which runs more than 30 seconds.
--
==================
Remove the "x" from my email address
Jerry Stuckle
JDS Computer Training Corp.
jstucklex(at)attglobal(dot)net
==================
|
|
|
|
| Re: 500. Turbo Sort [message #172604 is a reply to message #172602] |
Tue, 22 February 2011 03:56 |
n00m
Messages: 25
Registered: February 2011
Karma: 0
|
Junior Member |
|
|
Time limit for the prob = 5s.
+
It's nothing to do with web & webservers.
Here PHP is just a regular lang, like C/C++ and so on.
Btw am I right in "%d\n"? Must "\n" be in format string?
We read numbers from stdin, one line - one number
|
|
|
|
| Re: 500. Turbo Sort [message #172605 is a reply to message #172599] |
Tue, 22 February 2011 03:57 |
The Natural Philosoph
Messages: 993
Registered: September 2010
Karma: 0
|
Senior Member |
|
|
n00m wrote:
> http://www.spoj.pl/problems/TSORT/
> My php code gets TimeLimitExceeded. Can it be accelerated somehow?
sure rewrite the offending bit in C and make it a php callable library
function!
> Just curious. No problem here with C, C++, Pascal etc.
>
> <?php
>
> $a = array_fill(0, 1000001, 0);
>
> fscanf(STDIN, "%d\n", &$n);
>
> for ($i = 0; $i < $n; ++$i) {
> fscanf(STDIN, "%d\n", &$v);
> ++$a[$v];
> }
>
> //sort($a, SORT_NUMERIC);
>
> for ($i = 0; $i < 1000001; ++$i) {
> for ($j = 0; $j < $a[$i]; ++$j) {
> echo $i."\n";
> }
> }
>
> ?>
|
|
|
|
| Re: 500. Turbo Sort [message #172606 is a reply to message #172599] |
Tue, 22 February 2011 04:22 |
Peter H. Coffin
Messages: 245
Registered: September 2010
Karma: 0
|
Senior Member |
|
|
On Mon, 21 Feb 2011 18:57:46 -0800 (PST), n00m wrote:
> http://www.spoj.pl/problems/TSORT/
> My php code gets TimeLimitExceeded. Can it be accelerated somehow?
> Just curious. No problem here with C, C++, Pascal etc.
>
> <?php
>
> $a = array_fill(0, 1000001, 0);
>
> fscanf(STDIN, "%d\n", &$n);
>
> for ($i = 0; $i < $n; ++$i) {
> fscanf(STDIN, "%d\n", &$v);
> ++$a[$v];
> }
>
> //sort($a, SORT_NUMERIC);
>
> for ($i = 0; $i < 1000001; ++$i) {
> for ($j = 0; $j < $a[$i]; ++$j) {
> echo $i."\n";
> }
> }
>
> ?>
Is it the sort that's dragging you down, or is it the the multiple
multi-million iteration I/O segments?
------------------
$ cat foo.php
<?php
for ($i = 0; $i < 1000001; ++$i) {
echo "nothing\n";
}
?>
$ time php foo.php >/dev/null
0m2.10s real 0m0.89s user 0m0.73s system
$
------------------
I may not have the fastest machine in the world, but since it takes two
seconds to *throw away* just a million rows of output to something that
has about as little overhead as is possible to have makes me think that
the sort is only a tiny part of your overhead.
--
They got rid of it because they judged it more trouble than it was
worth. (And considering they'd gone to great lengths to minimize its
worth, I suppose they were right.)
-- J. D. Baldwin
|
|
|
|
| Re: 500. Turbo Sort [message #172607 is a reply to message #172599] |
Tue, 22 February 2011 04:30 |
Kevin Wells
Messages: 4
Registered: November 2010
Karma: 0
|
Junior Member |
|
|
In message <a6c84d7c-f2f0-4141-8ad4-73329dba24a6(at)p12g2000vbo(dot)googlegroups(dot)com>
n00m <n00m(at)narod(dot)ru> wrote:
> http://www.spoj.pl/problems/TSORT/
> My php code gets TimeLimitExceeded. Can it be accelerated somehow?
> Just curious. No problem here with C, C++, Pascal etc.
>
> <?php
>
> $a = array_fill(0, 1000001, 0);
>
> fscanf(STDIN, "%d\n", &$n);
>
> for ($i = 0; $i < $n; ++$i) {
> fscanf(STDIN, "%d\n", &$v);
> ++$a[$v];
> }
>
> //sort($a, SORT_NUMERIC);
>
> for ($i = 0; $i < 1000001; ++$i) {
> for ($j = 0; $j < $a[$i]; ++$j) {
> echo $i."\n";
> }
> }
>
> ?>
Shouldn't it be $i++ not ++$i on the for loop?
--
Kev Wells http://riscos.kevsoft.co.uk/
http://kevsoft.co.uk/ http://kevsoft.co.uk/AleQuest/
ICQ 238580561
I will not cease from mental fight,
|
|
|
|
| Re: 500. Turbo Sort [message #172608 is a reply to message #172607] |
Tue, 22 February 2011 05:00 |
n00m
Messages: 25
Registered: February 2011
Karma: 0
|
Junior Member |
|
|
Actually I sort (in usual sense) nothing.But my output is sorted, of
course.
> Shouldn't it be $i++ not ++$i on the for loop?
And what's the difference (I refer only to my code above)?
It's because my fingers like a bit more to press "++" first, then the
rest.
A kind of mechanical habit.
|
|
|
|
| Re: 500. Turbo Sort [message #172614 is a reply to message #172608] |
Tue, 22 February 2011 05:26 |
n00m
Messages: 25
Registered: February 2011
Karma: 0
|
Junior Member |
|
|
This took 1.82s (g++4.0.0-8) and was accepted of course.
Seems it's not for PHP
#include <stdio.h>
#include <ctype.h>
int read_ui() {
int m = 0;
char c;
while (!isdigit(c = getchar()));
while (isdigit(c)) {
m = m * 10 + (c - '0');
c = getchar();
}
return m;
}
int a[1000001], n, i, j;
int main() {
n = read_ui();
for (i = 0; i < n; ++i) {
++a[read_ui()];
}
for (i = 0; i < 1000001; ++i) {
for (j = 0; j < a[i]; ++j) {
printf("%d\n", i);
}
}
return 0;
}
|
|
|
|
| Re: 500. Turbo Sort [message #172620 is a reply to message #172599] |
Tue, 22 February 2011 09:22 |
Luuk
Messages: 329
Registered: September 2010
Karma: 0
|
Senior Member |
|
|
On 22-02-11 03:57, n00m wrote:
> http://www.spoj.pl/problems/TSORT/
> My php code gets TimeLimitExceeded. Can it be accelerated somehow?
> Just curious. No problem here with C, C++, Pascal etc.
>
> <?php
>
> $a = array_fill(0, 1000001, 0);
>
> fscanf(STDIN, "%d\n", &$n);
>
> for ($i = 0; $i < $n; ++$i) {
> fscanf(STDIN, "%d\n", &$v);
> ++$a[$v];
> }
>
> //sort($a, SORT_NUMERIC);
>
> for ($i = 0; $i < 1000001; ++$i) {
> for ($j = 0; $j < $a[$i]; ++$j) {
> echo $i."\n";
> }
> }
>
> ?>
<?php
fscanf(STDIN, "%d\n", &$n);
$a = array_fill(0, $n+1, 0);
for ($i = 0; $i < $n; ++$i) {
fscanf(STDIN, "%d\n", &$v);
++$a[$v];
}
//sort($a, SORT_NUMERIC);
for ($i = 0; $i < $n+1; ++$i) {
echo ".";
for ($j = 0; $j < $a[$i]; ++$j) {
echo $i."\n";
}
}
?>
The second loop goes down from 1 milion to how many number you want to
sort...
--
Luuk
|
|
|
|
|
|
| Re: 500. Turbo Sort [message #172622 is a reply to message #172621] |
Tue, 22 February 2011 09:47 |
The Natural Philosoph
Messages: 993
Registered: September 2010
Karma: 0
|
Senior Member |
|
|
Álvaro G. Vicario wrote:
> El 22/02/2011 6:00, n00m escribió/wrote:
>> Actually I sort (in usual sense) nothing.But my output is sorted, of
>> course.
>>
>>> Shouldn't it be $i++ not ++$i on the for loop?
>>
>> And what's the difference (I refer only to my code above)?
>> It's because my fingers like a bit more to press "++" first, then the
>> rest.
>> A kind of mechanical habit.
>
> It's documented here:
>
> http://es2.php.net/manual/en/language.operators.increment.php
>
>
But since the value of $i is not tested in that statement, it makes no
difference.
It does in the sort of statement like while($i++<10); versus while(++$i<10)
I think. I NEVER EVER use an increment operator in a test statement
because if I can't remember, chances are the next person to read the
code wont, either.
Always ask yourself, 'how stupid, lazy & forgetful can I be on a Bad
Monday morning in February, double it, and assume the guy who has to
maintain your code is worse'
THEN when you come back to your code on that morning after a row with
your other half, ha raging hangover and you crashed the car on the way
in, you stand some chance of being able to find the bug as well;-)
|
|
|
|
| Re: 500. Turbo Sort [message #172626 is a reply to message #172622] |
Tue, 22 February 2011 12:16 |
sheldonlg
Messages: 166
Registered: September 2010
Karma: 0
|
Senior Member |
|
|
On 2/22/2011 4:47 AM, The Natural Philosopher wrote:
> Álvaro G. Vicario wrote:
>> El 22/02/2011 6:00, n00m escribió/wrote:
>>> Actually I sort (in usual sense) nothing.But my output is sorted, of
>>> course.
>>>
>>>> Shouldn't it be $i++ not ++$i on the for loop?
>>>
>>> And what's the difference (I refer only to my code above)?
>>> It's because my fingers like a bit more to press "++" first, then the
>>> rest.
>>> A kind of mechanical habit.
>>
>> It's documented here:
>>
>> http://es2.php.net/manual/en/language.operators.increment.php
>>
>>
> But since the value of $i is not tested in that statement, it makes no
> difference.
>
> It does in the sort of statement like while($i++<10); versus while(++$i<10)
>
> I think. I NEVER EVER use an increment operator in a test statement
> because if I can't remember, chances are the next person to read the
> code wont, either.
>
> Always ask yourself, 'how stupid, lazy & forgetful can I be on a Bad
> Monday morning in February, double it, and assume the guy who has to
> maintain your code is worse'
>
> THEN when you come back to your code on that morning after a row with
> your other half, ha raging hangover and you crashed the car on the way
> in, you stand some chance of being able to find the bug as well;-)
This illustrates the problem I had with C programmers back in the days.
They tended to have a "Name That Tune" philosophy. "I can write that
code in five lines". "I can write that code in three lines". I can
write that code in one line." "Write that code".
Debugging that one line multi-multi conditions for loop was a nightmare.
I could not set a break point inside the loop because everything was
done inside the definition of the loop. I would have to rewrite it so
that I could set some break points and examine values in the debugger.
For the the example above, it would then become either
if (i < 10) ....
i++
or
i++
if (i < 10)
and I knew then exactly what I wanted. So, I agree, NEVER include an
increment inside a test.
--
Shelly
|
|
|
|
| Re: 500. Turbo Sort [message #172640 is a reply to message #172607] |
Wed, 23 February 2011 01:15 |
Thomas 'PointedEars'
Messages: 701
Registered: October 2010
Karma: 0
|
Senior Member |
|
|
Kevin Wells wrote:
> n00m <n00m(at)narod(dot)ru> wrote:
>> http://www.spoj.pl/problems/TSORT/
>> My php code gets TimeLimitExceeded. Can it be accelerated somehow?
>> Just curious. No problem here with C, C++, Pascal etc.
>>
>> <?php
>>
>> $a = array_fill(0, 1000001, 0);
>>
>> fscanf(STDIN, "%d\n", &$n);
>>
>> for ($i = 0; $i < $n; ++$i) {
>> fscanf(STDIN, "%d\n", &$v);
>> ++$a[$v];
>> }
>>
>> //sort($a, SORT_NUMERIC);
>>
>> for ($i = 0; $i < 1000001; ++$i) {
>> for ($j = 0; $j < $a[$i]; ++$j) {
>> echo $i."\n";
>> }
>> }
>>
>> ?>
>
> Shouldn't it be $i++ not ++$i on the for loop?
Yes, it should not. First of all, the two expressions are semantically
equivalent *there*: the variable value is increased by one *after* one
cycle. Second, the algorithm for $i++ has to back up the original value of
$i since it is that which this expression evaluates to; ++$i does not have
to back up anything, saving one step. But since the variable value is not
immediately used here, optimization by the compiler might smooth out the
difference. Personally, I have used post-increment before on such occasions
but since a while I am using pre-increment just in case compilers are not as
advanced as I wish them to be.
On a funny side note, Bjarne Stroustrup said in an interview that there was
general agreement that his C++ (formerly, "C with Classes") should have been
named ++C, but he thought "that would [have created] too many problems for
non-geeks"¹ ;-)
PointedEars
___________
¹ <http://www.computerworld.com.au/article/250514/
a-z_programming_languages_c_/>
--
Anyone who slaps a 'this page is best viewed with Browser X' label on
a Web page appears to be yearning for the bad old days, before the Web,
when you had very little chance of reading a document written on another
computer, another word processor, or another network. -- Tim Berners-Lee
|
|
|
|
Calendar
Search
Help
Members
Register
Login
Home
]