VPF::работа с временем - Форум программистов

wallstreet

Дата 13.2.2013, 14:52 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 153
Регистрация: 11.8.2011

Репутация: нет
Всего: нет

Доброго всем дня.
У меня есть двумерная очередь в которую динамически льются данные.  Первым полем в очереди является время в строковом формате, оно же фактически и будет являться ключем выборки по остальным данным.
Таким образом, мне необходимо брать определенные данные, которые, грубо говоря, позже указанного времени.
Пример:
мне нужно взять данные начиная с 13:30:45.
Из ряда данных:
0.  13:21:15
1.  13:28:48.
2.  13:31:25.
3.  13:45:05.
4.  13:50:35.
5.  13:51:15.
мне нужно найти первую запись которая была позже или равна необходимому, т.е. в моем случае  13:31:25 с индексом в очереди 2.
Собственно я бы хотел узнать насколько мой вариант реализации является оптиммальным и правильным.
Заранее всех благодарю за участие в теме!

и так, приступим.
Для наглядности я привел пример с одномерной очередью.
Вот очередь:

Код


deque<string> dStr;
    dStr.push_back("10:30:10");
    dStr.push_back("10:30:12");
    dStr.push_back("10:30:14");
    dStr.push_back("10:30:18");
    dStr.push_back("10:30:20");

вот интересующее меня время:

Код


char *str = "10:30:17";

ну и собственно, решение

Код


int main()
{
    int count=0, t=0;
    int iMinPeriod = 20;
    char ch;
    struct tm *timeInfo, *timeInfoFind;
    time_t tPresTime, tTimeToFind;
    int hour, min, sec;
    char hBuf[2], mBuf[2], sBuf[2];
    char *str = "10:30:17";

    hBuf[0] = str[0];
    hBuf[1] = str[1];
    hour = atoi(hBuf);
    mBuf[0] = str[3];
    mBuf[1] = str[4];
    min = atoi(mBuf);
    sBuf[0] = str[6];
    sBuf[1] = str[7];
    sec = atoi(sBuf);

    time( &tPresTime );
    timeInfo = localtime( &tPresTime );
    timeInfo->tm_hour = hour;
    timeInfo->tm_min = min;
    timeInfo->tm_sec = sec;
    tPresTime = mktime(timeInfo);

    for(int i=dStr.size()-1; i>=0; --i)
    {
        int h, m, s;
        char cHourBuf[2], cMinBuf[2], cSecBuf[2];

        cHourBuf[0] = dStr[i].c_str()[0];
        cHourBuf[1] = dStr[i].c_str()[1];
        cMinBuf[0] = dStr[i].c_str()[3];
        cMinBuf[1] = dStr[i].c_str()[4];
        cSecBuf[0] = dStr[i].c_str()[6];
        cSecBuf[1] = dStr[i].c_str()[7];
        h = atoi(cHourBuf);
        m = atoi(cMinBuf);
        s = atoi(cSecBuf);

        time(&tTimeToFind);
        timeInfoFind = localtime(&tTimeToFind);
        timeInfoFind->tm_hour = h;
        timeInfoFind->tm_min = m;
        timeInfoFind->tm_sec = s;
        tTimeToFind = mktime(timeInfoFind);
        if(tPresTime >= tTimeToFind)
        {
            count = dStr.size() - i;
            break;
        }
    }

    std::cout << "Count of first time is: " << count;
    std::cin >> ch;
    return 0;
}

Сразу сажу, в данном варианте данных правильный индекс начала выборки будет 3.

Это сообщение отредактировал(а) wallstreet - 13.2.2013, 15:32

volatile

Дата 13.2.2013, 17:37 (ссылка)

(голосов:2)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(wallstreet @ 13.2.2013, 14:52

)

насколько мой вариант реализации является оптиммальным

Намека даже нет.

Что я бы сделал в первую очередь.
1. Бинарный поиск, время же отсортировано.
2. Время хранить не в строковом виде, а в цифре. (превращать в цифру при добавлении в очередь.)

ну и соответственно, от вышележащего кода мало что остаёцца...

Добавлено через 7 минут и 51 секунду
2-е в принципе опционально, зависит от других факторов, но очень желательно.

wallstreet

Дата 14.2.2013, 01:38 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 153
Регистрация: 11.8.2011

Репутация: нет
Всего: нет

Цитата

1. Бинарный поиск, время же отсортировано.

сделал так:

Код


#include <iostream>
#include <deque>
#include <ctime>
using namespace std;


