Алгоритм для выравнивания данных массивов с плавающей точкой в ​​Java

Question

У меня есть два массива с плавающей точкой, представляющих значения y на линейном графике. Теперь я хочу совместить эти две диаграммы. Существуют ли алгоритмы для выравнивания двух массивов?

Очень простой пример

a:
2.5 1.3 1.6 4.2 3.6

b:
3.3 1.4 2.5 1.3 1.6

Теперь после выравнивания должно быть:

        2.5 1.3 1.6 4.2 3.6
3.3 1.4 2.5 1.3 1.6

На самом деле все гораздо сложнее, когда каждый массив имеет размер около 30 000 и плавает как -6,94709206

Answer 1

В принципе, это просто:

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 ...

При использовании чисел с плавающей точкой у вас может возникнуть проблема, заключающаяся в том, что они не обязательно должны быть точно равными, чтобы считаться совпадением, если в ваших данных есть вероятность неточности. Вместо a [an] == b [bn] вы можете сказать abs (a [an] -b [bn])

Отказ от ответственности: Код находится на моей голове и не проверен. Нет гарантий, выраженных или подразумеваемых. Ваш пробег может варьироваться. Пустота там, где это запрещено. Если появляется сыпь, обратитесь к врачу.

Answer 2

Предполагая, что оба массива совпадают в определенной части.

1. Используйте бинарный поиск, чтобы найти положение первого элемента a внутри b
2. Если такой позиции не существует, найдите позицию первого элемента b внутри a
3. Если все еще нет совпадения, поставьте a позади b, если first a> last b - b позади a в противном случае

Answer 3

Это в основном нормальное сопоставление с образцом, вы должны быть в состоянии использовать самые простые алгоритмы, подходящие и для сопоставления символов.

Наихудшим случаем для простого поиска обычно будет n * m (при условии, что n и m - длина ваших последовательностей с плавающей запятой), возможно, вы можете сократить время выполнения, используя алгоритм, аналогичный Boyer-Moore быть линейным, если одна из последовательностей остается неизменной.