Russian Qt Forum

Здравствуйте. В моей модели данных есть _history  (ключ-элемент) в которую заносятся новые элементы. В  Submit  пробегаемся по истории и сохраняем элементы в базу В ТОМ ПОРЯДКЕ В КОТОРОМ ОНИ БЫЛИ ДОБАВЛЕНЫ В ИСТОРИЮ.
вопрос: в чём хранить _history?
1) изначально был QHash - но он я так понимаю не упорядочивает данные.
2) QMap сортирует по ключу. А надо тупо оставить тот порядок, в котором вставлялись элементы
3) QList порядок - ок, но нельзя достать нужный элемент по ключу, не пробегаясь по всему списку

Ещё варианты?
пока склоняюсь к Qlist+QHash. (в списке лежат id, QHash - хранит эл-ты c ключом id)

Если нужен порядок и быстрый поиск, то вполне нормальное решение.
Правда я бы элементы хранил в QList (указатели на них), а в хеше хранил пару [id : указатель на элемент].

да, пожалуй так будет лучше. спасибо.

жду ещё варианты, если не будет, завра закрою тему

всё-таки всё-равно пробегаться нужно по списку.
когда из истории надо удалить, нужно и из QHash удалить и из Qlist. Не зная номера в списке, удалить по элементу можно только пробегаясь по списку. Ну или removeAll(указатель на эл-т), но тоже не быстро.

Адреса элементов в QList могут "уплыть"

- при удалении/вставке если sizeof(element) <= sizeof(void) (маловероятно но все же - напр QString)
- при std::sort/qSort
- при std::remove_if

Почти наверняка этого не будет, но заботиться об этом напрягает. Если связываться с хранением адресов то лучше std::map. Первоначальный вариант неплох, но для удаления придется использовать линейный поиск по id. Можно сделать одним QHash, только

- запоминать id первого элемента в переменной
- в элементе хранить id следующего (или адрес - по вкусу)

Ваше право, но зачем? Разве тема кому-то мешает?  :)

1)при удалении тогда надо будет лезть в предыдущий элемент и задавать новый id следующего
2)в случаях хранения элементов не как истории, указатель на следующий элемент не нужен

а что насчёт QCache? в описании ничего не написано про порядок в нём, но думаю что как и QHash(

Придумываете. :)
В QList храним указатели на элементы, специально для вас в скобках написал. :)

QList+QHash часто использую,и да, указатели - тогда все быстро и компактно

хорошо, есть список и хеш.

C++ (Qt)
		QHash<IdType, TreeNode*> _history;
        QList <TreeNode*> _historyOrder;

1)получить эл-т

C++ (Qt)
TreeNode* nodePtr = _history[id];

2)добавить

C++ (Qt)
        _history.insert(newId, newNodePtr );
        _historyOrder.append(newNode);

3)удалить

C++ (Qt)
            _history.remove(nodePtr->id);
            _historyOrder.removeOne(nodePtr);

removeOne(nodePtr) будет работать?

Да, ну и слазите в следующий/предыдущий - зато один контейнер на все-про все

Здесь указатели, во втором тоже, где ж тогда сами тела?  :)

Будет, но все равно это поиск перебором

Внимание! В куче.
И владеть элементами должен QList.

Не то чтобы "ошибка" или "плохо", но как-то слишком развесисто, кучеряво  :)

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

Почему?
QList и так и так будет все хранить в куче развесисто и кучеряво. :)

Смотрите, при добавлении в хеш элемента с ключем, который уже есть в хеше, приведет к замене элемента для этого ключа. Т.е. ключ-значение будет по прежнему одно.
А вот в QList вы добавите еще один элемент.

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

Похоже, что нужен аналог Java-класса LinkedHashMap (http://docs.oracle.com/javase/7/docs/api/java/util/LinkedHashMap.html).

Можно сразу взять готовый и навороченный boost::multi_index (http://www.boost.org/doc/libs/1_54_0/libs/multi_index/doc/tutorial/index.html). Там можно у контейнера сразу несколько индексов иметь: по ключу id и по порядку добавления.

Или что-то свое сделать. Вроде бы вот так вполне должно работать:
Итераторы у std::list не инвалидируются при добавлении/удалении элементов. Поиск итератора по ключу делается за O(log n), а по итератору можно и значение вернуть, и удалить элемент из std::list за константное время.

Да, все четко. Вот как бы еще индекс элемента иметь (да, это др задача, просто у меня она есть  :))

в общем пока имею:

1) Qlist с указателями и QHash c [ид,указатель];

