Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
 Когда используются структуры типа деки (deque)?  [new]
Фэйтл Эра
Member

Откуда:
Сообщений: 98
Привидите, пожалуйста, практический пример использования деков.
Не их вырожденных случаев, типа очереди или стека, а именно чистого дека.
Спасибо.
6 ноя 18, 11:23    [21725001]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
skyANA
Member

Откуда: Зеленоград
Сообщений: 25717
https://docs.python.org/2/library/collections.html#collections.deque
6 ноя 18, 13:44    [21725196]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
alex55555
Member

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

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

Пример библиотеки - работа с очередями сообщений. Выкидывать сообщение из начала очереди в случае массива крайне неэффективно, а вот в двустороннюю очередь ложить с конца и выкидывать с начала вполне эффективно.
6 ноя 18, 14:06    [21725237]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
Фэйтл Эра
Member

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

...
Пример библиотеки - работа с очередями...

Спасибо, но зачем ты про очередь рассказал? Может, ты вопрос до конца не дочитал?
6 ноя 18, 15:25    [21725383]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
alex55555
Member

Откуда:
Сообщений: 907
Фэйтл Эра
Может, ты вопрос до конца не дочитал?

Может я не дочитал, а может и ты не понял.
6 ноя 18, 15:50    [21725423]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
SashaMercury
Member

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


Практически любой брокер сообщений
6 ноя 18, 20:08    [21725826]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
SashaMercury
Member

Откуда: Москва
Сообщений: 2637
alex55555
Фэйтл Эра
Привидите, пожалуйста, практический пример использования деков

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

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


Дело скорее не в эффективности, а в том насколько это правильно или неправильно
6 ноя 18, 20:11    [21725831]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
alex55555
Member

Откуда:
Сообщений: 907
SashaMercury
Дело скорее не в эффективности, а в том насколько это правильно или неправильно

В "правильной" постановке должны быть указаны более чёткие критерии. Итог работы бизнеса - деньги. Эффективность - выход на вложения. Где здесь что-то про "правильность"? Ещё Маркс подметил (правда со слов другого персонажа), что нет такого преступления, на которое не пошёл бы капиталист ради 300% прибыли. А я перефразирую так - нет тех правил, которые бы капиталист не захотел нарушить, ради получения прибыли. Поэтому в мире бизнеса ваш подход совершенно неприемлем. А основная доля всячески "брокеров сообщений" как раз там.
6 ноя 18, 20:52    [21725869]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
MBo
Member

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


Это не так, зависит от реализации очереди в массиве.
7 ноя 18, 16:38    [21727091]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
MBo
Member

Откуда:
Сообщений: 61
Фэйтл Эра,

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

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

Можно попробовать решить её с помощью упомянутой структуры данных.
За линейное время (пропорционально N, независимо от от K)
7 ноя 18, 16:51    [21727110]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
Anatoly Moskovsky
Member

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

Например, когда размер загружаемых данных заранее не известен, а после загрузки к данным нужен быстрый произвольный доступ по типу массива. Дек позволяет выделять память по мере загрузки без реаллокаций. Ну и дает индексный доступ с O(1).
В отличие от вектора или списка, у которых есть только одно из этих свойств.
7 ноя 18, 20:14    [21727351]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
MBo
Member

Откуда:
Сообщений: 61
Anatoly Moskovsky,
это не свойство дека, как структуры данных, а особенность реализации его в с++
7 ноя 18, 20:21    [21727357]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
Anatoly Moskovsky
Member

Откуда: Odessa
Сообщений: 6243
MBo,

Ну почему же только С++. Во многих языках реализовано так же.
ТС явно указал что имеет в виду не очередь (изначальный смысл дека), а другие применения, т.е. он рассматривает дек не как абстрактный тип данных представляющий концепцию очереди, а как средство реализации этой концепции.
Вот я ему и привел что для чего еще можно использовать одну из реализаций.
7 ноя 18, 22:48    [21727490]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
mayton
Member

Откуда: loopback
Сообщений: 37917
Фэйтл Эра
alex55555
пропущено...

...
Пример библиотеки - работа с очередями...

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

Тебе правильно сказали про очередь.

Но как мне кажется - не в твоих интересах хамить тем кто тебе бесплатно помогает.

Не так ли?
7 ноя 18, 22:53    [21727499]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
MBo
Member

Откуда:
Сообщений: 61
Anatoly Moskovsky,
ОК, возможно, мы с Вами немного по-разному додумываем, что хотел автор ;)
8 ноя 18, 08:54    [21727684]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
Фэйтл Эра
Member

Откуда:
Сообщений: 98
Anatoly Moskovsky
...
Например, когда размер загружаемых данных заранее не известен, а после загрузки к данным нужен быстрый произвольный доступ по типу массива. Дек позволяет выделять память по мере загрузки без реаллокаций...

