Форум программистов, компьютерный форум CyberForum.ru

Как сгладить неоднородности в массиве - C++

Восстановить пароль Регистрация
 
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 100
26.11.2013, 12:45     Как сгладить неоднородности в массиве #1
Доброго дня, пытаюсь решить второй день задачу по удалению случайных значений из массива.
Проблема осложнена тем, что массив содержит порядка 500.000 элементов и алгоритм нужен очень быстрый, т.к. время обработки массива очень критично.

Для понимания моей проблемы приведу пример, в виде уменьшенной копии масива:
{1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 }

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

{1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 }

Если единица встречается редко - меняем ее на ноль, если ноль встречается редко меняем его на единицу.

Подскажите, пожалуйста, как это можно сделать?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
programina
 Аватар для programina
1912 / 597 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
26.11.2013, 12:54     Как сгладить неоднородности в массиве #2
Определите критерии неоднородности. Что считать неоднородностью? 3 нуля, 4 нуля или 9 нулей среди единиц?
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
26.11.2013, 13:02     Как сгладить неоднородности в массиве #3
ну по идее, надо знать максимальную длинну ложного слова, или(и) минимальную истинного, соответственно сравнивать в цикле, сохранять 1 индекс и последний, потом вызывать инлайн функцию, в аргумент которой передаем адрес начала ложного слова и его конец, ну и заполняем там всё нулями между ними

с точки зрения быстродействия не знаю, лучше не придумаю т.к. я бездарь))
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (a[i]==0&&a[i+1]==1)
begin=i;
if (a[i]==1&&a[i+1]==0)
{
i=end;
flag=true
}
 
if (flag==true)
{
len=end-begin;
if(len>max)
continue;
else
swap(&PtrBegin,&PtrEnd);
flag==false;
}
ещё флаг нужно запилить чтобы знать о конце слова
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 100
26.11.2013, 13:06  [ТС]     Как сгладить неоднородности в массиве #4
Цитата Сообщение от programina Посмотреть сообщение
Определите критерии неоднородности. Что считать неоднородностью? 3 нуля, 4 нуля или 9 нулей среди единиц?
Так как массив по своему размеру состоит из 500 тыс. элементов, критерий неоднородности на таких расстояниях будет примерно равен 10.000 элементов.
Т.е. если среди 10000 элементов (в свеоего рода окне, бегузем по массиву) нулей больше, чем единиц, то заменяем все эти 10000 значений на нули, иначе меняем на единицы.
dzrkot
26.11.2013, 13:08
  #5

Не по теме:

это прикладная задача или вы студент и препод задал?))

ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 100
26.11.2013, 13:14  [ТС]     Как сгладить неоднородности в массиве #6
Цитата Сообщение от dzrkot Посмотреть сообщение
ну по идее, надо знать максимальную длинну ложного слова, или(и) минимальную истинного, соответственно сравнивать в цикле, сохранять 1 индекс и последний, потом вызывать инлайн функцию, в аргумент которой передаем адрес начала ложного слова и его конец, ну и заполняем там всё нулями между ними

с точки зрения быстродействия не знаю, лучше не придумаю т.к. я бездарь))
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if (a[i]==0&&a[i+1]==1)
begin=i;
if (a[i]==1&&a[i+1]==0)
{
i=end;
flag=true
}
 
if (flag==true)
{
len=end-begin;
if(len>max)
continue;
else
swap(&PtrBegin,&PtrEnd);
flag==false;
}
ещё флаг нужно запилить чтобы знать о конце слова
Максимальную длинну ложного слова определить невозможно...
Т.к. данный массив содержит данные скорости, когда скорость у локоматива есть, то значение этой скорости единица, так как только локомотив стоит, значение скорости нуль. Локомотив может неизвестно сколько времени стоять на симафоре или быть на станции. Нужна опраксимация этих значений.
В идеале мне нужно получить максимум пять самых продолжительных по времени отрезков движения.

Добавлено через 1 минуту
Цитата Сообщение от dzrkot Посмотреть сообщение

Не по теме:

это прикладная задача или вы студент и препод задал?))

Это прикладная задача по работе, давно уже не студент...
Но так как ранее не занимался алгоритмизацией приходится довольно сложновато...
dzrkot
zzzZZZ...
 Аватар для dzrkot