2) добавляться элемент  дважды в историю не будет. При изменении какого либо эл-та, уже существующего в очереди на Submit в  истории, в хеш и список не заноситься новый элемент, а изменяется существующи

3) пробегаться по Qlist для поиска по значению(в данном случае это указатель) нужно только в одном случае, когда элемент сначала добавили, а потом удалили. Из хеша удаляется по ключу.

4) После того как делаем Sumbit и  по очереди из списка все элементы занеслись\изменились\удалились в базу, список чистится. Из хэша указатели удаляются во время прохода. Если на каком-то шаге возникла ошибка то выход из цикла и удаление из списка всех элементов до косячного.

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

Может тема уже для автора не актуальна, но для меня интересна.
Мозг сломал, как скрестить QLIst c QHash. Вообще не возможно. Нет, если задаста целью, то у меня есть пару вариантов, но это крик души, КРИК!

Столкнулся с проблемой автора.
Точно также думал реализовывать через дельту (историю изменений).

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

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

Дельту держать бессмысленно, проще держать два списка - один оригинальный, второй клиентский.
При обновлении чего либо, проще пробежаться по 100 тыс. записям и построить новый. Благо пробегание по 100 тыс. записей в QVecore (да даже в QLIst) детский лепет по сравнению с прорисовкой окна. Я повторюсь - НИЧЕГО НЕ СТОИТ! Вообще. Также вы должны понимать, что пробег по этим записям - это либо запись в БД, либо отмена - редкие операции, которые по времени не сопоставимы (с записью в БД и придумайте сами).

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

Анализ держания дельты - при любой операции (вставке, удалении) -  нужна её сортировка.

А идею автора не понял - перестройка всего и вся (всех листов и хешей)
Если автор простой код создал, хочу чтобы поделился как.

Цена Хеша и Листа, его заполнения, кол-во к нему обращений не стОит цене линейного перебора записей.

Замете, я беру граничные значение 100 тыч. записей. Граничней некуда. Вьюха  загнётся на 10 тыс.

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

Вы правы конечно, просто очень хотел усилить. Иногда незаметны другие ресурсоемкие операции, а свои видно на лицо, поэтому иногда акцент делается не на тех оптимизациях. Это как знаете - утверждение, которое я никогда не понимал: "Скриптовые языки программирования догнали по производительности нативные приложения". Как, как это может быть, любому готов был доказать, что это бред (благо, не пришлось). Пока не пришло прозрение - 1 мс на Си, или 30 мс на скрипте - для пользователя не важно. Они одинаково быстры. Он глазом дольше моргает. Он быстрее не среагирует. Так и тут, модель - это не та вещь, которая минует участие человека, она только для взаимодействия с пользователем и создана. Именно в этом контексте, операция перебора 100 тыс. записей ничего не стоит. Да и вообще, 100 тыс. Кому скажи, открой ексель со 100 тыс. записями, он у виска покрутит (если не ошибаюсь, там макс 65 тыс.). Но модель со 100 тыс. имеет почему то право на жизнь.

В общем для этой ситуации может и действительно лучше использовать вектор, но вот другая ситуация из того же проекта:
поиск по дереву. Надо сохранять куда-то индексы и при каждом вызове вьюхой Data(index, Qt::BackgroundRole) проверять лежит ли он в результатах (кроме того надо оставить порядок, чтобы можно было двигаться по результатам вверх-вниз) А это операция повторяется куда чаще чем выборочное изменение модели в предыдущем примере. Записей где-то около 5тыс. В результах поиска допустим будет 3тыс индексов. Таким образом грубо говоря 5*3тыс проходов. Тут бы я не рискнул список использовать.
вот собственно тема http://www.prog.org.ru/index.php?topic=25659.msg183709#msg183709