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

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?

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ś.

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.

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.