Array Optimization

[Ricardo Furtado]

I've made a VB .Net application that use arrays, a lot. I'm optimizing my
application for speed because it is very slow, specially in the areas where
arrays are massively used.
I've searched in google and books and i found technics to speed up array
search but none of them referenced multi-dimensional arrays, so the question
i've been making for months remains:
How can i speed up multi-dimensional array search?
As an example i have the event listed bellow that is inserted in one of the
code areas where the windows task manager blows of scale and the cpu usage
reaches 100% and my application hangs for while (enough time for the
picturebox to present a red cross instead of the image)
Can You help?


Private Sub registerPointsInLstPoints(ByVal strPoint As String) Handles
MainDrawPics.registerPoints
Dim bolContinue As Boolean = True
Dim intCounter As Integer
Dim bolFound As Boolean = False

For intCounter = 0 To lstPoints.Items.Count() - 1
If lstPoints.GetItemText(lstPoints.Items().Item(intCounter)) =
strPoints Then
lstPoints.SetItemChecked(intCounter, True)
bolFound = True
Exit For
End If
Next
If Not bolFound Then
lstPoints.Items.Add(strPoints, True)
End If
End Sub


My thanks in Advanced

Ricardo Furtado

 

[Armin Zingler]

I've made a VB .Net application that use arrays, a lot. I'm
optimizing my application for speed because it is very slow,
specially in the areas where arrays are massively used.
I've searched in google and books and i found technics to speed up
array search but none of them referenced multi-dimensional arrays,
so the question i've been making for months remains:
How can i speed up multi-dimensional array search?
As an example i have the event listed bellow that is inserted in one
of the code areas where the windows task manager blows of scale and
the cpu usage reaches 100% and my application hangs for while
(enough time for the picturebox to present a red cross instead of
the image)
Can You help?


Private Sub registerPointsInLstPoints(ByVal strPoint As String)
Handles MainDrawPics.registerPoints
Dim bolContinue As Boolean = True
Dim intCounter As Integer
Dim bolFound As Boolean = False

For intCounter = 0 To lstPoints.Items.Count() - 1
If lstPoints.GetItemText(lstPoints.Items().Item(intCounter)) =
strPoints Then
lstPoints.SetItemChecked(intCounter, True)
bolFound = True
Exit For
End If
Next
If Not bolFound Then
lstPoints.Items.Add(strPoints, True)
End If
End Sub

I guess lstPoints is a CheckedListbox?

First, I'd simplify
lstPoints.Items().Item(intCounter)
to
lstPoints.Items(intCounter)
Though, doesn't change the performance.

Second, why is the arg named "strPoint" and the variable used inside is
"strPoints"? Typo in this post?

And, you shouldn't search the items in the control. Instead, search the
array/collection/list/whatever that contains the data that is displayed
in the control. Seperate data layer from presentation layer. Retrieving
the item's text from the control is slower.

In order to find the Index by a String, you could fill a dictionary
using the Text and the Index in the list as the Key and the value.
(System.Collections.Generic.Dictionary(Of TKey, TValue) for example)

In addition, I don't see a multi-dimensional array in your code. Only
the one-dimensional Items property which returns a kind of collection.


Armin

 

[Ricardo Furtado]

First of all, thank you for your answer

I've copy the wrong code, i'm sorry. What i meant was:

Public Function returnPoint(ByVal x As Integer, ByVal y As Integer) As String
Dim strReturn As String = ""
Dim intCounter As Integer

For intCounter = 0 To UBound(ArrayPontos) - 1

If (ArrayPontos(intCounter).lngValueY = y) AndAlso
(ArrayPontos(intCounter).lngValueX = x) Then
strReturn = ArrayPontos(intCounter).strPointName
End If
Next

Return strReturn
End Function


The code looks nothing important in terms of cpu usage, the problem is that
the software (a cephalometric analysis application where i need to draw
point, lines and images uppon images on a picturebox) is allways checking the
arrays everytime the mouse moves or clicks,... because it needs to know the
name of the points or if the mouse is uppon a line, in order to drag
lines,... these functions/procedures running almost at the same time, make
the application slow,... so there's the need to optimize arrays

Thank you

Ricardo Furtado

 

[Armin Zingler]

First of all, thank you for your answer

I've copy the wrong code, i'm sorry. What i meant was:

Public Function returnPoint(ByVal x As Integer, ByVal y As Integer)
As String Dim strReturn As String = ""
Dim intCounter As Integer

