Need a smart Array shuffle

[Mike Trader]

MyNew.EXE reads an ascii file 10k lines long, one line at a time.

For each line it executes all my code. I need to be able to "look Back" 50 lines without re-reading the ascii file.

So I have an array
Global lookBack() AS LONG
Function MainCode() AS LONG
Dim LookBack(50)

Now i need to constantly move all 50 elements down one each time I read a new line of data. I could do it with

LookBack(2) = LookBack(1)
LookBack(3) = LookBack(2)
LookBack(4) = LookBack(3)
...
LookBack(50) = LookBack(49)
LookBack(1) = NewData

But I am sure there is a better (faster) way to do this.
Is there a way to "push" all the values down?

Would welcome any suggestions


------------------
Kind Regards
Mike

[Eric Pearson]

Have you looked at ARRAY INSERT?

-- Eric

------------------
Perfect Sync: Perfect Sync Development Tools
Email: mailto:[email protected][email protected]</A>

[Borje Hagsten]

Or, if intention is to put file backwards into array, use the
following in your loop:

  LookBack(50 - I) = NewData
  INCR I

------------------

[Mike Trader]

Wow! Thanks. Very cool. I am really starting to love PB.

I am actually working with a multi Dimensional array:

Dim Lookback(9999,5)
NumElements = 10000*6

So to insert the latest 6 values at the start I would write:

ARRAY INSERT LookBack(0,0) For NumElements-0, NewData1
ARRAY INSERT LookBack(0,1) For NumElements-1, NewData2
ARRAY INSERT LookBack(0,2) For NumElements-2, NewData3
ARRAY INSERT LookBack(0,4) For NumElements-3, NewData4
ARRAY INSERT LookBack(0,5) For NumElements-4, NewData5

Is that right?

------------------
Kind Regards
Mike

[Eric Pearson]

Well, you missed the (0,3) element, but other than that it looks ok.

Since you are shifting the entire contents of the array you can skip the FOR clause. You are telling ARRAY INSERT where to start, and the end of the array is the default, so you don't really need to tell ARRAY INSERT where to stop.

Is speed a concern? It looks like you are shifting 60,000 elements (=240,000 bytes) six times in a row, and that could be a slow process. I'd recommend using an array of User Defined Types, like this:

TYPE DataRow
     Element(0 TO 5) AS LONG
END TYPE
 
DIM LookBack(9999) AS DataRow

Then instead of using LookBack(100,4) you would use LookBack(100).Element(4). This method of storing data is just as efficient as a two-dimensional array of LONGs -- in fact it uses exactly the same memory structure -- but it would allow you to perform a single ARRAY INSERT instead of six of them, each time you want to add a row.

-- Eric

P.S. Oops... I see Bern suggested something similar while I was editing this.

------------------
Perfect Sync: Perfect Sync Development Tools
Email: mailto:[email protected][email protected]</A>



[This message has been edited by Eric Pearson (edited February 28, 2001).]

[Bern Ertl]

Mike, if the purpose of the multi-dimensional array is to store
6 fields for every record of your file, you might try creating a
type structure instead of the multi-dimensional array depending on
your processing needs. It's easier to read your code that way.

Ie.:

TYPE FileRecData
   Field(5) AS LONG 'Use whatever your actual data type is...
END TYPE

.......

DIM LookBack(50) AS FileRecData
DIM Temp AS FileRecData

OPEN #Device%, ......
WHILE NOT EOF( Device%)
   INPUT #Device%, Temp.Field(1), Temp.Field(2), etc..
   ARRAY INSERT LookBack(0), Temp
WEND

------------------
Bernard Ertl

[This message has been edited by Bern Ertl (edited February 28, 2001).]

[Peter P Stephensen]

I would expect this code to be very fast as no mem is moved.

Regards
Peter

#compile exe
#dim all
#register none
 
type MEMTYPE
    test as long
end type
  
%MEM_SIZE = 50
 
%Remember  = 1
%LookBack  = 2
 
'Object
function Memory(byval func_id as long, byval param as long) as long
 
    dim m_data(%MEM_SIZE) as static MEMTYPE
    static m_index as long
 
    local lpmt as MEMTYPE pointer
    local i as long
 
    select case func_id
    case %Remember
	lpmt = param				
	m_data(m_index) = @lpmt
	incr m_index
	if m_index > %MEM_SIZE then m_index = 0
  	
    case %LookBack
	i = param
	select case i
	case > %MEM_SIZE 
	    exit function
	case <= m_index - 1
	    function = varptr(m_data(m_index - 1 - i))
	    exit function
	case else
  	    function = varptr(m_data(%MEM_SIZE + m_index - i))
	    exit function
	end select
 
    end select
 
