Russian Qt Forum

Qt => Общие вопросы => Тема начата: xintrea от Ноябрь 12, 2014, 11:12



Название: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: xintrea от Ноябрь 12, 2014, 11:12
Долгое время пользовался таким наивным кодом для преобразований:

Код:
void convertByteArrayToVector(const QByteArray &qba, vector<unsigned char> &vec)
{
 unsigned int size=qba.size();

 vec.resize(size, 0);

 for(unsigned int i=0; i<size; i++)
  vec[i]=(unsigned char)qba[i];
}


void convertVectorToByteArray(const vector<unsigned char> &vec, QByteArray &qba)
{
 unsigned int size=vec.size();

 qba.resize(size);

 for(unsigned int i=0; i<size; i++)
  qba[i]=(unsigned char)vec[i];
}

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


QByteArray в вектор

Как я понимаю, самый правильный путь для преобразования QByteArray в вектор - это получить представление QByteArray в виде char-массива, потом этот char-массив преобразовать в вектор (примечание - вектор уже существует, загонять char-массив в вектор через конструктор нельзя).

Я нашел такой код преобразования массива char в вектор:

Код:
vector<unsigned char> v;
v.resize(100);
memcpy(&v[0], someArrayOfSize100, 100 * sizeof(unsigned char));

Но не хочу его использовать, так как вектор - это более сложная структура чем массив char, у вектора элементы в памяти не обязательно идут друг за другом, и вот это memcpy() выглядит очень подозрительно.

Вопрос: как правильно и быстро преобразовать массив char в вектор char-ов?


Вектор в QByteArray

Обратная задача. Надо из вектора получить представление в виде массива char, и загнать его в QByteArray через метод fromRawData(). Основной вопрос в получении массива char.

Интернет предлагает:

Код:
vector<unsigned char> buf;
...
(char *)(&buf[0])

Или:

Код:
vector<unsigned char> buf;
...
unsigned char *p = &*buf.begin();

Но тут тоже вопрос - вектор не гарантирует последовательность элементов в памяти, как это так лихо получают ссылку на первый элемент и работают с данными?


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: Пантер от Ноябрь 12, 2014, 11:16
Почему это не гарантирует? На сколько я помню, стандарт гарантирует расположение элементов вектора последовательно в памятию Поэтому юзай как написал и не парься.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: vulko от Ноябрь 12, 2014, 12:14
Цитировать
Код:
vector<unsigned char> v;
v.resize(100);
memcpy(&v[0], someArrayOfSize100, 100 * sizeof(unsigned char));

так точно делать нельзя. вектор это не примитивный тип данных и попахивает memory corruption'ом.

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

как вариант:
Код:
vector<int> dataVec;

int dataArray[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
unsigned dataArraySize = sizeof(dataArray) / sizeof(int);

// Method 1: Copy the array to the vector using back_inserter.
{
    copy(&dataArray[0], &dataArray[dataArraySize], back_inserter(dataVec));
}

// Method 2: Same as 1 but pre-extend the vector by the size of the array using reserve
{
    dataVec.reserve(dataVec.size() + dataArraySize);
    copy(&dataArray[0], &dataArray[dataArraySize], back_inserter(dataVec));
}

// Method 3: Memcpy
{
    dataVec.resize(dataVec.size() + dataArraySize);
    memcpy(&dataVec[dataVec.size() - dataArraySize], &dataArray[0], dataArraySize * sizeof(int));
}

// Method 4: vector::insert
{
    dataVec.insert(dataVec.end(), &dataArray[0], &dataArray[dataArraySize]);
}

// Method 5: vector + vector
{
    vector<int> dataVec2(&dataArray[0], &dataArray[dataArraySize]);
    dataVec.insert(dataVec.end(), dataVec2.begin(), dataVec2.end());
}


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обр
Отправлено: Пантер от Ноябрь 12, 2014, 12:21
Можно еще заюзать http://en.cppreference.com/w/cpp/container/vector/data
На счет размещения элементов:
Цитировать
The elements are stored contiguously, which means that elements can be accessed not only through iterators, but also using offsets on regular pointers to elements. This means that a pointer to an element of a vector may be passed to any function that expects a pointer to an element of an array.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: m_ax от Ноябрь 12, 2014, 12:30
Цитировать
так точно делать нельзя.
С вектором так делать можно) Но можно это сделать и элегантнее)

