Russian Qt Forum

Qt => Общие вопросы => Тема начата: G-virus от Июнь 10, 2012, 21:58

Название: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: G-virus от Июнь 10, 2012, 21:58

Здравствуйте. Подскажите, пожалуйста, почему не получается преобразовать список в множество и обратно. Возможно, я бы сам понял ошибку, но у меня выводится подобное (см скрин), я пытался с этим бороться и опустил руки, танцую с бубном около полугода, угадывая ошибки.
(http://dl.dropbox.com/u/6052533/Screens/232338d.png)
Суть проблемы: Нужно удалить дубликаты из 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);

Подскажите, пожалуйста, где не прав.
Спасибо

Название: Re: QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: kambala от Июнь 10, 2012, 22:28

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

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

Название: Re: QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: G-virus от Июнь 10, 2012, 22:35

Цитата: kambala от Июнь 10, 2012, 22:28

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

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

Название: Re: QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Kurles от Июнь 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);
}

Название: Re: QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: G-virus от Июнь 10, 2012, 22:47

Спасибо большое, Kurles, все заработало :)

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Igors от Июнь 11, 2012, 10:11

Конечно 30k точек - пионерский размер, пройдет все что угодно. Но все-таки ресурсы Вы разбазариваете по-черному, машину совсем не бережете :'(

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: kostya2vntu от Июль 03, 2012, 02:12

Нормальное решение. Алгоритмическая сложность оптимальная - nlogn. Можно оптимизировать только константу, применив другое решение - отсортировав список и затем за один проход выбрав уникальные значения. Но выиграш на таких размерах данных будет незаметным. И то не факт что он будет.
И да, замечание - предложенная выше хеш функция просто отвратна, самое что ни есть разбазаривание ресурсов :)

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Bepec от Июль 03, 2012, 06:47

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

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: DmitryM от Июль 03, 2012, 07:14

Цитата: Константин Щепановский от Июль 03, 2012, 02:12

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

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

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Igors от Июль 03, 2012, 14:06

Код

C++ (Qt)
QList<QVector3D> Menu::calcNewVector3D(const QList<QVector3D> &list)
{
    return list.toSet().toList();
}

Надо понимать что "просто так" (бесплатно) ничего не бывает. Выигрывая в простоте и легкости написания мы проигрываем в скорости и расходах памяти, часто во много раз. Человеку с небольшим опытом возможно покажется такой текст очень крутым (вот, одной строкой все сделал), но когда-то он будет удивлен узнав что, оказывается, возможно сделать в 5-10 раз быстрее. И будет не очень приятно осознать что "простая реализация" оказывается "лоховская реализация". Поэтому лучше к таким "уж очень удобным" ф-циям не привыкать.

Использование QList (вместо QVector) в данном случае уже увеличивает расход памяти более чем в полтора раза. Создание нового контейнера и возврат его по значению также операция недешевая и никакой необходимостью не вызывается. Заметим что эти, довольно грубые, ляпы не вызывают никаких замечаний :'( Конвертация в QString для получения ключа - ну хоть это осуждается.

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: kostya2vntu от Июль 03, 2012, 17:13

Цитата: Bepec от Июль 03, 2012, 06:47

Код:

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 более надежно - написать компаратор проблемы нет вообще никакой.

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Igors от Июль 03, 2012, 18:02

Цитата: Кoнcтантин от Июль 03, 2012, 17:13

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

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

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

Есть желающие блеснуть техникой? :) Верес, не надо говорить что Вы "не сильны в графике" (ее здесь нет). Покажите себя вместо того чтобы клевать новичков :)

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Bepec от Июль 03, 2012, 18:22

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

Igors - думаете порог вхождения в ваши чертоги так низок? :)

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: kostya2vntu от Июль 03, 2012, 18:30

Цитата: Igors от Июль 03, 2012, 18:02

Цитата: Кoнcтантин от Июль 03, 2012, 17:13

Не вижу коллизий, все очень прилично.

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

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Igors от Июль 03, 2012, 18:43

Цитата: Bepec от Июль 03, 2012, 18:22

И даже не представляю что это за контейнер и что себе представляет :)

QVector <QPoint3D>

Цитата: Bepec от Июль 03, 2012, 18:22

