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

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

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

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

26.11.2013, 12:45. Просмотров 556. Ответов 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 }

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

Подскажите, пожалуйста, как это можно сделать?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
26.11.2013, 12:45     Как сгладить неоднородности в массиве
Посмотрите здесь:

Как происходит циклический сдвиг (как сдвинуть элементы в массиве) - C++
Задан массивы действительных чисел а1, а2,…,а20. Сдвинуть циклическим сдвигом все его элементы так, чтобы минимальный элемент стоял на...

Как узнать есть ли в массиве одинаковые числа и как найти эти числа ? - C++
Всем привет ,можете помочь как узнать есть ли в массиве одинаковые числа и как найти эти числа . Например массив с элементами 1 4 4 0 2 ....

Как записать Z в трёхмерном массиве - C++
ребята, простите за дурной вопрос, но не могу разобраться. есть массив const int Y = 2, X = 2, Z = 2; int a = {1,1,1, ...

Как найти сумму в массиве - C++
дан массив А(50).найти сумму и кол-во нечетных положительных элементов,следующих за первым по порядку нулевым элементом.

Как найти в массиве цифру - C++
Помогите решить задачу, вот уже целый семестр парюсь и не знаю как решить. 1. Среди N треугольников, у которых известна одна сторона и...

Как найти размерность в массиве С - C++
Знаю что в одномерном массиве: sezeof(a)/sizeof(a) А как для двухмерного?

Как удалить в массиве цифру - C++
Здравствуйте. В моей предыдущей теме, я решил задачу Как найти в массиве цифру. И теперь мне нужно сделать похожую задачу. Условие: ...

После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
programina
1914 / 599 / 37
Регистрация: 23.10.2011
Сообщений: 4,468
Записей в блоге: 2
26.11.2013, 12:54     Как сгладить неоднородности в массиве #2
Определите критерии неоднородности. Что считать неоднородностью? 3 нуля, 4 нуля или 9 нулей среди единиц?
dzrkot
zzzZZZ...
519 / 349 / 53
Регистрация: 11.09.2013
Сообщений: 1,996
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
Сообщений: 110
Завершенные тесты: 1
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
Сообщений: 110
Завершенные тесты: 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 Посмотреть сообщение

Не по теме:

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

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

Можно рассматривать последовательность блоками и для данного блока устанавливать значение большинств, что правда снизит дискретность данных.
vxg
Модератор
3146 / 1948 / 214
Регистрация: 13.01.2012
Сообщений: 7,439
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
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 минуту
блин а вот накладные расходы работы стека я и не учел. из за этого может стать медленнее чем поиск "пятен"
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 110
Завершенные тесты: 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
Алгоритм работает, сглаживание есть, но оно не идеальное, все равно мелочевка пролезает, а она сказывается на работе в целом, ну и конечно время работы... можно во время пробега по массиву заварить кофе и выпить его неспеша...
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. они не сглаживаются
хотя это все на вскидку без проб и компиляций
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.11.2013, 16:15     Как сгладить неоднородности в массиве
Еще ссылки по теме:

Из массива А удалить те элементы, встречающиеся и в массиве А и в массиве В хотя бы два раза - C++
Всем привет ! В силу своей ограниченности и качества современного образования, не могу преодолеть задачу первого курса по программированию...

Вывести элементы, которые есть в массиве А в нескольких экземплярах и отсутствуют в массиве В - C++
Задание : вывести на экран элементы, которые есть в массиве А в нескольких экземплярах и отсутствуют в массиве В. Есть задача, но она...

Найти наибольший элемент в массиве A которого нет в массиве B - C++
Даны два массива натуральных чисел A ( m ) и B ( n ) . Найти наибольший элемент в массиве A , которого нет в массиве B.

наименьшее значение в массиве поменять с последним элементом в массиве - C++
В массиве C из N элементов найти элемент, имеющий наименьшее значение и поменять его местами с последним элементом. Значение N задать при...

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


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

Или воспользуйтесь поиском по форуму:
ustus_alex
6 / 6 / 1
Регистрация: 22.11.2013
Сообщений: 110
Завершенные тесты: 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. они не сглаживаются
хотя это все на вскидку без проб и компиляций
Большое Спасибо, сейчас постараюсь вникнуть в происходящее с данными и уже самостоятельно допилить до победного конца
Yandex
Объявления
26.11.2013, 16:15     Как сгладить неоднородности в массиве
Ответ Создать тему
Опции темы

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