Russian Qt Forum

Добрый день

Есть контейнер объектов, каждый имеет такие (интересующие нас) поля. все они НЕ уникальны

- имя (QString)
- тип (enum или int)
- visibility (bool)

Нужно: для заданного имени + типа найти "наилучший" объект в контейнере, т.е.

- имя должно точно совпадать, иначе объект не найден
- тип:  если совпадает с заданным - хорошо, это "наилучший", иначе годится любой
- visibility:  если true это "наилучший", иначе годится и false

И наконец если все ключи совпадают, должен быть найден первый (по порядку в исходном контейнеру). Как лучше/техничнее сделать такой поиск ?

Спасибо

Обьектов много? Имен не уникальных много? Если в лоб, находим первый объект с именем(если все совпало - в ответ), иначе ищем следующий (если лучше - заменяемб совпало в ответ)... и так пока все объекты не пройдем.

Чтобы быстрее искалось - QMap, QMsql.... Если объектов с одинаковым именем очень много, тогда БД - ищем полное совпадение, потом хуже и хуже...

QMultiMap можно заюзать, если есть совпадающие имена. Тогда в значениях ее можно хранить структуру int/bool.

Причем тут много-мало? :) Интересует корректное, "академическое" решение задачи, действительно ли оно такое уж сложное? А может оно проще "прямого перебора" который кстати здесь достаточно хлопотливый ?

Да, можем создавать любые контейнеры (поиск нужен многократно). И что? Как искать-то?

Вначале я подумал слить все проверки в ключ (или оператор <) и отсортировать по этому (композитному) ключу. Тогда поиск: lower_bound и проверяем найденный + предыдуший. Но почему-то мне показалось это не проходит... Или я неправ?

Согласен  с  QMultiMap, только в значениях проще хранить QVariant… Это мне кажется проще :)

Исходя из первого поста если я правильно понял, то иерархию поиска можно описать по убыванию:
- имя
- видимость
- тип
т.о. у мапы ключ - имя, в значениях отсортированный лист структур, оператор < можно сделать только по полю "видимость".
Ну а далее либо самый первый в листе берем, либо есть видимость в фолсе, тогда переходим к следующему.

Нет, см первый пост: имя + тип + видимость
Чего это ??? Почему не

C++ (Qt)
typedef QPair<QString, int> TKey;  // имя + тип
typedef QPair<QString, QPair<int, bool> > TKey;  // имя + тип + видимочть

Я может не сильно до конца задачу понял, но показалось, что первичное условие это имя, и если его нет, то далее искать бессмысленно.
Поэтому поиск по оставшимся 2 параметрам можно сократить, объединив элементы с одинаковыми именами.

А что сложного в прямом переборе? Создаете пустой указатель и перебираете массив, заменяя значение более выгодным (если все совпало, поиск останавливаете).
Если память не так важна, и вызовов очень много, то загоните в QMap<QString /*Name*/, QMap<int /*Type*/, bool /*Visible*/>> и двумя строчками извлеките ответ.

Да, так и есть, правильно поняли

??? Совершенно непонятный вывод. А остальные правила (или критерии) поиска разве нельзя задать в ключах мапы?

Ну вообще-то прямой перебор - "визитная карточка лоха"  :)

Какой Вы быстрый  :) Ну во-первых мапа не гарантирует что эл-ты с одним ключом будут в порядке исходного массива. И хотелось бы увидеть эти "две строчки извлечения"  :)

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

Спасибо, но давайте лучше уясним что писать-то, тогда собсно написание не проблема. Пусть напр ключи в мапе легли так
Ищем { "Name", 2, false, 0 }. QMap::lowerBound (std::lowerBound) вернет итератор на второй { "Name", 3, false, 10 }, он "не меньше". Проверяем найденный и предыдущий - у обоих тип не совпадает, у обоих видимость false. Однако был ключ "лучше" - у последнего тоже тип не совпадает, зато видимость true. Поэтому я и решил что не проходит, нужно топать по всем эл-там пока искомое имя не кончится и руками искать "лучший". Верно ли я мыслюсь?

вот чего накидал:

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