Igors - думаете порог вхождения в ваши чертоги так низок? :)

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

Цитата: Кoнcтантин от Июль 03, 2012, 18:30

Не думаю что мантиссы так интенсивно совпадут - файл в котором записаны флоты практически не сжимается. А еще лучше так

Код

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];
}

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: kostya2vntu от Июль 03, 2012, 18:58

Цитата: Igors от Июль 03, 2012, 18:43

Код

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];
}

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

Код:

return (dummy[0] * A) ^ (dummy[1] * B) ^ (dummy[2] * C);

где А,В,С - некоторые большие разные простые числа.

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Igors от Июль 03, 2012, 19:26

Цитата: Кoнcтантин от Июль 03, 2012, 18:58

Чего это ??? Напр 2 точки на оси X: (1, 0. 0) и (2, 0, 0) хеши явно разные. Наверное Вы имели ввиду что-то типа зеркала, напр (1, 0, 0)(0, 1, 0). Да, можно помножить x, y, z напр на 11, 13, 17, но можно и забить - ну будет больше точек в одной из корзин, зато ключ считаем пошустрее, то на то и выйдет.

Хкш - дело хорошее, но в данной задаче вряд ли к месту если искать "неточное" совпадение (как оно в жизни). Да и по памяти расходен весьма - привыкли шиковать.

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: DmitryM от Июль 03, 2012, 21:23

Цитата: Кoнcтантин от Июль 03, 2012, 17:13

Hешение с сортировкой или std::set более надежно - написать компаратор проблемы нет вообще никакой.

Вот и предъявите пожалуйста, а то ввести отношение порядка на множестве точек не могу.

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: kostya2vntu от Июль 04, 2012, 01:20

Цитата: Igors от Июль 03, 2012, 19:26

Цитата: Кoнcтантин от Июль 03, 2012, 18:58

Точно, ошибся, трудный рабочий день выдался )

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: kostya2vntu от Июль 04, 2012, 01:22

Цитата: DmitryM от Июль 03, 2012, 21:23

Цитата: Кoнcтантин от Июль 03, 2012, 17:13

Hешение с сортировкой или std::set более надежно - написать компаратор проблемы нет вообще никакой.

Вот и предъявите пожалуйста, а то ввести отношение порядка на множестве точек не могу.

Сначала сравниваем по X, если одинаковые - по Y, если Y тоже равны - по Z ...

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Bepec от Июль 04, 2012, 06:50

Igors - я из ваших рассуждений понял только слово зеркало, да и то в виде нашлёпки на шкаф :D

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: DmitryM от Июль 04, 2012, 07:20

Цитата: Кoнcтантин от Июль 04, 2012, 01:22

Сначала сравниваем по X, если одинаковые - по Y, если Y тоже равны - по Z ...

Причем тут равенство? Когда требуется неравенство.

Пример:
(0,0,1) < (1,0,0) или (0,0,1) > (1,0,0)

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: kostya2vntu от Июль 04, 2012, 11:14

Цитата: DmitryM от Июль 04, 2012, 07:20

Цитата: Кoнcтантин от Июль 04, 2012, 01:22

Сначала сравниваем по X, если одинаковые - по Y, если Y тоже равны - по Z ...

Причем тут равенство? Когда требуется неравенство.

Пример:
(0,0,1) < (1,0,0) или (0,0,1) > (1,0,0)

Функция возвращает true усли a < b

Код

C++ (Qt)
bool comp(QVector3D &a, QVector3D &b) {
    if (a.x() < b.x()) return true;
    if (a.x() > b.x()) return false;
    if (a.y() < y.x()) return true;
    if (a.y() > y.x()) return false;
    return a.z() < b.z();
}

Что тут сложного?

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Igors от Июль 04, 2012, 14:24

Цитата: Bepec от Июль 04, 2012, 06:50

Igors - я из ваших рассуждений понял только слово зеркало, да и то в виде нашлёпки на шкаф :D

Ну типа x одной координаты равен y другой, т.е. координаты разные а хеш-код получается одинаковый и тормозит. Случай довольно редкий, можно пренебречь

Цитата: Кoнcтантин от Июль 04, 2012, 11:14

Код

