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

Хотел посоветоваться со специалистами в одном непростом вопросе. Каково Ваше мнение?

Ситуация следующая - непрерывно во времени поступают отсчёты. Каждый отсчёт это пятёрка чисел с плавающей точкой.

Необходимо разработать механизм кластеризации - то есть по заданному в ТЗ алгоритму сгруппировать отсчёты в группы(кластеры). Каждый отсчёт может принадлежать только одному кластеру. Формирование кластеров идёт также непрерывно во времени. Каждый поступивший отсчёт включается либо в существующий кластер, либо под него создаётся новый кластер, если он не подходит ни под один существующий.
У разрабатываемого класса должно быть два базовых основных метода -
1)Метод 1(Get_sample) принимает отсчёт, вызывает private методы класса которые юзая сложный алгоритм пробегаются по существующим кластерам принимают решения в какой кластер включить отсчёт или создать под него новый кластер.
2)Метод 2(Return_Clusters) должен возвращать существующие(сгруппированные) на данный момент в классе кластера.(Довольно таки сложный вопрос как их вернуть)

Какой сложный тип данных Вы бы рекомендовали использовать для хранения одного отсчёта(объект,структура или что-то другое) и кластера(группы отсчётов)?
Как функции вернуть группу кластеров? Всё думаю над типами данных.

[modnote=TermoSINteZ]не надо тереть. Пусть народ подскажет еще что-либо.[/modnote]

ADD: Какую литературу Вы бы рекомендовали почитать по механизмам кластеризации?
Интересует древовидная кластеризация.

 

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

Можно скопировать их во временный связанный список и вернуть указатель на первый элемент, но тогда копирование обязательно, что может быть накладным и освобождать память от этого списка должна принимающая сторона, что не очень хорошо, но в принципе применяется, только требует аккуратности.
Ещё можно сделать что-то типа функций FindFirst / FindNext возвращающих по одному кластеру в виде указателя на Read only данные очередного кластера, количество отсчётов в котором хранится вначале кластера.

 

Y_Mur Огромное Вам спасибо!
Можно ли использовать для группы кластеров список векторов? По мере создания нового кластера включать новый вектор в список. Возвращать указатель на первый вектор в списке. Я stl неважно знаю.

 

Nafanya
Зря убрал первый пост может ещё кто что-нибудь подсказал
Вектор в stl по сути тот же динамический массив с уже готовыми типовыми функциями, лично мне его низкоуровневая реализация не нравится, но это дело вкуса , и если в низкоуровневых тонкостях не разбираешься, то конечно, лучше конечно использовать stl.

 

Y_Mur
Вы не подскажете возможно ли в Си++ используя stl объявить список - элементами которого являются динамические массивы(вектора)? Это как раз должно подойти под мой случай. При создании нового кластера добавляется вектор в список.Методом класса возвращаем указатель на первый элемент списка -пробегаемся по списку и смотрим существующие кластеры.

 

Какой сложный тип данных Вы бы рекомендовали для хранения группы кластеров?
Каждый кластер - это динамический массив структур. С течением времени некоторые кластеры из группы будут удалятся, некоторые кластеры будут объединяться между собой, также в группе непрерывно будут появляться новые кластеры. Необходима какая-то сложная динамическая структура данных в которой одним элементом будет являться кластер(динамический массив структур).
Что бы вы посоветовали?

 

Nafanya
Поддержу TermoSINteZ - собрать кластеры в собственный двусвязный список для начала самое оно, а нужно ли это потом усложнять выяснится при отладке

 

Спасибо за помощь. Значит в задаче будут следующие типы данных:
1)Отсчёт ---> структура.
2)Кластер ---> динамический массив(std::vector) структур.
3)Группа кластеров ---> собственный двусвязный список, элементами которого являются кластера.
Наверное всё же это самый лучший вариант.
Как лучше двусвязный список реализовать в виде отдельного класса или внутри разрабатываемого основного(пусть class F например)? Задача класса F преобразовывать последовательность отсчётов в последовательность кластеров по сложным алгоритмам. Какие базовые операции определить для списка?
Мне кажется список должен быть реализован в отдельном классе, т.к. алгоритмы работы с кластерами имеют слабое отношение к списку.

 

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

 

То что под группу кластеров нужен список-это однозначно. Так как требуется операция удаления кластера из середины группы(слияние его с другим кластером). Почитал сейчас в интернете - операция удаления элемента из середины массива съедает намного больше времени,чем удаление элемента из середины списка.
Терзают сомнения по другому поводу. 1-ый кластер содержит в себе 2 отсчёта. 2-ой кластер содержит в себе 102 отсчёта. Соответственно они разное кол-во памяти занимают. Смогут ли ужиться такие разношёрстные элементы как кластеры в одном списке?

 

