Which might be faster?

General
1

I have an app right now that manages an ARRAY of classes.
At various points in the process the program currently uses a FOR/NEXT loop to go thru the array
and then based on various properties, does something with that instance.

I cannot use a Dictionary as the items MUST be processed in a very specific order, and there are places where I “rearrange” the position in the array, giving (for example) a particular instance a higher “prioritiy”.

Also I am currently accessing the array in a “random” manner by its index postionin the array. [ xclass=theArray(index) ]

I was just wondering if a COLLECTION might give me the same functionality… but be faster. [speed is an important factor here]

So the criteria is

a) must be able to access complete list in priority order (skipping those that don’t have certain flags set)
b) be able to access by an index value (returning the correct item, from 0 to N)
c) be able to update/replace that item

Before anyone suggests a Dictionary using “index/priority” as the key. there can be no gap in the index. and with an Array… INSERT/REMOVE handles that automatically.

So the longer I type this the more convincied I am that an array is really the only viable solution

2

THe Xojo Collection class is not very fast. It was introduced before the Dictionary that made it obsolete for some aspects.
So I guess an Array is the solution.

3

I’d say the array is your best bet.

4

How many class properties will determine whether you will act or not within the for/next loop? And how big might the array get?

If the array might get large, I’m thinking of a master class around the main array that maintains shadow arrays or dictionaries that will help you lookup the instances you want quickly. The master class would implement Append, Remove, and even MoveTo to keep everything in sync.

5

The array (on average) might contain up to 300 items
each item describes a shape/image/text/line (etc) to be drawn (or not) along with all attributes (x,y, color, thickness etc)
so there are properties such as Visible, Group, Layer to name a few
In order to maintain Undo/Redo… nothing is removed from this array until the data is saved… it is just marked INACTIVE so that REDO can just flip the flag back again and it is still in the same position it was before.

6

For that number of elements, I think a straight array with a for/next loop should be fast enough.

7

I concur with everyone else, that using an array should be the fastest solution. There are some things I’ve found which can help through processing.

Don’t

for i=0 to ubound( array )

Do

Dim n as integer = ubound( array ) for i=0 to n

Don’t allocate variables within the loop.

for... Dim i as myObject = array( l )

if you can, either directly access the object’s methods

array( l ).myFunction

or create a variable before the loop, and then set it to the element.

Dim i as myObject for... i = array( l ) i.myfunction

If your array contains even numbers, you can get a slight advantage by processing two items in each cycle of the loop.

The last thing to do is to really really try to use as little code as possible within the loop and also try to avoid calling too many functions.

Last but not least, you can use #pragmas to squeeze a little more out of the processing.

The last thing you could try is to use Xojo Script (if you can) as Xojo Script features LLVM, which for some things is faster than compiled Xojo code.

8

Oh forgot, make sure that the array is the same type as your object, not a variant otherwise you’ll need to re-cast every time.

9

All good tips.

FYI, someone on the mailing list did a test of using Ubound in a loop vs. caching the value of Ubound first. I don’t remember the exact numbers, but it turned out to make just a few ms difference in a million iterations or so.

10

Yeah, Ubound is highly optimized.

11

It’s been my experience that unless you’re trying to eek out as much speed as possible, leaving it in the loop doesn’t matter - the end user will never notice it.

Get it working first and then figure out where to optimize.

12

Found it, this is what I meant as allocation in the loop.

for i As integer = 0 to array.Ubound

In my own tests I did some time ago, I found that replacing this code with the slightly longer code, made speed improvements.

Dim i as integer Dim n as integer = array.ubound for i = 0 to n

13

Seriously, Sam, this kind of “optimization” is total overkill for any but the most time-consuming tight loops. It only makes the code harder to read, but gains nothing even close to noticable speed improvements unless you have a loop with 10000s of iterations where the elements are not objects but integers, booleans and the like, and where you also use pragmas to disable background tasks and other things that costs much more time in comparison.

It’s more important to make your code easily readable, avoid clutter like these extra lines. You may still believe that your optimization is better but it’s not good advice to the general Xojo user who has more trouble understanding which algorithms to use than worrying about minuscule speed improvements.

The only time where such advice is helpful is when it comes to invoking time-consuming subroutines for the upper bound of the for loop, for example (assuming myFolder is a FolderItem):

for i = 1 to myFolder.Count

One has to understand that a for loop gets the upper bound value anew EVERY TIME it loops (some other languages have defined that they consider the upper bound constant and only calculate it once, but REALbasic doesn’t). So, in this case, Count is called in every loop, which is indeed somewhat time consuming, especially if the accessed directory is on a server. Therefore, it’s smarter to pull the Count call out of the loop like this:

dim n as Integer = myFolder.Count for i = 1 to n

Getting an array’s Ubound value is not time consuming, however, and so it’s fairly unnecessary to remove the call from the loop.

14

I can’t wait for Geoff’s next blog parody… “Do you suffer from pre-mature optimization? LoopMax can help!”

15

It is also useful to pre-define the endpoint when using CountFields(…).

16

The programmer’s purple pill…

17

Thomas,
Mostly I deal with photo editing and want to provide the quickest possible updates, so I squeeze speed where I can. if you use RGBSurface to iterate over pixels, I have found (and I did document somewhere, think it was the old forums) that using the techniques I used saves a lot of time, I try to provide live editing (so as the user drags a slider, the image updates), so each update ideally needs to be completed with 100,000 microseconds or it’s quite jerky. Even then reaching that goal can be quite difficult, although I’m getting at it.

Not to nit-pick here, but the op was asking what was faster, so I was sharing my experience.[quote=27782:@Brad Hutchings]I can’t wait for Geoff’s next blog parody… “Do you suffer from pre-mature optimization? LoopMax can help!”[/quote]
lol!

18

Don’t mean to thread-jack, but this is interesting…

Whoa! That’s a huge bit of information that I was somehow never aware of. Putting aside the potential speed penalties, this method of counter/bounds evaluation actually has some really interesting potential. I assume that even simple variables are evaluated during each iteration of the loop so that something like the following would work:

for i = a to b 'put some code in here that modifies b on the fly next i

FWIW, this needs to be emphasized in any sort of “Switching from VB” documentation since it is exactly opposite to how Visual Studio handles loop bounds checking. I’m going to need to re-visit some of my code to see if this could be a potential source of problems…

19

To the best of my knowledge… most every language evaluates FOR/NEXT the same way…

it is the same as coding a DO/LOOP instead or a WHILE/WEND loop…

i=A
WHILE (i<=B)
'put some code in here that modifies b on the fly
b=b+1
'---------
i=i+1
WEND

20

Not VB6. For…Next loop bounds are determined at the start of the loop and don’t get evaluated again. I was always curious why stepping through a For:Next loop in RB would pass over the For statement every time, this isn’t the case when stepping through a VB6 loop. Now I know.

[code]Private Sub Command1_Click()

Dim a As Integer
Dim b As Integer
Dim i As Integer
Dim n As Integer

a = 0
b = 20

For i = a To b
n = n + 1
b = b + 1
If n > 100 Then Exit For
Next i

Call MsgBox(CStr(n))

End Sub
[/code]

In VB6 the MsgBox always displays 21. That’s a HUGE difference between the two languages.