I was stuck on the Bash version for awhile. That is, the large data set problem was too slow. After much frustration, I was able to narrow down the problem. I hope this is a help to someone.
Array access can be very problematic in Bash, for a number of reasons. This seems to be especially true when using any kind arithmetic in your index. For example:
${val[$n-1]} seems perfectly reasonable. But here's the experience I had.
I rigged my test to always print out 47 at the bottom, then I started tweaking the loop variable to see how many pieces of data I could process and still get to the end before timing out. That is, instead of i < N, my loop was i < 10000. (N in this case is 99999) After some tinkering around, I found that my code could do about 36,000 iterations and still make it to the end in time. So I needed to cut that run time to about a third. (Mind you, this was the bash version of the same solution I had no trouble with in C++.)
I don't want to give anything away, so I'm just going to give an abstract of a part of the solution in pseudo code.
for i < N, i++
{
read P
for j > 0, j--
{
if(val[j-1] < whatever) etc
}
x = val[j-1] - y
}
As I said, I had to lower N to 36000 to get this code to work. Here's where things got weird. I tried removing the arithmetic from that last line, making it:
x = val[j] - y
This had no problem at all executing up to 99999. Simply changing that j-1 to j tripled my speed. (In case you're wondering, this was all happening inside a condition wherein j was greater than 0.) That gave me the idea to try something a little odd:
j--
x = val[j] - y
That gave me the decrement I wanted, and took the arithmetic out of the indexer. But still, the performance dropped back to the 36000 level. After many frustrated and convoluted attempts to make Bash do roughly the same thing, this is the solution that for whatever reason gave me the performance I needed:
for i < N, i++
{
read P
for j > 0, j--
{
if(val[j-1] < whatever) etc
data = val[j-1]
}
x = data - y
}
So the moral of the story is:
1) I'm stupid.
2) Bash is stupid.
3) When using Bash, avoid any form of nested arithmetic wherever possible, because (See 2).
I can't tell you why certain things worked and certain things didn't. Just be very careful how you access arrays in Bash, because they're in reality linked lists, and Bash can be weird about how it parses variables, since they're all in reality strings.