Чисто для теста накатал сейчас простенький двусвязный список. Пихнул туда три вектора различной длины (на 3,5,10 элементов с плавающей точкой вектора). Ура! Список принял разношёрстные вектора,значит кластеры уживутся. Потом используя список обратился ко второму вектору, изменил в нём значение последнего элемента,затем в него операцией push_back втиснул ещё одно double число. Вывел на экран список векторов. Список не накрылся, значит поддерживает вектора различной длины и видит что вектор сменил свой размер в ходе выполнения программы, что радует.

Время на разработку есть - до конца января 2011 срок отведён, так что думаю успею.
WASM я уважаю, так что если интересно, буду выкладывать информацию по развитию проекта в этой теме.

 

Сегодня под свою задачу разработал генератор отсчётов(не real-time -просто генератор). Пока генератор может работать только в двух режимах - линейный и квадратичный. При чём возможно плавное переключение из одного режима в другой. Например генератор может сгенерировать 100 отсчётов в линейном режиме с дельтой равной 1ms, затем переключиться в квадратичный режим с новыми коэффициентами и дельтой=1s.

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

 

Nafanya

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

 

Y_Mur
За предупреждение спасибо! "Вектор переедет на новый адрес" - чуть со стула со смеху не упал. Вот оказывается какая засада меня еще поджидает

Я вот что думаю. Сейчас у меня есть базовый класс Generator и два производных LinearGenerator и SquareGenerator. Для Генератора у меня перегружен оператор вывода operator<<. Но ведь если по логике подумать, перегружать то operator<< надо для отсчёта, а не для генератора, т.к. именно отсчёт на экран и выводится, а не генератор.

Вот и отсюда и возникла идея сделать отсчёт не структурой, а классом Sample с перегруженным оператором вывода. Так же реализовать класс Claster, основным членом в котором vector <Sample> vec. Также в кластере будут разные методы добавления отсчёта в кластер, сортировка отсчётов и т.д.
Основной и самый огромный класс решил назвать Transformer(осуществляет преобразование последовательности отсчётов в последовательность кластеров). В нем будет реализован двусвязный список объектов класса Cluster.
метод-Get_sample будет принимать объект класса Sample. Затем включать его в какой-нить кластер в списке кластеров.
метод-Return_Clasters - будет возвращать по одному кластеру из списка.(все сразу не получится вернуть).

Вот примерно так я продумал ядро приложения. Y_Mur как Вы смотрите на такую архитектуру?

 

Друзья подскажите, пожалуйста, как из private-функции можно вернуть что-то во внешний мир(в main)?
Я знаю способ, чтоб private-функция изменила какую-нибудь глобальную переменную, но он не подходит.Еще можно в методе объекта в файл писать, а в main читать -но это очень медленно.

Тут ситуация такая. Я передаю отсчеты объекту,каждый раз вызывая метод Send_Sample(). Вызывать для возврата кластера метод объекта из main нельзя, т.к. на момент вызова может не быть кластеров сформированных, а может 100 штук уже накопиться. Только объект знает,когда сформировался кластер. Соответственно после формирования метод,который нельзя вызывать снаружи, как-то должен кластер выкинуть в main.
Как это можно проще сделать?
Приложение однопоточное.

Если б мне разрешили прям в объекте методом на экран кластер вывести, было бы здорово. Но надо сначала в main выкинуть его, а лишь потом только на экран выводить.

 

Ну так передайте callback - указатель на функцию. Про main ничего не понял.

 

Booster
Ну примерно так:
int main()
{
double k[4]={1,2,3,4};//Коэффициенты генератора
Sample thesample;//Объект Отсчет
Generator *plin=new LinearGenerator(0,1,k);//Создаю линейный генератор
Transformer * ptrans=new Transformer;// Создаю преобразователь отсчетов в кластера

Cluster *pcluster=new Cluster; //Создается объект кластер.

for(int i=0;i<1000000;i++)
{
thesample=plin->Generate_Sample();//Генератор генерирует в цикле несколько лямов отсчетов
ptrans->Send_Sample(thesample); //И отправляет их друг за другом преобразователю отсчетов в кластера
}
//?
}

?Допустим после n отправленных отсчетов преобразователь используя внутренние механизмы(private-функции) сформировал первый кластер. КАК преобразователю из private-функции вернуть кластер в main()? main() функция не знает, что из n отсчетов Преобразователь сформировал кластер и его уже надо забирать и выводить на экран.

 

Nafanya

Примерно так:

Код (Text):

1. int claster_count = 0;
2. ...
3. for(...) {
4.    ...
5.    ptans->Send_Sample(...);
6.    if(ptrans->claster_count != claster_count) {
7.        cout << ptrans->last_claster << endl;
8.        claster_count ++;
9.    }
10.    ...
11. }

Можно ещё научить ptrans рассылать эвенты, если что-то интересное случится. Можно в ptrans запихнуть callback или класс callback'ов. В конце концов, можно научить метод Send_Sample возвращать значение -- указатель на созданный кластер, который будет равен NULL, если кластер не создан. Вариантов много, если подумать. А то что запрещают из private методов ptrans выводить на экран -- это они правильно делают: всегда надо разграничивать UI и алгоритмику.