int main()
{
    char ch;
    char *str = "13:30:12";
    deque<std::string> dStr;
    int hour, min, sec;
    char hBuf[2], mBuf[2], sBuf[2];
    struct tm *timeInfo, *timeInfoFind;
    time_t tPresTime, tTimeToFind;

    dStr.push_back("10:30:10");
    dStr.push_back("13:30:12");
    dStr.push_back("13:30:12");
    dStr.push_back("14:30:18");
    dStr.push_back("15:20:20");
    dStr.push_back("15:23:05");
    dStr.push_back("15:23:05");
    dStr.push_back("15:23:05");
    dStr.push_back("15:32:15");
    dStr.push_back("15:33:05");

    int deque_size = dStr.size();
    int last_index =deque_size;
    int avg_index = 0;
    int first_index = 0;

    hBuf[0] = str[0];
    hBuf[1] = str[1];
    hour = atoi(hBuf);
    mBuf[0] = str[3];
    mBuf[1] = str[4];
    min = atoi(mBuf);
    sBuf[0] = str[6];
    sBuf[1] = str[7];
    sec = atoi(sBuf);

    time( &tPresTime );
    timeInfo = localtime( &tPresTime );
    timeInfo->tm_hour = hour;
    timeInfo->tm_min = min;
    timeInfo->tm_sec = sec;
    tPresTime = mktime(timeInfo);                  // время которое задано для поиска

    if(last_index == -1)
        cout << "deque is empty!!\n";

    int h, m, s;
    char cHourBuf[2], cMinBuf[2], cSecBuf[2];

    while(first_index < last_index)
    {
        avg_index = first_index + (last_index - first_index) / 2;

        cHourBuf[0] = dStr[avg_index].c_str()[0];
        cHourBuf[1] = dStr[avg_index].c_str()[1];
        cMinBuf[0] = dStr[avg_index].c_str()[3];
        cMinBuf[1] = dStr[avg_index].c_str()[4];
        cSecBuf[0] = dStr[avg_index].c_str()[6];
        cSecBuf[1] = dStr[avg_index].c_str()[7];
        h = atoi(cHourBuf);
        m = atoi(cMinBuf);
        s = atoi(cSecBuf);

        time(&tTimeToFind);
        timeInfoFind = localtime(&tTimeToFind);
        timeInfoFind->tm_hour = h;
        timeInfoFind->tm_min = m;
        timeInfoFind->tm_sec = s;
        tTimeToFind = mktime(timeInfoFind);       // время на совпадение с которым проверяем

        tPresTime <= tTimeToFind ? last_index = avg_index : first_index = avg_index +1;
    }

    cHourBuf[0] = dStr[last_index].c_str()[0];
    cHourBuf[1] = dStr[last_index].c_str()[1];
    cMinBuf[0] = dStr[last_index].c_str()[3];
    cMinBuf[1] = dStr[last_index].c_str()[4];
    cSecBuf[0] = dStr[last_index].c_str()[6];
    cSecBuf[1] = dStr[last_index].c_str()[7];
    h = atoi(cHourBuf);
    m = atoi(cMinBuf);
    s = atoi(cSecBuf);

    time(&tTimeToFind);
    timeInfoFind = localtime(&tTimeToFind);
    timeInfoFind->tm_hour = h;
    timeInfoFind->tm_min = m;
    timeInfoFind->tm_sec = s;
    tTimeToFind = mktime(timeInfoFind);    

    if(tPresTime == tTimeToFind)
        cout << "value was found" << "\nindex = " << last_index << endl;
    else
        cout << "\nvalue is not found" << endl;

    cin >> ch;
    return 0;
}

Что-то меня смущает эта суета с конвертирование времени, не слишком ли это затратно получится?

Цитата

2. Время хранить не в строковом виде, а в цифре. (превращать в цифру при добавлении в очередь.)

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

xvr

Дата 14.2.2013, 13:20 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Цитата(wallstreet @ 14.2.2013, 01:38

)

а конвертировать при добавлении в очередь думаю не очень рационально,

То есть вы считаете что многократно конвертировать при поиске будет более рационально? smile

NB. Храните данные не в deque, а map (или multimap) - данные будут сразу отсортированные и поиск будет в 1 строку

wallstreet

Дата 14.2.2013, 14:05 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 153
Регистрация: 11.8.2011

Репутация: нет
Всего: нет

Цитата(xvr @ 14.2.2013, 13:20

)