Цитировать
// Method 1: Copy the array to the vector using back_inserter.
{
    copy(&dataArray[0], &dataArray[dataArraySize], back_inserter(dataVec));
}
Вот так делать точно не стоит.. Здесь на каждое итерирование back_inserter будет заново создавать новый блок для вектора, что очень не дёшево, и к тому же дефрагментируя память..
Гораздо логичнее делать так:
Код
C++ (Qt)
dataVec.assign(dataArray, dataArray+dataArraySize);
 

Ну и т.д. и т.п..

Цитировать
Долгое время пользовался таким наивным кодом для преобразований
Я бы эти две функции проще бы написал:
Код
C++ (Qt)
std::vector<char> convert(const QByteArray &b)
{
   return std::vector<char>(b.begin(), b.end());
}
 
QByteArray convert(const std::vector<char>& v)
{
   return QByteArray(v.data(), v.size());
}
 
Этот вариант раза в два будет быстрее, изначального варианта..


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: vulko от Ноябрь 12, 2014, 13:35
Цитировать
так точно делать нельзя.
С вектором так делать можно) Но можно это сделать и элегантнее)

&v
  • [/b], индекс не разглядел. Да, так и правда можно делать.


    Код:
    std::vector<char> convert(const QByteArray &b)
    {
        return std::vector<char>(b.begin(), b.end());
    }

    2 раза копировать будет.
    лучше по ссылке, либо без отдельной функции.

    ещё интересно как работает
    std::vector<char>(b.begin(), b.end())

    не быстрее ли сделать memcpy?


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: m_ax от Ноябрь 12, 2014, 13:39
Цитировать
2 раза копировать будет.
Нет, в данном случае только один)

Два раза было бы, при такой реализации:
Код
C++ (Qt)
std::vector<char> convert(const QByteArray &b)
{
   std::vector<char> tmp(b.begin(), b.end());
   return tmp;
}
 


Цитировать
std::vector<char>(b.begin(), b.end())
Не исключено, что внутри там как раз memcpu или что-то аналогичное используется)


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: vulko от Ноябрь 12, 2014, 13:43
Цитировать
2 раза копировать будет.
Нет, в данном случае только один)

Два раза было бы, при такой реализации:
Код
C++ (Qt)
std::vector<char> convert(const QByteArray &b)
{
   std::vector<char> tmp(b.begin(), b.end());
   return tmp;
}
 


одно и то же.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: m_ax от Ноябрь 12, 2014, 13:58
Цитировать
одно и то же.
Неееет) Не то же самое)

Код
C++ (Qt)
return std::vector<char>(b.begin(), b.end());
 
На первый взгляд похоже на вызов конструктора, но это не так..
Это синтаксис создания временного объекта: создать временный вектор и вернуть его.

В отличии от
Код
C++ (Qt)
std::vector<char> tmp(b.begin(), b.end());
   return tmp;
 
где происходит следующее: сначала будет создан объект tmp с вызовом конструктора, затем копирующий конструктор скопирует tmp в область памяти вне функции. Далее, для tmp будет вызван деструктор.

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

Это примерно также, как если бы мы написали:
Код
C++ (Qt)
std::vector<char> tmp(b.begin(), b.end());
   return std::move(tmp);
 


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: vulko от Ноябрь 12, 2014, 14:03
Цитировать
одно и то же.
Неееет) Не то же самое)

Код
C++ (Qt)
return std::vector<char>(b.begin(), b.end());
 
На первый взгляд похоже на вызов конструктора, но это не так..
Это синтаксис создания временного объекта: создать временный вектор и вернуть его.

