Russian Qt Forum
Ноябрь 25, 2024, 06:16 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1] 2   Вниз
  Печать  
Автор Тема: Множества (std::set, QSet)  (Прочитано 11305 раз)
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« : Сентябрь 03, 2017, 00:30 »

Привет друзья!
Прошу помочь найти решение, ибо не хотелось бы велосипедить.
Я выделяю для себя положительные стороны контейнеров:
std::set - возможность конструирования по месту с подсказкой (emplace_hint, почему этого нет в 5,7+ реализациях QSet, ведь, объявляли о переходе на c++11??)
QSet - наличие простых методов и операторов для вычисления пересечений, сложений и вычитаний.

Используя std::set я не имею возможности выполнить вычитание без создания контейнера для результата. Я говорю про std::set_difference.
Меня же интересует аналог QSet<T> &QSet::operator-=(const T &value). Не хотелось бы выделять дополнительной памяти. Быть может есть какой-нибудь обобщенный erase_iterator? Так можно было бы освобождать память из-под обработанных элементов.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #1 : Сентябрь 03, 2017, 10:32 »

Это принципиально разные ассоциативные контейнеры, и выбор определяется соображением "нужна ли упорядоченность". Напр если данные нужно рисовать по точкам, одна за другой, то QSet (на базе QHash) просто не годится.

Если такой необходимости нет, то выбор обычно в пользу более быстрого QSet. Правда если хеш-ключ получается слишком замороченный, то ну его нафиг, лучше set.

И третье: в любом случае ключ - сами данные, т.е. менять их будет нельзя, в этом нужно сразу точно убедиться

Меня же интересует аналог QSet<T> &QSet::operator-=(const T &value). Не хотелось бы выделять дополнительной памяти. Быть может есть какой-нибудь обобщенный erase_iterator? Так можно было бы освобождать память из-под обработанных элементов.
Была подобная задача с интенсивным вычитанием. Как ни странно, оптимально получается.. на векторах (т.е. вообще без ассоциативных контейнеров). Ну а если выжимать не надо, то делов 5 минут - проходитесь итераторм по первому делая erase для тех что есть во втором (ах это уже велосипед Улыбающийся). Оптимизировать память - см squeeze()
Записан
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« Ответ #2 : Сентябрь 03, 2017, 11:17 »

Да, нужна упорядоченность и меньшее потребление памяти.
Ключ менять нет необходимости.
На векторах делать точно не хочу. Имеется много операций вставки и удаления.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #3 : Сентябрь 03, 2017, 12:08 »

Да, нужна упорядоченность и меньшее потребление памяти.
Ключ менять нет необходимости.
Ну тогда QSet пролетает. Когда-то (давно) мерял, помещение в std::set обходится примерно +20 байт на элемент (в 64бит может больше)
На векторах делать точно не хочу. Имеется много операций вставки и удаления.
Всем известно что вставка/удаление в set/map намного (или несравненно) быстрее чем вставка в вектор (там же массу данных надо сдвигать). Однако для "множественных" операций это может оказаться не так. Напр надо вставить тысячу вертексов. Для set это будет тысяча операций, время просто умножится на тысячу. А вот для вектора это можно сделать одной операцией. Поэтому начиная с какой-то интенсивности вектор догонит, а затем и перегонит set. Это заманчиво если финальные данные нужны как вектор. Правда нужна такая задача  Улыбающийся
Записан
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« Ответ #4 : Сентябрь 03, 2017, 12:26 »

Как производился замер потребления? Очень странно, ведь QSet хранит и хэшданные.
В std::set можно и кусками вставлять через insert(container.cbegin(), container.cend()). Также есть замечательная emplace_hint, которая позволит сэкономить на поиске места вставки.
Записан
kambala
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4747



Просмотр профиля WWW
« Ответ #5 : Сентябрь 03, 2017, 15:09 »

может линейный список подойдет?
Записан

Изучением C++ вымощена дорога в Qt.

UTF-8 has been around since 1993 and Unicode 2.0 since 1996; if you have created any 8-bit character content since 1996 in anything other than UTF-8, then I hate you. © Matt Gallagher
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #6 : Сентябрь 03, 2017, 15:25 »

Как производился замер потребления?
Я мерял std::set, просто шагал в отладчике пока не дотопал до new а там посмотрел.

В std::set можно и кусками вставлять через insert(container.cbegin(), container.cend()).
Это не делает вставки быстрее

Расскажите чего хотите добиться, тогда может и "матчасть" присмотрим подходящую
Записан
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« Ответ #7 : Сентябрь 03, 2017, 16:21 »

Кажется линейный список не подходит. Недопустимы дубликаты и предпочтительно упорядочивание.