end function
 
'Wrappers
sub Remember(mt as MEMTYPE)
    Memory %Remember, varptr(mt)
end sub
 
sub LookBack(i as long, mt as MEMTYPE)
    local lpmt as MEMTYPE pointer
    lpmt = Memory(%LookBack, i)
    if lpmt then mt = @lpmt
end sub
 
function pbmain
 
    local mt as MEMTYPE, i as long
 
    for i = 1 to 110
	mt.test = i
	Remember mt
    next i
 
    LookBack 10, mt

    msgbox format$(mt.test)
 
end function

------------------

[Borje Hagsten]

If number of elements are known and purpose is to fill an already
dimensioned array for the first time, I don't see any reason for
ARRAY INSERT. Using backwards counter, UBOUND(ARRAY) - Index, will
give same result much faster. Combined with a user defined TYPE for
the six different elements, process would be both lean and mean..


------------------

[Bern Ertl]

Borje, you're right. There's really no need for ARRAY INSERT at all.

In my example, just load the data directly into the array with a
record counter. You can access the first, 50th, last or whichever
records you want by adjusting from the current record count.



------------------
Bernard Ertl

[Mike Trader]

Jeeeze Peter, what the heck does that do?

pls remember I am still very green ...
Could you annotate it a little pls )


Bjorg,
It seems I only need to write one set of data to memory. the other 9999 can stay put if I just pretend the start has moved. Perhaps I do this with pointers....

------------------
Kind Regards
Mike

[Bern Ertl]

Mike, my sample may not be as efficient as Peter's, but it might
be easier to understand:

TYPE FileRecData
   Field(5) AS LONG 'or whatever your type is...
END TYPE


DIM FileBuffer(9999) AS FileRecData


OPEN #Device%, ....
I = 0
WHILE NOT EOF(Device%)
   INPUT #Device%, FileBuffer(I).Field(0), FileBuffer(I).Field(1), etc..
   INCR I  'INCR before INPUT if you want BASE 1
WEND
DECR I 'Reset to last record actually read if BASE 0


'Can access last 50 records are accessed, from most recent to 50 
'records ago, as:
'  I       (most recent access)
'  I - 1   (prior access)
'  I - 2
'  etc.

------------------
Bernard Ertl

[This message has been edited by Bern Ertl (edited February 28, 2001).]

[Mike Trader]

OK thx Bern.
Peters example (whatever its method) raises an issue i have wondered about for many years. What is the order of time consuming statements?

In order of time consumption, is it..

1. Execute a > = < If statement
2. Moving 8bytes in memory (&&A = &&B)
3. Moving 4 Bytes in memory (&A = &B)
4. Setup a SELECT CASE and execute one CASE
5. Setup a While/For Loop
6. Execute a FUNCTION call
7. Execute a SUB call
8. Dimension an Array
9. Dimension a Long
10.Define a Variable as Global
11.Deinfe a Variable as Local
12.String Operations Left$/Right$ etc (guess this should be #1!)'


Cos I am allways minimizing my If statements and declaring vars etc etc to try and keep the cost (in Time) as low as possible for my apps. I guess this comes from crappy Prog environments where the overhead is high. but im still curious. Is the IF statement expensive?

------------------
Kind Regards
Mike

[Ian Cairns]

Mike,
If you want to get your feet wet programming, then don't worry (to start with)
how long each statement is going to take. Unless you are working in an intesive
loop, you won't likely notice any difference in program execution speed.

Look out for the Number 1 problem of programming. Blindness! Don't assume that
the only way that you can solve a "problem" is by using technique "X". Take the
time to look at a few things.
1. What am I trying to achieve? (final result)
2. What do I have to work with? (information)
3. How many different ways do I know of to solve this problem?
4. How many other ways are there? (There will be at least 3 more than you can think of)
5. Will I ever have to do this again? (will it become a library function?)
If 5 is true, then spend some time making your routine maintainable as well as "fast."

regards,

------------------
[email protected]

[Mike Trader]

OK Ian. point taken.

the reason I ask is cos Peters example has a SUB call and a FUNCTION call for each iteration, AND several CASE executions AND assigns and destroys two variables AND an IF statement or two for each iteration.

Now if an IF statement is equivelant to moving 100 BYTEs for example and a LOCAL var is eqivelatn to moving 20 BYTEs in memory etc etc you can see that it might be faster to just move the array elements in a 50 element array. in a 10k element array using pointers is obviously going to be faster.

But I just have NO IDEA wht the overhead is for these things. And since I have 10k iterations to perform and speed is very important in this case (the whole reason for porting this all to PB in the first place) i thought i would ask

------------------
Kind Regards
Mike

[Borje Hagsten]

Not very intelligent answer, but - it depends..

IF/THEN is fast for few checks, but I think SELECT CASE is slightly
faster for many. At least code becomes cleaner, IMO.

People say using LONG in 32-bit environment is faster than INTEGER.
Probably true in most cases, but for small, repeated loops, I have
noticed otherwise - INTEGER can sometimes be faster there..

When executing < or > checks, try to determine what will most likely
and put that one first. Code jumps out when condition is filled, so
the less checks that has to be made, the faster the loop will run.

LOCAL may be a but faster. Don't know, haven't tested, but don't think
difference is that big. Sometimes worth experimenting with REGISTER
though..

Always try to pre-calculate as many things as possible before entering
a loop. Even simple 2+2 takes time, if it has to be done millions of times.

If possible, dimension whole array before loop. 10,000 REDIM's inside a loop
takes a lot of time..

String handling stuff is always slow. Try to avoid inside big loops
if possible (or get/use ASM written routines).

Calling Functions are usually slower than Subs. Best is to avoid
both in loops, if possible. It's sometimes even worth using multiple
copies of code, by inserting a Function's code directly inside a loop.

Finally, something funny I have learned over the years. In a loop,
where many things are done, it often is worth experimenting with
the order of things. Sometimes, re-arranging things can save a
lot of time. Reason is probably because everything that happens is
a flow, and sometimes this flow gets out of sync. By re-arranging
even a couple of simple things, one sometimes actually can get
amazing speed improvements..

Also declaring B AS LONG before A AS LONG, or reverse, sometimes
can have pretty big effect with big loops. Reason is the internal
optimization of REGISTER variables PB does.


------------------

[Eric Pearson]

> IF/THEN is fast for few checks, but I
> think SELECT CASE is slightly faster for many.

If I'm not mistaken, a PowerBASIC numeric SELECT CASE performs all of its comparisons with floating point operations, so if you are comparing integer values SELECT will usually be slower than IF/THEN. Remember, SELECT CASE gives the impression of comparing a single value to one or more "cases", but in the end the computer has to ask "is this equal to this?" and it doesn't really matter if the first "this" is always the same.

If you're a real speed freak, check out ON GOTO. If you need a super-fast branch based on a single value, you won't believe how fast it is. And you can create structured, easily maintainable code using ON GOTO, it just takes a little effort. Treat it like an IF/THEN or SELECT block, and you'll get the idea.

-- Eric

------------------
Perfect Sync: Perfect Sync Development Tools
Email: mailto:[email protected][email protected]</A>

[This message has been edited by Eric Pearson (edited February 28, 2001).]

[Mike Trader]

Peter,
I have spent many hours with your example. Its brilliant and exactly what I wanted. Thankyou.

I understand most of it. But I still have trouble with pointers.

I rewrote it for my own edification with some notes. I post it here to help anyone reading the post later in the archive.

'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
' Array shuffle (add a new item, removing the oldest)
'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
#COMPILE EXE
#DIM ALL
#REGISTER NONE
TYPE HiLoType
OpenPrice AS LONG
HighPrice AS LONG
LowPrice AS LONG
ClosePrice AS LONG
END TYPE
GLOBAL HiLo AS HiLoType ' An instance of the TYPE, used to assign elements
GLOBAL DataStore() AS HiLoType ' Array to store the TYPE
GLOBAL lpHiLo AS HiLoType Pointer 'TYPE Pointer
GLOBAL DataIndex AS LONG, MaxLookBack AS LONG
'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
FUNCTION StoreHiLo() AS LONG ' Store HiLo and track the Data Index
DIM DataStore(MaxLookBack)
DataStore(DataIndex) = HiLo ' Store all HiLo Componants
lpHiLo = VARPTR(HiLo)
INCR DataIndex
IF DataIndex > MaxLookBack THEN DataIndex = 0 ' Reset Index
END FUNCTION
'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
FUNCTION Retrieve(BYVAL LookBack AS LONG) AS LONG
SELECT CASE LookBack
CASE > MaxLookBack ' Beyond MaxLookBack
MSGBOX("Error: Increase MaxLookBack!")
EXIT FUNCTION
CASE <= DataIndex - 1
lpHiLo = VARPTR( DataStore(DataIndex - 1 - LookBack) )
CASE ELSE ' DataIndex - 1 to MaxLookBack
lpHiLo = VARPTR( DataStore(MaxLookBack + DataIndex - LookBack) )
END SELECT
HiLo = @lpHiLo
END FUNCTION
'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
FUNCTION PBMAIN
LOCAL Count AS LONG
DataIndex = 0
MaxLookBack = 10
'----------------------------------- Load Up the Array
FOR Count = 1 TO 3010
HiLo.OpenPrice = Count + 1305
HiLo.HighPrice = Count + 1310
HiLo.LowPrice = Count + 1300
HiLo.ClosePrice = Count + 1307
CALL StoreHiLo ' Store HiLo in an array
NEXT Count
'---------------------------------- Retrieve the last 10 High/Lows
FOR Count = 0 TO 10
CALL Retrieve(Count) ' Retrieve HiLo
MSGBOX "High "+FORMAT$(HiLo.HighPrice)+" Low "+FORMAT$(HiLo.LowPrice)
NEXT Count

END FUNCTION
'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤



------------------
Kind Regards
Mike

[Peter P Stephensen]

Mike,

Glad you liked my code You do not need pointers. I used pointers
because I wanted to hide data in an 'object' to avoid globals.

Regards
Peter

Without pointers your code could be something like:

'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
' Array shuffle (add a new item, removing the oldest)
'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
#COMPILE EXE
#DIM ALL
#REGISTER NONE
 
TYPE HiLoType
    OpenPrice  AS LONG
    HighPrice  AS LONG
    LowPrice   AS LONG
    ClosePrice AS LONG
END TYPE
 
GLOBAL HiLo AS HiLoType ' An instance of the TYPE, used to assign elements
GLOBAL DataStore() AS HiLoType ' Array to store the TYPE
GLOBAL DataIndex AS LONG, MaxLookBack AS LONG
 
'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
FUNCTION StoreHiLo() AS LONG        ' Store HiLo and track the Data Index
 
    DataStore(DataIndex) = HiLo ' Store all HiLo Componants
    INCR DataIndex
    IF DataIndex > MaxLookBack THEN DataIndex = 0 ' Reset Index
 
END FUNCTION
'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
FUNCTION Retrieve(BYVAL LookBack AS LONG) AS LONG
 
    SELECT CASE LookBack
        CASE > MaxLookBack    ' Beyond MaxLookBack
            MSGBOX("Error: Increase MaxLookBack!")
            EXIT FUNCTION
        CASE <= DataIndex - 1
            HiLo = DataStore(DataIndex - 1 - LookBack) 
        CASE ELSE             ' DataIndex - 1 to MaxLookBack
	    HiLo = DataStore(MaxLookBack + DataIndex - LookBack) 
    END SELECT
 
END FUNCTION
'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤
 
FUNCTION PBMAIN
 
    LOCAL Count AS LONG
 
    DataIndex   = 0
    MaxLookBack = 10
    DIM DataStore(MaxLookBack)
    '----------------------------------- Load Up the Array
    FOR Count = 1 TO 3010
        HiLo.OpenPrice  = Count + 1305
        HiLo.HighPrice  = Count + 1310
	HiLo.LowPrice   = Count + 1300
	HiLo.ClosePrice = Count + 1307
	CALL StoreHiLo       ' Store HiLo in an array
    NEXT Count
    '---------------------------------- Retrieve the last 10 High/Lows
    FOR Count = 0 TO 10
	CALL Retrieve(Count) ' Retrieve HiLo
	MSGBOX "High "+FORMAT$(HiLo.HighPrice)+"     Low "+FORMAT$(HiLo.LowPrice)
    NEXT Count
  
END FUNCTION
'¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

------------------

[Mike Trader]

Thanks again Peter.
I try to use Globals where possible and a different one for each thing. I realise that my funtions are not cut and pasteable as library functions but i dont care. Im not in that catagory yet. I like everything to be available everywhere at the moment. that way i dont have to think to hard about what is sent where and constanty adding variables to the function definitions.

I thought you had used pointers cos it would execute faster.
Either way thanks for solving my problem.

------------------
Kind Regards
Mike