516 / 346 / 53
Регистрация: 11.09.2013
Сообщений: 1,977
26.11.2013, 13:38     Как сгладить неоднородности в массиве #7
так, получается что обрабатываем данные с датчика оборотов? или акселерометров? Можно поподробнее задачу, к примеру в личку или здесь, мне просто из любопытства м.б. я смогу чем-то помочь.
Просто надо знать какую ТЗ решить мб есть и другое решение... Какие данные, какова задача...
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 100
26.11.2013, 13:55  [ТС]     Как сгладить неоднородности в массиве #8
Цитата Сообщение от dzrkot Посмотреть сообщение
так, получается что обрабатываем данные с датчика оборотов? или акселерометров? Можно поподробнее задачу, к примеру в личку или здесь, мне просто из любопытства м.б. я смогу чем-то помочь.
Просто надо знать какую ТЗ решить мб есть и другое решение... Какие данные, какова задача...
Совершенно верно, идет обработка данных с датчика скорости. Задача обработки, - привязать временные отрезки с наличием скорости к расчету интервала движения (продожительность движения, средняя скорость на участке движения). Т.е. из массива нужно убрать все незначительные паузы движения, т.к. их учет не требуется и более того мешает обработке.
Для этого я уже видоизменил массив, заменив скорость больше нуля единицами и инвертировал массив, построил соответствующий график и передал его в свою функцию по расчету интервалов. Но так как интервалов много, функция работает неадекватно.
HedgehogLu
 Аватар для HedgehogLu
146 / 67 / 1
Регистрация: 04.09.2013
Сообщений: 250
26.11.2013, 13:59     Как сгладить неоднородности в массиве #9
Тут еще вопрос о допустимых погрешностях.
С одной стороны все просто. зная длины интервалов мы можем их воспринимать как истинные или ложные, однако тут необходимо еще учитывать влияние краевых значений
так например даже в приведенном примере
Цитата Сообщение от ustus_alex Посмотреть сообщение
Для понимания моей проблемы приведу пример, в виде уменьшенной копии масива:
{1 1 1 1 1 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 }
Конец кода при определенных размерах интервалов приобретает неоднозначность
...0 1 1 1 1 1 1 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 } интерпретировать как ... 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 } (случайная вставка нулей) или же как
...0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 } ложная вставка единиц в нулевом отрезке.

Можно рассматривать последовательность блоками и для данного блока устанавливать значение большинств, что правда снизит дискретность данных.
vxg
Модератор
 Аватар для vxg
2669 / 1680 / 158
Регистрация: 13.01.2012
Сообщений: 6,281
26.11.2013, 14:04     Как сгладить неоднородности в массиве #10
Цитата Сообщение от ustus_alex Посмотреть сообщение
В идеале мне нужно получить максимум пять самых продолжительных по времени отрезков движения.
разбиваете весь отрезок времени на количество интервалов которые вам нравятся. в каждом интервале вычисляете количество 1 и 0. каких оказалось больше - тех и считаете активными в течение интервала. еще вариант - фильтр. например, экспоненциальное среднее
y(i) = y(i - 1) + (x(i) - y(i - 1)) * alpha
где y(i) фильтрованное значение для точки i, y(i - 1) фильтрованное значение для точки i - 1, x(i) - не фильтрованное значение для точки i, alpha - коэффициент фильтра (чем меньше тем меньше влияние помех на значение, но тем более оно инерционное)

Добавлено через 1 минуту
Цитата Сообщение от ustus_alex Посмотреть сообщение
В идеале мне нужно получить максимум пять самых продолжительных по времени отрезков движения.
ну так и найдите 5 самых длинных цепочек из единиц в последовательности
HedgehogLu
 Аватар для HedgehogLu
