Заполняем vector<vector<string> >
От: igna Россия  
Дата: 12.08.09 05:52
Оценка:
Пример внизу заполняет vector<vector<string> > беря значения из некой коллекции:

vector<vector<string> > text_to_vvs(Text const* const text)
{
    vector<vector<string> > vvs;
    for (Sentence const* sent = text->FirstSentence(); sent; sent = sent->Next()) {
        vector<string> vs;
        for (Word const* w = sent->FirstWord(); w; w = w->Next())
            vs.push_back(w->Str()); // w->Str() returns char const*
        vvs.push_back(vs);
    }
    return vvs;
}


Пример реализован прямолинейно, а как бы вы написали?
Re: Заполняем vector<vector<string> >
От: Alexander G Украина  
Дата: 12.08.09 06:03
Оценка:
Здравствуйте, igna, Вы писали:

I>Пример внизу заполняет vector<vector<string> > беря значения из некой коллекции:


I>Пример реализован прямолинейно, а как бы вы написали?


Можно сэкономить на одном из копирований.

vector<vector<string> > text_to_vvs(Text const* const text)
{
    vector<vector<string> > vvs;
    for (Sentence const* sent = text->FirstSentence(); sent; sent = sent->Next()) {
        vvs.push_back(vector<string>());
        vector<string> & vs = vvs.back();
        for (Word const* w = sent->FirstWord(); w; w = w->Next())
            vs.push_back(w->Str()); // w->Str() returns char const*
    }
    return vvs;
}


Можно определить размер и зарезервить, сэкономить на других копированиях.
Русский военный корабль идёт ко дну!
Re: Заполняем vector<vector<string> >
От: Аноним  
Дата: 12.08.09 06:44
Оценка:
Здравствуйте, igna, Вы писали:

I>Пример внизу заполняет vector<vector<string> > беря значения из некой коллекции:


I>
I>vector<vector<string> > text_to_vvs(Text const* const text)
I>{
I>    vector<vector<string> > vvs;
I>    for (Sentence const* sent = text->FirstSentence(); sent; sent = sent->Next()) {
I>        vector<string> vs;
I>        for (Word const* w = sent->FirstWord(); w; w = w->Next())
I>            vs.push_back(w->Str()); // w->Str() returns char const*
I>        vvs.push_back(vs);
I>    }
I>    return vvs;
I>}
I>


I>Пример реализован прямолинейно, а как бы вы написали?



I>
I>size_t sentence_to_vs(vector<string>& vs,Sentence const* sent)
I>{
I>    size_t count=0;
I>    for (Word const* w = sent->FirstWord(); w; w = w->Next(),count++)
I>       vs.push_back(w->Str()); // w->Str() returns char const*
I>    return count;
I>}


I>size_t text_to_vvs(vector<vector<string> >& vvs,Text const* const text)
I>{
I>    
I>    size_t count=0;
I>    for (Sentence const* sent = text->FirstSentence(); sent; sent = sent->Next()) {
I>        vector<string>& vs = *vvs.insert(vvs.end(),vector<string>()); 
I>        count+=sentence_to_vs(vs,sent);
I>    }
I>    return count;
I>}
I>
Re: Заполняем vector<vector<string> >
От: _Dreamer Россия  
Дата: 12.08.09 06:48
Оценка:
Здравствуйте, igna, Вы писали:

I>Пример внизу заполняет vector<vector<string> > беря значения из некой коллекции:

I>Пример реализован прямолинейно, а как бы вы написали?

а NRVO в Вашем компиляторе есть ? оно здесь срабатывает ?
а то я бы написал влоб —
void text_to_vvs(Text const* const text, vector< vector< string > >& result);

// или 
vector< vector< string > >& text_to_vvs(Text const* const text, vector< vector< string > >& result);
Re: Заполняем vector<vector<string> >
От: Юрий Жмеренецкий ICQ 380412032
Дата: 12.08.09 07:00
Оценка:
Здравствуйте, igna, Вы писали:

I>Пример внизу заполняет vector<vector<string> > беря значения из некой коллекции:


