Profesjonalny sposób na stworzenie dużego problemu bez wypełniania ogromnych tablic: C ++, wolna pamięć z części tablicy

20

Rozwijam symulację fizyki, a ponieważ jestem raczej nowy w programowaniu, ciągle napotykam problemy podczas tworzenia dużych programów (głównie problemy z pamięcią). Wiem o dynamicznym przydzielaniu i usuwaniu pamięci (nowe / usuwanie itp.), Ale potrzebuję lepszego podejścia do struktury programu.

Powiedzmy, że symuluję eksperyment, który trwa kilka dni, z bardzo dużą częstotliwością próbkowania. Musiałbym zasymulować miliard próbek i przejrzeć je.

W wersji super uproszczonej powiemy, że program pobiera napięcia V [i] i sumuje je w piątki:

tj. Nowe V [0] = V [0] + V [1] + V [2] + V [3] + V [4]

następnie NewV [1] = V [1] + V [2] + V [3] + V [4] + V [5]

następnie NewV [2] = V [2] + V [3] + V [4] + V [5] + V [6] ... i to trwa w przypadku miliarda próbek.

Na koniec miałbym V [0], V [1], ..., V [1000000000], gdy zamiast tego jedyne, które musiałbym zapisać na następny krok, to ostatnie 5 V [i] s.

Jak mam usunąć / cofnąć przydział części tablicy, aby pamięć mogła ponownie użyć (powiedz V [0] po pierwszej części przykładu, gdzie nie jest już potrzebna)? Czy istnieją alternatywy dla struktury takiego programu?

Słyszałem o malloc / free, ale słyszałem, że nie należy ich używać w C ++ i że istnieją lepsze alternatywy.

Dziękuję bardzo!

tldr; co zrobić z częściami tablic (pojedynczymi elementami), których już nie potrzebuję, które zajmują ogromną ilość pamięci?

Drummermean
źródło
2
Nie można cofnąć przydziału części tablicy. Możesz go ponownie przydzielić do mniejszej tablicy gdzie indziej, ale może to okazać się kosztowne. Zamiast tego możesz użyć innej struktury danych, takiej jak lista połączona. Może mógłbyś również zapisać kroki Vzamiast w nowej tablicy. Zasadniczo jednak myślę, że twój problem dotyczy algorytmów lub struktur danych, a ponieważ nie mamy żadnych szczegółów, trudno jest wiedzieć, jak to zrobić skutecznie.
Vincent Savard
4
Uwaga dodatkowa: SMA o dowolnej długości można obliczyć szczególnie szybko z tą relacją powtarzalności: NewV [n] = NewV [n-1] - V [n-1] + V [n + 4] (twoja notacja). Pamiętaj jednak, że nie są to szczególnie przydatne filtry. Ich pasmo przenoszenia to sinc, który prawie nigdy nie jest tym, czego chcesz (naprawdę wysokie sidelobes).
Steve Cox
2
SMA = prosta średnia ruchoma dla każdego, kto się zastanawia.
Charles
3
@ SteveCox, jak to napisał, ma filtr FIR. Twój nawrót jest równoważnym formularzem IIR. Tak czy inaczej, utrzymasz okrągły bufor ostatnich N odczytów.
John R. Strohm
@ JohnR.Strohm odpowiedź impulsowa jest identyczna i skończona
Steve Cox

Odpowiedzi:

58

To, co opisujesz, „wygładzanie przez piątki”, to filtr cyfrowy o skończonej odpowiedzi impulsowej (FIR). Takie filtry są implementowane z okrągłymi buforami. Zachowujesz tylko ostatnie N wartości, trzymasz indeks w buforze, który mówi ci, gdzie jest najstarsza wartość, nadpisujesz aktualną najstarszą wartość najnowszą wartością na każdym kroku i indeksujesz krokowo, za każdym razem.

Na dysku przechowujesz zgromadzone dane, które chcesz rozbić.

W zależności od środowiska może to być jedno z tych miejsc, w których lepiej jest uzyskać doświadczoną pomoc. Na uniwersytecie umieściłeś notatkę na tablicy ogłoszeń w dziale informatyki, oferując wynagrodzenie dla studentów (a nawet stawki za konsultacje studenckie) za kilka godzin pracy, aby pomóc ci przełamać swoje dane. A może oferujesz licencjackie punkty badań naukowych. Lub coś.

John R. Strohm
źródło
6
Rzeczywiście szukam okrągłego bufora! Zainstalowałem teraz biblioteki boost C ++ i dołączyłem boost / circular_buffer.hpp i działam zgodnie z oczekiwaniami. Dzięki, @John
Drummermean
2
tylko bardzo krótkie filtry FIR są implementowane bezpośrednio w oprogramowaniu, a SMA prawie nigdy nie są.
Steve Cox
@SteveCox: Zastosowana formuła krawędzi okna jest dość skuteczna w przypadku filtrów liczb całkowitych i stałopunktowych, jednak jest niepoprawna w przypadku liczb zmiennoprzecinkowych, w których operacje nie są przemienne.
Ben Voigt
@BenVoigt Myślę, że chciałeś odpowiedzieć na mój inny komentarz, ale tak, ta forma wprowadza cykl limitów wokół kwantyzacji, co może być bardzo trudne. na szczęście ten szczególny cykl limitów zdarza się być stabilny.
Steve Cox
Tak naprawdę nie potrzebujesz doładowania dla okrągłego bufora do tego użycia. Będziesz używał znacznie więcej pamięci, niż to konieczne.
GameDeveloper,
13