То есть вы считаете что многократно конвертировать при поиске будет более рационально?

принято!

Цитата(xvr @ 14.2.2013, 13:20

)

NB. Храните данные не в deque, а map (или multimap) - данные будут сразу отсортированные и поиск будет в 1 строку

если капнуть глубже и учесть что данные льются по DDE, то тут для большей скорости добавления, думаю, лучше подойдет list

xvr

Дата 14.2.2013, 17:12 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Цитата(wallstreet @ 14.2.2013, 14:05

)

Все же deque. У list'а будут большие накладные расходы на работу с динамической памятью.

Но тут надо учесть, что чаще происходит - модификация данных или поиск в них. Если второе, и метки времени могут идти не по порядку, то лучше map. Иначе лучше deque.

PS. Для бинарного поиска в deque можно воспользоваться стандартным алгоритмом lower_bound

volatile

Дата 14.2.2013, 17:52 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

wallstreet, я бы еше хранил не время а дату целиком, потому-что при переходе через полночь программа начнет глючить.
Согласитесь, странно будет, если работоспособность программы будет зависеть от времени суток . smile

wallstreet

Дата 26.2.2013, 14:15 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 153
Регистрация: 11.8.2011

Репутация: нет
Всего: нет

Цитата(xvr @ 14.2.2013, 17:12

)

Но тут надо учесть, что чаще происходит - модификация данных или поиск в них.

модификация происходит один раз, при их поступлении. А вот их анализ и вывод результата на форму происходит при получении любых данных, не обязательно только из этой таблицы. Т.е. я делаю вывод что лучше их конвертировать один раз при получении.

Цитата(xvr @ 14.2.2013, 17:12

)

Для бинарного поиска в deque можно воспользоваться стандартным алгоритмом lower_bound

честно признаться, не понял как передать туда итератор двумерной очереди. Точнее указатель именно на то поле двумерной deque в которой будет храниться время.

Цитата(volatile @ 14.2.2013, 17:52

)

я бы еше хранил не время а дату целиком

я решил сохранять время в формате time_t с предварительной инициализацией текущей даты.

Код


time_t rawtime;
struct tm *tm_info;

time(&rawtime);                       // записываем текущую дату
tm_info = localtime(&rawtime); // заполняем структуру tm текущей датой
tm_info->tm_hour = h;            //
tm_info->tm_min = m;            // заполняем время структуры tm, временем пришедших данных
tm_info->tm_sec = s;              // 
deq_struct.t = mktime(tm_info);

А вот код приема и конвертации данных:

Код


            if(AllDeals.size()==0)
                    {
                        AllDeals.resize(Tbl.size());

                        for ( int y=0; y<tbl_size; ++y)
                        { 
                            AllDeals[y].resize(columnCount);
                            for ( int x=0; x<columnCount; ++x)
                            {
                                if (x==1)
                                {
                                    sTime = Tbl[y][x].s.c_str();
                                    h[0] = sTime[0];
                                    h[1] = sTime[1];
                                    m[0] = sTime[3];
                                    m[1] = sTime[4];
                                    s[0] = sTime[6];
                                    s[1] = sTime[7];
                                    hour = atoi(h);
                                    min = atoi(m);
                                    sec = atoi(s);
                                    time(&rawtime);
                                    tmstruct = localtime(&rawtime);
                                    tmstruct->tm_hour = hour;
                                    tmstruct->tm_min = min;
                                    tmstruct->tm_sec = sec;
                                    rawtime = mktime(tmstruct);
                                    AllDeals[y][x].time = rawtime;
                                }
                                else
                                    AllDeals[y][x] = Tbl[y][x];
                            }
                        }
                    }
                    else 
                    {
                        int as = AllDeals.size()+1;
                        AllDeals.resize(as);
                        for ( int x=0; x<columnCount; ++x)
                        {
                            AllDeals[AllDeals.size()-1].resize(columnCount);
                            if (x==1)
                            {
                                sTime = Tbl[0][x].s.c_str();
                                h[0] = sTime[0];
                                h[1] = sTime[1];
                                m[0] = sTime[3];
                                m[1] = sTime[4];
                                s[0] = sTime[6];
                                s[1] = sTime[7];
                                hour = atoi(h);
                                min = atoi(m);
                                sec = atoi(s);
                                time(&rawtime);
                                tmstruct = localtime(&rawtime);
                                tmstruct->tm_hour = hour;
                                tmstruct->tm_min = min;
                                tmstruct->tm_sec = sec;
                                rawtime = mktime(tmstruct);
                                AllDeals[as-1][x].time = rawtime;
                            }
                            else
                                AllDeals[as-1][x] = Tbl[0][x];
                        }
                    }
                }