I>
I>vector<vector<string> > text_to_vvs(Text const* const text)
I>{
I>    vector<vector<string> > vvs;
I>    for (Sentence const* sent = text->FirstSentence(); sent; sent = sent->Next()) {
I>        vector<string> vs;
I>        for (Word const* w = sent->FirstWord(); w; w = w->Next())
I>            vs.push_back(w->Str()); // w->Str() returns char const*
I>        vvs.push_back(vs);
I>    }
I>    return vvs;
I>}
I>


I>Пример реализован прямолинейно, а как бы вы написали?


Скорее всего без возврата по значению.
Re: Заполняем vector<vector<string> >
От: sokel Россия  
Дата: 12.08.09 07:45
Оценка:
Здравствуйте, igna, Вы писали:

I>Пример реализован прямолинейно, а как бы вы написали?


При добавлении очередного предложения произойдет реаллокация вектора и все ранее добавленные будут копироваться. По значению. Возможно, лучше будет не vector<vector>, a vector<vector*>.
Re[2]: Заполняем vector<vector<string> >
От: igna Россия  
Дата: 12.08.09 07:57
Оценка:
Здравствуйте, Alexander G, Вы писали:

AG>Можно сэкономить на одном из копирований.


AG>vector<vector<string> > text_to_vvs(Text const* const text)
AG>{
AG>    vector<vector<string> > vvs;
AG>    for (Sentence const* sent = text->FirstSentence(); sent; sent = sent->Next()) {
AG>        vvs.push_back(vector<string>());
AG>        vector<string> & vs = vvs.back();
AG>        for (Word const* w = sent->FirstWord(); w; w = w->Next())
AG>            vs.push_back(w->Str()); // w->Str() returns char const*
AG>    }
AG>    return vvs;
AG>}


Ты так пишешь всегда или только тогда, когда нужно cоптимизировать?
Re[2]: Заполняем vector<vector<string> >
От: igna Россия  
Дата: 12.08.09 08:08
Оценка:
Здравствуйте, _Dreamer, Вы писали:

_D>а NRVO в Вашем компиляторе есть ? оно здесь срабатывает ?


Стараюсь избегать копирования объектов там, где это не приводит к значительному усложнению кода; но не для того, чтобы выполнить оптимизацию, которую разрешено выполнять компилятору.

(Естественно, это не относится к случаю, когда оптимизация действительно нужна.)
Re[2]: Заполняем vector<vector<string> >
От: igna Россия  
Дата: 12.08.09 08:16
Оценка:
Здравствуйте, Юрий Жмеренецкий, Вы писали:

ЮЖ>Скорее всего без возврата по значению.


Почему? В моем примере как раз создание лишних копий vector<string> не может быть соптимизировано компилятором, а с возвратом по значению с точки зрения языка все в порядке, компилятор вправе не создавать копии. Проверять поведение компилятора до выяснения необходимости оптимизации в данном месте не стоит.
Re[2]: Заполняем vector<vector<string> >
От: igna Россия  
Дата: 12.08.09 08:25
Оценка:
Здравствуйте, Аноним, Вы писали:

    return count;


Зачем count?
Re[2]: Заполняем vector<vector<string> >
От: igna Россия  
Дата: 12.08.09 08:29
Оценка:
Здравствуйте, sokel, Вы писали:

S>При добавлении очередного предложения произойдет реаллокация вектора и все ранее добавленные будут копироваться. По значению. Возможно, лучше будет не vector<vector>, a vector<vector*>.


Возможно. А возможно, что это копирование по значению будет производится 1 раз при запуске программы, а косвенный доступ 1000000 раз.
Re: Заполняем vector<vector<string> >
От: IROV..  
Дата: 12.08.09 08:45
Оценка:
Здравствуйте, igna, Вы писали:

I>Пример внизу заполняет vector<vector<string> > беря значения из некой коллекции:


I>
I>vector<vector<string> > text_to_vvs(Text const* const text)
I>{
I>    vector<vector<string> > vvs;
I>    for (Sentence const* sent = text->FirstSentence(); sent; sent = sent->Next()) {
I>        vector<string> vs;
I>        for (Word const* w = sent->FirstWord(); w; w = w->Next())
I>            vs.push_back(w->Str()); // w->Str() returns char const*
I>        vvs.push_back(vs);
I>    }
I>    return vvs;
I>}
I>


