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

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

Страниц: [1] 2 3   Вниз
  Печать  
Автор Тема: Простой (?) поиск  (Прочитано 14380 раз)
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« : Сентябрь 16, 2018, 11:34 »

Добрый день

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

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

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

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

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

Спасибо
Записан
deMax
Хакер
*****
Offline Offline

Сообщений: 600



Просмотр профиля
« Ответ #1 : Сентябрь 18, 2018, 17:18 »

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

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

Сообщений: 221


Просмотр профиля
« Ответ #2 : Сентябрь 18, 2018, 19:04 »

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

Сообщений: 11445


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

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

Чтобы быстрее искалось - QMap,
QMultiMap можно заюзать, если есть совпадающие имена. Тогда в значениях ее можно хранить структуру int/bool.
Да, можем создавать любые контейнеры (поиск нужен многократно). И что? Как искать-то?

Вначале я подумал слить все проверки в ключ (или оператор <) и отсортировать по этому (композитному) ключу. Тогда поиск: lower_bound и проверяем найденный + предыдуший. Но почему-то мне показалось это не проходит... Или я неправ?
Записан
Figaro
Гость
« Ответ #4 : Сентябрь 19, 2018, 14:09 »

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

Согласен  с  QMultiMap, только в значениях проще хранить QVariant… Это мне кажется проще Улыбающийся
Записан
RedDog
Частый гость
***
Offline Offline

Сообщений: 221


Просмотр профиля
« Ответ #5 : Сентябрь 19, 2018, 19:02 »

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

Чтобы быстрее искалось - QMap,
QMultiMap можно заюзать, если есть совпадающие имена. Тогда в значениях ее можно хранить структуру int/bool.
Да, можем создавать любые контейнеры (поиск нужен многократно). И что? Как искать-то?

Вначале я подумал слить все проверки в ключ (или оператор <) и отсортировать по этому (композитному) ключу. Тогда поиск: lower_bound и проверяем найденный + предыдуший. Но почему-то мне показалось это не проходит... Или я неправ?
Исходя из первого поста если я правильно понял, то иерархию поиска можно описать по убыванию:
- имя
- видимость
- тип
т.о. у мапы ключ - имя, в значениях отсортированный лист структур, оператор < можно сделать только по полю "видимость".
Ну а далее либо самый первый в листе берем, либо есть видимость в фолсе, тогда переходим к следующему.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #6 : Сентябрь 20, 2018, 08:27 »

Исходя из первого поста если я правильно понял, то иерархию поиска можно описать по убыванию:
- имя
- видимость
- тип
Нет, см первый пост: имя + тип + видимость
т.о. у мапы ключ - имя,
Чего это Непонимающий Почему не
Код
C++ (Qt)
typedef QPair<QString, int> TKey;  // имя + тип
typedef QPair<QString, QPair<int, bool> > TKey;  // имя + тип + видимочть
Записан
RedDog
Частый гость
***
Offline Offline

Сообщений: 221


Просмотр профиля
« Ответ #7 : Сентябрь 20, 2018, 09:36 »

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

Сообщений: 600



Просмотр профиля
« Ответ #8 : Сентябрь 20, 2018, 09:47 »

Причем тут много-мало? Улыбающийся Интересует корректное, "академическое" решение задачи, действительно ли оно такое уж сложное? А может оно проще "прямого перебора" который кстати здесь достаточно хлопотливый ?
А что сложного в прямом переборе? Создаете пустой указатель и перебираете массив, заменяя значение более выгодным (если все совпало, поиск останавливаете).
Если память не так важна, и вызовов очень много, то загоните в QMap<QString /*Name*/, QMap<int /*Type*/, bool /*Visible*/>> и двумя строчками извлеките ответ.
Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #9 : Сентябрь 20, 2018, 09:58 »

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

Поэтому поиск по оставшимся 2 параметрам можно сократить, объединив элементы с одинаковыми именами.
Непонимающий Совершенно непонятный вывод. А остальные правила (или критерии) поиска разве нельзя задать в ключах мапы?

А что сложного в прямом переборе?
Ну вообще-то прямой перебор - "визитная карточка лоха"  Улыбающийся

Если память не так важна, и вызовов очень много, то загоните в QMap<QString /*Name*/, QMap<int /*Type*/, bool /*Visible*/>> и двумя строчками извлеките ответ.
Какой Вы быстрый  Улыбающийся Ну во-первых мапа не гарантирует что эл-ты с одним ключом будут в порядке исходного массива. И хотелось бы увидеть эти "две строчки извлечения"  Улыбающийся
Записан
RedDog
Частый гость
***
Offline Offline

Сообщений: 221


Просмотр профиля
« Ответ #10 : Сентябрь 20, 2018, 13:16 »

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

Сообщений: 11445


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

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

Сообщений: 221


Просмотр профиля
« Ответ #12 : Сентябрь 20, 2018, 19:32 »

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

Код:
#include <QHash>
#include <QVector>
#include <QSet>
#include <QDebug>

#include <algorithm>

struct ObjectInfo
{
    QString name;
    int type;
    bool visible;

};

QList<ObjectInfo> objects;

QHash<QString, QList<int>> nameIndex;
QHash<int, QList<int>> typeIndex;
QHash<bool, QList<int>> visibleIndex;


void fill()
{
    for (int i = 0; i < 100; ++i)
    {
        const QString name = QString("name%1").arg(qrand()%5);
        const int type = qrand()%27;
        const bool visible = (i%2);
        ObjectInfo objectInfo{name, type, visible};

        const int index = objects.size();

        nameIndex[name] << index;
        typeIndex[type] << index;
        visibleIndex[visible] << index;
        objects << objectInfo;
    }
}

int find(const QString& name, const int type, const bool visible)
{
    auto it = nameIndex.find(name);
    if (it == nameIndex.cend()) // имя не найдено - увы
        return -1;

    if (it.value().isEmpty()) // ничего не проиндексировано - увы
        return -1;

    QSet<int> types = typeIndex.value(type).toSet();
    QSet<int> visibles = visibleIndex.value(visible).toSet();

    QSet<int> intersects = types.intersect(visibles); // пересекающиеся индексы типа и видимости
    if (intersects.isEmpty()) // ничего не персекается - возвращаем первый индекс по имени
        return it.value().first();

    intersects = intersects.intersect(it.value().toSet()); //пересечение имени и типа/видимости
    if (intersects.isEmpty())
        return it.value().first();

    QList<int> indexes = intersects.toList();
    auto min = std::min_element(indexes.cbegin(), indexes.cend());
    return *min;
}


int main(int argc, char *argv[])
{
    Q_UNUSED(argc);
    Q_UNUSED(argv);

    fill();

    const int index = find("name1", 5, true);
    if (index >= 0)
        qDebug() << objects.at(index).name;

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

Сообщений: 11445


Просмотр профиля
« Ответ #13 : Сентябрь 21, 2018, 09:12 »

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

Сообщений: 221


Просмотр профиля
« Ответ #14 : Сентябрь 21, 2018, 09:44 »

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


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