Когда используются структуры типа деки (deque)?

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

https://docs.python.org/2/library/collections.html#collections.deque

Фэйтл Эра
Привидите, пожалуйста, практический пример использования деков

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

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

alex55555
Фэйтл Эра Привидите, пожалуйста, практический пример использования деков ... Пример библиотеки - работа с очередями...

Спасибо, но зачем ты про очередь рассказал? Может, ты вопрос до конца не дочитал?

Фэйтл Эра
Может, ты вопрос до конца не дочитал?

Может я не дочитал, а может и ты не понял.

Фэйтл Эра
Привидите, пожалуйста, практический пример использования деков. Не их вырожденных случаев, типа очереди или стека, а именно чистого дека. Спасибо.

Практически любой брокер сообщений

alex55555

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

Дело скорее не в эффективности, а в том насколько это правильно или неправильно

SashaMercury
Дело скорее не в эффективности, а в том насколько это правильно или неправильно

В "правильной" постановке должны быть указаны более чёткие критерии. Итог работы бизнеса - деньги. Эффективность - выход на вложения. Где здесь что-то про "правильность"? Ещё Маркс подметил (правда со слов другого персонажа), что нет такого преступления, на которое не пошёл бы капиталист ради 300% прибыли. А я перефразирую так - нет тех правил, которые бы капиталист не захотел нарушить, ради получения прибыли. Поэтому в мире бизнеса ваш подход совершенно неприемлем. А основная доля всячески "брокеров сообщений" как раз там.

alex55555
Выкидывать сообщение из начала очереди в случае массива крайне неэффективно

Это не так, зависит от реализации очереди в массиве.

Фэйтл Эра,

Есть такая задача, имеющая практическое применение:

Поступают отсчёты данных (вариант - есть массив из N элементов), нужно знать максимум за K последних отсчётов (максимум в скользящем окне). Или за последние K единиц времени.

Можно попробовать решить её с помощью упомянутой структуры данных.
За линейное время (пропорционально N, независимо от от K)