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

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

Страниц: [1] 2 3   Вниз
  Печать  
Автор Тема: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка  (Прочитано 15737 раз)
G-virus
Гость
« : Июнь 10, 2012, 21:58 »

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

Суть проблемы: Нужно удалить дубликаты из QList<QVector3D>, решил делать так: копирую лист в множество, возвращаю множество как лист и готово, но вот компилятор со мной не согласен.
Код
C++ (Qt)
QList<QVector3D> Menu::calcNewVector3D(const QList<QVector3D> &list)
{
   return list.toSet().toList();
}
 

Попробовал исполнить подобный код для проверки, выскакивает такая же ошибка:
Код
C++ (Qt)
QVector3D vec;
QSet<QVector3D> set;
set.insert(vec);
 

Подскажите, пожалуйста, где не прав.
Спасибо
« Последнее редактирование: Июнь 10, 2012, 22:47 от G-virus » Записан
kambala
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 4732



Просмотр профиля WWW
« Ответ #1 : Июнь 10, 2012, 22:28 »

#include <QSet> не забыл?

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

Изучением 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
G-virus
Гость
« Ответ #2 : Июнь 10, 2012, 22:35 »

#include <QSet> не забыл?
если размер списка большой, то такое преобразование может быть довольно дорогой операцией.

Заинклудить не забыл. Да, списки большие, около 30 000 элементов.
Записан
Kurles
Бывалый
*****
Offline Offline

Сообщений: 480



Просмотр профиля
« Ответ #3 : Июнь 10, 2012, 22:40 »

Он для проверки на уникальные значения генерирует для каждого значения списка хеш с помощью функции uint qHash(...),а ее, принимающей QVector3D нет. Собственно если ее реализовать - то все заработает.
Код
C++ (Qt)
uint qHash(const QVector3D &val)
{
   qreal x = val.x();
   qreal y = val.y();
   qreal z = val.z();
   QString temp = QString("%0%1%2").arg(x, 0).arg(y).arg(x).arg(z);
   return ::qHash(temp);
}
Записан

Код
C++ (Qt)
while(!asleep()) sheep++;
G-virus
Гость
« Ответ #4 : Июнь 10, 2012, 22:47 »

Спасибо большое, Kurles, все заработало Улыбающийся
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #5 : Июнь 11, 2012, 10:11 »

Конечно 30k точек - пионерский размер, пройдет все что угодно. Но все-таки ресурсы Вы разбазариваете по-черному, машину совсем не бережете  Плачущий
Записан
kostya2vntu
Гость
« Ответ #6 : Июль 03, 2012, 02:12 »

Нормальное решение. Алгоритмическая сложность оптимальная - nlogn. Можно оптимизировать только константу, применив другое решение - отсортировав список и затем за один проход выбрав уникальные значения. Но выиграш на таких размерах данных будет незаметным. И то не факт что он будет.
И да, замечание - предложенная выше хеш функция просто отвратна, самое что ни есть разбазаривание ресурсов Улыбающийся
Записан
Bepec
Гость
« Ответ #7 : Июль 03, 2012, 06:47 »

Щепановский - можешь только оценивать других? Улыбающийся Видишь как сделать лучше - напиши. А не разводи тут фигню на постном масле Улыбающийся
Записан
DmitryM
Гость
« Ответ #8 : Июль 03, 2012, 07:14 »

отсортировав список и затем за один проход выбрав уникальные значения.
У QVector3D нет оператора operator<, потому тебе придется придумать компаратор, что бы отсортировать.
Но если есть компаратор, то его можно передать std::set
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #9 : Июль 03, 2012, 14:06 »

Код
C++ (Qt)
QList<QVector3D> Menu::calcNewVector3D(const QList<QVector3D> &list)
{
   return list.toSet().toList();
}
 
Надо понимать что "просто так" (бесплатно) ничего не бывает. Выигрывая в простоте и легкости написания мы проигрываем в скорости и расходах памяти, часто во много раз. Человеку с небольшим опытом возможно покажется такой текст очень крутым (вот, одной строкой все сделал), но когда-то он будет удивлен узнав что, оказывается, возможно сделать в 5-10 раз быстрее. И будет не очень приятно осознать что "простая реализация" оказывается "лоховская реализация". Поэтому лучше к таким "уж очень удобным" ф-циям не привыкать. 

