XPUSR
asked on
Store Array of x,y coordinate elements
I have a function that takes an x an y coordinate as parameters
void storecoords(float x, floaty)
{
float Array[][2];
}
I need to store a number of x,y coordinates in an array such that:
Array [x1 ][x2][x3][x4][x5] ...
[y1 ][y2][y3][y4][y5] ...
i.e.
As the x y coordinates are recieved by the function I need to
1) check if the coordinates are in the array.
2) if if the coordinates are do nothing.
3) if the coordinates are not in the array: add the coordinates to the array.
n.b the array must be able to grow dynamically as more and more coordinates are added?
Any suggestions appreciated?
Thanks,
void storecoords(float x, floaty)
{
float Array[][2];
}
I need to store a number of x,y coordinates in an array such that:
Array [x1 ][x2][x3][x4][x5] ...
[y1 ][y2][y3][y4][y5] ...
i.e.
As the x y coordinates are recieved by the function I need to
1) check if the coordinates are in the array.
2) if if the coordinates are do nothing.
3) if the coordinates are not in the array: add the coordinates to the array.
n.b the array must be able to grow dynamically as more and more coordinates are added?
Any suggestions appreciated?
Thanks,
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
o.k thanks,
but if i store it dynamically,
how can I seach this array (as efficient as possible(real time based app)) to find if the co-ordinate is present or not.
do i have to search through each element of the array looking for (x,y) or can this be achieved any faster?
but if i store it dynamically,
how can I seach this array (as efficient as possible(real time based app)) to find if the co-ordinate is present or not.
do i have to search through each element of the array looking for (x,y) or can this be achieved any faster?
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Hi XPUSR,
Is the data sorted? If so, you can do a binary search on it just as you would any other array. An array of 1,000,000 entries is then searched with only 20 tests.
If not, you'd have to sequentially search the array just as you would any other array.
Here's an example of using a single array to contain all of the data would add an entry.
float *MyData = NULL;
int MyDataLength = 0;
AddDataPair (float X, float Y)
{
MyData = (float *)realloc (MyData, 2*(MyDataLength+1));
MyData[MyDataLength*2] = X;
MyData[MyDataLength*2+1] = Y;
MyDataLength++;
}
Here's the same technique using separate X and Y arrays:
float *MyDataX = NULL;
float *MyDataY = NULL;
int MyDataLength = 0;
AddDataPair (float X, float Y)
{
MyDataX = (float *)realloc (MyDataX, (MyDataLength+1));
MyDataY = (float *)realloc (MyDataY, (MyDataLength+1));
MyDataX[MyDataLength] = X;
MyDataX[MyDataLength] = Y;
MyDataLength++;
}
Search functions would use any/all of these arrays in similar fashion.
Kent
Is the data sorted? If so, you can do a binary search on it just as you would any other array. An array of 1,000,000 entries is then searched with only 20 tests.
If not, you'd have to sequentially search the array just as you would any other array.
Here's an example of using a single array to contain all of the data would add an entry.
float *MyData = NULL;
int MyDataLength = 0;
AddDataPair (float X, float Y)
{
MyData = (float *)realloc (MyData, 2*(MyDataLength+1));
MyData[MyDataLength*2] = X;
MyData[MyDataLength*2+1] = Y;
MyDataLength++;
}
Here's the same technique using separate X and Y arrays:
float *MyDataX = NULL;
float *MyDataY = NULL;
int MyDataLength = 0;
AddDataPair (float X, float Y)
{
MyDataX = (float *)realloc (MyDataX, (MyDataLength+1));
MyDataY = (float *)realloc (MyDataY, (MyDataLength+1));
MyDataX[MyDataLength] = X;
MyDataX[MyDataLength] = Y;
MyDataLength++;
}
Search functions would use any/all of these arrays in similar fashion.
Kent
The speed of retrieval would depend on how u store the data.
For e.g. if the array values are stored sorted(keep storing in sorted order),checking for presence can be done using Binary search which is much faster than Linear Search.
For e.g. if the array values are stored sorted(keep storing in sorted order),checking for presence can be done using Binary search which is much faster than Linear Search.
Kent,sorry for that.
Didnt refresh the page so didnt see ur last post.
Didnt refresh the page so didnt see ur last post.
Even if the data is not sorted,
U have to take a decision as to whether the frequency of u checking for presence of co-ordinates is high enough
for u to keep the array sorted or sorting the list regularly.
U have to take a decision as to whether the frequency of u checking for presence of co-ordinates is high enough
for u to keep the array sorted or sorting the list regularly.
ASKER
hi Kdo,
I have compiled & executed your code it works somewhat but there seems to be a bug with
MyData = (float *)realloc (MyData, 2*(MyDataLength+1));
It seems that realloc is not allocation enough space. When I change it to
MyData = (float *)realloc (MyData, 2*(MyDataLength+10)); it works again,
until such time as I call the AddDataPair (float X, float Y) function more that say 6 or 7 times.
then it carshes again. But if i change it to MyData = (float *)realloc (MyData, 2*(MyDataLength+1000)); it works again,
do you understand why this is happening?
I have compiled & executed your code it works somewhat but there seems to be a bug with
MyData = (float *)realloc (MyData, 2*(MyDataLength+1));
It seems that realloc is not allocation enough space. When I change it to
MyData = (float *)realloc (MyData, 2*(MyDataLength+10)); it works again,
until such time as I call the AddDataPair (float X, float Y) function more that say 6 or 7 times.
then it carshes again. But if i change it to MyData = (float *)realloc (MyData, 2*(MyDataLength+1000)); it works again,
do you understand why this is happening?
ASKER
When realloc is called it seems to erase all previous elements in the array????
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
Working now!!
Thank Mercantilum
Thank Mercantilum
Hi XPUSR,
As soon as I read your symptom I knew what I'd left off. My apologies....
Good Catch, Mercantilum.
Kent
As soon as I read your symptom I knew what I'd left off. My apologies....
Good Catch, Mercantilum.
Kent
ASKER
Hi,
Regarding "the check if coords are in array or not"
"U have to take a decision as to whether the frequency of u checking for presence of co-ordinates is high enough
for u to keep the array sorted or sorting the list regularly."
I am going to be checking this very frequently.
I will not have many co-ordinates in the array at most 30-40 (x,y).
So what do you think is the best way to seach
maybe something like the following?
//new coordinate check if it is in the array if not add it to the array
flag inarray=false;
Xcoord=21;
Ycoord=343;
for(i=0;i<sizeof(MyData);i
{
if(MyData[i]==Xcoord)//che
{
//check if y coord is next to the x coordinate
if(MyData[i+1]==Ycoord)
{
printf("co-ordinate in array");
}
inarray=true;
}
if(inarray==false) addCoordArray(Xcoord,ycoor
}
Can I make this any faster considering I have to test is the coord in the array frequently and the fact that there is only a max of
40 coordinates?
Thanks
Regarding "the check if coords are in array or not"
"U have to take a decision as to whether the frequency of u checking for presence of co-ordinates is high enough
for u to keep the array sorted or sorting the list regularly."
I am going to be checking this very frequently.
I will not have many co-ordinates in the array at most 30-40 (x,y).
So what do you think is the best way to seach
maybe something like the following?
//new coordinate check if it is in the array if not add it to the array
flag inarray=false;
Xcoord=21;
Ycoord=343;
for(i=0;i<sizeof(MyData);i
{
if(MyData[i]==Xcoord)//che
{
//check if y coord is next to the x coordinate
if(MyData[i+1]==Ycoord)
{
printf("co-ordinate in array");
}
inarray=true;
}
if(inarray==false) addCoordArray(Xcoord,ycoor
}
Can I make this any faster considering I have to test is the coord in the array frequently and the fact that there is only a max of
40 coordinates?
Thanks
If you have only 40 maybe it's ok - or you have to think of a more complex algorithm, sorting the coords.
ASKER
Is sorting the coordinates the only method of speeding it up.
Is it woth sorting the coord given the fact that there are only 40?
Is it woth sorting the coord given the fact that there are only 40?
Hi XPUSR,
The next question is how often will you be adding or deleting coordinates.
It may be beneficial to insert new coordinates into their sorted locations.
Kent
The next question is how often will you be adding or deleting coordinates.
It may be beneficial to insert new coordinates into their sorted locations.
Kent
ASKER
"The next question is how often will you be adding or deleting coordinates"
coordinates will be added when the program is executed and after that very very rarely...
"It may be beneficial to insert new coordinates into their sorted locations."
But how will sorting them help me increace my find time?
What way do i sort them?
coordinates will be added when the program is executed and after that very very rarely...
"It may be beneficial to insert new coordinates into their sorted locations."
But how will sorting them help me increace my find time?
What way do i sort them?
Hi XPUSR,
Sort the array in ascending order. Because the data rarely changes when the program is running, the sorting/inserting algorithm doesn't need to be particularly efficient.
The bsearch() function can be used to examine the array. Because the array is so small, it might be worthwhile to write your own binary search routine that doesn't rely on the system provided algorithm. The bsearch() function has to call your comparison routine every time through the loop. If bsearch() proves too slow, writing your own (I can help with this, too) should drastically cut search times -- perhaps by as much as 50%.
Kent
Sort the array in ascending order. Because the data rarely changes when the program is running, the sorting/inserting algorithm doesn't need to be particularly efficient.
The bsearch() function can be used to examine the array. Because the array is so small, it might be worthwhile to write your own binary search routine that doesn't rely on the system provided algorithm. The bsearch() function has to call your comparison routine every time through the loop. If bsearch() proves too slow, writing your own (I can help with this, too) should drastically cut search times -- perhaps by as much as 50%.
Kent
ASKER
kent,
how could I improve on the bsearch()?
how could I improve on the bsearch()?
Hi XPUSR,
Writing your own is faster on such a small dataset.
bsearch (int Target)
{
int LowIdx;
int HighIdx;
int MidIdx;
int CompareValue;
LowIdx = 0;
HighIdx = idx-1;
MidIdx = (LowIdx + HighIdx) / 2;
while (LowIdx != HighIdx)
{
CompareValue = Target - X[idx];
if (CompareValue < 0)
HighIdx = MidIdx;
else if (CompareValue > 0)
LowIdx = MidIdx+1;
else
break;
MidIdx = (LowIdx + HighIdx) / 2;
}
return MidIdx;
}
The system released bsearch is "general purpose" so you have to provide it some help, like the comparison function.
Kent
Writing your own is faster on such a small dataset.
bsearch (int Target)
{
int LowIdx;
int HighIdx;
int MidIdx;
int CompareValue;
LowIdx = 0;
HighIdx = idx-1;
MidIdx = (LowIdx + HighIdx) / 2;
while (LowIdx != HighIdx)
{
CompareValue = Target - X[idx];
if (CompareValue < 0)
HighIdx = MidIdx;
else if (CompareValue > 0)
LowIdx = MidIdx+1;
else
break;
MidIdx = (LowIdx + HighIdx) / 2;
}
return MidIdx;
}
The system released bsearch is "general purpose" so you have to provide it some help, like the comparison function.
Kent
ASKER
thanks,
Q. what is idx?
Q. if i have only 5 coordinates in the array is it worth using the above algorithm.
Q. what is idx?
Q. if i have only 5 coordinates in the array is it worth using the above algorithm.
Hi XPUSR,
Sorry -- took the code from another application and didn't change that one variable. :) This was actually borrowed from an app that compared strings. A "true" binary search doesn't have three conditions, as this one does.
idx is th number of items in the array. If idx==1, then HighIdx becomes 0, meaning that the only item in the array is the correct one.
If you're searching a small dataset, a sequential search is just fine. You might start there, and convert to a binary search only when you think that performance is a problem.
Kent
Sorry -- took the code from another application and didn't change that one variable. :) This was actually borrowed from an app that compared strings. A "true" binary search doesn't have three conditions, as this one does.
idx is th number of items in the array. If idx==1, then HighIdx becomes 0, meaning that the only item in the array is the correct one.
If you're searching a small dataset, a sequential search is just fine. You might start there, and convert to a binary search only when you think that performance is a problem.
Kent
SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
jmcg,
What you said is absolutely correct.
None of us tried to analyze in the way you have suggested!
It is very surprising....!!
We must start thinking about this and ....:-)
May be we would have reached those points if the discussion had continued:-)
Thanks for the suggestion....
-ssnkumar
What you said is absolutely correct.
None of us tried to analyze in the way you have suggested!
It is very surprising....!!
We must start thinking about this and ....:-)
May be we would have reached those points if the discussion had continued:-)
Thanks for the suggestion....
-ssnkumar
If the array must be able to grow, you cannot define it as static data, or heap data with 'float Array[][2]'. You'll have to use malloc(), calloc(), and/or realloc() to grow the array.
It really is a piece of cake to put into effect. In fact, if you can live with a singly dimensioned array this is almost trivial, and it will certainly be "standard C". A singly dimensioned array would put the X,Y pairs into consecutive locations. For any pair (N) that is in the array, X is at location (X * 2) and Y is at (X * 2 + 1).
Kent