Здравствуйте, 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>
Здравствуйте, igna, Вы писали:
I>Пример внизу заполняет vector<vector<string> > беря значения из некой коллекции: I>Пример реализован прямолинейно, а как бы вы написали?
а NRVO в Вашем компиляторе есть ? оно здесь срабатывает ?
а то я бы написал влоб —
Здравствуйте, igna, Вы писали:
I>Пример реализован прямолинейно, а как бы вы написали?
При добавлении очередного предложения произойдет реаллокация вектора и все ранее добавленные будут копироваться. По значению. Возможно, лучше будет не vector<vector>, a vector<vector*>.
Здравствуйте, _Dreamer, Вы писали:
_D>а NRVO в Вашем компиляторе есть ? оно здесь срабатывает ?
Стараюсь избегать копирования объектов там, где это не приводит к значительному усложнению кода; но не для того, чтобы выполнить оптимизацию, которую разрешено выполнять компилятору.
(Естественно, это не относится к случаю, когда оптимизация действительно нужна.)
Здравствуйте, Юрий Жмеренецкий, Вы писали:
ЮЖ>Скорее всего без возврата по значению.
Почему? В моем примере как раз создание лишних копий vector<string> не может быть соптимизировано компилятором, а с возвратом по значению с точки зрения языка все в порядке, компилятор вправе не создавать копии. Проверять поведение компилятора до выяснения необходимости оптимизации в данном месте не стоит.
Здравствуйте, sokel, Вы писали:
S>При добавлении очередного предложения произойдет реаллокация вектора и все ранее добавленные будут копироваться. По значению. Возможно, лучше будет не vector<vector>, a vector<vector*>.
Возможно. А возможно, что это копирование по значению будет производится 1 раз при запуске программы, а косвенный доступ 1000000 раз.
Здравствуйте, 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>Пример реализован прямолинейно, а как бы вы написали?
Если итерация быстрая, и элементов не слишком много.
То думаю будет дешевле посчитать размер, сделать ресайз.
а потом заполнять без дополнительных реалокаций и копирований.
Здравствуйте, IROV.., Вы писали:
IRO>Если итерация быстрая, и элементов не слишком много. IRO>То думаю будет дешевле посчитать размер, сделать ресайз. IRO>а потом заполнять без дополнительных реалокаций и копирований.
Ты бы так и сделал с самого начала, еще до проверки того, что такая экономия даст? То есть "посчитать размер, сделать ресайз" это не преждевременная оптимизизация, а избегание преждевременной пессимизации?
Здравствуйте, 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
Здравствуйте, igna, Вы писали:
I>Здравствуйте, Юрий Жмеренецкий, Вы писали:
ЮЖ>>Скорее всего без возврата по значению.
I>Почему?
Я предполагаю что vector<vector<string> > будет членом в каком-либо классе, иначе такое "переливание" выглядит странным. Дальше сразу встает вопрос о коировании объектов такого класса. Вот если бы было так:
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 с приблизительно таким видом:
Затраты на один вызов 'new' по сравнению с тем что происходит в text_to_vvs — мизерны, присутствует гарантия отсутствия deep copy и т.п. Если заменить auto_ptr на boost::unique_ptr, то семантика становится еще более ясной, + исчезают проблемы, связанные с std::auto_ptr.
PS. Ожидался, наверное ответ на вопрос "как заполнить vector<vector<string> >", но присутствие text_to_vvs увело в другую сторону.
Здравствуйте, igna, Вы писали:
I>Здравствуйте, Юрий Жмеренецкий, Вы писали:
ЮЖ>>Скорее всего без возврата по значению.
I>Почему? В моем примере как раз создание лишних копий vector<string> не может быть соптимизировано компилятором, а с возвратом по значению с точки зрения языка все в порядке, компилятор вправе не создавать копии. Проверять поведение компилятора до выяснения необходимости оптимизации в данном месте не стоит.
+ Разьясню, вектор который мы туда передадим может уже быть за ресайзеный(выделено памяти) и тогда внутрения функция ресайз (в тру версии) не будет ничего делать а проскипается, вот эту оптимизацию компилятор в твоем случаее не сделает.