146 / 67 / 1
Регистрация: 04.09.2013
Сообщений: 250
26.11.2013, 14:26     Как сгладить неоднородности в массиве #11
Как вариант сделать потоковое сглаживание.
А именно задать окно сглаживание (минимальный размер изменения значений, которое считается истинным)
Изначально потоком считываем данные и расчитываем среднеарифметическое до заполнения окна (если данных не хватает то ссно прекращаем считывание) определяем среднеарифметическую для окна, если она больше 0,5 тогда это 1 если меньше тогда 0.
Следовательно первоначально выводим ПОЛОВИНУ окна заполненную соответственно средне арифметическому
Затем последующие значения мы получаем добавляя отнимая краевые значения у окна.
А изменения вносимые мы знаем, т.к. ширина окна фиксирована
По окончанию данных оставшуюся часть заполняем согласно оставшемуся значению среднего арифметического. Если же значение равно 0,5 ровно, можно инвертировать значение а можно и оставить согласно среднему арифметическому
таким образом сдвигая окно сглаживаются данные

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

Добавлено через 5 минут
В принципе осуществляя несколько проходов с увеличением размера окна можно сгладить данные до необходимых интервалов.
однако не забываем про вносимую погрешность и неопределенность при среднем арифметическом равном 0,5

Добавлено через 2 минуты
Для корректной работы окна достаточно реализовать стек FIFO.

Добавлено через 1 минуту
блин а вот накладные расходы работы стека я и не учел. из за этого может стать медленнее чем поиск "пятен"
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 100
26.11.2013, 15:15  [ТС]     Как сгладить неоднородности в массиве #12
Цитата Сообщение от HedgehogLu Посмотреть сообщение
Как вариант сделать потоковое сглаживание.
А именно задать окно сглаживание (минимальный размер изменения значений, которое считается истинным)
Изначально потоком считываем данные и расчитываем среднеарифметическое до заполнения окна (если данных не хватает то ссно прекращаем считывание) определяем среднеарифметическую для окна, если она больше 0,5 тогда это 1 если меньше тогда 0.
Следовательно первоначально выводим ПОЛОВИНУ окна заполненную соответственно средне арифметическому
Затем последующие значения мы получаем добавляя отнимая краевые значения у окна.
А изменения вносимые мы знаем, т.к. ширина окна фиксирована
По окончанию данных оставшуюся часть заполняем согласно оставшемуся значению среднего арифметического. Если же значение равно 0,5 ровно, можно инвертировать значение а можно и оставить согласно среднему арифметическому
таким образом сдвигая окно сглаживаются данные

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

Добавлено через 5 минут
В принципе осуществляя несколько проходов с увеличением размера окна можно сгладить данные до необходимых интервалов.
однако не забываем про вносимую погрешность и неопределенность при среднем арифметическом равном 0,5

Добавлено через 2 минуты
Для корректной работы окна достаточно реализовать стек FIFO.

Добавлено через 1 минуту
блин а вот накладные расходы работы стека я и не учел. из за этого может стать медленнее чем поиск "пятен"
Для быстроты визуализации резальтата сделал вначале код в матлабе:

Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
d=b;                          % передаем основной массив в темп
for j=1:length(d)          % задаем цикл в длинну массива
    count0=0;           % счетчик нуля в нуль
    count1=0;           % счетчик единицы в нуль
    for i=1:15000       % задаем окно на 15.000 элементов
        if b(i)==0
            count0=count0+1;   % считаем нули
        else
            count1=count1+1;   % считаем единицы
        end
        if count0>count1             % если нулей больше все элементы окна заполняем нулями
            d(i)=0;            
        else
            d(i)=1;
        end
    end
j=j+15001;      % т.к. первые 15000 элементов массива просмотрены, начинаем смотреть с 15001
end
Алгоритм работает, сглаживание есть, но оно не идеальное, все равно мелочевка пролезает, а она сказывается на работе в целом, ну и конечно время работы... можно во время пробега по массиву заварить кофе и выпить его неспеша...
HedgehogLu
 Аватар для HedgehogLu
146 / 67 / 1
Регистрация: 04.09.2013
Сообщений: 250
26.11.2013, 16:01     Как сгладить неоднородности в массиве #13
Эммм проблема в том, что вы постоянно пересчитываете среднюю арифметическую, что является избыточным.
Необходимо и достаточно ее посчитать только раз, при последующем считывании данных достаточно вносить изменения.
Ща набросаю код на си

Добавлено через 32 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstring>
bool read(char &data)
    {
        return 0; //Функция потокового считывания исходных данных
    }
    
    bool write(char data)
    {
         return 0;//функция потоковой записи результирующих данных 
    }
    
     
 
