ReSQL.ru
     
powered by simpleCommunicator - 2.0.49     © 2025 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Когда используются структуры типа деки (deque)?
25 сообщений из 26, страница 1 из 2
  1  все
Когда используются структуры типа деки (deque)?
    #39728419
Фэйтл Эра
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Фэйтл Эра
Участник
Привидите, пожалуйста, практический пример использования деков.
Не их вырожденных случаев, типа очереди или стека, а именно чистого дека.
Спасибо.
...
Рейтинг: 0 / 0
06.11.2018, 11:23
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39728508
Фотография skyANA
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
skyANA
Участник
https://docs.python.org/2/library/collections.html#collections.deque
...
Рейтинг: 0 / 0
06.11.2018, 13:44
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39728534
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
Фэйтл ЭраПривидите, пожалуйста, практический пример использования деков
Это оптимизация, соответственно применяется в оптимальных местах. В массовой практике оптимальность скрывается в библиотеках и большинству двусторонние очереди ненужны. В менее массовой практике (например - компиляторы) эта штука позволяет быстро (эффективно) и удобно манипулировать данными.

Пример библиотеки - работа с очередями сообщений. Выкидывать сообщение из начала очереди в случае массива крайне неэффективно, а вот в двустороннюю очередь ложить с конца и выкидывать с начала вполне эффективно.
...
Рейтинг: 0 / 0
06.11.2018, 14:06
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39728611
Фэйтл Эра
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Фэйтл Эра
Участник
alex55555Фэйтл ЭраПривидите, пожалуйста, практический пример использования деков
...
Пример библиотеки - работа с очередями...
Спасибо, но зачем ты про очередь рассказал? Может, ты вопрос до конца не дочитал?
...
Рейтинг: 0 / 0
06.11.2018, 15:25
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39728631
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
Фэйтл ЭраМожет, ты вопрос до конца не дочитал?
Может я не дочитал, а может и ты не понял.
...
Рейтинг: 0 / 0
06.11.2018, 15:50
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39728859
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
Фэйтл ЭраПривидите, пожалуйста, практический пример использования деков.
Не их вырожденных случаев, типа очереди или стека, а именно чистого дека.
Спасибо.

Практически любой брокер сообщений
...
Рейтинг: 0 / 0
06.11.2018, 20:08
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39728863
Фотография SashaMercury
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
SashaMercury
Участник
alex55555Фэйтл ЭраПривидите, пожалуйста, практический пример использования деков
Это оптимизация, соответственно применяется в оптимальных местах. В массовой практике оптимальность скрывается в библиотеках и большинству двусторонние очереди ненужны. В менее массовой практике (например - компиляторы) эта штука позволяет быстро (эффективно) и удобно манипулировать данными.

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

Дело скорее не в эффективности, а в том насколько это правильно или неправильно
...
Рейтинг: 0 / 0
06.11.2018, 20:11
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39728884
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
SashaMercuryДело скорее не в эффективности, а в том насколько это правильно или неправильно
В "правильной" постановке должны быть указаны более чёткие критерии. Итог работы бизнеса - деньги. Эффективность - выход на вложения. Где здесь что-то про "правильность"? Ещё Маркс подметил (правда со слов другого персонажа), что нет такого преступления, на которое не пошёл бы капиталист ради 300% прибыли. А я перефразирую так - нет тех правил, которые бы капиталист не захотел нарушить, ради получения прибыли. Поэтому в мире бизнеса ваш подход совершенно неприемлем. А основная доля всячески "брокеров сообщений" как раз там.
...
Рейтинг: 0 / 0
06.11.2018, 20:52
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729417
MBo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MBo
Гость
alex55555 Выкидывать сообщение из начала очереди в случае массива крайне неэффективно

Это не так, зависит от реализации очереди в массиве.
...
Рейтинг: 0 / 0
07.11.2018, 16:38
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729430
MBo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MBo
Гость
Фэйтл Эра,

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

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

Можно попробовать решить её с помощью упомянутой структуры данных.
За линейное время (пропорционально N, независимо от от K)
...
Рейтинг: 0 / 0
07.11.2018, 16:51
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729561
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
Фэйтл ЭраПривидите, пожалуйста, практический пример использования деков.
Не их вырожденных случаев, типа очереди или стека, а именно чистого дека.
Например, когда размер загружаемых данных заранее не известен, а после загрузки к данным нужен быстрый произвольный доступ по типу массива. Дек позволяет выделять память по мере загрузки без реаллокаций. Ну и дает индексный доступ с O(1).
В отличие от вектора или списка, у которых есть только одно из этих свойств.
...
Рейтинг: 0 / 0
07.11.2018, 20:14
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729564
MBo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MBo
Гость
Anatoly Moskovsky,
это не свойство дека, как структуры данных, а особенность реализации его в с++
...
Рейтинг: 0 / 0
07.11.2018, 20:21
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729613
Фотография Anatoly Moskovsky
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Anatoly Moskovsky
Участник
MBo,

Ну почему же только С++. Во многих языках реализовано так же.
ТС явно указал что имеет в виду не очередь (изначальный смысл дека), а другие применения, т.е. он рассматривает дек не как абстрактный тип данных представляющий концепцию очереди, а как средство реализации этой концепции.
Вот я ему и привел что для чего еще можно использовать одну из реализаций.
...
Рейтинг: 0 / 0
07.11.2018, 22:48
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729621
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
mayton
Участник
Фэйтл Эраalex55555пропущено...

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

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

