Печать страницы

Название: QPriorityQueue
Отправлено: SLiDER от Ноябрь 08, 2006, 17:51

Понадобилась мне недавно очередь с приоритетами, заглянул в Tulip не нашел, а так как на стандартную библиотеку в этом проекте использовать нехочется, решил написать это детище сам. Смотрим далее что получилось. Может кому и пригодиться.
Для начала, мне очень нравится интерфейс std::priority_queue и конечный вариант будет весьма похож на нее (только без поддержки итераторов, т.к. лень, сейчас не нужны).
Посмотрев на реализацию stl и Qt родил последовательно три вот таких класса:
1. Ни что иное как QQueue с расширенной функциональностью. Реализация через наследование от QList-а с добавлением определять функцию сортировки. Т.к. используется qSort то получем соответствующее ограничение: либо используем стандартные для Qt функции qLess и qGreater, либо с больной головой сами пытаемся реализовать соответствующие функторы. Все очень просто, но зато дешево и сердито.

Код:

template <typename T, typename LessThan=qLess<typename T> >
class QPriorityQueue : public QList<T>{
	LessThan comp;
	public:
		inline QPriorityQueue(): comp() {}
		inline ~QPriorityQueue() {}
		inline void enqueue(const T &t) { QList<T>::append(t); qSort(QList<T>::begin(), QList<T>::end(), comp);}
		inline T dequeue() { return QList<T>::takeFirst(); }
		inline T &head() { return QList<T>::first(); }
		inline const T &head() const { return QList<T>::first(); }
};

2. Больше похоже на stl, так как хочется, все таки, отвязаться от QList-а, в смысле наследования. Этакий промежуточный вариант но тоже может быть полезен, так как в отличие от следующего случая имеет более простой интерфейс.

Код:

template <typename T, typename LessThan=qLess<typename T> >
class QPriorityQueue{
	QList<T> cont;
	LessThan comp;
public:
	inline QPriorityQueue(): comp() {}
	inline QPriorityQueue(const QList &_cont): cont(_cont), comp() {}
	inline ~QPriorityQueue() {}
	inline void enqueue(const T &t) { cont.append(t); qSort(cont.begin(), cont.end(), comp);}
	inline T dequeue() { return cont.takeFirst(); }
	inline T &head() { return cont.first(); }
	inline const T &head() const { return cont.first(); }
};

3. Ну и наконец почти QSTL 8-). Избавляемся от QList-а вовсе, и имем возможность использовать другие контейнеры (например QVector), и добавляем, так не хватающей нам, привычной функциональности из std::priority_queue.

Код:

template <typename T, typename Cont=QList<T>, typename LessThan=qLess<typename T> >
class QPriorityQueue{
	Cont cont;
	LessThan comp;
public:
	inline QPriorityQueue(): comp() {}
	inline QPriorityQueue(const Cont &_cont): cont(_cont), comp() {}
	inline ~QPriorityQueue() {}
	inline void enqueue(const T &t) { cont.push_back(t); qSort(cont.begin(), cont.end(), comp);}
	inline T dequeue() { T t = cont.front(); cont.pop_front(); return t; }
	inline T &head() { return cont.front(); }
	inline void clear() { return cont.clear(); }
	inline void size() { return cont.size(); }
	inline bool empty() { return cont.empty(); }
	inline T &top() { return cont.front(); }
	inline const T &head() const { return cont.first(); }
};

Вот собственно и все. Хотелось бы услышать мнения, предпочтения, рекомендации.

P.S. Контейнеры конечно же должны поддерживать соответствующие интерфейсы, а объекты помещаемые в очередь иметь реализацию оператора <.

P.S. Тут есть еще вопрос по контейнерам Qt, как у них с многопоточностью? Интерисует режим когда есть пара потоков, и один поток только забирает данные из контейнера, а другой только кладет. Возникнут ли здесь проблемы если не использовать примитвов межпоточной синхронизации при обращении к функциям контейнера.

Название: QPriorityQueue
Отправлено: Sergeich от Ноябрь 09, 2006, 17:02

