Алгоритм "коррекции"

[Staub_37]

Здрасте, Господа!

я программирую год и впервые столкнулся с таким алгоритмом с которым, наверняка, сталивались многие. прошу Вашей помощи. Итак..

Пусть есть массив значений типа float, и всем его элементам присвоены значения.
Массив заполнен заранннее, однако не все элементы отвечают требованиям.
Массив должен быть заполнен по возрастанию ПОЛОЖИТЕЛЬНЫМИ элементами.
однако среди элементов массива есть те, значения которых равны 0, отрицательные или меньше предыдущих (болшше следующих).

Понимаю что написал непонятно, но как смог. вот пример:

допустим есть массив, значениями элементов которого является время ( в секундах). и его элементы имеют значения:
(массив заполнен раннее, необходимо произвести "корректировку" значений)

Для еще большей определенности-пусть значения элементов массива кол*цензура*тся в пределе от 0.0000 до 15.9999. Любые значения больше чем максимум (т.е. 15.9999) считать невенрыми
(Но это только для определенности, реально диапазон значений в программе никак не задан-просто "видно на глаз", в соотсетсвии со знанием задачи)

float pTime[5];

pTime[0] = 12.45;
pTime[1] = 0;
pTime[2] = -1;
pTime[3] = 13.45;
pTime[4] = 13322331.455668843;

Надо:
откорректировать значения массива, согласно требованиям:
1) первый элемент массива (с индексом 0) НЕ ОБЯЗАН быть равным 0, но не может быть отрицательным.
2) любой элемент массива должен иметь ТОЛЬКО ПОЛОЖИТЕЛЬНОЕ значение, отличное от 0 (если это только не pTime[0], т.е. начальный элемент массива).
3) каждый элемент массива должен быть больше предыдущего и меньше следующего, т.е.

pTime[i-1]<pTime<pTime[i+1]

P/S: Наверное, легко. как смог сформулировал. но для меня много подводных камней.. хотябы такой вариант:

[0] = 12.33
[1]=15555.2333
[2]=16666.222
[3]=14.33;

здесь правильно элемент [0] и элемент [3], но стандартными маневреами не подойдешь:

[0] < [1] <[2] => [1] элемент имеет верное значение (напоминаю, что на ПРАКТИКЕ в работающей программе ДИАПАЗОН ЗНАЧЕНИЙ НЕ ОГРАНИЧЕН НИКАК, т.е. я только по совокупности значений всех элементов массива могу понять какой диапазон значений приемлем).

[3] < [2], но 2й > [1].

Как тут анализировать? смотреть на несколько (на 2-3) элементов вперед?

подскажите пожалуйста или может ссылки на ресурсы подскажете...
зараннее благодарен!

 

[????]

простой способ: удаление значений выходящих за пределы, сортировка массива по ворастанию.

 

[grigsoft]

Главный вопрос - что должно получиться в результате? Вот приведи как должны быть преобразованы оба твоих тестовых массива, там будем смотреть.

 

[Staub_37]

Для определенности. возмем как раньше предел значений - от 0.0000 до 15.9999. Любые значения больше чем максимум (т.е. 15.9999) считать невенрыми
(Но это только для определенности, реально диапазон значений в программе никак не задан-просто "видно на глаз", в соотсетсвии со знанием задачи)

Пример 1:

Исходный массив :

float pTime[5];

pTime[0] = 12.45;
pTime[1] = 0;
pTime[2] = -1;
pTime[3] = 13.45;
pTime[4] = 13322331.455668843;

Примерный результат (преоьразованный массив):

pTime[0] = 12.45;
pTime[1] = 13.00;
pTime[2] = 13.37;
pTime[3] = 13.45;
pTime[4] = 14.21;

Пример 2:

Исходный массив:

float pTime[5];

pTime[0] = 12.33
pTime[1]=15555.2333
pTime[2]=16666.222
pTime[3]=14.33;
pTime[4]=14.43;

Примерный результат:

pTime[0] = 12.33
pTime[1]=13.48
pTime[2]=13.59
pTime[3]=14.33;
pTime[4]=14.43;

Пример 3:

Исходный массив:

float pTime[5];

pTime[0] = 0.00
pTime[1]=11111111.2333
pTime[2]=13.22
pTime[3]=14.33;
pTime[4]=14.43;

Примерный результат:

pTime[0] = 11.00
pTime[1]=12.11
pTime[2]=13.22
pTime[3]=14.33;
pTime[4]=14.43;

