Array sort - to find "top ten"

[refsmmat]

Hi,

I have an application that identifies the "general region" based on a post code / zip code list.

I am looking to identify the ten closest regions to the phone's current position. To do this,

As a one-off, the distance from 'current position' to all post offices is determined.

I am searching this distance list ten times. Each time this search is done, the minimum is set from the previous search.

This works, but I don't think it is the best way by far.

Can anyone suggest an alternative way? I am happy with a suggestion of a function or sort method that would be more efficient. The list size at the moment is 16000 roughly.


Thanks & Best wishes,

refsmmat

   For k =0 To rows-1 
distarray(k) = Sqrt(Power((MyArray(k, 1) - Latitude),2) + Power((MyArray(k, 2) - Longitude),2) ) * 111120
   Next



   For i=0 To (lstsize - 2)
         dist2 =  10000000

         For k =0 To rows-1   
      
         If (distarray(k) < dist2) AND (distarray(k) > minima(i))  Then 
   
         dist2 = distarray(k)
         
         goodindex(i) = k
                  
         End If 
      
         Next
         minima(i+1) = dist2
         distance(i) = dist2 
         ListView1.AddSingleLine(MyArray(goodindex(i), 0) & " " & distance(i) & "m")   
            
   Next

 

[Erel]

You can add the items to the list and sort the list (descending). You should then take the 10 first items.

This is not the quickest possible solution. You should test it and see if it works quick enough.

 

[kickaha]

This may work.

Put the first ten distances in a list (I will call it results), then sort results - sort it descending so the largest value is in results.Get(0).

loop through the rest of the distances -

when the distance is smaller than results.Get(0):
results.RemoveAt(0)
results.Add (distance)
results.Sort (False)

This means you only go through your distances once.

 

[refsmmat]

Thanks Erel & Kickaha,

I am trying the list sort at the moment.

Kickaha - its an interesting idea for a solution.

i will try both out & report back.

Best wishes

refsmmat

 

[refsmmat]

Sorry to impose - I may need some further advice.

The purpose of the sort was to find the closest point, but maintain its index in the original list. A list sort of the distance values can't mantian the original index.
The reason i need this, as the distance value from

 distarray(k) = Sqrt(Power((MyArray(k, 1) - Latitude),2) + Power((MyArray(k, 2) - Longitude),2) ) * 111120)

maintained the index of the location/site names.


I have used a list to sort the top ten, but at this point I have to take the top ten values and find them individually to re-establish the original list index - in order to grab the site name.

having said that the list sort was very fast & the code is much better now - despite the slightly clunky way of reestablishing the index.

Is there an alternative sort function that can be used to preserve the original index?

Thanks,

refsmmat

 

[kickaha]

You could define a type:

Type DistDetail(Distance As Long, Index As Int)

Then in your loop:

Dim Detail As DistDetail
Detail.Distance = Sqrt(Power((MyArray(k, 1) - Latitude),2) + Power((MyArray(k, 2) - Longitude),2) ) 111120)
Detail.Index =k
distarray(k)=Detail

Then you can use SortType on the distance field, so you can always find the index of any distance.

 

[bluejay]

There is no logical reason to store more than 10 distances.

As you calculate each distance:
If number of items in distance list is less than 10 or new distance is less than last item in distance list
then Do Insertion Sort into distance list
else ignore new distance

Most of the 160,000 distances will get ignored and you only deal with each distance once.

Bluejay

 

[refsmmat]

Thanks Kickaha,
"defining a type" = a structure? Sorry - I learnt programming using MATLAB.

Using your suggestion will work & fits nicely with the code I have so far. I know I was asking for an index value, but really I only need the index to refernece the town names in the reference array.

The reference array is lat, long, town name for each row.

Hi Bluejay,

Thanks for the suggestion. originally I wasn't storing all of the distances but I ran into problems in other ways. Im still on the way to the best solution.
I haven't heard of an insertion sort - it sounds like a good idea.

I will post the search code when I get it finished (I will need a few days).

Best wishes,

refsmmat

 

[refsmmat]

list sort solution

Apologies,

I meant to reply to this sooner.
I tried a lot of the more appropriate list sort algorithms, but each had their own drawbacks - primarily execution time (as the postcode list is quite large).

I came up with a good solution. It is not pretty, but it works very well.

1. Do a first pass search (based on initial lat/long) to identify array elements within "N" kilometres. Transpose these to a new array. If "N" is too small (I.E. a rural area where there are no towns/post offices within "N" kilometres, "N" is grown until at least 50 or so towns are identified.

2. Perform the sort operation on the new (much shorter) array. I used a less efficient sort technique that maintained my indexing - the efficiency didn't matter as the list size is smaller.

3. As the device moves away from the point outlined in 1. we perform a resort (rerun step 1) once the device moves more than "M" kilometres away from the origin. When this is done, the lat/long where the resort is performed
becomes the new origin.

Not exactly elegant, but it works nicely.
Thanks again for all of your advice.
Regards,


refsmmat