For intCounter = 0 To UBound(ArrayPontos) - 1

If (ArrayPontos(intCounter).lngValueY = y) AndAlso
(ArrayPontos(intCounter).lngValueX = x) Then
strReturn = ArrayPontos(intCounter).strPointName

Can you exit the loop here if the first point is found? If not, you're
always getting the last point, but then you should search from the end
to the start and exit at the first hit.

What's the type of an item in ArrayPontos? Is it a Structure or a class?
If it's a Structure, you should get the Item only once:

dim Point as YourType=ArrayPontos(intCounter)
If (point.lngValueY = y) AndAlso (point.lngValueX = x) Then
...

This avoids copying the object two times.

End If
Next

Return strReturn
End Function


The code looks nothing important in terms of cpu usage, the problem
is that the software (a cephalometric analysis application where i
need to draw point, lines and images uppon images on a picturebox)
is allways checking the arrays everytime the mouse moves or
clicks,... because it needs to know the name of the points or if the
mouse is uppon a line, in order to drag lines,... these
functions/procedures running almost at the same time, make the
application slow,... so there's the need to optimize arrays

How many points can there be in the array? Have you already measured the
time for the loop?

With a huge number of points, you could go several ways. The best
solution depends on the number of points, the max index and so on.

For example, you could build a kind of tree. It's like splitting a 2D
area into rectangular parts. The parts are the nodes of the tree. Each
part is splitting the superior part again into smaller parts (which are
splitted again.. and so on).
Imagine you have some bookshelves (cabinets) containing thousands of
books and you want to find a certain book by it's title. The bookshelves
are labeled A-F, G-M, N-S, T-Z. You can quickly narrow the search down
to a certain cabinet. Each cabinet is split into shelves also labeled
A-F etc. You can narrow the search further down. And so on; you get the
point.

Another solution is putting your Points into a Dictionary (or one of the
many classes in the Framework that I don't know by heart anymore). I
don't know how the Dictionary is implemented internally, maybe
tree-like, too. Use the X coordinate as the key and another dictionary
as the value. The latter dictionary uses the y coordinate as the key
and a List(Of YourPoint) as the value. The List contains all points at
that location. Or directly reference the point if there can only be one
point at a distinct coordinate.

Or, probably most memory intensive (eg 2560x1280x8 (64-bit OS) consume
~26 MB; decide on your own if it's worth), use a 2D array with a fixed
size. Each item references the Point (or, with > 1 point at a location,
references a list of points (only if it contains items; otherwise is
Nothing)).

Or, use an array of arrays (or List(Of)), using the x coordinate to
search the main array and the y coordinate in the sub ordinate array.

Or.... (maybe I've forgotten the simplest solution ;-) )


Armin

 

[Phill W.]

I've made a VB .Net application that use arrays, a lot. I'm optimizing my
application for speed because it is very slow, specially in the areas where
arrays are massively used.

"Used" /how/?

Arrays are really good for accessing elements directly by index; they're
rubbish for [serial] searching or "keyed" look-ups.

I've searched in google and books and i found technics to speed up array
search but none of them referenced multi-dimensional arrays, so the question
i've been making for months remains:
How can i speed up multi-dimensional array search?

Multi-dimensional arrays are even /better/ at direct access by
[multiple] indexes, but even /worse/ and any other sort of lookup.

As an example ...

For intCounter = 0 To lstPoints.Items.Count() - 1
If lstPoints.GetItemText(lstPoints.Items().Item(intCounter)) =
strPoints Then
lstPoints.SetItemChecked(intCounter, True)

Oh look! A keyed look-up.
An Array is definitely /not/ the thing to use.

You don't say which version of Visual Basic you're using but, if you had
VB'2005, you could something like:

Dim list as New Dictionary<String,Thing>()

' lots of
list.Add( key, Thing )

.... then ...

Private Sub registerPointsInLstPoints( _
ByVal strPoint As String _
) Handles MainDrawPics.registerPoints
' Strange event declaration, but anyway ...

Dim item as Thing = Nothing
If ( Not list.ContainsKey( strPoints ) ) Then
item = New Thing
list.Add( strPoints, item )
else
item = list( strPoints )
End If

item.SetItemChecked( True )

End Sub

(If you're not using '2005 yet, you /can/ do the same with a Hashtable
and a bit of "down-casting" to get at each item).

HTH,
Phill W.