int main()
{
    long bufsize=15000;
    bool first=true;
    char *buf=new char[bufsize];
    char res=0;
    long average=0;
    long gran=bufsize/2;
    long start,end;
    start=0;
    end=0;
    char vol=0;
    //изначально заполняем окно
    while ((read(vol)==0)&&(end<bufsize))
    {
      average+=vol;
      end++;  
    }
    //получаем среднее итоговое значение для окна
    if (average>=gran) res=1;
    //если заполнили все окно
    if (end==15000)
    {
        //потоково анализируем данные
        while (read(vol)==0)
        {
            average+=vol; //добавляем новое значение к среднему
            average-=buf[start++]; //вычитаем первое считанное значение в буфере смещаем положение в буфере
            end++; //смещаем последнее считанное значение в буфере
            if (start>=bufsize) start=0;//корректируем индексы
            if (end>=bufsize) end=0;
            buf[end]=vol;//сохраняем новое значение в буфере как последнесчитанное
            if (average>=gran) res=1 ; //переопределяем результирующее среднее для окна
            else res=0; 
            write(res); //выводим в результат
        }
    }
    //сохряняем остаточный буфер согласно итоговому среднему значению
    for (;start!=end;start++) 
    {
        write(res);
        if (start>=bufsize) start=0;
    }
    return 0;
}
Добавлено через 1 минуту
навскидку так, но уже нашел один недостаток.
когда происходят изменения значений одно за другим на гране зоны 0.5. они не сглаживаются
хотя это все на вскидку без проб и компиляций
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.11.2013, 16:15     Как сгладить неоднородности в массиве
Еще ссылки по теме:

Вывести элементы, которые есть в массиве А в нескольких экземплярах и отсутствуют в массиве В C++
C++ Как найти в массиве цифру
C++ Как удалить в массиве цифру

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 100
26.11.2013, 16:15  [ТС]     Как сгладить неоднородности в массиве #14
Цитата Сообщение от HedgehogLu Посмотреть сообщение
Эммм проблема в том, что вы постоянно пересчитываете среднюю арифметическую, что является избыточным.
Необходимо и достаточно ее посчитать только раз, при последующем считывании данных достаточно вносить изменения.
Ща набросаю код на си

Добавлено через 32 минуты
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstring>
bool read(char &data)
    {
        return 0; //Функция потокового считывания исходных данных
    }
    
    bool write(char data)
    {
         return 0;//функция потоковой записи результирующих данных 
    }
    
     
 
int main()
{
    long bufsize=15000;
    bool first=true;
    char *buf=new char[bufsize];
    char res=0;
    long average=0;
    long gran=bufsize/2;
    long start,end;
    start=0;
    end=0;
    char vol=0;
    //изначально заполняем окно
    while ((read(vol)==0)&&(end<bufsize))
    {
      average+=vol;
      end++;  
    }
    //получаем среднее итоговое значение для окна
    if (average>=gran) res=1;
    //если заполнили все окно
    if (end==15000)
    {
        //потоково анализируем данные
        while (read(vol)==0)
        {
            average+=vol; //добавляем новое значение к среднему
            average-=buf[start++]; //вычитаем первое считанное значение в буфере смещаем положение в буфере
            end++; //смещаем последнее считанное значение в буфере
            if (start>=bufsize) start=0;//корректируем индексы
            if (end>=bufsize) end=0;
            buf[end]=vol;//сохраняем новое значение в буфере как последнесчитанное
            if (average>=gran) res=1 ; //переопределяем результирующее среднее для окна
            else res=0; 
            write(res); //выводим в результат
        }
    }
    //сохряняем остаточный буфер согласно итоговому среднему значению
    for (;start!=end;start++) 
    {
        write(res);
        if (start>=bufsize) start=0;
    }
    return 0;
}
Добавлено через 1 минуту
навскидку так, но уже нашел один недостаток.
когда происходят изменения значений одно за другим на гране зоны 0.5. они не сглаживаются
хотя это все на вскидку без проб и компиляций
Большое Спасибо, сейчас постараюсь вникнуть в происходящее с данными и уже самостоятельно допилить до победного конца
Yandex
Объявления
26.11.2013, 16:15     Как сгладить неоднородности в массиве
Ответ Создать тему
Опции темы

Текущее время: 21:05. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru