optimize me #4

Forum Attachments

optimize me #4

jnesselr 14 Nov 2008 00:06

can it go any faster?

0→Xmin
94→Xmax
0→Ymax
–62→Ymin
DispGraph
":"→Str9
{0}→L₁
L₁→L₂
L₂→L₃
0→B
For(A,0,62
For(B,0,94
0→Z
pxl-Test(A,B)→V
If V=1:Then
B→C
Repeat C≥93 or pxl-Test(A,C)=0
If C<94
C+1→C
End
dim(L₁)→H
A→L₁(H)
B→L₂(H)
C-1+(pxl-Test(A,C)=1→L₃(H)
H+1→H
H→dim(L₁)
H→dim(L₂)
H→dim(L₃)
C→B
End
End
Pxl-Change(A,0
End
H-1→H
H→dim(L₁
H→dim(L₂
H→dim(L₃
ClrDraw
For(A,1,dim(L₁))
If L₁(A)=94:Then
augment(seq(L₁(E),E,1,A-1),seq(L₁(E),E,A+1,dim(L₁))→L₁
augment(seq(L₂(E),E,1,A-1),seq(L₂(E),E,A+1,dim(L₂))→L₂
augment(seq(L₃(E),E,1,A-1),seq(L₃(E),E,A+1,dim(L₃))→L₃
End
End

Re: optimize me #4

Weregoose 16 Nov 2008 04:21

Faster? That would crash as it is, so let's worry about that first. For(A,1,dim(L1)) sets the destination for A and doesn't update it, so shrinking the list would mean later trying to access elements that are no longer there. A conditional loop would solve this, but the optimization I've got in the works would remove the need for searching altogether.

If you had a strictly-increasing list prepared but with large numbers at every position for which a 94 exists in L1, and then sorted lists 1–3 using the fourth list as a seed (so as to push said elements to the right side), and finally cut out those last elements via dim(, you would get the same effect as what your seq( lines are accomplishing:

E9(L1=94)+cumSum(binomcdf(dim(L1)-1,0→S
SortA(LS,L1,L2,L3
dim(Ans)-sum(Ans>E9→dim(L1
Ans→dim(L2
Ans→dim(L3

This is roughly 100 bytes smaller and probably several times faster. I didn't take a crack at the rest of the code, but the optimization articles might give you a good idea on what other things I might be looking for.

This code also abolishes the error that comes up when the first or last element is a 94.

Last edited on 16 Nov 2008 09:37 by Weregoose Show more

Re: optimize me #4

jnesselr 16 Nov 2008 13:58

Actually, that code has an error that I just noticed. L1 is the coordinates 0 through 62 for the y coordinate. L2 is for the start of the line, and L3 is for the end of it on the x coordinates. On the code above that, the only way it would work would be to have it make two 94's in the list every time it comes across it. That is why the second loop gets rid of one 94 decreasing the list size by one. Which means that when the loop reaches end, A is added to 1 and stored into A causing it to be at the right element. I could fix the problem where it would overflow with this code:

For(A,1,dim(L1))
if dim(L₁)>A:Then
If L₃(A)=94:Then
augment(seq(L₁(E),E,1,A-1),seq(L₁(E),E,A+1,dim(L₁))→L₁
augment(seq(L₂(E),E,1,A-1),seq(L₂(E),E,A+1,dim(L₂))→L₂
augment(seq(L₃(E),E,1,A-1),seq(L₃(E),E,A+1,dim(L₃))→L₃
End
End
End

As for the rest of the code, it scans the screen.
I have some parts not included, but they didn't need to be optimized.

Re: optimize me #4

Weregoose 16 Nov 2008 19:04

Great. The only thing that needs to be changed in my code is to go from L1=94 to L3=94.

But, I'm a little doubtful that adding a second 94 can't be avoided.