View previous topic :: View next topic |
Author |
Message |
TSEYFARTH
Joined: 01 Jul 2006 Posts: 1054
|
Posted: Tue Oct 13, 2015 5:09 am Post subject: How to create a Table Array in RAM and quickly perform looku |
|
|
Hello all,
Can anyone point me to some sample code that would allow very fast lookup of data that has been added to an array in RAM - creating a table in ram. There could be up to 1k rows, but this would likely change in size up and down. The index however, would not be 1 to n, but would use a two byte device address - so it is likely that there would be many *missing* rows between addresses.
Such as 1,2,10, 15, 1000, 24765,52710, etc.
I don't think looping would work well, since it would take lots of time, especially if there is a large number of rows.
Any ideas, suggestions etc would be greatly appreciated!
Thank you,
Tim
(BASCOM-AVR version : 2.0.7.9 , Latest : 2.0.7.8 ) |
|
Back to top |
|
|
AdrianJ
Joined: 16 Jan 2006 Posts: 2483 Location: Queensland
|
Posted: Tue Oct 13, 2015 6:29 am Post subject: |
|
|
You need some database theory.
One way is to create an index which is sequential, and runs in order, regardless of how your device numbers run. Use that as the array index. Depending on whether your table is static or dynamic, you might have to rebuild the index as you add more data.
Then look up how to do a binary search on an ordered list, to save steps and avoid brute force looping to do the search.
There are many other approaches, eg using linked lists, which will give far more efficient retreival than brute force searching, and at the same time make it easy to insert or remove data on the fly.
I once built a 2D version of a list like that, that allows searching a data point array for Latitude and Longitude with arbitrary gaps in both directions. Found I could do it in a fixed number of search steps, regardless of the size of the list. That used some special properties of the type of search I was doing, but meant I could increase the array size indefinitely, without increasing the search time at all.
List and array handling is all about being clever, not about being brute force fast. _________________ Adrian Jansen
Computer language is a framework for creativity |
|
Back to top |
|
|
TSEYFARTH
Joined: 01 Jul 2006 Posts: 1054
|
Posted: Tue Oct 13, 2015 6:53 am Post subject: |
|
|
Hi AdrianJ!
I could not agree more! Brute force is not the way to go, hence my post.
This looks like a good google search "binary search on an ordered list"
My array would be more than 2 dimensional, but not tremendously more - not really sure yet. This is truly the 'R' part of this project.
Have you any sample code you might share just to demo the concept of " Found I could do it in a fixed number of search steps". This would be quite helpful.
Again, thank you for your response!
Tim |
|
Back to top |
|
|
AdrianJ
Joined: 16 Jan 2006 Posts: 2483 Location: Queensland
|
Posted: Thu Oct 15, 2015 12:05 am Post subject: |
|
|
The tricks I used to keep the search time constant and independent of the size of the array only work because I had a special case. I had a large number of points ( Lat/Long coordinates ) in a data array, and a GPS continuosly getting locations in a vehicle.
Since the GPS could not move very far within the fix interval, I could always assume that at most I needed to step forward or backward one data point to get the current closest position in the array. Hence this sets the search time to at most a couple of compares and one shift of a data pointer.
This is somewhat like a dictionary, where you are asked to look up say "STOP" and then "STOVE". Rather than start the second search at the beginning "AAA", you start at the current entry "STOP" and just move forward a few entries to get to the next target.
Needless to say, you can only do this if your targets are correlated like this, so you dont need to start each search from the beginning each time.
Of course the initial search after first turn on could be much longer, but I found even a brute force search of 100,000 points took no more than 20-30 seconds, which was well within what I needed. ( think of the time needed to start a car and enter traffic ).
The data array used a doubly linked list, so each point had an index ( the actual pointer location on an SD card ) as a long, a forward link ( also a long pointer ) to the next highest latitude, and a reverse link to the next lowest latitude. ( and two more pointers for longitude ) That way, I could step forward or backward just by following up and down the links. Adding a new point is done by finding the nearest upper and lower points, and changing their links to point to the new point, that way the list stays in searchable order regardless of where the physical data is stored. Linked lists are great ! _________________ Adrian Jansen
Computer language is a framework for creativity |
|
Back to top |
|
|
AdrianJ
Joined: 16 Jan 2006 Posts: 2483 Location: Queensland
|
Posted: Thu Oct 15, 2015 7:28 am Post subject: |
|
|
Some code snippets, not enough to run as a stand-alone program, but maybe enough to give you some ideas:
Code: |
'pointers are long int to byte location in file on SD card
'*****************************************************************
Function FileAddPoint(pLat As Long , pLon As Long , pSpeed As Byte , pDir As Byte , pType As Byte) as byte
'add the new point to the linked mark file
Local lPtr As Long
Local fk As Byte
Local bHeader As Byte
Local fTemp As Long
local ltlat as long
local ltlon as long
Local errflag As Byte
Local wRadius as word
local bskipflag as byte
local bskiptest as byte
local bdir as byte
local freturn as byte
Freturn = 0 ' preset return to false
errflag = 0
'Open "LMARK.BIN" For Binary As #fn
lPtr = LOF(#fn) + 1 ' point at end of file
'#if SerialDiag = 1
'print #2,"Ptr ";lPtr
'#endif
If lPtr > 1 Then ' not a new file
'track current insertion point to get pointers
'lPtrLowLat = lPtr
If lPtrLowLat = 0 Then ' if low pointer doesnt point anywhere yet
lPtrLowLat = 1
End If
Call Track(lPtrLowLat , lPtrHighLat , pLat , 0)
#if SerialDiag = 1
print #2 , "Ptr " ; lPtr;" Lat pointer ";lPtrLowLat
#endif
If lPtrLowLat > lPtr Then
errflag = 1
End If
If lPtrHighLat > lPtr Then
errflag = 2
End If
If lPtrLowLon = 0 Then ' if low pointer doesnt point anywhere yet
lPtrLowLon = 1
End If
Call Track(lPtrLowLon , lPtrHighLon , pLon , 4)
#if SerialDiag = 1
print #2 , "Ptr " ; lPtr;" Lon pointer ";lPtrLowLon
#endif
If lPtrLowLon > lPtr Then
errflag = 3
End If
If lPtrHighLon > lPtr Then
errflag = 4
End If
else ' was a new file
lPtrLowLat = 0
lPtrHighLat = 0
lPtrLowLon = 0
lPtrHighLon = 0
End If
#if SerialDiag = 1
print #2 , "Error flag ";errflag
#endif
Select Case errflag
Case 0:
'(
I never found any error needing this in the creation process
'first check to ensure current location is not too close to existing location
'next lower lat is at lPtrLowLat
'if longitude pointers do not point to the same location, the point cant be close
btemp = 0
if lPtrLowLon = lPtrLowLat then
btemp = 1
end if
if lPTrHighLon = lPtrLowLat then
btemp = 2
end if
if lPtrLowLat = lPtrLowLon then
btemp = 3
end if
if lPtrHighLat = lPtrLowLon then
btemp = 4
end if
select case btemp
case 1:
case 2:
case 3:
case 4:
end select
')
bskipflag = 1 ' set flag, cleared if point different enough
fTemp = lPtrLowLat + 1 ' point to latitude
Get #fn, ltlat,ftemp
Get #fn,ltLon
Call Calc_DistL(ltlat,ltlon,plat,plon,ftemp,wtemp)
if ftemp > cMarkMin then ' new pos > 100 m from low
bskipflag = 0 ' dist far away, must be a different point
else
#if SerialDiag = 1
if bskipflag = 1 then
print #2,"Low Distance ";ftemp
end if
#endif
'have to check direction
ftemp = lPtrLowLat + cDirectionOffset ' direction byte
Get #fn,bdir,ftemp
bskipflag = Checkdirection(bdir,pdir) ' if direction same, returns 1
#if SerialDiag = 1
'if bskipflag = 1 then
print #2,"Directions Mark ";bdir;" Point ";pdir
'end if
#endif
end if
bskiptest = 1
fTemp = lPtrHighLat + 1 ' point to next higher latitude
Get #fn, ltlat,ftemp
Get #fn,ltLon
Call Calc_DistL(ltlat,ltlon,plat,plon,ftemp,wtemp)
if ftemp > cMarkMin then
bskiptest = 0
else
#if SerialDiag = 1
if bskiptest = 1 then
print #2,"High Distance ";ftemp
end if
#endif
'have to check direction
ftemp = lPtrhighLat + cDirectionOffset ' direction byte
Get #fn,bdir,ftemp
bskiptest = Checkdirection(bdir,pdir) ' if direction same, returns 1
#if SerialDiag = 1
'if bskiptest = 1 then
print #2,"Directions mark ";bdir;" Point ";pdir
'end if
#endif
end if
bskipflag = bskipflag or bskiptest ' either point was too close, and same dir
#if SerialDiag = 1
print #2 , "Skipflag ";bskipflag
#endif
if bskipflag = 0 then ' skip flag was not set, so point is different
bHeader = cSpeedHeader
wRadius = eZoneRadius(pType) ' get default zone radius
#if SerialDiag = 1
print #2 , "Writing new Mark ";lPtr
#endif
Put #fn , bHeader , lPtr
Put #fn , pLat ' insert new lat
Put #fn , pLon ' and lon
'write pointers
Put #fn , lPtrLowLat
Put #fn , lPtrLowLon
Put #fn , lPtrHighLat
Put #fn , lPtrHighLon
'write the rest of the data
put #fn, pType
Put #fn , pSpeed
Put #fn , pDir
Put #fn , wRadius
Call SetTimes(pType )
'For fk = 1 To 6
' Put #fn , bTime(fk)
'Next fk
'now adjust the pointers for the tracked hi and lo points to point to
'the new inserted point
If lPtrHighLat > 0 Then
fTemp = lPtrHighLat + cLowLatOffset ' 9 ' pointer to parent
Put #fn , lPtr , fTemp
End If
If lPtrHighLon > 0 Then
fTemp = lPtrHighLon + cLowLonOffset ' 13
Put #fn , lPtr , fTemp
End If
If lPtrLowLat > 0 Then
fTemp = lPtrLowLat + cHighLatOffset ' 17 ' pointer to child
Put #fn , lPtr , fTemp
End If
If lPtrLowLon > 0 Then
fTemp = lPtrLowLon + cHighLonOffset ' 21
Put #fn , lPtr , fTemp
End If
#if SerialDiag = 1
print #2,"Pos ";pLat;" ";pLon;" Ptr ";lPtrLowLat;" ";lPtrLowLon
#endif
Freturn = 1 ' set return value to true
end if
' end if
Case 1:
strHold = "Low lat pointer error"
Case 2:
strHold = "High lat pointer error"
Case 3:
strHold = "Low lon pointer error"
Case 4:
strHold = "High lon pointer error"
End Select
#if serialdiag = 1
If errflag > 0 Then
print #2 , strHold
End If
#endif
flush #fn ' flush buffer to update card
'else we might lose points if unit turned off
#if serialdiag = 1
lptr = lof(#fn)
print #2,"New file end";lptr
#endif
FileAddPoint = freturn 'assign return value
End Function
Sub Track(pLow As Long , pHigh As Long , pCurrPos As Long , poffset As byte)
'this the the search function, but I call it Track
'because it relies on having the entry index set to the last
'point 1 lower than the last current location
'this is because we only move a small distance from the last
'point, so at most we only have to move 1 point either way
'from where we were last time.
'Track returns the current indexes, changed if necessary
'pLow = null if we are before the lowest point in the list
'pHigh = null if we are after the last
'one nice thing about doubly linked lists is that you can check
'the forward and backward links for consistency.
'a parent points to a child, and that child must point back
'to the parent.
'As well, the child must be smaller than the parent in value.
'this version for files, not sheets
Local iTest As Long
Local lTest As Long
Local lPos As Long
Local lDist1 As Long
Local lDist2 As Long
Local fTemp As Long
local bTempT as byte
Do
bTempT = TestPoint(pLow , pCurrPos , poffset)
If bTempT = 1 Then
'we are higher than current value
'so we need to test whether we are also above the next higher point
'iTest = Me.Cells(pLow + rowOffset, 8 + 2 * ioffset) 'get pointer to parent
fTemp = pOffset + 17
fTemp = fTemp + pLow
' fTemp = fTemp + 17 ' point to high pointer of either lat or lon
iTest = 0
' if ftemp < 1 or ftemp > lMarkPtrMax then
' print #si,"Pointer error ";ftemp;" Max ";lMarkPtrMax
' end if
Get #fn , iTest , fTemp
#if SerialDiag = 4 ' @@ diag
print #2 , "Track " ; pLow ; " " ; iTest ; " Lat " ; lCurrlat ; " Pos " ; pCurrPos ; " " ; fTemp
#endif
pHigh = iTest
#if SerialDiag = 4 ' @@ diag
print #2 , "Track above ";pHigh;" at ";fTemp
#endif
If iTest = 0 Then
Exit Do ' we are above highest
End If
bTempT = TestPoint(iTest , pCurrPos , poffset)
If bTempT = 1 Then
'we are higher than this value too
'so we can set iCurr up to this one
pLow = iTest
Else
'we are lower than this higher one, so we are between points
#if SerialDiag = 4 ' @@ diag
print #2 , "Track between"
#endif
Exit Do
End If
Else
'we are lower
'so set point current at next lower
pHigh = pLow ' set high pointer to current
'pLow = Me.Cells(pLow + rowOffset, 7 + 2 * ioffset) 'pointer to child
fTemp = pOffset + 9
fTemp = pLow + fTemp
' fTemp = fTemp + 9
'could just do fTemp = fTemp - 8 'from fTemp above
pLow = 0
' if ftemp < 1 or ftemp > lMarkPtrMax then
' print #2,"Pointer error ";ftemp;" Max ";lMarkPtrMax
' end if
Get #fn , pLow , fTemp
#if SerialDiag = 4 ' @@ diag
print #2 , "Track below ";pLow;" at ";fTemp
#endif
If pLow = 0 Then
Exit Do ' we are below lowest
End If
End If
Loop
End Sub
Function TestPoint(pTestPtr As Long , pCurrPos As Long , poffset As byte) As Byte
'test whether the current position is larger than the position
'pointed to by the pTestPtr index
'Pointer points to start of record, lat is at start + 1
'lon is at start + 5
'return true(1) if is, else false (0)
'iOffset sets whether we test lat(0) or lon(1)
'this version for files, not sheets
'iTest points to the file location of the header for the current record
local lTestPos As Long
Local lTempPtr As Long
Local lPtr2 as long
local freturn as byte
lTempPtr = pOffset + 1
'incr lTempPtr
lTempPtr = lTempPtr + pTestPtr
'lPtr2 = pTestPtr
'lTempPtr = lTempPtr + lPtr2
'lTempPtr = pTestPtr + 1 + 4 * ioffset 'point to either lat or lon
lTestPos = 0
'if lTempPtr < 1 or lTempPtr > lMarkPtrMax then
' print #2,"Test pointer error ";lTempPtr;" Max ";lMarkPtrMax
'end if
Get #fn , lTestPos , lTempPtr
'lTest = Me.Cells(iTest + rowOffset, 5 + ioffset) 'get value from index
If pCurrPos > lTestPos Then
freturn = 1
else
freturn = 0 ' NB MUST do this explicitly
End If
TestPoint = freturn
End Function
|
Data file format:
'Header, Type , Direction , Lat , Lon , Limit,
time , allow 6 possible start / end times
Header - 1 byte
Lat - 4 byte long degrees * 1e7
Lon - 4 byte long degrees * 1e7
Low Lat pointer - to next lowest Lat
Low Lon pointer - to next lowest Lon
High Lat pointer - to next highest lat
High Lon pointer - to next highest Lon
Typ_e - 1 byte limit type
Speed - 1 byte
Dir - 1 byte set to 255 if not direction sensitive(normal possible values 0 -178 )
Radius - word in metres
Time - 6 bytes start , end times in 10 min units
Record is now 36 bytes incl 1 header _________________ Adrian Jansen
Computer language is a framework for creativity |
|
Back to top |
|
|
TSEYFARTH
Joined: 01 Jul 2006 Posts: 1054
|
Posted: Thu Oct 15, 2015 5:39 pm Post subject: |
|
|
Hi Adrian,
Thanks for posting this. I was not looking for a complete program, just some sample code to see how others do it.
I will have a look in a little while and advise.
Thank you for sharing!
Tim |
|
Back to top |
|
|
|
|
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum You cannot attach files in this forum You cannot download files in this forum
|
|