Hi,
I have a float array with random numbers, what is the best method to find positions of elements that have the same value (the difference is within an epsilon)
Regards
Finding float elements have the same value in an array
The naive way, without modifying the array itself in any way, is to nest two loops and compare all pairs of elements of the array. Say you have an array of N elements. The outer loops with index i loops from 0 to N-2, and the inner loop with index j loops from i to N-1. The index pair i and j will cover all pairs for you to compare.
An algorithmically quicker method is to sort the array first (and preserve the original index information if you need that) and then only look for adjacent element with equal values.
Note that once you introduce an epsilon in your comparison, you may get some non-intuitive results. Your code may say that elements x and y are equal and that y and z are equal, but that x and z are not equal. The epsilon-comparison is not transitive.
An algorithmically quicker method is to sort the array first (and preserve the original index information if you need that) and then only look for adjacent element with equal values.
Note that once you introduce an epsilon in your comparison, you may get some non-intuitive results. Your code may say that elements x and y are equal and that y and z are equal, but that x and z are not equal. The epsilon-comparison is not transitive.
Hmm, I would do this in three steps, I think.
In the first step I would create an int array to store all the indexes for each value in the float array and create an exact copy of the float array(assuming you still want it to be intact and have the values not being moved around).
I would then implement some sorting algorithm(which one I decide to use depends on the amount of numbers and how important the efficiency is required to be). This algorithm will then sort from smallest to largest in my copy of the float array and at the same time swap the corresponding value in the int array I created.
When this is all done my copy of floats will store its values from smallest to largest and my int array will have the indexes of these values corresponding to their initial value in the original float array. Then I would need to check the first element in my copy and compare it to the next element. If they are not the same I would stop checking that first element since the array will be stored in order of size. If the next element isn't the same size then there are no values that are the same size as this one. I would then continue with the next element.
So TL;DR:
1. Create a float array which will be a copy of your float array to check. Also create an int array to store the indexes of the float array. This int array will simply have 1,2,3,4,5 etc. The use of the int array will come when sorting the float array.
2. Implement a sorting algorithm to sort the copy of the float array by size. Move their corresponding index value in the int array. Example: number 38.2 is on index 3. 38.2 is the lowest number generated. Move the number 38.2 to position float array[0] in your copy. Move the value 3 to position int array[0] in the int array.
3. Go through each index in your sorted array and compare it to the element next in that array. If that value is not equal then your element does not appear more than once in your array. Go to the next element, i.e element [1]. Compare it against element [2] and if they are the same, then do what ever you are supposed to do if there are more than one of an element. In the int array at position [2] the value of its corresponding index in the original float array will be listed.
Note: This is a solution on top of my head and is quite a lot of work ^^ There are probably several other efficient ways of doing this, but this is the first solution that came to mind.
In the first step I would create an int array to store all the indexes for each value in the float array and create an exact copy of the float array(assuming you still want it to be intact and have the values not being moved around).
I would then implement some sorting algorithm(which one I decide to use depends on the amount of numbers and how important the efficiency is required to be). This algorithm will then sort from smallest to largest in my copy of the float array and at the same time swap the corresponding value in the int array I created.
When this is all done my copy of floats will store its values from smallest to largest and my int array will have the indexes of these values corresponding to their initial value in the original float array. Then I would need to check the first element in my copy and compare it to the next element. If they are not the same I would stop checking that first element since the array will be stored in order of size. If the next element isn't the same size then there are no values that are the same size as this one. I would then continue with the next element.
So TL;DR:
1. Create a float array which will be a copy of your float array to check. Also create an int array to store the indexes of the float array. This int array will simply have 1,2,3,4,5 etc. The use of the int array will come when sorting the float array.
2. Implement a sorting algorithm to sort the copy of the float array by size. Move their corresponding index value in the int array. Example: number 38.2 is on index 3. 38.2 is the lowest number generated. Move the number 38.2 to position float array[0] in your copy. Move the value 3 to position int array[0] in the int array.
3. Go through each index in your sorted array and compare it to the element next in that array. If that value is not equal then your element does not appear more than once in your array. Go to the next element, i.e element [1]. Compare it against element [2] and if they are the same, then do what ever you are supposed to do if there are more than one of an element. In the int array at position [2] the value of its corresponding index in the original float array will be listed.
Note: This is a solution on top of my head and is quite a lot of work ^^ There are probably several other efficient ways of doing this, but this is the first solution that came to mind.
int x, y;
float array[ ARRAY_SIZE ];
for(x = 0; x < ARRAY_SIZE; x++)
for(y = x+1; y < ARRAY_SIZE; y++)
if(fabs(array[x] - array[y]) < EPSILON)
printf("array[%d] (%f) ~ array[%d] (%f)\n", x, array[x], y, array[y]);
for some reason the float array line wasn't showing ARRAY_ part, so I added spaces around it so it would render properly.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