Każdy problem można rozwiązać, dodając dodatkowy poziom pośredni. Zrób to.

Nie można usunąć części tablicy w C ++. Ale możesz utworzyć nową tablicę zawierającą tylko dane, które chcesz zachować, a następnie usunąć starą. Dzięki temu możesz zbudować strukturę danych, która pozwala „usuwać” elementy, których nie chcesz z przodu. W rzeczywistości zrobi to, tworząc nową tablicę i kopiując nieusunięte elementy do nowej, a następnie usuwając starą.

Lub możesz po prostu użyć std::deque, który może już to skutecznie zrobić. dequelub „kolejka podwójnie zakończona” to struktura danych przeznaczona do przypadków usuwania elementów z jednego końca podczas dodawania elementów do drugiego.

Nicol Bolas
źródło
30
Każdy problem można rozwiązać, dodając dodatkowy poziom pośredni ... oprócz wielu poziomów pośrednich.
YSC
17
@YSC: i pisownia :)
Lekkość
1
dla tego konkretnego problemu std::dequejest droga
davidbak
7
@davidbak - Co? Nie ma potrzeby ciągłego przydzielania i zwalniania pamięci. Okrągły bufor o stałym rozmiarze, który jest przydzielany raz w czasie inicjalizacji, znacznie lepiej pasuje do tego problemu.
David Hammen,
2
@DavidHammen: Być może, ale 1) Biblioteka standardowa nie ma w swoim zestawie narzędzi „okrągłego bufora o stałej wielkości”. 2) Jeśli naprawdę potrzebujesz takiej optymalizacji, możesz wykonać kilka czynności związanych z alokatorem, aby zminimalizować realokacje deque. Oznacza to przechowywanie i ponowne wykorzystywanie przydziałów zgodnie z żądaniem. dequeWydaje się więc idealnym rozwiązaniem problemu.
Nicol Bolas,
4

Odpowiedzi FIR i SMA, które otrzymałeś, są dobre w twoim przypadku, jednak chciałbym skorzystać z okazji, aby posunąć się naprzód w bardziej ogólny sposób.

To, co masz tutaj, to strumień danych: zamiast strukturyzować swój program w 3 dużych krokach (pobieranie danych, obliczanie, wynik), które wymagają załadowania wszystkich danych na raz, możesz zamiast tego utworzyć strukturę potoku .

Rurociąg rozpoczyna się od strumienia, przekształca go i wypycha do zlewu.

W twoim przypadku rurociąg wygląda następująco:

  1. Odczytuj elementy z dysku, emituj elementy pojedynczo
  2. Odbieraj przedmioty pojedynczo, za każdy otrzymany przedmiot wyślij 5 ostatnich otrzymanych (tam, gdzie przychodzi twój okrągły bufor)
  3. Otrzymuj przedmioty 5 na raz, dla każdej grupy oblicz wynik
  4. Odbierz wynik, zapisz go na dysku

C ++ ma tendencję do używania iteratorów zamiast strumieni, ale szczerze mówiąc, łatwiej jest modelować strumienie (istnieje propozycja zakresów, które byłyby podobne do strumieni):

template <typename T>
class Stream {
public:
    virtual boost::optional<T> next() = 0;
    virtual ~Stream() {}
};

class ReaderStream: public Stream<Item> {
public:
    boost::optional<Item> next() override final;

private:
    std::ifstream file;
};

class WindowStream: public Stream<Window> {
public:
    boost::optional<Window> next() override final;

private:
    Window window;
    Stream<Item>& items;
};

class ResultStream: public Stream<Result> {
public:
    boost::optional<Result> next() override final;

private:
    Stream<Window>& windows;
};

A następnie rurociąg wygląda następująco:

ReaderStream itemStream("input.txt");
WindowStream windowStream(itemsStream, 5);
ResultStream resultStream(windowStream);
std::ofstream results("output.txt", std::ios::binary);

while (boost::optional<Result> result = resultStream.next()) {
    results << *result << "\n";
}

Strumienie nie zawsze mają zastosowanie (nie działają, gdy potrzebujesz losowego dostępu do danych), ale kiedy są, kołyszą się: działając na bardzo małej ilości pamięci, przechowujesz wszystko w pamięci podręcznej procesora.


Inna uwaga: wygląda na to, że twój problem może być „zawstydzająco równoległy”, możesz podzielić duży plik na części (pamiętaj, że w przypadku przetwarzania przez okna 5, musisz mieć 4 wspólne elementy na każdej granicy) a następnie przetwarzaj porcje równolegle.

Jeśli procesor jest wąskim gardłem (a nie We / Wy), możesz go przyspieszyć, uruchamiając jeden proces na rdzeń, który masz po podzieleniu plików na mniej więcej równe ilości.

Matthieu M.
źródło