Не так ли?
...
Рейтинг: 0 / 0
07.11.2018, 22:53
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729748
MBo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MBo
Гость
Anatoly Moskovsky,
ОК, возможно, мы с Вами немного по-разному додумываем, что хотел автор ;)
...
Рейтинг: 0 / 0
08.11.2018, 08:54
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729849
Фэйтл Эра
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Фэйтл Эра
Участник
Anatoly Moskovsky...
Например, когда размер загружаемых данных заранее не известен, а после загрузки к данным нужен быстрый произвольный доступ по типу массива. Дек позволяет выделять память по мере загрузки без реаллокаций...
Зависит от реализации. Да, важно знать, как реализовано, чтобы грамотно выбрать конкретный тип реализации контейнера для своего случая.
...
Всех прошу извинить за невнятный вопрос в начальной теме: я ошибся, пытаясь грубо классифицировать контейнеры по их общепринятым названиям (векторы-спискы-деки-...) реализуемых структур данных; для правильного выбора в конкретных случаях полезно также учитывать и их реализацию.
...
Спасибо.
...
Рейтинг: 0 / 0
08.11.2018, 11:46
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729876
Фэйтл Эра
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Фэйтл Эра
Участник
В англоязычном варианте статьи в Википедии в качестве примера использования дека указан алгоритм планирования заданий "A-Steal".
Алгоритм представляет собой вариант реализации задачи балансировки нагрузки для нескольких процессоров Для каждого процессора выделяется отдельный дек с тредами. Для выполнения следующего треда процессор извлекает (с удалением) первый элемент из дека. Если текущий тред "форкается", он снова помещается в начало дека, а выполняется новый тред. Когда один из процессоров завершает выполнение всех "своих" (например, когда его дек становится пустым) тредов, он может "украсть" тред другого процессора: извлекает для исполнения последний элемент дека другого процессора.
...
На немецкой странице в качестве примера использования деков названы алгоритмы реализации недетерминированных конечных автоматов, а также для реализации текстового поиска с использованием регулярных выражений (алгоритм поиска на основе шаблонов).
Еще там сказано, что деки являются единственной структурой данных для эзотерического языка программирования ABC: https://esolangs.org/wiki/AlPhAbEt#Queack_operators.
...
Рейтинг: 0 / 0
08.11.2018, 12:53
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729943
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MBoМожно попробовать решить её с помощью упомянутой структуры данных.
Но проще и эффективнее использовать кольцевой буфер. O(1).
...
Рейтинг: 0 / 0
08.11.2018, 14:36
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39729948
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
MBoalex55555 Выкидывать сообщение из начала очереди в случае массива крайне неэффективно

Это не так, зависит от реализации очереди в массиве.
Ждём доказательств. Ну и готовимся пороть за очевидные косяки.
...
Рейтинг: 0 / 0
08.11.2018, 14:41
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39730022
Фотография Akina
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Akina
Участник
Фэйтл ЭраПривидите, пожалуйста, практический пример использования деков.
Очередь в травмпункте.

Добавление в начало - пришёл новый пациент.
Удаление из начала - он посмотрел, что очередь не шевелится, и ушёл в платный ТП.
Удаление с конца - отлеченный ушёл.
Добавление в конец - он вернулся "только спросить".
Удаление из середины - прислали на помощь второго врача, специалиста исключительно по левым пяткам.
Добавление в середину - ему надоели левые пятки, и он ушёл на обед.
...
Рейтинг: 0 / 0
08.11.2018, 16:17
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39730055
MBo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MBo
Гость
alex55555,
Кольцевая очередь в массиве.
Пока хватает места, добавляем в конец, сдвигая правый индекс вправо
Код: plaintext
1.
right = (right + 1) % size.


Извлекаем из начала, сдвигая левый индекс вправо таким же образом. O(1) на операцию.
...
Рейтинг: 0 / 0
08.11.2018, 17:16
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39730058
MBo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MBo
Гость
Dimitry Sibiryakov,
А как именно?
Под сложностью N я имею в виду- O(N) на обработку всего набора данных, т.е. O(1) на каждый сдвиг окна.
...
Рейтинг: 0 / 0
08.11.2018, 17:18
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39730568
alex55555
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
alex55555
Участник
MBoКольцевая очередь в массиве.
Ну а тот случай, который всё же "так"? Заявляя безапелляционно "это не так" надо показать все случаи. А за одно ещё и показать отклонения от О(1) при необходимости наращивать массив, а так же при сокращении массива в случае спада после пиковой нагрузки (которая на пару порядков больше средней). Либо осветить тему "мне плевать на количество памяти".

Так что ждём продолжения.
...
Рейтинг: 0 / 0
09.11.2018, 14:08
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39730612
Dimitry Sibiryakov
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Dimitry Sibiryakov
Участник
MBoА как именно?
При ограниченном диапазоне значений - таблица частот. Добавляешь в неё приходящий элемент, удаляешь уходящий. Если пришёл новый максимум - запоминаешь его. Если ушёл текущий максимум - ищешь новый сканированием вниз.
...
Рейтинг: 0 / 0
09.11.2018, 14:49
| Ответить | Цитировать | Написать  
Когда используются структуры типа деки (deque)?
    #39730738
MBo
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
MBo
Гость
Dimitry Sibiryakov
Угу, хороший метод при плотном диапазоне значений.
...
Рейтинг: 0 / 0
09.11.2018, 16:15
| Ответить | Цитировать | Написать  
25 сообщений из 26, страница 1 из 2
  1  все
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Когда используются структуры типа деки (deque)?
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение
NoSQL.ru       Новости, Чат       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&fpage=12&tid=1340033]:
 0ms
get settings:
 9ms
get forum list:
 15ms
check forum access:
 5ms
check topic access:
 5ms
track hit:
 65ms
get topic data:
 12ms
get forum data:
 3ms
get page messages:
 67ms
get tp. blocked users:
 2ms
others: 12ms
total:  195ms
созд. / загр.: 195ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]