I>Пример реализован прямолинейно, а как бы вы написали?


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

я не волшебник, я только учусь!
Re[2]: Заполняем vector<vector<string> >
От: igna Россия  
Дата: 12.08.09 08:55
Оценка:
Здравствуйте, IROV.., Вы писали:

IRO>Если итерация быстрая, и элементов не слишком много.

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

Ты бы так и сделал с самого начала, еще до проверки того, что такая экономия даст? То есть "посчитать размер, сделать ресайз" это не преждевременная оптимизизация, а избегание преждевременной пессимизации?
Re[3]: Заполняем vector<vector<string> >
От: Alexander G Украина  
Дата: 12.08.09 08:56
Оценка:
Здравствуйте, igna, Вы писали:

I>Ты так пишешь всегда или только тогда, когда нужно cоптимизировать?


Обычно я пишу именно как приведено в исходном сообщении. (разве что w != NULL явно делаю).

С оптимизацией — оборачиваю потенциально большие контейнеры в shared_ptr, но и в этом случае push_back нулевого указателя дешевле ненулевого.
Русский военный корабль идёт ко дну!
Re[3]: Заполняем vector<vector<string> >
От: IROV..  
Дата: 12.08.09 09:48
Оценка:
Здравствуйте, igna, Вы писали:

I>Ты бы так и сделал с самого начала, еще до проверки того, что такая экономия даст? То есть "посчитать размер, сделать ресайз" это не преждевременная оптимизизация, а избегание преждевременной пессимизации?


Коротко:
— Да, обязательно, если бы знал что вычисление размера не очень сложная функция(А я почти уверен что оно так и есть)
— "а избегание преждевременной пессимизации?" — В точку!

Рассуждения:

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

Нужно ли здесь оптимизировать? Раз выложил пост в форум значит — тревожит

вызов New это всегда скверно, копирование тоже скверно, но уже гораздо менее.

Узнать размер у range заданых двумя итераторами тоже скверно.

Теперь вот рассуждаем что из этих зол страшнее.

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

vector<string> vs;
for (Word const* w = sent->FirstWord(); w; w = w->Next())
  vs.push_back(w->Str()); // Ведь даже сдесь при реалокации мы будем перегенерировать новые стринги по несколько раз.
vvs.push_back(vs); //Здесь еще хуже мало того что мы будем копировать вектор в котором содержится "вектор чаров", так мы еще можем попасть на реалокацию масива.



на больших текстовых данных данная оптимизация даст большой бенифит. я не удевлюсь если будет порядка х10
я не волшебник, я только учусь!
Re[3]: Заполняем vector<vector<string> >
От: IROV..  
Дата: 12.08.09 09:51
Оценка:
vector<vector<string> > text_to_vvs(Text const* const text)


Правило хорошего тона,

void text_to_vvs(Text const* const text, vector<vector<string> > & vvs )


З.Ы. не использовать шаблоные типы напрямую (заменить на typedef)

я не волшебник, я только учусь!
Re[3]: Заполняем vector<vector<string> >
От: Юрий Жмеренецкий ICQ 380412032
Дата: 12.08.09 09:58
Оценка:
Здравствуйте, igna, Вы писали:

I>Здравствуйте, Юрий Жмеренецкий, Вы писали:


ЮЖ>>Скорее всего без возврата по значению.


I>Почему?


Я предполагаю что vector<vector<string> > будет членом в каком-либо классе, иначе такое "переливание" выглядит странным. Дальше сразу встает вопрос о коировании объектов такого класса. Вот если бы было так:

struct A : noncopyable
{
  A(Text const* const text) : vec(text_to_vvs(text))
  {}

  //...
private:
  vector<vector<string> > vec;
}


I>В моем примере как раз создание лишних копий vector<string> не может быть соптимизировано компилятором, а с возвратом по значению с точки зрения языка все в порядке, компилятор вправе не создавать копии. Проверять поведение компилятора до выяснения необходимости оптимизации в данном месте не стоит.