в таком случае выборка делается вот так

Код


nt StratFunc::TimeFind(std::deque<std::deque<Cell>> data, int iMinusMinuts)
{
    int StartPerIndex = 0;

    if(data.size()!=0)
    {
        int deque_size = data.size();
        int last_index =deque_size;
        int avg_index = 0;
        int first_index = 0;
        time_t tPresTime;
        time_t tTimeToFind = data[deque_size-1][1].time - iMinusMinuts * 60;
        while(first_index < last_index)
        {
            avg_index = first_index + (last_index - first_index) / 2;
            tPresTime = data[avg_index][1].time;
            tTimeToFind <= tPresTime ? last_index = avg_index : first_index = avg_index +1;
        }
        StartPerIndex = last_index;
    }
    
    return StartPerIndex;
}

xvr

Дата 26.2.2013, 18:08 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Цитата(wallstreet @ 26.2.2013, 14:15

)

честно признаться, не понял как передать туда итератор двумерной очереди.

Ну как то так -

Код


bool cmp_func(const std::deque<Cell>& data, time_t tm)
{
 return data[1].time < tm;
}

...
lower_bound(data.begin(),data.end(),tTimeToFind,cmp_func);
...

Если компилятор поддерживает С++11, то cmp_func можно заменить на лямбда функцию в месте вызова

Код


lower_bound(data.begin(),data.end(),tTimeToFind, 
 [](const std::deque<Cell>& data, time_t tm) {return return data[1].time < tm;}
);

volatile

Дата 27.2.2013, 00:02 (ссылка)

(голосов:1)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

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

wallstreet

Дата 27.2.2013, 14:46 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 153
Регистрация: 11.8.2011

Репутация: нет
Всего: нет

Цитата(xvr @ 26.2.2013, 18:08

)

Ну как то так -

суть уловил, но как мне первый аргумент представить в виде time_t? ведь Cell это структура, тип нужен её элемента (Cell.time);

Цитата

Error 4 error C2664: 'bool (const std::deque<_Ty> &,time_t)' : cannot convert parameter 2 from 'std::deque<_Ty>' to 'time_t'

Цитата(volatile @ 27.2.2013, 00:02

)

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

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

Код


                         else if(sTblName=="AllDeals")                 // пришли данные из таблице всех сделок
                {
                    int columnCount=7;                        // кол-во полей в таблице не меняется
                    struct tm *tmstruct;
                    time_t rawtime;
                    char h[2], m[2], s[2];
                    int hour, min, sec;
                    const char *sTime;
                    int tbl_size = Tbl.size();

                    if(AllDeals.size()==0)                    // если данные новые, то они приходят одним сообщением вся таблица
                    {                                         // поэтому необходимо их размещать по индексу пришедшей таблицы
                        AllDeals.resize(Tbl.size());
                                                              // двойной цикл, по двумерной очереди
                        for ( int y=0; y<tbl_size; ++y)       // бежим по записям
                        { 
                            AllDeals[y].resize(columnCount);
                            for ( int x=0; x<columnCount; ++x)// бежим по полям
                            {
                                if (x==1)                     // находим второе поле в котором время, что бы его конвертнуть
                                {
                                    sTime = Tbl[y][x].s.c_str();
                                    h[0] = sTime[0];
                                    h[1] = sTime[1];
                                    m[0] = sTime[3];
                                    m[1] = sTime[4];
                                    s[0] = sTime[6];
                                    s[1] = sTime[7];
                                    hour = atoi(h);
                                    min = atoi(m);
                                    sec = atoi(s);
                                    time(&rawtime);
                                    tmstruct = localtime(&rawtime);
                                    tmstruct->tm_hour = hour;
                                    tmstruct->tm_min = min;
                                    tmstruct->tm_sec = sec;
                                    rawtime = mktime(tmstruct);
                                    AllDeals[y][x].time = rawtime; // вносим время в формате time_t во 2е поле каждой записи
                                }
                                else
                                    AllDeals[y][x] = Tbl[y][x];    // вносим все остальное по индексу пришедшей таблицы
                            }
                        }
                    }
                    else                                   // здесь буду сохранять данные которые пришли уже во втором и последующих сообщениях. Их особенность
                    {                                      // в том, что приходят они построчно. Т.е. в очереди уже не таблица целиком, а одна запись.
                        int as = AllDeals.size()+1;
                        AllDeals.resize(as);               //ресайзим моё хранилище на одну запись больше
                        for ( int x=0; x<columnCount; ++x) // соответственно, цикл одномерный, т.к. данные пришли всего с одной строкой и
                        {                                  // мне необходимо просто скопировать эту строку в последнюю запись AllDeals
                            AllDeals[AllDeals.size()-1].resize(columnCount); 
                            if (x==1)
                            {
                                sTime = Tbl[0][x].s.c_str();
                                h[0] = sTime[0];
                                h[1] = sTime[1];
                                m[0] = sTime[3];
                                m[1] = sTime[4];
                                s[0] = sTime[6];
                                s[1] = sTime[7];
                                hour = atoi(h);
                                min = atoi(m);
                                sec = atoi(s);
                                time(&rawtime);
                                tmstruct = localtime(&rawtime);
                                tmstruct->tm_hour = hour;
                                tmstruct->tm_min = min;
                                tmstruct->tm_sec = sec;
                                rawtime = mktime(tmstruct);
                                AllDeals[as-1][x].time = rawtime; // вносим сконвертированное время во 2е поле 
                            }
                            else
                                AllDeals[as-1][x] = Tbl[0][x];    // копируем всё остальное
                        }
                    }
                }

