Кластеризация отсчётов

r90

<<В конце концов, можно научить метод Send_Sample возвращать значение -- указатель на созданный кластер, который будет равен NULL, если кластер не создан.

Думал долго об этом,хорошее решение. Но наверное придется возвращать по значению. Ведь перед возвращением кластера в main, объект должен освободить память которую он занимал. Иначе 4 Гб оперативы вылетят за несколько секунд пробега программы. Если возвращать указатель, то память освобождать до возврата нельзя.

Cluster Transformer::Get_Cluster()
{
list_iter=plist->begin();
Cluster thecluster(*list_iter);//Локальная переменная, у которой память после выхода из видимости освободится.
//Инициализируется первым элементом списка.
list_iter=plist->erase(list_iter);//Освобождается память кластера в объекте
number--;//Кол-во кластеров уменьшается
return(thecluster);//Возврат кластера в main, и освобождение памяти локальной переменной.
}

Если указатель на кластер в main вернуть, как память для него освобождать в объекте?

 

Nafanya

Про счётчики ссылок слышал?

 

Отчитался перед руководителем по проделанной работе. На данный момент полностью реализовано ядро алгоритма кластеризации (Clusterization_Core), которое осуществляет преобразование отсчетов в кластера.

Руководитель сказал, что пора перейти к последнему этапу - оптимизации.
Преобразование происходит в реальном времени. Поэтому необходимо исключить сортировку из ядра, заменив её слиянием двух упорядоченных наборов. Для приложений реального времени сортировка - слишком дорогостоящая операция, поэтому она должна быть исключена.

У меня требование, чтоб приложение было кросс-платформенным. Для себя самого хотелось бы протестировать его в ОСИ жесткого реального времени, а не мягкого(как я понял в дальнейшем,эксплуатировать мою разработку будут в ОС мягкого реального времени).

Пожалуйста подскажите возможно ли где-нибудь в интернете достать хотя бы 30-дневную ОС QNX(дистрибутив с компилятором)? Может ли кто нибудь этой драгоценной осью поделиться, был бы очень благодарен!

Если не получится достать QNX, придётся тестировать в Linux с мягким реальным временем.

 

qnx.com ?

 

n0name
Спасибо!
Вы не подскажите,как в QNX померить время затраченное на выполнение
1)Строки кода программы(без системного вызова),например(count++
2)Строки кода с системным вызовом,время=выполнение строки кода+время обработки системного вызова , например(ptr=new Cluster
Что-то додуматься никак не могу.
Как там вообще задержки меряются?

 

малые интервалы - ClockCycles(), большие - clock_gettime().
доки по функциям есть в манах прямо на qnx.com

 

А с помощью System Profiler, Application Profiler в Momentics IDE никак нельзя измерить?
Они вроде тоже времена мерят, только я пока до конца не разобрался как они работают.
Просто понимаете мне желательней временную диаграмму получить, чтоб потом ее вывесить на плакате можно было.

Вопрос не актуален, измерил.

 

Учитывая справедливое замечание Y_Mur,теперь буду задавать вопросы конкретнее - меньше воды, больше технических терминов.

Какова трудоемкость операций insert() и push_back() для вектора стандартной библиотеки(std::vector) из N элементов?
Если кто знает, подскажите пожалуйста.

Эти сведения необходимы мне для оценки трудоемкости моего алгоритма.

 

Откуда такие термины берёте - "трудоёмкость"? Как можно писать диплом так слабо разбираясь в языке? По поводу вашего вопроса - http://www.sgi.com/tech/stl/Vector.html

 

Booster
Если Вы не знаете о чем идет речь и что такое трудоемкость, зачем делать какие-то выводы?

Вы не в курсе, что если Вы создаете новый алгоритм, то перед комиссией надо вывешивать статистически снятую зависимость Трудоемкости алгоритма?

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

Трудоемкость может быть равна N, N^2,log N, Const и т.д.

Да, и как мне сегодня сказали,программная реализация алгоритма - это только пол-работы, нужна ещё оценка трудоемкости, для новых алгоритмов-это обязательно.

 

Кажется нашел:
"std::vector - C-подобный динамический массив произвольного доступа с автоматическим изменением размера при добавлении/удалении элемента. Доступ по индексу за O(1). Добавление-удаление элемента в конец vector занимает амортизированное O(1) время, та же операция в начале или середине vector — O(n)."

 

Nafanya
Это очередной пример неудачно заданного вопроса - не знаю в каком учебнике вы вычитали про трудоёмкость (очень неудачный термин в даннном контексте) - обычно все пользуются термином сложность.

 

Y_Mur
А вы не могли бы сказать,где можно найти алгоритм слияния двух упорядоченных наборов(N и M элементов) со сложностью O(M+N)?
У меня сейчас реализовано это с O(N^2). Нужен другой алгоритм.

Никак не получается найти. Кнута скачал, что-то тоже там в трех томах не выходит найти.

 

Сейчас автор топа снова на меня обидится, но это жесть. Как можно умудрится слить два упорядоченных набора за O(N^2), выше моего понимания. Вы хоть немного подумайте, прежде чем писать. ^)

 

Booster
Имеется в виду в каждом упорядоченном наборе по N элементов.
Я использовал операцию добавления insert(),которая сама по себе имеет сложность O(N).
Ну и считайте N раз добавляли в вектор элемент, сложность одного добавления O(N). Выходит O(N^2).
Сегодня этот косяк нашли,сказали выкинуть insert(). Сам разве догадаешься, что insert() вместо одной операции добавления, выполняет N операций.

 

Nafanya
Ну так и выкиньте insert. В чём проблема?

 

Booster
Ну есть два вектора.
А как в середину первого пихнуть элемент со сложностью O(1)? Или все таки придется использовать временный третий вектор для слияния, а потом его копировать в первый. Результат слияния в первом должен быть.

 

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

Кстати ещё связанные списки существуют, где можно вставлять в середину или объединять наборы вообще без копирования элементов.

 

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

 

This question was resolved.