P.S: ессесено во весх примерах в конце числа в итоговом массиве я писал ПРОИЗВОЛЬНО, для того чтобы объяснить логику.

конечным автоматом вроде как не получаеися, пробовал посчитать знак производной-тоже потом в дебри ухзодишь, когда начинаешь выяснять какой элемент неверный, особенно если их подряд несколько. а искать минимальный и максимальный не поможет, ведь может быть и такой вариант к примеру:

Исходный массив:

// Диапазон значений от 140 до 180 с
float pTime[5];

pTime[0] = 11.30
pTime[1]=141.23
pTime[2]=143.22
pTime[3]=144.33;
pTime[4]=144.43;

В данном случае минимальное положительное значение 11.30, но оно неверно. еще раз напомню - на практике программно дипазон никак не ограничен.

 

[grigsoft]

Во, это уже интересно. Я так понимаю что задача делится на 2:
1. Выделить из массива "правильные" значения
2. Откорректировать остальные.

С №2 все просто - прямая по 2м точкам и точки на ней. А вот №1 - это сложнее. И при большом числе точек и неизвестном распределении неверных значений - видимо, нетривиальная. В теории - это максимальный путь в направленном графе, ребра которого либо вычисляются на ходу (много времени) либо строятся до обсчета (много памяти). Если известно что сбойных значений не больше пары %, то имеет смысл накромсать массив на куски и решать задачу на частях - будет быстрее.


Кстати - построение графика процесса с учетом сбойных показаний приборов - задача известная, и наверняка в сети должны быть интересные решения.

 

[grigsoft]

Впрочем, с утра на свежую голову видно, что с прямой я погорячился Тупо разделить отрезок между двумя элементами массива на несколько частей - и все.

 

[Staub_37]

вы подали интересную мысль насчет деления на части! возможно стоит подсчитать число элементов массива, разделить весь массив условно на n-частей (10 к примеру), и потом для каждолго куска найти минимальный и максимальный элемент.
дальше задать какуюнибудь погрешность dt (точнее ее величину) и счетчик (понадобится далее).и сравнить минимальные и максимальные элементы с соответсвующими элементами других частей. и если разница между соответствующими элементами <=dt, то увеличить значение счетчика. если значение счетчика >n/2, тогда считать элемент минимальным (максимальным) в диапазоне верных значений.

как по вашему, правильное направление?
а про задачу вот сел искать, и сейчас про графы еще читаю! спасибо за подсказку!!=)

кстати, на практике размерность массива не превышает 1000 элементов. такова спецификация задачи.

 

[grigsoft]

Реальные пределы допустимых значений все же есть, или нет?
Вопрос - могут ли быть в массиве значения в допустимых пределах, но не правильные? Если не могут, то все просто - тупо обнулить все что вне пределов и все. Если все неправильные числа сильно отличаются от правильных, то можно, видимо, мат.статистику призвать - посчитать какое-нибудь средне-квадратичное отклонение и т.п. Они умеют явно неправильные значения отбрасывать. Мой сложный случай с путем в графе имеет смысл считать только если возможна такая комбинация:
1, 10, 11, 12, 2, 14, 3, 4, 18.
Разобраться какой из рядов здесь правильный - никакая статистика не поможет.
Минимум\максимум считать бесполезно, на мой взгляд.

Кроме того, совсем без характеристик кривой отбрасывать значения будет некорректно. Возьми твой ряд:
1, 2, 3, 120.
120 тут не верно? А если это график типа тангенса?

 

[Staub_37]

1) сейчас чуть ниже объясню суть задачи, может тогда будет чуток яснее.
2) в парвильном диапазое неверными значениями считаются только те которые меньше предыдущих (больше следующих), т.е. ((pTime>pTime[i+1]) || (pTime < pTime[i-1]))

ну если примерно объянисть смысл задачи-то выгдяит примерно так.
представьте, что есть "система" из нескольких компонентов (аппаратно). один из этих компонентов отвечает за опрос и сбор параметров системы , для вывода результатов на печать. данный компонент включается при включении всей системы в целом .
компонент производит предстартовый опрос готовности, вносит запись в лог. но до выключения системы-он не выключается. известно только, что стартовый опрос должен производиться, к ПРИМЕРУ, начиная от 5 до 25с, с момента подачи питания на компонент. конкрентно СТАРТОВЫЙ ОПРОС можно оследить, т.к. имеется признак, и точно известен временной интревал.