Для тяжелых объектов, имхо, должно быть четко определено — кто, и когда является их владельцем (ownership semantics). В случае со 'struct A' выше все понятно — время жизни владельца совпадает с временем жизни подобъекта. Еще остаются случаи 'владеет сейчас' — если владелец разрушен, то и разрушается подобъект, но подобъект можно изменить на другой, забрав у него владение предыдущим, и 'владелец не определен' — это в чистом виде boost::shared_ptr, 'подобъект' (здесь уже не совсем корректный термин) разрушается в тот момент, когда будут разрушены все кто держит ссылку.

Случаи 'один владелец' и 'владеет сейчас' можно реализовать на swap'ах, но тогда семантика становется менее ясной:

// Тот факт что здесь передается владение нужно документировать
// явно, либо смотреть реализацию для выяснения.
A::A(vector<vector<string> >& v)


У вариант со 'struct A' есть еще одна потенциальная проблема: явная связь с text_to_vvs. Это придет к тому что, например, для тестировани функциональности 'A' необходимо будет иметь фейковую реализацию 'Text' (или специально подготовленный объект, а это потянет связанные с 'Text' части), хотя для тестирования достаточно объекта 'vector<vector<string> >'.

text_to_vvs в данном случае я скорее рассматриваю как factory с приблизительно таким видом:

auto_ptr<vector<vector<string> > > text_to_vvs(/*...*/)


Затраты на один вызов 'new' по сравнению с тем что происходит в text_to_vvs — мизерны, присутствует гарантия отсутствия deep copy и т.п. Если заменить auto_ptr на boost::unique_ptr, то семантика становится еще более ясной, + исчезают проблемы, связанные с std::auto_ptr.

PS. Ожидался, наверное ответ на вопрос "как заполнить vector<vector<string> >", но присутствие text_to_vvs увело в другую сторону.
Re[2]: Заполняем vector<vector<string> >
От: IROV..  
Дата: 12.08.09 09:58
Оценка:
Здравствуйте, IROV.., Вы писали:

Сорри не компилировал, писал по приборам

void text_to_vvs( Text const* const text, vector<vector<string> > & vvs )
{
    std::size_t size = 0;
    for (Sentence const* sent = text->FirstSentence(); sent; sent = sent->Next()) 
    {
        ++size;
    }

    vvs.resize( size );

    for( vvs::iterator 
        it = vvs.begin(),
        it_end = vvs.end();
    it != it_end;
    ++it )
    {
        it->resize( size );
    }

    vvs::iterator it_place = vvs.begin();

    for (Sentence const* sent = text->FirstSentence(); sent; sent = sent->Next(), ++it_place ) 
    {
        vvs::value_type::iterator it_place_string = it_place->begin();

        for (Word const* w = sent->FirstWord(); w; w = w->Next(), ++it_place_string )
        {
            *it_place_string = w->Str();
        }
    }
}
я не волшебник, я только учусь!
Re[3]: Заполняем vector<vector<string> >
От: IROV..  
Дата: 12.08.09 10:01
Оценка:
Здравствуйте, igna, Вы писали:

I>Здравствуйте, Юрий Жмеренецкий, Вы писали:


ЮЖ>>Скорее всего без возврата по значению.


I>Почему? В моем примере как раз создание лишних копий vector<string> не может быть соптимизировано компилятором, а с возвратом по значению с точки зрения языка все в порядке, компилятор вправе не создавать копии. Проверять поведение компилятора до выяснения необходимости оптимизации в данном месте не стоит.


http://www.rsdn.ru/forum/cpp/3501445.1.aspx
Автор: IROV..
Дата: 12.08.09


+ Разьясню, вектор который мы туда передадим может уже быть за ресайзеный(выделено памяти) и тогда внутрения функция ресайз (в тру версии) не будет ничего делать а проскипается, вот эту оптимизацию компилятор в твоем случаее не сделает.

я не волшебник, я только учусь!
Re[4]: Заполняем vector<vector<string> >
От: igna Россия  
Дата: 12.08.09 10:03
Оценка:
Здравствуйте, IROV.., Вы писали:

IRO>Правило хорошего тона,


IRO>void text_to_vvs(Text const* const text, vector<vector<string> > & vvs )

Это правило возможно устарело. VC++, GCC и Intel C++ поддерживают RVO: http://en.wikipedia.org/wiki/Return_value_optimization

IRO>З.Ы. не использовать шаблоные типы напрямую (заменить на typedef)


Так. А это почему?
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.