Зависит от реализации. Да, важно знать, как реализовано, чтобы грамотно выбрать конкретный тип реализации контейнера для своего случая.
...
Всех прошу извинить за невнятный вопрос в начальной теме: я ошибся, пытаясь грубо классифицировать контейнеры по их общепринятым названиям (векторы-спискы-деки-...) реализуемых структур данных; для правильного выбора в конкретных случаях полезно также учитывать и их реализацию.
...
Спасибо.
8 ноя 18, 11:46    [21727932]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
Фэйтл Эра
Member

Откуда:
Сообщений: 98
В англоязычном варианте статьи в Википедии в качестве примера использования дека указан алгоритм планирования заданий "A-Steal".
Алгоритм представляет собой вариант реализации задачи балансировки нагрузки для нескольких процессоров Для каждого процессора выделяется отдельный дек с тредами. Для выполнения следующего треда процессор извлекает (с удалением) первый элемент из дека. Если текущий тред "форкается", он снова помещается в начало дека, а выполняется новый тред. Когда один из процессоров завершает выполнение всех "своих" (например, когда его дек становится пустым) тредов, он может "украсть" тред другого процессора: извлекает для исполнения последний элемент дека другого процессора.
...
На немецкой странице в качестве примера использования деков названы алгоритмы реализации недетерминированных конечных автоматов, а также для реализации текстового поиска с использованием регулярных выражений (алгоритм поиска на основе шаблонов).
Еще там сказано, что деки являются единственной структурой данных для эзотерического языка программирования ABC: https://esolangs.org/wiki/AlPhAbEt#Queack_operators.
8 ноя 18, 12:53    [21728035]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 46152
MBo
Можно попробовать решить её с помощью упомянутой структуры данных.

Но проще и эффективнее использовать кольцевой буфер. O(1).
8 ноя 18, 14:36    [21728189]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
alex55555
Member

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


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

Ждём доказательств. Ну и готовимся пороть за очевидные косяки.
8 ноя 18, 14:41    [21728200]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
Akina
Member

Откуда: Зеленоград, Москва, Россия
Сообщений: 18115
Фэйтл Эра
Привидите, пожалуйста, практический пример использования деков.

Очередь в травмпункте.

Добавление в начало - пришёл новый пациент.
Удаление из начала - он посмотрел, что очередь не шевелится, и ушёл в платный ТП.
Удаление с конца - отлеченный ушёл.
Добавление в конец - он вернулся "только спросить".
Удаление из середины - прислали на помощь второго врача, специалиста исключительно по левым пяткам.
Добавление в середину - ему надоели левые пятки, и он ушёл на обед.
8 ноя 18, 16:17    [21728365]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
MBo
Member

Откуда:
Сообщений: 61
alex55555,
Кольцевая очередь в массиве.
Пока хватает места, добавляем в конец, сдвигая правый индекс вправо
right = (right + 1) % size.

Извлекаем из начала, сдвигая левый индекс вправо таким же образом. O(1) на операцию.
8 ноя 18, 17:16    [21728454]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
MBo
Member

Откуда:
Сообщений: 61
Dimitry Sibiryakov,
А как именно?
Под сложностью N я имею в виду- O(N) на обработку всего набора данных, т.е. O(1) на каждый сдвиг окна.
8 ноя 18, 17:18    [21728458]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
alex55555
Member

Откуда:
Сообщений: 907
MBo
Кольцевая очередь в массиве.

Ну а тот случай, который всё же "так"? Заявляя безапелляционно "это не так" надо показать все случаи. А за одно ещё и показать отклонения от О(1) при необходимости наращивать массив, а так же при сокращении массива в случае спада после пиковой нагрузки (которая на пару порядков больше средней). Либо осветить тему "мне плевать на количество памяти".

Так что ждём продолжения.
9 ноя 18, 14:08    [21729546]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
Dimitry Sibiryakov
Member

Откуда:
Сообщений: 46152
MBo
А как именно?

При ограниченном диапазоне значений - таблица частот. Добавляешь в неё приходящий элемент, удаляешь уходящий. Если пришёл новый максимум - запоминаешь его. Если ушёл текущий максимум - ищешь новый сканированием вниз.
9 ноя 18, 14:49    [21729626]     Ответить | Цитировать Сообщить модератору
 Re: Когда используются структуры типа деки (deque)?  [new]
MBo
Member

Откуда:
Сообщений: 61
Dimitry Sibiryakov

Угу, хороший метод при плотном диапазоне значений.
9 ноя 18, 16:15    [21729829]     Ответить | Цитировать Сообщить модератору
Топик располагается на нескольких страницах: [1] 2   вперед  Ctrl      все
Все форумы / Программирование Ответить