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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 118
Завершенные тесты: 1
#1

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

26.11.2013, 12:45. Просмотров 567. Ответов 13
Метки нет (Все метки)

Доброго дня, пытаюсь решить второй день задачу по удалению случайных значений из массива.
Проблема осложнена тем, что массив содержит порядка 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 }

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

Подскажите, пожалуйста, как это можно сделать?
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2013, 12:45
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Как сгладить неоднородности в массиве (C++):

Как сгладить движение - Java
Я написал программу, где при каждом клике изображение сдвигается на 5 пикселей. Но получается движение рывками, как это сгладить?

Как сгладить шрифты? - Arch Linux
Здравствуйте. Вопрос такого плана. Могу ли я сделать сглаживание шрифтов такое-же как и в Windows? Я делал шрифты со сглаживанием freetype...

Как сгладить шрифты - HTML, CSS
Как сгладить шрифты? На первой картинке шрифт times new roman, на второй шрифт, скачанный из интернета. Откройте картинке на полный экран и...

Законы неоднородности - Maple
Нужна помощь в написании законов неоднородности для кручения,конкретно в написании кода для отображения графика.Законы есть,есть пример,но...

Как сгладить график функции? - Matlab
Помогите сделать график более гладким. figure(2) y2=2*log(x).*sin(x); plot(x,y2,'b'), grid title('2*log(x)*sin(x)') xlabel('x'),...

Как можно “сгладить” event onResize в Mozilla - JavaScript
У меня блок абсолютно позиционирован(использую css свойство fixed), при изменении размеров экрана браузера мне нужно менять координаты...

13
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
26.11.2013, 12:54 #2
Определите критерии неоднородности. Что считать неоднородностью? 3 нуля, 4 нуля или 9 нулей среди единиц?
0
dzrkot
zzzZZZ...
519 / 349 / 53
Регистрация: 11.09.2013
Сообщений: 2,004
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;
}
ещё флаг нужно запилить чтобы знать о конце слова
1
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 118
Завершенные тесты: 1
26.11.2013, 13:06  [ТС] #4
Цитата Сообщение от programina Посмотреть сообщение
Определите критерии неоднородности. Что считать неоднородностью? 3 нуля, 4 нуля или 9 нулей среди единиц?
Так как массив по своему размеру состоит из 500 тыс. элементов, критерий неоднородности на таких расстояниях будет примерно равен 10.000 элементов.
Т.е. если среди 10000 элементов (в свеоего рода окне, бегузем по массиву) нулей больше, чем единиц, то заменяем все эти 10000 значений на нули, иначе меняем на единицы.
0
dzrkot
26.11.2013, 13:08
  #5

Не по теме:

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

0
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 118
Завершенные тесты: 1
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 Посмотреть сообщение

Не по теме:

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

Это прикладная задача по работе, давно уже не студент...
Но так как ранее не занимался алгоритмизацией приходится довольно сложновато...
0
dzrkot
zzzZZZ...
519 / 349 / 53
Регистрация: 11.09.2013
Сообщений: 2,004
26.11.2013, 13:38 #7
так, получается что обрабатываем данные с датчика оборотов? или акселерометров? Можно поподробнее задачу, к примеру в личку или здесь, мне просто из любопытства м.б. я смогу чем-то помочь.
Просто надо знать какую ТЗ решить мб есть и другое решение... Какие данные, какова задача...
0
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 118
Завершенные тесты: 1
26.11.2013, 13:55  [ТС] #8
Цитата Сообщение от dzrkot Посмотреть сообщение
так, получается что обрабатываем данные с датчика оборотов? или акселерометров? Можно поподробнее задачу, к примеру в личку или здесь, мне просто из любопытства м.б. я смогу чем-то помочь.
Просто надо знать какую ТЗ решить мб есть и другое решение... Какие данные, какова задача...
Совершенно верно, идет обработка данных с датчика скорости. Задача обработки, - привязать временные отрезки с наличием скорости к расчету интервала движения (продожительность движения, средняя скорость на участке движения). Т.е. из массива нужно убрать все незначительные паузы движения, т.к. их учет не требуется и более того мешает обработке.
Для этого я уже видоизменил массив, заменив скорость больше нуля единицами и инвертировал массив, построил соответствующий график и передал его в свою функцию по расчету интервалов. Но так как интервалов много, функция работает неадекватно.
0
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
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 } ложная вставка единиц в нулевом отрезке.

Можно рассматривать последовательность блоками и для данного блока устанавливать значение большинств, что правда снизит дискретность данных.
0
vxg
Модератор
3172 / 1975 / 222
Регистрация: 13.01.2012
Сообщений: 7,605
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 самых длинных цепочек из единиц в последовательности
1
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
26.11.2013, 14:26 #11
Как вариант сделать потоковое сглаживание.
А именно задать окно сглаживание (минимальный размер изменения значений, которое считается истинным)
Изначально потоком считываем данные и расчитываем среднеарифметическое до заполнения окна (если данных не хватает то ссно прекращаем считывание) определяем среднеарифметическую для окна, если она больше 0,5 тогда это 1 если меньше тогда 0.
Следовательно первоначально выводим ПОЛОВИНУ окна заполненную соответственно средне арифметическому
Затем последующие значения мы получаем добавляя отнимая краевые значения у окна.
А изменения вносимые мы знаем, т.к. ширина окна фиксирована
По окончанию данных оставшуюся часть заполняем согласно оставшемуся значению среднего арифметического. Если же значение равно 0,5 ровно, можно инвертировать значение а можно и оставить согласно среднему арифметическому
таким образом сдвигая окно сглаживаются данные

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

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

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

Добавлено через 1 минуту
блин а вот накладные расходы работы стека я и не учел. из за этого может стать медленнее чем поиск "пятен"
1
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 118
Завершенные тесты: 1
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
Алгоритм работает, сглаживание есть, но оно не идеальное, все равно мелочевка пролезает, а она сказывается на работе в целом, ну и конечно время работы... можно во время пробега по массиву заварить кофе и выпить его неспеша...
0
HedgehogLu
147 / 68 / 1
Регистрация: 04.09.2013
Сообщений: 260
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. они не сглаживаются
хотя это все на вскидку без проб и компиляций
1
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 118
Завершенные тесты: 1
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. они не сглаживаются
хотя это все на вскидку без проб и компиляций
Большое Спасибо, сейчас постараюсь вникнуть в происходящее с данными и уже самостоятельно допилить до победного конца
0
26.11.2013, 16:15
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.11.2013, 16:15
Привет! Вот еще темы с ответами:

Как сгладить неровные, зазубренные края линии? - Photoshop
Как сгладить неровные, зазубреные края? Допустим у линии, наклоненную на небольшой градус от горизонтали появляется неровность.

Круглый Button - Можно как то сгладить Region - C#
Можно как то сгладить Region? Вроде кнопка круглая но всё ровно торчат пиксели... Заранее спасибо

Как сгладить график построенный по точкам в Mathcad Prime - MathCAD
Помогите научиться сглаживать графики в Mathcad Prime.

Как сгладить пики на графике чтобы он выглядел более плавным? - MathCAD
Здраствуйте! Подскажите пожалуйста, как сгладить пики на графике чтобы он выглядел более плавным? Но чтобы при этом не изменялся...


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

Или воспользуйтесь поиском по форуму:
14
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru