Czy istnieje struktura danych przypominająca tablicę, która może rosnąć po obu stronach?

Question

Jestem studentem pracującym nad małym projektem na kursie obliczeniowym o wysokiej wydajności, a więc efektywność to kluczowy problem.

Powiedzmy, że mam wektor N floats i chcę usunąć najmniejsze n elementów i największe n elementów. Istnieją dwa proste sposoby osiągnięcia tego celu:

sort in ascending order // O(NlogN) 
remove the last n elements // O(1) 
invert elements order  // O(N) 
remove the last n elements // O(1) 

B

sort in ascending order  // O(NlogN) 
remove the last n elements // O(1) 
remove the first n elements // O(N) 

In A Odwracanie elementów zamówić wymagają wymiany wszystkich elementów, natomiast w B usunięcie pierwsze n elementów wymagają przesunięcia wszystkich pozostałych, aby zajęły pozycje pozostawione puste. Użycie std :: remove dałoby ten sam problem.

Gdybym mógł usunąć pierwsze n elementów za darmo, rozwiązanie B byłoby tańsze. To powinno być łatwe do osiągnięcia, jeżeli zamiast mieć wektor, tj. Tablicę z pustą przestrzenią po vector::end(), będę miał pojemnik z pewną wolną przestrzenią również przed vector::begin().

Więc pytanie brzmi: czy istnieją już takie tablicę podobną (czyli pamięć ciągły, bez związane listy) w niektórych bibliotekach (STL, Boost), który pozwala na O (1) wstawianie/usuwanie na obu stronach szyk?

Jeśli nie, to czy uważasz, że istnieją lepsze rozwiązania niż tworzenie takiej struktury danych?

Answer 1

Czy myślałeś o użyciu std::partition z niestandardowym funktora jak na poniższym przykładzie:

#include <iostream> 
#include <vector> 
#include <algorithm> 

template<typename T> 
class greaterLess { 
    T low; 
    T up; 
    public: 
    greaterLess(T const &l, T const &u) : low(l), up(u) {} 
    bool operator()(T const &e) { return !(e < low || e > up); } 
}; 

int main() 
{ 
    std::vector<double> v{2.0, 1.2, 3.2, 0.3, 5.9, 6.0, 4.3}; 
    auto it = std::partition(v.begin(), v.end(), greaterLess<double>(2.0, 5.0)); 
    v.erase(it, v.end()); 

    for(auto i : v) std::cout << i << " "; 
    std::cout << std::endl; 

    return 0; 
} 

ten sposób chcesz usunąć elementy z Twojego wektora w O(N) czasie.

Answer 2

Spróbuj boost::circular_buffer:

Obsługuje iteratory dostępu losowego, stałą wkładkę czasu i kasowanie operacji na początku lub na końcu bufora i interoperacyjności z algorytmów std.

Po przejrzeniu source wydaje się (i jest to logiczne), że dane są przechowywane jako ciągły blok pamięci.

Jedynym zastrzeżeniem jest to, że bufor ma stałą pojemność, a po jej wyczerpaniu elementy zostaną nadpisane. Możesz sam wykryć takie przypadki i ręcznie zmienić rozmiar bufora lub użyć boost::circular_buffer_space_optimized z deklarowaną pojemnością, ponieważ nie będzie go alokował, jeśli nie będzie potrzebny.

Answer 3

Aby zmniejszyć rozwijać wektor na obu końcach, można użyć pomysłu plasterków, rezerwując dodatkową pamięć, aby rozwinąć się do przodu z przodu iz tyłu, jeśli potrzebny jest wydajny wzrost.

Po prostu, utwórz klasę o nie tylko długości, ale indeksach dla pierwszych ostatnich elementów o wielkości & i wektor o odpowiedniej wielkości, aby utworzyć okno danych na bazowym bloku przechowywanych elementów pływających.Klasa C++ może udostępniać funkcje wbudowane, takie jak usuwanie elementów, adres do tablicy, znajdowanie n-tej największej wartości, przesunięcie wartości plasterków w dół lub w górę w celu wstawienia nowych elementów zachowujących posortowaną kolejność. Jeśli nie są dostępne żadne elementy zapasowe, wówczas dynamiczna alokacja nowego większego magazynu typu "float" pozwala na ciągły wzrost kosztem kopii w postaci macierzy.

Okrągły bufor jest zaprojektowany jako FIFO, z nowymi elementami dodanymi na końcu, usunięciem z przodu i niewpuszczaniem wstawiania w środku, zdefiniowana klasa może również (trywialnie) obsługiwać wartości indeksu tablicy różne od 0. N-1

Ze względu na lokalizację pamięci, unikanie nadmiernego oblężenia z powodu łańcuchów wskaźnikowych oraz potokowanie obliczeń indeksów dolnych na nowoczesnym procesorze, rozwiązanie oparte na macierzy (lub wektorze) najprawdopodobniej będzie najbardziej wydajne, pomimo kopiowania elementu podczas wstawiania. Deque byłby odpowiedni, ale nie gwarantuje ciągłego przechowywania.

Dodatkowe informacje uzupełniające. Badania zajęcia zapewniające plastry, znajdzie kilka prawdopodobnych alternatyw ocena:

A) std::slice which uses slice_arrays B) Boost Class Range

nadzieję, że to rodzaj specyficznej informacji, liczyliśmy na ogół prostsze jaśniejsze rozwiązanie jest bardziej w utrzymaniu, niż podchwytliwe . Spodziewam się, że wycinki i zakresy na posortowanych zestawach danych będą dość powszechne, na przykład filtrowanie danych eksperymentalnych, w których "wartości odstające" są wykluczone jako błędne odczyty.

Myślę, że dobrym rozwiązaniem powinno być - O (NlogN), 2xO (1), z dowolnymi wyszukiwaniami binarnymi O (logN +1) do filtrowania na wartościach oddalonych, zamiast usuwania ustalonej liczby małych lub duże wartości; ważne jest, że "O" jest względnie szybkie, czasami algorytm O (1) może być w praktyce wolniejszy dla praktycznych wartości N niż O (N).

Answer 4

jako uzupełnienie odpowiedzi @ 40two, przed partycjonowaniem macierzy należy znaleźć przestawnik partycjonowania, który będzie potrzebny do znalezienia n-tej najmniejszej liczby oraz n-tej największej liczby w tablicy nieposortowanej. Dyskusja na ten temat w języku SO: How to find the kth largest number in unsorted array

Istnieje kilka algorytmów rozwiązania tego problemu. Niektóre są deterministyczne O (N) - na nich jest wariacja na temat znalezienia mediany (mediana median). Istnieją pewne niedeterministyczne algorytmy ze średnim przypadkiem O (N). Dobra książka źródłowa do znalezienia tych algorytmów to Introduction to algorithms. także w książkach takich jak

więc w końcu, Twój kod będzie działał w O (N) czasu