Если объектов десятки-сотни миллионов, тогда поиск лучше возложить на БД.
Что касается производительности, то поиск по хешу О(1) в среднем. Пересечение только замедлить может.
Ну в общем, принцип пересечения подмножеств я предложил, дальше вам решать, подойдёт ли он под конкретную задачу.
ps: у меня в проекте с 300-2000 тыс объектов подобные индексации используются, производительности хватает, памяти на индексирование до 200мб жрется.

Ну вот, опять пошли "анализы" :) А можно просто "решить задачу" без всяких "если"? Неужели она и вправду настолько сложна, что надо ловчить, привлекать БД и.т.п ? Не аерю. По меньшей мере один вариант есть - в мапе пройтись по всем объектам с одинаковым именем (кода не больше)

И смысл мапы при условии, что у всех объектов будет одинаковое имя?
ps: это частный случай, того что я написал.

Нельзя :). Т.е. можно, но это решение не будет одинаково эффективным для множества разных "если". Если элементов около сотни. Если элементов сотни миллионов. Если можно/нельзя использовать многопоточность. Если быстродействие важнее расходов по памяти. Если наоборот. Напишите одно решение, которое будет одинаково эффективно работать хотя бы для всех тех "если", которые я перечислил :).

Так а чем вариант с QMap <QMap... не подошел? Поиск правда не совсем 2мя строками, но...

C++ (Qt)
QMap <QString, QMap <int, QMap <bool, Data*>>> byName;
QMap <QString, Data*> anyType;
 
Data* findObject(QString name, int type, bool visible)
{
    auto byType = byName.find(name);
    //has name
    if (byType != byName.end())
    {
        auto byVisibility = byType->find(type);
        //has type
        if (byVisibility != byType->end())
        {
            auto object = byVisibility->find(visibility);
            //has visible
            if (object != byVisibility->end())
                return *object;
            //no visible
            else
                return byVisibility[!visibility];
        }
        //no type
        else
        {
            return anyType[name];
        }
    }
 
    //no name
    return nullptr;
}

И заполнять обратным перебором как-то так

C++ (Qt)
void insert(QString name, int type, bool visible, Data *value)
{
    anyType[name] = value;
    byName[name][type][visible] = value;
}

Не выполнится условие "первый в оригинальном массиве"

1. Проиндексировать все объекты по именам:
QMap<QString, QList<int> >

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

2. При поиске, если имя в мапе найдено, то взять массив индексов и далее "в лоб" только по нему.
Ну а иначе объект не найден.

Вроде несложно, не? :)

Почему это?

Потому что во второй мапе ключ это тип, а не индекс в оригинальном массиве

Да не вопрос

C++ (Qt)
struct Node {
	QString GetName( void ) const;
	int		GetType( void ) const;
	bool	GetVisibility( void ) const;
};
 
typedef QPair<QString, int> TKey;	// name + index
typedef QPair<int, int>		TAux;	// id (as bool) + visible  (as bool)
typedef QMap<TKey, Node *>	TFindMap;
 
TFindMap BuildFindMap( const QVector<Node *> & nodes )
{
	TFindMap fmap;
	for (int i = 0; i < nodes.size(); ++i)
		fmap[TKey(nodes[i]->GetName(), i)] = nodes[i];
 
	return fmap;
}
 
Node * FindNode( const TFindMap & fmap, const QString & name, int type )
{
	TKey key(name, -1);
	TFindMap::const_iterator it = fmap.lowerBound(key);
	Node * bestNode = 0;
	TAux bestAux(-1, -1);
	while (it != fmap.end()) {
		if (it.key().first != name) break;
		Node * node = it.value();
		TAux curAux((node->GetType() == type) ? 1 : 0,
					 node->GetVisibility() ? 1 : 0);
		if (curAux > bestAux) {
			bestNode = node;
			bestAux = curAux;
			if (bestAux.first && bestAux.second) break;
		}
		++it;
	}
	return bestNode;
}
 

Как это улучшить? И что там за дичь с эл-тами которые сами контейнеры? Может лучше на чистом "С" потренироваться,  чтобы контейнерами так не ляпать?