Использование QList (вместо QVector) в данном случае уже увеличивает расход памяти более чем в полтора раза. Создание нового контейнера и возврат его по значению также операция недешевая и никакой необходимостью не вызывается. Заметим что эти, довольно грубые, ляпы не вызывают никаких замечаний  Плачущий  Конвертация в QString для получения ключа - ну хоть это осуждается.
Записан
kostya2vntu
Гость
« Ответ #10 : Июль 03, 2012, 17:13 »

Щепановский - можешь только оценивать других? Улыбающийся Видишь как сделать лучше - напиши. А не разводи тут фигню на постном масле Улыбающийся

Код:
uint qHash(const QVector3D &val)
{
    qreal x = val.x();
    qreal y = val.y();
    qreal z = val.z();
    return ::qHash(uint(x)) ^ ::qHash(uint(y)) ^ ::qHash(uint(z));
}

Быстро, но далеко от идеала - будут проблемы с коллизиями для определенных наборов данных. В общем случае хеш от даблов сложно брать. Hешение с сортировкой или std::set более надежно - написать компаратор проблемы нет вообще никакой.

Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #11 : Июль 03, 2012, 18:02 »

Быстро, но далеко от идеала - будут проблемы с коллизиями для определенных наборов данных. В общем случае хеш от даблов сложно брать. Hешение с сортировкой или std::set более надежно - написать компаратор проблемы нет вообще никакой.
Не вижу коллизий, все очень прилично. Но это "в теории". Автор темы сильно упростил себе жизнь, удаляя "совпадающие", а реально это такая задача: дан контейнер QPoint3D. Нужно:

- слить точки стоящие друг от друга на расстоянии меньше критического, которое принимается равным достаточно малому epsilon, часто 1.0e-5

- изменять исходный порядок точек не разрешается

Есть желающие блеснуть техникой? Улыбающийся Верес, не надо говорить что Вы "не сильны в графике" (ее здесь нет). Покажите себя вместо того чтобы клевать новичков  Улыбающийся
Записан
Bepec
Гость
« Ответ #12 : Июль 03, 2012, 18:22 »

Я очень не силён в графике ) И даже не представляю что это за контейнер и что себе представляет Улыбающийся

Igors - думаете порог вхождения в ваши чертоги так низок? Улыбающийся
Записан
kostya2vntu
Гость
« Ответ #13 : Июль 03, 2012, 18:30 »

Быстро, но далеко от идеала - будут проблемы с коллизиями для определенных наборов данных. В общем случае хеш от даблов сложно брать. Hешение с сортировкой или std::set более надежно - написать компаратор проблемы нет вообще никакой.
Не вижу коллизий, все очень прилично.

Из-за приведения double к int, которое по сути сохраняет только целую часть значения отбрасывая дробную. Из-за этого, например, если у множества точек координаты будут в диапазоне [0,1) - хеш код их всех будет одинаковым, и хеш-таблица превратится в одну большую коллизию.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #14 : Июль 03, 2012, 18:43 »

И даже не представляю что это за контейнер и что себе представляет Улыбающийся
QVector <QPoint3D>

Igors - думаете порог вхождения в ваши чертоги так низок? Улыбающийся
Да какие там чертоги? "Хижина дяди Тома". Работа с контейнерами и структурами данных, хотите в терминах Qt, хотите std. Никто не подавляет, не тыкает в нос Вындоуз хуками, прОтокалами и прочей лабудой. Так, небольшой кроссворд/пузл после трудового дня.

Из-за приведения double к int, которое по сути сохраняет только целую часть значения отбрасывая дробную. Из-за этого, например, если у множества точек координаты будут в диапазоне [0,1) - хеш код их всех будет одинаковым, и хеш-таблица превратится в одну большую коллизию.
Не думаю что мантиссы так интенсивно совпадут - файл в котором записаны флоты практически не сжимается. А еще лучше так
Код
C++ (Qt)
uint qHash(const QVector3D &val)
{
   float f[3] = { val.x(), val.y(), val.z() };
   uint32 * dummy = (uint32 *) f;
   return dummy[0] ^ dummy[1] ^ dummy[2];
}
 
Записан
Страниц: [1] 2 3   Вверх
  Печать  
 
Перейти в:  


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