а вот далле, опрос параметров во время работы системы производитсчя только в определенные моменты. наступление этих моментов характеризуется не временем, а скажем установкой какогото параметра (выставляется другим аппаратным комопнентом).
в итоге.

включили систему, включился компонент->стартовый опрос готовности (вывод информации в лог)-> при установки необходимого параметра , происходит опрос параметров системы (при этом, тк "измеритель" не выключался, то время от подачи питания). а установка признака определяется конкретной задачей.

вот утрированый пример:

// Опрос показаний:

Номер Время опроса Признак
1 5.007 S // S - признак стартового опроса
2 14.00 S
3 19.97 S
4 24.99 S
5 235.65 1 // 1- признак 1 опроса после стартового
6 236.25 1
7 237.81 1
8 13.91 1
9 65555555.333 1
10 238.123 1
11 1455.23 2 // 2- признак 2 опроса после стартового
12 1479.33 2
13 1500.588 2

Как видно из "лоа", неверные только 8 и 9 элементы. а начиная с 11-го производится 2-ой опрос после старта, и эти показания времени тоже считаются нормальными.

ессесно ко всему этому применимо холотое правило-т.к. с момента подачи питания на систему компонент не выключается, время всегда увеличивается

 

[grigsoft]

А есть гарантия что первые показания в серии - правильные? Тогда можно считать их минимом и максимумом.
И откуда все-таки берутся кривые значения, вроде 65555555.333. Какова вероятность их появления? Если нарезать массив на куски из 50(например) значений, может в одном куске оказаться большинство ложных?

 

[Staub_37]

если вы имеете ввиду сатртовый опрос, то практически всегда он верный.да, его время допустим можно взять за минимум, но тогда :

Номер Время опроса Признак
1 5.007 S // S - признак стартового опроса
2 14.00 S
3 19.97 S
4 24.99 S
5 235.65 1 // 1- признак 1 опроса после стартового
6 236.25 1
7 237.81 1
8 13.91 1
9 14.41
10 15.26
11 240.11

показания 8,9,10 будут считаться вроде как правильными-т.к. минимум равен 5.007, но на самом деле это не так.

нет никаких гарантий. все дело в том, что могут возникнуть какие-нибудь помехи, скакнуть напряжение, или просто неправильно отработает аппарат, который дает команду на запуск опроса "измерителя". понимаю, что чем больше рассказываю тем фантастичнее кажется рассказ-но это правда так. в идеале вообще не должно быть кривых значений и такой пробелмы быть недолжно.но на практике в реальных условиях это так. еслиб скажем для каждого момента запроса было строго характернаы величины времени-тогда б и проблемы такой не возникло=)

при моделировании в "комнатных условиях" вообще практически нет проблем никаких.а на практике все обстоит иначе.

практика показывает, что эти ошибки (скачки) не централизованы, а расположены как бы на протяжении всех показаний. т.е. если массив поделить на части, то не будет такого что все ложные показания в одном месте.



ладно, пойду еще раз прочитаю протокол, может увижу в контексте. и попробую еще придумать варианты.

p.s: ГАРАНТИИ того, что в КАЖДОЙ серии первые элементы однозначно верны-тоже нет. но это очень интересно!!! я не задумывался раньше об этом... сейчас пойду еще изучу логи!
правда появлюсь на форуме уже наверное только завтра..

спасибо в любом случае за оказываемую помощь!

 

[grigsoft]

В общем, если нет требования делать все в реальном времени, я бы брал куски по 20\50\100 штук (определить на практике - какое число гарантирует достаточное число правильных значений) , искал бы путь в графе, вычисляя ребра на ходу. Дополнительные ограничения из практики - например не может быть более 10 ложных показаний подряд - позволят значительно ускорить вычисление графа.

 

[grigsoft]

Вот еще подумалось - в качестве предварительной оптимизации можно за один проход найти все правильные под-последовательности. Часть из них будет ложными. Но если взять 5%-50% с максимальной длиной - то получим (вероятно) правильные куски. Их начало\конец могут служить локальными границами - между которыми можно отбрасывать все выходящие за эти границы значения. Опять же, если по опыту ложные сигналы по 10 подряд не встречаются, то все последовательности из 10+ значений - правильные(Это неверно - неправильные значения вполне могут быть началом правильной последовательности. Но такие случаи можно словить сравнением границ с предыдущим куском- и отбросить из оптимизации) В простых случаях этого может оказаться достаточно.

 

[Staub_37]

спасибо за помощь! сейчас только вернулся-поробую!