C++ (Qt)
bool comp(QVector3D &a, QVector3D &b) {
    if (a.x() < b.x()) return true;
    if (a.x() > b.x()) return false;
    if (a.y() < y.x()) return true;
    if (a.y() > y.x()) return false;
    return a.z() < b.z();
}

Что тут сложного?

Придираюсь: в приличном обществе const положено писать :)

Сложного конечно ничего, и условие сортировки записано совершенно верно. Ну а дальше-то что? Как будете удалять/фильтровать?

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: G-virus от Июль 04, 2012, 15:31

Товарищи, позвольте узнать, по поводу чего тут развилась демагогия, и почему Конфуций-Igors пытается во всех внедрить свою философию?

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Igors от Июль 04, 2012, 16:42

Цитата: G-virus от Июль 04, 2012, 15:31

Какая демагогия и что не нравится? Обсуждается как сделать грамотно, как в плане реализации, так и постановки.

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Bepec от Июль 04, 2012, 16:49

G-virus вы некорректны. Тут спокойно и нормально протекает процесс "как сделать лучше".

И если это философия Igors -то такую философию нужно внедрять принудительно.

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: DmitryM от Июль 04, 2012, 19:35

Цитата: Igors от Июль 04, 2012, 14:24

Цитата: Кoнcтантин от Июль 04, 2012, 11:14

Код

C++ (Qt)
bool comp(QVector3D &a, QVector3D &b) {
    if (a.x() < b.x()) return true;
    if (a.x() > b.x()) return false;
    if (a.y() < y.x()) return true;
    if (a.y() > y.x()) return false;
    return a.z() < b.z();
}

Что тут сложного?

Возможно правильно вот так:

Код

C++ (Qt)
   if (a.x() < b.x()) return true;
   if (a.x() > b.x()) return false;
   if (a.y() < b.y()) return true;
   if (a.y() > b.y()) return false;

Если это так, то получается:
(1, 1.3, 10)<(1,1.301, 100)<...<(1,1.34, 100500) < (1, 1.35, 10)

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Igors от Июль 04, 2012, 20:00

Цитата: DmitryM от Июль 04, 2012, 19:35

Возможно правильно вот так:

Код

C++ (Qt)
   if (a.x() < b.x()) return true;
   if (a.x() > b.x()) return false;
   if (a.y() < b.y()) return true;
   if (a.y() > b.y()) return false;

Если это так, то получается:
(1, 1.3, 10)<(1,1.301, 100)<...<(1,1.34, 100500) < (1, 1.35, 10)

Да, это Константин описАлся (y.x() - кто такой y ?) а я и не заметил. Да, транзитивность выполняется, ну и что? Допустим в сортированном массиве имеем (согласно условию сортировки)

Цитировать

(1, 1, 0)
(1, 2, 0)
..
(1.00001, 1, 0)

Расстояние между первой и последней точкой меньше критического, но подряд они не идут, std::remove_if (любимое знатоками STL) ничего не дает

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: kostya2vntu от Июль 04, 2012, 21:50

Цитата: Igors от Июль 04, 2012, 20:00

Цитировать

(1, 1, 0)
(1, 2, 0)
..
(1.00001, 1, 0)

Это уже твоя, более усложненная задача. Очевидное решение - сравнение всех точек со всеми отработает за квадрат. Но по моему должен быть более быстрый способ.

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: Igors от Июль 05, 2012, 13:15

Цитата: Кoнcтантин от Июль 04, 2012, 21:50

Это уже твоя, более усложненная задача. Очевидное решение - сравнение всех точек со всеми отработает за квадрат.

Не думаю что упоминать о таком "решении" удобно/прилично. Каждый раз когда слышу рассуждения об O(n), логарифмах и.т.п. - удивляюсь куда что девается когда задача чуть-чуть сложнее (ну не совсем уж "для сопливых" :))

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: DmitryM от Июль 05, 2012, 13:58

Цитата: Кoнcтантин от Июль 04, 2012, 21:50

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

Название: Re: [РЕШЕНО] QSet, QList, QVector3D/2D, toList() и toSet(). Ошибка
Отправлено: kostya2vntu от Июль 05, 2012, 14:07

Цитата: Igors от Июль 05, 2012, 13:15

Цитата: Кoнcтантин от Июль 04, 2012, 21:50

Можно поподробнее? Почему неприлично? Что именно и куда девается?