как его можно сделать более оптимальным?

Это сообщение отредактировал(а) wallstreet - 27.2.2013, 15:36

xvr

Дата 27.2.2013, 15:46 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Комодератор
Сообщений: 7046
Регистрация: 28.8.2007
Где: Дублин, Ирландия

Репутация: 60
Всего: 223

Цитата(wallstreet @ 27.2.2013, 14:46

)

суть уловил, но как мне первый аргумент представить в виде time_t?

Первый не надо - функция сравнения сама достанет нужное поле

Цитата(wallstreet @ 27.2.2013, 14:46

)

Error 4 error C2664: 'bool (const std::deque<_Ty> &,time_t)' : cannot convert parameter 2 from 'std::deque<_Ty>' to 'time_t'

Судя по сообщению вы подали 3м параметром в lower_bound сам deque вместо time_t (tTimeToFind)

wallstreet

Дата 27.2.2013, 15:53 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 153
Регистрация: 11.8.2011

Репутация: нет
Всего: нет

Цитата(xvr @ 27.2.2013, 15:46

)

Судя по сообщению вы подали 3м параметром в lower_bound сам deque вместо time_t (tTimeToFind)

да вроде нет, не передавал?!?!

Код


const time_t tTimeToFind = AllDealsTbl[AllDealsTbl.size()-1][0].t - iMinusPer * 60;
low = std::lower_bound(AllDealsTbl.begin(), AllDealsTbl.end(), tTimeToFind, cmp_func);

....
bool cmp_func(const std::deque<MS_1>& data, time_t tm)
{
    return data[0].t < tm;
}
....

volatile

Дата 27.2.2013, 16:04 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2107
Регистрация: 7.1.2011

Репутация: 37
Всего: 85

Цитата(wallstreet @ 27.2.2013, 14:46

)

здесь буду сохранять данные которые пришли уже во втором и последующих сообщениях

wallstreet, первое что надо сделать, это общую процедуру для включения одной записи, и для включения нескольких.
просто при одной размер равен 1.
зачем дублировать?

Чтоб что-то еще подсказать, мне не понятно:
зачем у вас таблица двумерная, на словах можете объяснить?
почему время храницца только в blabla[][1].time, а что находицца например в blabla[][0].time, или в blabla[][2].time ?

wallstreet

Дата 27.2.2013, 16:23 (ссылка)

(нет голосов)

Загрузка ...

Бывалый

Профиль
Группа: Участник
Сообщений: 153
Регистрация: 11.8.2011

Репутация: нет
Всего: нет

Цитата(volatile @ 27.2.2013, 16:04

)

почему время храницца только в blabla[][1].time, а что находицца например в blabla[][0].time, или в blabla[][2].time ?

таблица состоит из 7 полей:
Номер записи; Время; Эмитент; Цена; Объем; Операция
Тип short time_t std::string double double std::string

первая запись в таблице всегда строка.
Во всех проме первой записи в поле, к примеру цены, всегда в структуру заполняется только struct.d (т.е. double) все остальные не инициализируются

Это сообщение отредактировал(а) wallstreet - 27.2.2013, 16:49

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »