Algorithm for data alignment of float arrays in Java
I have two float arrays representing y values in a line chart. Now I want to align these two diagrams. Are there existing algorithms for aligning two arrays?
A very simple example
a:
2.5 1.3 1.6 4.2 3.6
b:
3.3 1.4 2.5 1.3 1.6
Now after aligning it should be:
2.5 1.3 1.6 4.2 3.6
3.3 1.4 2.5 1.3 1.6
In reality it is much more complicated with each array being about 30,000 in size and floating as -6.94709206
a source to share
Basically it's easy:
for (an=0;an<a.length;++an)
{
for (bn=0;bn<b.length;++bn)
{
if (a[an]==b[bn])
{
boolean run=true;
for (offset=1;offset<a.length-an && offset<b.length-bn;++offset)
{
if (a[an+offset]!=b[bn+offset])
{
run=false;
break;
}
}
if (run)
... match at a[an], etc matching b[bn], etc
}
}
}
... no match ...
With floats, you will have the problem that they may not need to be exactly equal if considered a match, if there is any possibility of inaccuracy in your data. Instead of [an] == b [bn] you can say abs (a [an] -b [bn]) <errorMargin or some such.
Disclaimer: The code is off my head and untested. No warranties, expressed or implied. Your mileage may vary. Emptiness where prohibited. If a rash develops, check with your doctor.
a source to share
This is a common pattern match, you should use most of the simple algorithms that match characters.
The worst case for a simple search would usually be n * m (assuming n and m are the length of your floating point sequences), perhaps you can shorten the execution time using an algorithm similar to Boyer-Moore towards linearity if one of the sequences remains unchanged.
a source to share