#arrays #sorting #merge #fuzzy-comparison
#массивы #сортировка #слияние #нечеткое сравнение
Вопрос:
Должен быть какой-то алгоритм, который сделает это проще, чем то, что я делаю…
У меня есть два массива, каждый с двумя столбцами. Один столбец в обоих — это временная метка, а другой в обоих — измерение.
Что должно произойти, так это превратить это в единый массив: timestamp, measurement1, measurement2
Проблема в том, что временные метки часто не совпадают точно. В одном массиве может полностью отсутствовать значение за период времени, или временные метки могут быть отключены на незначительную величину (достаточно незначительную, чтобы было нормально назначить оба измерения одной и той же временной метке).
Существует ли какой-нибудь хорошо известный способ выполнения этой операции нечеткого слияния? Простая функция общественного достояния??
Комментарии:
1. Это домашнее задание? Я не совсем понимаю правила того, как вы собираетесь создавать объединенный массив. Почему вы сохраняете оба измерения?
2. Не домашнее задание 🙂 Измерения разные, но взаимосвязанные. Представьте себе два датчика температуры в разных частях комнаты. Если бы все было идеально, они оба выполняли бы измерение и сообщали об этом в одно и то же время. Но они этого не делают. Тем не менее, я хочу показать оба на графике вместе, но использовать только одну временную шкалу.
3. Пока что я отсортировал оба массива, получаю время из массива 1 и ищу время закрытия в массиве 2. Звучит просто, но код становится уродливым (пытаясь не перебирать каждый раз весь массив2). Для этого должен быть шаблон, которого я не знаю…
Ответ №1:
Начните с того, что задайте себе следующие вопросы: имеют ли массивы одинаковое количество элементов? Как вы хотите объединить два элемента с одинаковой временной меткой? Как вы хотите объединить два элемента с разными временными метками?
Вероятно, вам придется написать алгоритм самостоятельно. Что-то подобное было бы легко реализовать:
- Начните с сортировки каждого из массивов по отдельности в порядке временных меток.
- Объявляйте два итератора в начале каждого входного массива соответственно и пустой выходной массив.
- Затем вы проверяете, какой из массивов имеет самую раннюю временную метку. Вызовите его РАНО, а другой ПОЗДНО.
- Если РАННЕЕ значение близко к ПОЗДНЕМУ (меньше некоторой константы), вы применяете операцию слияния и вставляете результат в конец выходного массива. Увеличьте оба итератора и вернитесь к 3.
- В остальном, РАНО — это далеко не ПОЗДНО. Вам нужно обработать пропущенное значение в ПОСЛЕДНЕМ массиве, возможно, повторив предыдущее значение или интерполировав его с помощью какой-либо функции. Решите, вставлять или нет значение в выходной массив. В этом случае вы только увеличиваете НАЧАЛЬНЫЙ итератор массива и возвращаетесь к 3.
- Если вы достигли конца любого из массивов, остальная часть другого массива ЗАПАЗДЫВАЕТ. Возможно, вы захотите интерпретировать это как пропущенные значения, а также повторить или интерполировать измерения.
- Возвращает выходной массив.
~
OutputArray merge(InputArrayamp; a, InputArrayamp; b) {
InputArray::iterator a_it = a.begin();
InputArray::iterator b_it = b.begin();
while(a_it != a.end() amp;amp; b_it != b.end()) {
InputArray::iteratoramp; early = *a_it.timestamp < *b_it.timestamp ? a_it : b_it;
InputArray::iteratoramp; late = *a_it.timestamp < *b_it.timestamp ? b_it : a_it;
if(*late.timestamp - *early.timestamp < TIMESTAMP_CLOSE_ENOUGH) {
output.timestamp = (*late.timestamp *early.timestamp) / 2; // mean value
output.measure1 = *a_it.measure;
output.measure2 = *b_it.measure;
outputArray.push_back(output);
a_it ; b_it ;
}
else {
output.timestamp = *early.timestamp;
output.measure1 = *a_it.timestamp < *b_it.timestamp ? *a_it.measure : outputArray.back.measure1; // previous value if missing
output.measure2 = *a_it.timestamp < *b_it.timestamp ? outputArray.back.measure2 : *b_it.measure;
outputArray.push_back(output);
early ;
}
}
InputArray::iteratoramp; late = a_it != a.end() ? a_it : b_it;
InputArray::iterator late_end = a_it != a.end() ? a.end() : b.end();
while(late != late_end) {
output.timestamp = *late.timestamp;
output.measure1 = a_it != a.end() ? *a_it.measure : outputArray.back.measure1; // previous value if missing
output.measure2 = a_it != a.end() ? outputArray.back.measure2 : *b_it.measure;
outputArray.push_back(output);
late ;
}
return outputArray;
}
Комментарии:
1. Хороший подход. Это то, до чего я пытался добраться, но ваша реализация намного понятнее моей!
2. Привет, спасибо. В следующий раз подумайте о публикации упрощенной версии вашей реализации, даже если в ней есть ошибки / она даже не компилируется. Код иногда является лучшим способом выразить себя 🙂