Ну конечно играть роль "эксперта" приятно  :), но в очередной раз замечаю (и/или замечу): углубление в детали проекта часто/обычно работает в минус. Проект живет своей жизнью и выводы могут быстро оказаться устаревшими. Напр пока я помню проект с макс 50К объектами, но в связи с недавним переводом на 64 запросто может быть уже и 200-300К. Также оценить "кратность" непросто даже в среднем проекте. Да, объектов может быть и сотка, но  поиск зовется для каждой ячейки в таблице. Только убедиться в этом - неск дней разрывания кода, часто чужого. Так может за это время просто сделать "нормально"?  :)

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

Ещё какой вопрос. Вот сидит пользователь, постоянно изменяет данные в контейнере с парой-тройкой сотен тысяч элементов. Иногда(очень редко) ищет  элемент по заданным условиям, смотрит на него, и продолжает дальше изменять данные. В предложенном решении каждый раз формируется дополнительный TFindMap (+ память, + время), хотя в лучшем случае нужный элемент найдётся в исходном контейнере менее чем за один проход, в худшем - один проход и ещё немного по наиболее подходящим элементам. И где в Вашем решении хоть какая-нибудь эффективность?  На кой нужен дополнительный TFindMap? Оно не эффективно ни по одному критерию из тех, что я приводил. Это плохое решение, переделывайте :).

Все происходит совсем не так :) Юзер может выбрать любое кол-во объектов и записать их установки в файл, потом этот файл надо как-то загрузить (возможно в совсем др сцене) - вот придумали/установили такие правила загрузки по умолчанию. Кстати "установки" - те самые curve(s) с которыми Вы уже знакомы  :)

Отчаянное желание придраться  :) 

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

Щас, разбежался  :)

Хотите сказать, что для моего варианта использования Ваше решение является очень эффективным и я всего лишь придираюсь? :)


А откуда товарищам знать, что всё происходит не так, как я описал, а "совсем не так"? Сколько ещё страниц в теме нужно исписать, чтобы выяснить что и как у Вас происходит? Если Вас, конечно, интересует эффективное решение задачи, а не "универсальное академическое среднее по больнице" :).

Академическое - это БД. Для случая когда непонятен текущий объем и непонятна масштабируемость. Если что, всегда можно перескочить на другую БД. или купить сервера помощнее.

Ой  :)  Крайность обратная "прямому перебору".

Да все товарищи правильно поняли как и положено профессиональным программистам. Если данные "не лезут в память" то описание с этого и начинается. Если я об этом не упомянул - значит этой проблемы нет. Так же и с изменением данных "на лету", это совсем др задача. Стало быть речь идет о самой банальной ситуации - построить структуры для поиска один раз, и затем искать многократно. Ну и чего тратить время и место на совершенно ненужные "выяснения" (хз чего) ?

Возвращаясь к теме. Практически пробежка по всем объектам с одинаковым именем вполне устраивает. Если юзер назначил всем одинаковые имена - значит сам "злобный Буратино", пусть страдает. Просто стало интересно как же так - все ключи есть, а быстрого поиска .. строго говоря нет. Приходится или перебирать диапазон или городить ужасные структуры (что еще хуже). Вот если бы тип был bool - тогда получается, а так нет. И похоже это нормально.

Еще рассматривал такой вариант:  ключи = имя + visible + тип, А на поиске (псевдокод)

C++ (Qt)
lowerBound(TKey(name, true, type))  // если найдено (name + type) - возвращаем, иначе 
lowerBound(TKey(name, false, type))  // если найдено (name + type) - возвращаем, иначе
// лучший из 2 

Возможно это точнее, хотя возни побольше

Так вот значит какая логика должна быть :).

Занятно, интересно сравнить по производительности и ресурсам с БД в памяти:
http://doc.qt.io/qt-5/qtsql-cachedtable-example.html

C++ (Qt)
    QSqlDatabase db = QSqlDatabase::addDatabase("QSQLITE");
    db.setDatabaseName(":memory:");
    // ...

На указанных объёмах данных, примерно монопенисуально, в пределах погрешности измерений, и даже файловый вариант БД приемлемые результаты показывает.
Оптимизация не идёт уже в ключе выбора хранилища данных, а идёт в ключе минимизации обращения к ним, разбиения на подмассивы (в БД отдельные таблицы), прикручивания различного распараллеливания и пр.
Удобство БД в том, что она инкапсулирует много рутинной работы, например то же пересечение множеств в любом виде, делается одной строкой.