ну ты же сам пишешь, что создается временный объект. а потом он копируется.

"это вам не это" (с)
...в смысле не жаба, где все типы, кроме примитивных, ссылочные.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: m_ax от Ноябрь 12, 2014, 14:08
Цитировать
ну ты же сам пишешь, что создается временный объект. а потом он копируется.
Я пишу: когда компилятор встречает такую конструкцию, то она означает: "создать временный объект и вернуть его".
а далее:
Цитировать
компилятор строит объект непосредственно в области памяти возвращаемого значения. Для этого достаточно только вызова конструктора, копирующий конструктор не используется, а деструктор не вызывается, потому что локальный объект реально не создаётся.

А вообще загуглите: "оптимизация возвращаемого значения с++"


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: vulko от Ноябрь 12, 2014, 14:13
Цитировать
ну ты же сам пишешь, что создается временный объект. а потом он копируется.
Я пишу: когда компилятор встречает такую конструкцию, то она означает: "создать временный объект и вернуть его".
а далее:
Цитировать
компилятор строит объект непосредственно в области памяти возвращаемого значения. Для этого достаточно только вызова конструктора, копирующий конструктор не используется, а деструктор не вызывается, потому что локальный объект реально не создаётся.

А вообще загуглите: "оптимизация возвращаемого значения с++"

http://msdn.microsoft.com/en-us/library/ms364057(vs.80).aspx

слишком много но.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: vulko от Ноябрь 12, 2014, 14:21
Не люблю вики, но все же:

http://en.wikipedia.org/wiki/Return_value_optimization#Summary

Цитировать
Depending upon the compiler, and that compiler's settings...

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


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: m_ax от Ноябрь 12, 2014, 14:29
Цитировать
http://msdn.microsoft.com/en-us/library/ms364057(vs.80).aspx

слишком много но.
Это ссылка не совсем о том, о чём я говорил..
В тех примерах нигде не было использована оптимизация возвращаемого значения (стандарт с++):
Код
C++ (Qt)
return vector(...)
 
Там говориться лишь о том, как MSVC оптимизирует такую ситуацию:
Код
C++ (Qt)
vector tmp;
return tmp;
 
 

Но это разные вещи..



Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: vulko от Ноябрь 12, 2014, 14:35
Цитировать
http://msdn.microsoft.com/en-us/library/ms364057(vs.80).aspx

слишком много но.
Это ссылка не совсем о том, о чём я говорил..
В тех примерах нигде не было использована оптимизация возвращаемого значения (стандарт с++):
Код
C++ (Qt)
return vector(...)
 
Там говориться лишь о том, как MSVC оптимизирует такую ситуацию:
Код
C++ (Qt)
vector tmp;
return tmp;
 
 

Но это разные вещи..



это NRVO, т.е. Named RVO. Работает также, только для случаев
type fname() {
    type a;
    return a;
}

Читай выше приводил вырезки из вики. Это не стандарт. Стандарт разрешает компилятору так делать, но не обязывает.
При этом совсем не обязательно что без флагов оптимизации оно будет работать. И совсем не обязательно что в любом компиляторе одинаково.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: m_ax от Ноябрь 12, 2014, 14:53
RVO умеют практически все компиляторы (в отличии от NRVO), это во-первых..
Во-вторых, зачем писать две строчки вместо одной..?

 
Цитировать
зачем на пустом месте создавать потенциальный гемор, когда можно прекрасно обойтись без отдельной функции, либо с параметром ссылкой на вектор.
Никакого гемора никто не создаёт, как и потенциальных граблей, в данном конкретном примере.. (с RVO). 
Потом, мне удобней написать так:
Код
C++ (Qt)
type x = func();
 
   
чем так:
Код
C++ (Qt)
type x;
func(x);
 
Первый вариант более прозрачный и лаконичный..


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обр
Отправлено: vulko от Ноябрь 12, 2014, 15:04
RVO умеют практически все компиляторы (в отличии от NRVO), это во-первых..
Во-вторых, зачем писать две строчки вместо одной..?

 
Цитировать
зачем на пустом месте создавать потенциальный гемор, когда можно прекрасно обойтись без отдельной функции, либо с параметром ссылкой на вектор.
Никакого гемора никто не создаёт, как и потенциальных граблей, в данном конкретном примере.. (с RVO). 
Потом, мне удобней написать так:
Код
C++ (Qt)
type x = func();
 
   
чем так:
Код
C++ (Qt)
type x;
func(x);
 
Первый вариант более прозрачный и лаконичный..

почти != все
с какими флагами оптимизации они это умеют? все ли при одной и той же оптимизации будут делать оптимизацию return value?


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обр
Отправлено: m_ax от Ноябрь 12, 2014, 19:48
Цитировать
почти != все
Это понятно.. какие-нибудь допотопные, возможно и не умеют RVO..
Но сейчас это уже не актуально. Вы делаете из мухи слона..

Если кто-то страдает RVO-фобией, то пожалуйста, передавайте объект через ссылку.. Мне в общем то фиолетово)

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

И если уж разговор зашёл об оптимизации, то, я надеюсь, вы 7(семь) раз подумаете прежде чем давать рекомендации типа:
Код
C++ (Qt)
copy(&dataArray[0], &dataArray[dataArraySize], back_inserter(dataVec));
 
:)
 


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: __Heaven__ от Ноябрь 13, 2014, 09:38
Не знал раньше про rvo и nrvo. Было интересно.
На мой взгляд оптимальным вариантом будет использование memcpy. Быстрее него всё равно ничего не напишешь. И голова не болит о том, как и какая строчка будет воспринята каким-либо компилятором. Или я ошибаюсь?


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: vulko от Ноябрь 13, 2014, 09:42
Не знал раньше про rvo и nrvo. Было интересно.
На мой взгляд оптимальным вариантом будет использование memcpy. Быстрее него всё равно ничего не напишешь. И голова не болит о том, как и какая строчка будет воспринята каким-либо компилятором. Или я ошибаюсь?

memcpy + обычный массив будут работать быстрее всегда.
тем более что затык в этом месте.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: RSATom от Ноябрь 13, 2014, 10:04
проблема в том что для того чтобы использовать memcpy в связке с  std::vector необходимо предварительно сделать тем или иным способом resize для вектора, а это сопровождается overhead в виде инициализации элементов вектора неким значением. Поэтому единственный вариант скопировать буфер в std::vector - это range insert в том или ином его виде, с надеждой на то что компилятор оптимизирует это до memcpy...


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: Пантер от Ноябрь 13, 2014, 10:14
проблема в том что для того чтобы использовать memcpy в связке с  std::vector необходимо предварительно сделать тем или иным способом resize для вектора, а это сопровождается overhead в виде инициализации элементов вектора неким значением.
А в чем проблема? Там идет memset, который тоже быстро выполняется.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: RSATom от Ноябрь 13, 2014, 10:19
memset конечно быстр - но в данном случае это overhead. т.к. заполненные одними значениями элементы тут же затираются другими. в 99% случаев этот overhead не критичен, а порой вообще не заметен - но он есть.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: vulko от Ноябрь 13, 2014, 10:46
memset конечно быстр - но в данном случае это overhead. т.к. заполненные одними значениями элементы тут же затираются другими. в 99% случаев этот overhead не критичен, а порой вообще не заметен - но он есть.

оверхед есть и от обращения к vtable и от создания вектора и его инициализации.

если это место нагружено, значит лучше максимально его уменьшить и перейти на char* + memcpy.
никаких преимуществ использования вектора в данной ситуации нет.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: Пантер от Ноябрь 13, 2014, 10:56
А еще можно на асме вставку сделать...


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: vulko от Ноябрь 13, 2014, 11:09
А еще можно на асме вставку сделать...

это перебор. char* + memcpy будет итак летать...)))


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: Пантер от Ноябрь 13, 2014, 11:12
А еще можно на асме вставку сделать...

это перебор. char* + memcpy будет итак летать...)))
Я к тому, что низкоуровневые варианты стоит использовать только в тех случаях, когда текущего уровня становится недостаточно. ИМХО, для начала ТС следует воспользоваться вариантом с вектором и посмотреть, не будет ли это достаточным.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: Igors от Ноябрь 18, 2014, 09:42
В отличии от
Код
C++ (Qt)
std::vector<char> tmp(b.begin(), b.end());
   return tmp;
 
где происходит следующее: сначала будет создан объект tmp с вызовом конструктора, затем копирующий конструктор скопирует tmp в область памяти вне функции. Далее, для tmp будет вызван деструктор.
Так делает MSVC и только в Debug, т.е. это просто "отклонение от нормы", разницы между 2 вариантами нет. 

Не знал раньше про rvo и nrvo. Было интересно.
На мой взгляд оптимальным вариантом будет использование memcpy. Быстрее него всё равно ничего не напишешь. И голова не болит о том, как и какая строчка будет воспринята каким-либо компилятором. Или я ошибаюсь?
memcpy не годится для типов с нетривиальным копированием. Вообще почитаешь - душа радуется, как люди заботятся о скорости! :) Увы, это пока так, "разговор ни о чем". Третьего дня столкнулся с такими тормозами

Код
C++ (Qt)
void DoSomething( const std::vector <CData *> & data );
 
Разумеется ф-ция DoSomething имеет очень хорошую частоту вызова (мульены). Известно что вектор data может иметь одинаковые эл-ты и нужно пропускать повторы, но как это сделать? Очевидное решение QHash заметно тормозит, время уходит на создание/инициализацию хеша. Это нормально если число эл-тов сотня, но не 3-4 (как может быть).

Предвкушаю взрыв энтузиазма, огромное число дельных советов и.т.п. или... я ошибаюсь?  :)


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: kambala от Ноябрь 18, 2014, 17:07
а если линейный список создать из вектора?


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: Igors от Ноябрь 18, 2014, 19:06
а если линейный список создать из вектора?
Нет проблем, можно сразу делать список, ну так что с того, как/чем это поможет?


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: kambala от Ноябрь 18, 2014, 19:26
сразу создать связи между неповторяющимися элементами, должно быть быстрее хеша по идее (диванная аналитика)


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: Igors от Ноябрь 18, 2014, 19:32
сразу создать связи между неповторяющимися элементами, должно быть быстрее хеша по идее (диванная аналитика)
Первый раз о таком слышу, а что это за связи и как их создать? Но все равно есть хоть какая-то мысль - уже хорошо, а то "запанувала тиша"  :)


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: kambala от Ноябрь 18, 2014, 19:58
может я не так выразился :) ну самый обычный линейный связный список:
Код
C++ (Qt)
struct Node
{
   Node *next; // можно и previous добавить по желанию
   CData *data;
};
 
struct LinkedList
{
   Node *head, *current;
};


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: kamre от Ноябрь 19, 2014, 17:31
Код
C++ (Qt)
void DoSomething( const std::vector <CData *> & data );
 
Разумеется ф-ция DoSomething имеет очень хорошую частоту вызова (мульены). Известно что вектор data может иметь одинаковые эл-ты и нужно пропускать повторы, но как это сделать? Очевидное решение QHash заметно тормозит, время уходит на создание/инициализацию хеша. Это нормально если число эл-тов сотня, но не 3-4 (как может быть).
1. Добавить флаг того, что элемент обработан, в CData. На входе у всех элементов из data флаг сброшен, на выходе из DoSomething сбрасывать эти флаги.
2. Сортировать data перед обработкой и обрабатывать только первый из подряд идущих одинаковых указателей.
3. Не передавать дубликаты, а отсеивать их на уровне выше. Например, если исходные CData лежат в каком-то векторе, то у них есть индекс в этом векторе, можно завести вектор из флагов и при сборке data учитывать эти флаги.

P.S. QHash тут вроде совсем не нужен.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: Igors от Ноябрь 19, 2014, 17:58
может я не так выразился :) ну самый обычный линейный связный список:
Все равно не понял. Ну завел, и что?

1. Добавить флаг того, что элемент обработан, в CData. На входе у всех элементов из data флаг сброшен, на выходе из DoSomething сбрасывать эти флаги.
Несомненно лучшее, но что делать с multi-threaded? Пользователи с 32 ядрами - уже дело рядовое, так что QAtomicInt не обойтись

2. Сортировать data перед обработкой и обрабатывать только первый из подряд идущих одинаковых указателей.
Не проверял, но сортировка - операция совсем не дешевая, возможно это будет "лучше хеша", но тормоз останется.

3. Не передавать дубликаты, а отсеивать их на уровне выше. Например, если исходные CData лежат в каком-то векторе, то у них есть индекс в этом векторе, можно завести вектор из флагов и при сборке data учитывать эти флаги.
Не очень понял. Расскажу откуда берутся повторы. Нужно (всего лишь) найти все пересечения полигонов в сцене. Сделал окто-дерево и добавил в него все полигоны. Теперь иду полигон за полигоном и смотрю какие ноды дерева он покрывает. Все полигоны этих нодов собираю в вектор. DoSomething считает пересечение текущего полигона со всеми из вектора. За счет того что полигон имеет протяженность, он может оказаться в 2 и более нодах - вот и повторы.



Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: kambala от Ноябрь 19, 2014, 18:56
может я не так выразился :) ну самый обычный линейный связный список:
Все равно не понял. Ну завел, и что?
список состоит сразу из неповторяющихся элементов, ничего пропускать не нужно — просто выполняется переход в node->next и все. либо я чего-то не понял в вопросе.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: Igors от Ноябрь 19, 2014, 19:17
список состоит сразу из неповторяющихся элементов, ничего пропускать не нужно — просто выполняется переход в node->next и все.
Ну вот есть CData * что нужно добавить. Хорошо, создал Node *, добавил его в список, но как проверить что такой CData * в списке уже есть? А если без Node, держать next  в самом CData - не раскрутиться с multi-threading

Да, а где же фаны memcpy? Куда же делась "склонность к анализу скорости"? Почему-то отвечают совсем др люди  :)


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: kambala от Ноябрь 19, 2014, 21:31
я почему-то подумал, что одинаковые элементы идут подряд...

тогда флаг статуса обработки можно ставить не в саму Cdata, а в какой-то менеджер. но это диванная аналитика-2 т.к. с многопоточностью дела практически не имел.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: kamre от Ноябрь 20, 2014, 02:15
Не очень понял. Расскажу откуда берутся повторы. Нужно (всего лишь) найти все пересечения полигонов в сцене. Сделал окто-дерево и добавил в него все полигоны. Теперь иду полигон за полигоном и смотрю какие ноды дерева он покрывает. Все полигоны этих нодов собираю в вектор. DoSomething считает пересечение текущего полигона со всеми из вектора. За счет того что полигон имеет протяженность, он может оказаться в 2 и более нодах - вот и повторы.
Имелось ввиду то, что полигоны лежат в векторе, а их индексы в окто-дереве используются. Также есть массив флагов такой же длины как и вектор полигонов. При сборке полигонов с узлов дерева выставляются флаги и тем самым избегаются дубликаты в собранном векторе. После вызова функции DoSomething флаги сбрасываются.


Название: Re: Как быстро преобразовывать QByteArray в std::vector<unsigned char> и обратно?
Отправлено: Igors от Ноябрь 20, 2014, 06:27
Имелось ввиду то, что полигоны лежат в векторе, а их индексы в окто-дереве используются. Также есть массив флагов такой же длины как и вектор полигонов. При сборке полигонов с узлов дерева выставляются флаги и тем самым избегаются дубликаты в собранном векторе. После вызова функции DoSomething флаги сбрасываются.
Только массив флагов двумерный (или свой на каждую нитку). Так да, быстро и без atomic. Я не додумался.

Спасибо