Gdzie zazwyczaj używałbym oprogramowania Deque w oprogramowaniu produkcyjnym?

Wiem, gdzie mam używać stosów, kolejek i drzew w aplikacjach, ale nigdy wcześniej nie korzystałem z Deque (Double Ended Queue). Gdzie zazwyczaj spotykam ich na wolności? Czy byłby w tych samych miejscach co Kolejka, ale z dodatkowymi łapami?

data-structures Inżynier świata
źródło

en.wikipedia.org/wiki/Double-ended_queue#Applications

Arseni Mourzenko

wygląda na to, że w tym wątku jest pewne zamieszanie. W Internecie „deque” to podwójna kolejka (wikipedia wspomina o implementacji listy linków). Jednak w C ++ STL „std :: deque” jest strukturą podobną do tablicy zaimplementowaną jako tablica bloków danych. Oferuje losowy dostęp, podobny do std :: vector, ale jego zdolność zmiany rozmiaru jest bliższa std :: list, ponieważ w miarę dodawania danych dodaje bloki i nie przenosi i nie przenosi istniejących danych.

DXM,

@DXM: deque STL jest jednak nadal kolejką podwójnie zakończoną i zapewnia szybsze operacje na końcach (w zależności od implementacji). To, że oferuje również dostęp do środka, nie czyni jego podstawowej operacji mniej podobną do kolejki.

gbjbaanb

@gbjbaanb: Mówię tylko, jeśli spojrzysz na publiczne interfejsy 3 klas: std :: vector, std :: list (lub std :: queue) i std :: deque, zobaczysz, że std :: vector i std :: deque mają identyczny interfejs publiczny i identyczne możliwości (std :: deque jest nieco bardziej elastyczny kosztem większej powierzchni pamięci). z drugiej strony std :: list i std :: queue zachowują się bardziej jak ich odpowiedniki CS, lista połączona i kolejka. ! CS deque = std :: deque

DXM

Uważam tę odpowiedź za bardziej praktyczną przez shiv.mymail - stackoverflow.com/questions/3880254/…

roottraveller

Odpowiedzi:

Jednym ze sposobów użycia deque jest „starzenie się” przedmiotów. Zwykle jest używany jako funkcja cofania lub historii. Nowa akcja jest wstawiana do deque. Najstarsze przedmioty są z przodu. Ograniczenie wielkości deque zmusza elementy z przodu do usunięcia w pewnym momencie, gdy wstawiane są nowe elementy (starzenie najstarszych elementów). Następnie zapewnia szybki dostęp do obu końców konstrukcji, ponieważ natychmiast znasz najstarsze i najnowsze elementy, aby albo usunąć przód i wykonać najstarszą akcję w O (1), albo cofnąć w O (1).

jmq
źródło

Nie sądzę, że deques są tutaj używane / potrzebne. Wystarczy prosty (może ograniczony rozmiar) stos.

Konrad Rudolph,

@Konrad Jak starzycie przedmioty w prostym stosie? (tj. jak usunąć polecenia, które są „za stare”?)

Andres F.,

@AndresF. Czy wiek jest niezależny od wielkości stosu? Jeśli tak, to nigdy nie słyszałem o tej strukturze danych. W przeciwnym razie jest to po prostu stos o ustalonym rozmiarze, który może być zaimplementowany w postaci deque, lub po prostu przez postulowanie prostszej struktury danych zwanej stosem o stałej wielkości.

Konrad Rudolph

A więc deques są w końcu przydatne;) Nigdy nie słyszałem o stosie o stałym rozmiarze (w sensie, że masz na myśli usunięcie najstarszego przedmiotu). Ma to sens, ale nie to, co zwykle rozumie się przez „stos”, i czy rzeczywiście jest to prostsze, okaże się :)

Andres F.

Zostało to opublikowane w komentarzach do pierwotnego pytania: en.wikipedia.org/wiki/Double-ended_queue To tylko podwójna kolejka. Użyłem go w praktyce w sposób opisany powyżej (dlatego go opublikowałem). W prawdziwym stosie jedynymi operacjami, które powinieneś mieć, są push, pop, top i peek (moglibyśmy argumentować inne, ale ogólnie tak jest). Nie powinieneś wiedzieć o tym, co znajduje się na dole stosu, ani nawet o tym, jak uzyskać dostęp do dna. W „stosie o stałym rozmiarze” po prostu wygenerowałbyś przepełnienie stosu zamiast starzejących się starych przedmiotów po jego wypełnieniu.

jmq

Doskonałe pytanie. Nie pamiętam naszego kursu CS 102 wspominającego o pojedynczej aplikacji dla podwójnie zakończonej kolejki.

Do dziś jedyną aplikacją, którą znam, jest harmonogram kradzieży pracy wspomniany w artykule w Wikipedii .

Działa zasadniczo w następujący sposób:

W normalnym, jednowątkowym modelu proceduralnym każde wywołanie funkcji wypycha rekord aktywacji na tak zwany stos wywołań . Rekord aktywacji zawiera lokalne zmienne i parametry tego połączenia. Po zakończeniu wywołania metody („zwraca”) ostatni rekord aktywacyjny jest usuwany ze stosu wywołań.

Jest to szczególnie ważne, ponieważ w ten sposób realizowana jest rekurencja: struktura rekurencji jest reprezentowana w bieżącym stanie stosu wywołań.

Równoległy algorytm rekurencyjny możemy wykorzystać tę właściwość, zastępując stos wywołań kolejką wywołań. Każdy wątek w obliczeniach pobiera własną kolejkę wywołań i przesuwa i aktywuje rekordy aktywacji, jak w przypadku wykonywania sekwencyjnego.

Ale gdy wątek zakończy pracę (= kolejka wywołań jest pusta), kradnie pracę z innego wątku, usuwając rekord aktywacyjny z kolejki wywołań tego wątku, usuwając go z „niewłaściwego” końca.

Zasadniczo kolejka połączeń działa jak dwa stosy połączeń, które obsługują teraz dwa wątki.

Konrad Rudolph
źródło

Czy masz na to źródło? Brzmi interesująco.

kyjelly90210

@ Richard1987 Artykuł w Wikipedii cytuje oryginalny artykuł. Istnieje kilka implementacji, na przykład implementacja kradzieży pracy równoległej rozszerzenia GNU c ++ stdlib (ale kod jest okropny do odczytania) lub równoległa implementacja uogólnionego podziału i podboju przez ciebie naprawdę (ale ta ostatnia używa bardzo idiomatycznego stylu programowania szczególnie do biblioteki i dlatego trudna do odczytania)

Konrad Rudolph