В std::set можно и кусками вставлять через insert(container.cbegin(), container.cend()).
Это не делает вставки быстрее
Та ну... https://ideone.com/tGvhpt
Код
C++ (Qt)
#include <set>
#include <chrono>
#include <iostream>
 
using Time = std::chrono::high_resolution_clock;
using ms = std::chrono::milliseconds;
 
int main()
{
   std::set<int> initialSet;
   for (int i = 0; i < 5000000; ++i) {
       initialSet.insert(i);
   }
 
   std::set<int> setFilledWithForInsert;
   {
       const auto start = Time::now();
       for (const int value: initialSet) {
           setFilledWithForInsert.insert(value);
       }
       std::cout << "Insert: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << "\n";
   }
 
   std::set<int> setFilledWithForEmplaceHint;
   {
       const auto start = Time::now();
       auto it = setFilledWithForEmplaceHint.cend();
       for (const int value: initialSet) {
           it = setFilledWithForEmplaceHint.emplace_hint(it, value);
       }
       std::cout << "EmplaceHint: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << "\n";
   }
 
   std::set<int> setFilledWithForInsertHint;
   {
       const auto start = std::chrono::system_clock::now();
       auto it = setFilledWithForEmplaceHint.cend();
       for (const int value: initialSet) {
           it = setFilledWithForInsertHint.insert(it, value);
       }
       std::cout << "InsertHint: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << "\n";
   }
 
   std::set<int> setFilledWithIterators;
   {
       const auto start = std::chrono::system_clock::now();
       setFilledWithIterators.insert(initialSet.cbegin(), initialSet.cend());
       std::cout << "InsertIterators: " <<  std::chrono::duration_cast<ms>(Time::now() - start).count() << "\n";
   }
 
   return 0;
}
 
Цитировать
Insert: 1065
EmplaceHint: 256
InsertHint: 281
InsertIterators: 273
clang на моём пк:
Цитировать
Insert: 3820
EmplaceHint: 684
InsertHint: 659
InsertIterators: 615

Расскажите чего хотите добиться, тогда может и "матчасть" присмотрим подходящую
Ушли от темы к замерам... Добиться хочу отсечения из текущего std::set другого std::set без дополнительного выделения памяти.
Нужен невелосипедный аналог  QSet::operator-=.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #8 : Сентябрь 03, 2017, 18:21 »

Добиться хочу отсечения из текущего std::set другого std::set без дополнительного выделения памяти.
Нужен невелосипедный аналог  QSet::operator-=.
Такое отсечение (ис каропки или нет) скорее всего не вернет распределенную память (как это водится в std). А фокус со swap (как для вектора) здесь вряд ли прокатит. Лучше это сразу проверить.

Доп выделение неизбежно так или иначе почти для всех контейнеров. Надо выделить память для новых данных, переписать и удалить оригинал. Поэтому не видно смысла упорно искать фирменный оператор -=, он делает то же самое  Улыбающийся

Код
C++ (Qt)
   std::set<int> initialSet;
   for (int i = 0; i < 5000000; ++i) {
       initialSet.insert(i);
   }
 
Вставки "по порядку/нарастающей" могут быть заметно быстрее других.
« Последнее редактирование: Сентябрь 03, 2017, 18:37 от Igors » Записан
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« Ответ #9 : Сентябрь 03, 2017, 22:57 »

Написал функцию без потребления доп памяти.
Хотел найти подобную реализацию от профессионалов.
Код
C++ (Qt)
template <typename T>
std::set<T> &subtract (std::set<T> &initSet, const std::set<T> &otherSet) {
   auto it = initSet.cbegin();
   auto end = initSet.cend();
   auto otherIt = otherSet.cbegin();
   auto otherEnd = otherSet.cend();
 
   while (it != end) {
       const auto &value = *it;
       while (otherIt != otherEnd) {
           if (*otherIt >= value) {
               break;
           }
           ++otherIt;
       }
 
       if (otherIt == otherEnd) {
           break;
       }
 
       if (*otherIt == value) {
           it = initSet.erase(it);
       }
       else {
           ++it;
       }
   }
   return initSet;
}
Записан
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« Ответ #10 : Сентябрь 03, 2017, 23:21 »

https://ideone.com/emlYr7
Код
C++ (Qt)
#include <algorithm>
#include <chrono>
#include <iostream>
#include <set>
 
using Time = std::chrono::high_resolution_clock;
using ms = std::chrono::milliseconds;
 
template <typename T>
std::set<T> &subtract (std::set<T> &initSet, const std::set<T> &otherSet) {
   auto it = initSet.cbegin();
   auto end = initSet.cend();
   auto otherIt = otherSet.cbegin();
   auto otherEnd = otherSet.cend();
 
   while (it != end) {
       const auto &value = *it;
       while (otherIt != otherEnd) {
           if (*otherIt >= value) {
               break;
           }
           ++otherIt;
       }
 
       if (otherIt == otherEnd) {
           break;
       }
 
       if (*otherIt == value) {
           it = initSet.erase(it);
       }
       else {
           ++it;
       }
   }
   return initSet;
}
 
int main()
{
   std::set<int> initialSet;
   auto it = initialSet.end();
   for (int i = 0; i < 5000000; ++i) {
       it = initialSet.emplace_hint(it, i);
   }
 
   std::set<int> diffSet;
   it = diffSet.end();
   for (int i = 0; i < 5000000; i += 2) {
       it = diffSet.emplace_hint(it, i);
   }
 
   auto start = Time::now();
 
   std::set<int> setSubtractedWithStl;
   {
       std::set<int> initialSetCopy = initialSet;
 
       start = Time::now();
       std::set_difference(initialSetCopy.cbegin(), initialSetCopy.cend(),
                           diffSet.cbegin(), diffSet.cend(),
                           std::inserter(setSubtractedWithStl, setSubtractedWithStl.end()));
   }
   std::cout << "Stl + destructor: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << '\n';
 
   start = Time::now();
   subtract(initialSet, diffSet);
   std::cout << "Heaven: " << std::chrono::duration_cast<ms>(Time::now() - start).count() << '\n';
 
   const bool hasEqualSize = initialSet.size() == setSubtractedWithStl.size();
   bool equal = false;
   if (hasEqualSize) {
       equal = std::equal(initialSet.cbegin(), initialSet.cend(),
                          setSubtractedWithStl.cbegin());
   }
 
   std::cout << "Sets are equal: " << std::boolalpha << equal << '\n';
 
   return 0;
}
Цитировать
Stl + destructor: 917
Heaven: 183
Sets are equal: true
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #11 : Сентябрь 04, 2017, 09:34 »

Этв реализация никакого отношения к std::set не имеет, она столь же подходит для напр сортированных массивов/векторов (только надо чуть переделать erase). Когда удаляемых эл-тов много - в этом есть смысл (о чем говорилось выше), иначе быстрее и проще так
Код
C++ (Qt)
template <class T>
void subtract( std::set<T> & set1, const std::set<T> & set2 )
{
typedef typename std::set<T>::iterator TIter;
TIter it2 = set2.begin();
 
while (it2 != set2.end()) {
TIter it1 = set1.find(*it2);
if (it1 != set1.end())
set1.erase(it1);
++it2;
}
}
 
Записан
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« Ответ #12 : Сентябрь 04, 2017, 10:47 »

Этв реализация никакого отношения к std::set не имеет
Да имеет она всё.
Я бы посмотрел, как вы применяете её к вектору с "чуть переделанным erase"

Сложно пишете.
Существует size_type erase( const key_type& key ).
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #13 : Сентябрь 04, 2017, 11:23 »

Да имеет она всё.
Предположим вычитаемое (второй set) содержит всего 1 эл-т - а Вы все равно молотите весь первый set который может быть огромен. Зачем так делать если set умеет быстро искать?
Я бы посмотрел, как вы применяете её к вектору с "чуть переделанным erase"
Напишем велик для удаления эл-тов из вектора
Код
C++ (Qt)
template<class T>
void RemoveElems( std::vector<T> & vec )
{
size_t place = 0;
for (size_t i = 0; i < vec.size(); ++i) {
 if (IsElementDeleted(vec[i])) continue;
 if (i != place)
  vec[place] = vec[i];
 ++place;
}
vec.resize(place);
}
Теперь вместо IsElementDeleted подставляете что написали выше. Если "ис каропки" - дело чести, то можно remove_if (хотя он чуть хуже). Да, это долгая операция, НО она практически не зависит от числа удаляемых эл-тов, поэтому для "массовых" удалений она может оказаться быстрее.
Записан
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« Ответ #14 : Сентябрь 04, 2017, 12:33 »

Да имеет она всё.
Предположим вычитаемое (второй set) содержит всего 1 эл-т - а Вы все равно молотите весь первый set который может быть огромен. Зачем так делать если set умеет быстро искать?

В моей программе чаще встречается вычитание ~ из 10млн элементов 10тыс - 8млн элементов. Если 10 млн на 10 млн случится, то будет долго искать. Думаю, что пробег ради 1 элемента - скромная плата за скорость на больших множествах. Хотя, можно и ветвление алгоритма сделать в зависимости от отношения размеров.

Вашего примера я не понял.
Записан
Страниц: [1] 2   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.236 секунд. Запросов: 22.