Ужоснах! Каждая операция enqueue() требует O(n log (n) ) операций!!! Хотя реально добиться производительности O( 1 ).

добавлено спустя 41 минуту:

Более того, данный код работает неправильно: сортировка, используемая в qSort() не является стабильной, после сортировки элементы с одинаковым приоритетом могут идти в другом порядке, что нарушает принцип FIFO. В принципе это лечится использованием qStableSort(), но все равно это не дело.

Название: QPriorityQueue
Отправлено: SLiDER от Ноябрь 10, 2006, 00:17

Цитата: "Sergeich"

Ужоснах! Каждая операция enqueue() требует O(n log (n) ) операций!!!

Хммм. Это конечно не push_heap ... , а вы можете сходу предложить что-либо более экономное, с учетом использования произвольного метода сравнения приоритетов и на произвольном sequence container-е?

Цитата: "Sergeich"

Хотя реально добиться производительности O( 1 ).

А вот от сюда пожалуйста по подробнее, я еще понимаю O( n ), но O( 1 ). :?

Цитата: "Sergeich"

Более того, данный код работает неправильно: сортировка, используемая в qSort() не является стабильной, после сортировки элементы с одинаковым приоритетом могут идти в другом порядке, что нарушает принцип FIFO. В принципе это лечится использованием qStableSort(), но все равно это не дело.

Тут полностью согласен, еще вчера у себя заменил.

добавлено спустя 3 часа 1 минуту:

Цитата: "SLiDER"

Цитата: "Sergeich"

Ужоснах! Каждая операция enqueue() требует O(n log (n) ) операций!!!

Гммммм. Ну и дурь сморозил. :( Пойду посыплю голову пеплом. :cry:
Однако коментарии по поводу O( 1 ) хотелось бы послушать. :roll:

Название: QPriorityQueue
Отправлено: Sergeich от Ноябрь 10, 2006, 05:43

Производительности O(1), точнее O(log m), где m - кол-во возможных приоритетов можно добится при условии что m достаточно мало ( как это обычно и бывает на практике ). Схема такая: для каждого приоритета заводим свой QList<T> и все эти списки пихаем в QMap ( или если кол-во приоритетов заранее известно - в обычный массив ).

Название: QPriorityQueue
Отправлено: Tonal от Ноябрь 10, 2006, 07:59

В STL-е есть priority_queue которая как раз имеет характеристики описанные Sergeich.
Используй её, и будет тебе щастье! ;-)
Если интересен алгоритм, ищи в гугле "очередь с приоритетами" - там всё есть.

Название: QPriorityQueue
Отправлено: SLiDER от Ноябрь 10, 2006, 22:04

Цитата: "Tonal"

В STL-е есть priority_queue которая как раз имеет характеристики описанные Sergeich.
Используй её, и будет тебе щастье! ;-)

Цитата: "SLiDER"

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

Цитата: "SLiDER"

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

To Sergeich: Спасибо за идею.

Название: QPriorityQueue
Отправлено: Tonal от Ноябрь 11, 2006, 08:17

Звиняй, забыл начало. ;-)
А по поводу алгоритма - ещё он называется "Пирамидальная сортировка".
Общая трудоёмкость O(n log n).
Т. к. при dequeue и enqueue полностью выполнять сортировку нет надобности, трудоёмкость этих операций получается O(log n) - один проход цикла сортировки.

Заметь, значения в priority_queue хранятся в виде "кучи" а не сортированно.

Название: QPriorityQueue
Отправлено: bigirbis от Ноябрь 11, 2006, 18:20

Но вообще, интересно, когда это Standart Template Library, являющийся частью стандарта с++, стал нестандартным? :)

Название: QPriorityQueue
Отправлено: SLiDER от Ноябрь 12, 2006, 20:23

Цитата: "bigirbis"

Но вообще, интересно, когда это Standart Template Library, являющийся частью стандарта с++, стал нестандартным? :)

"на" это не "не" :D , и вообще этого "на" быть не должо, очепятка :oops:

Russian Qt Forum

Qt => Общие вопросы => Тема начата: SLiDER от Ноябрь 08, 2006, 17:51