Cara profesional untuk menghasilkan masalah besar tanpa mengisi array besar: C ++, membebaskan memori dari bagian array

20

Saya mengembangkan simulasi fisika, dan karena saya agak baru dalam pemrograman, saya terus mengalami masalah ketika memproduksi program besar (terutama masalah memori). Saya tahu tentang alokasi dan penghapusan memori dinamis (baru / hapus, dll), tetapi saya perlu pendekatan yang lebih baik tentang bagaimana saya menyusun program.

Katakanlah saya mensimulasikan percobaan yang berjalan selama beberapa hari, dengan laju pengambilan sampel yang sangat besar. Saya perlu mensimulasikan satu miliar sampel, dan menabrak mereka.

Sebagai versi yang sangat disederhanakan, kita akan mengatakan sebuah program mengambil tegangan V [i], dan menjumlahkannya dalam lima:

yaitu NewV [0] = V [0] + V [1] + V [2] + V [3] + V [4]

lalu NewV [1] = V [1] + V [2] + V [3] + V [4] + V [5]

lalu NewV [2] = V [2] + V [3] + V [4] + V [5] + V [6] ... dan ini berlangsung selama satu miliar sampel.

Pada akhirnya, saya akan memiliki V [0], V [1], ..., V [1000000000], ketika satu-satunya yang saya perlu simpan untuk langkah selanjutnya adalah 5 V terakhir [i] s.

Bagaimana saya menghapus / deallocate bagian dari array sehingga memori bebas untuk menggunakan lagi (mengatakan V [0] setelah bagian pertama dari contoh di mana ia tidak lagi diperlukan)? Apakah ada alternatif untuk bagaimana menyusun program seperti itu?

Saya pernah mendengar tentang malloc / gratis, tetapi mendengar bahwa mereka tidak boleh digunakan dalam C ++ dan bahwa ada alternatif yang lebih baik.

Terima kasih banyak!

tldr; apa yang harus dilakukan dengan bagian array (elemen individual) yang tidak saya perlukan lagi yang menghabiskan banyak memori?

Drummermean
sumber
2
Anda tidak dapat membatalkan alokasi bagian dari array. Anda bisa mengalokasikannya kembali ke array yang lebih kecil di tempat lain, tetapi ini mungkin terbukti mahal. Anda bisa menggunakan struktur data yang berbeda seperti daftar tertaut, sebagai gantinya, mungkin. Mungkin Anda juga bisa menyimpan langkah-langkah ke dalam Vbukan dalam array baru. Namun pada dasarnya, saya pikir masalah Anda ada pada algoritme atau struktur data Anda, dan karena kami tidak memiliki detail, sulit untuk mengetahui cara melakukannya secara efisien.
Vincent Savard
4
Catatan sisi: SMA dengan panjang arbitrer dapat dihitung sangat cepat dengan hubungan perulangan ini: NewV [n] = NewV [n-1] - V [n-1] + V [n + 4] (notasi Anda). Namun perlu diingat bahwa ini bukan filter yang berguna. Respons frekuensi mereka adalah sinc, yang hampir tidak pernah seperti yang Anda inginkan (sidelob yang sangat tinggi).
Steve Cox
2
SMA = rata-rata bergerak sederhana, untuk siapa pun yang bertanya-tanya.
Charles
3
@SteveCox, cara dia menulisnya, dia punya filter FIR. Perulangan Anda adalah bentuk IIR yang setara. Either way, Anda bisa mempertahankan buffer melingkar dari pembacaan N terakhir.
John R. Strohm
@ JohnR.Strohm respons impuls identik, dan terbatas
Steve Cox

Jawaban:

58

Apa yang Anda gambarkan, "smoothing by fives", adalah filter digital hingga impulse response (FIR). Filter semacam itu diterapkan dengan buffer melingkar. Anda hanya menyimpan nilai N terakhir, Anda menyimpan indeks ke dalam buffer yang memberi tahu Anda di mana nilai terlama berada, Anda menimpa nilai terlama saat ini dengan yang terbaru di setiap langkah, dan Anda melangkah indeks, secara melingkar, setiap kali.

Anda menyimpan data yang dikumpulkan, bahwa Anda akan menguraikan, pada disk.

Tergantung pada lingkungan Anda, ini mungkin salah satu tempat di mana Anda lebih baik mendapatkan bantuan yang berpengalaman. Di sebuah universitas, Anda menaruh catatan di papan pengumuman di Departemen Ilmu Komputer, menawarkan upah siswa (atau bahkan tingkat konsultasi siswa) selama beberapa jam kerja, untuk membantu Anda mengolah data Anda. Atau mungkin Anda menawarkan poin Peluang Penelitian Sarjana. Atau sesuatu.

John R. Strohm
sumber
6
Buffer bundar tampaknya memang yang saya cari! Saya sekarang telah menginstal perpustakaan C ++ boost dan menyertakan boost / circular_buffer.hpp, dan berfungsi seperti yang diharapkan. Terima kasih, @John
Drummermean
2
hanya filter FIR yang sangat pendek diimplementasikan dalam bentuk langsung dalam perangkat lunak, dan SMA hampir tidak pernah.
Steve Cox
@SteveCox: Formula edge-of-window yang Anda gunakan cukup efektif untuk filter integer dan fixed-point, namun itu salah untuk floating-point, di mana operasi tidak komutatif.
Ben Voigt
@BenVoigt saya pikir Anda bermaksud menanggapi komentar saya yang lain, tapi ya, formulir itu memperkenalkan siklus batas sekitar kuantisasi yang bisa sangat rumit. untungnya, siklus batas khusus ini kebetulan stabil.
Steve Cox
Anda tidak benar-benar membutuhkan dorongan untuk buffer bundar untuk penggunaan itu. Anda akan menggunakan lebih banyak memori daripada yang dibutuhkan.
GameDeveloper
13

Setiap masalah dapat diselesaikan dengan menambahkan tingkat tipuan tambahan. Jadi lakukan itu.

Anda tidak dapat menghapus bagian dari array di C ++. Tapi Anda bisa membuat array baru yang hanya menyimpan data yang ingin Anda simpan, lalu hapus yang lama. Jadi Anda bisa membangun struktur data yang memungkinkan Anda untuk "menghapus" elemen yang tidak Anda inginkan dari depan. Apa yang sebenarnya akan dilakukan adalah membuat array baru dan menyalin elemen yang tidak dihapus ke yang baru, lalu hapus yang lama.

Atau Anda bisa menggunakan std::deque, yang sudah bisa melakukan ini secara efektif. deque, atau "antrian ujung ganda", adalah struktur data yang ditujukan untuk kasus di mana Anda menghapus elemen dari satu ujung sambil menambahkan elemen ke yang lain.

Nicol Bolas
sumber
30
Setiap masalah dapat diselesaikan dengan menambahkan tingkat tipuan tambahan ... kecuali ke berbagai tingkat tipuan.
YSC
17
@YSC: dan mengeja :)
Lightness Races dengan Monica
1
untuk masalah khusus ini std::dequeadalah cara untuk pergi
davidbak
7
@davidbak - Apa? Tidak perlu lagi mengalokasikan dan melepaskan memori. Buffer melingkar ukuran tetap yang dialokasikan satu kali pada waktu inisialisasi jauh lebih cocok untuk masalah ini.
David Hammen
2
@ Davidvidammen: Mungkin, tapi 1) Perpustakaan standar tidak memiliki "buffer melingkar ukuran tetap" di toolkitnya. 2) Jika Anda benar-benar membutuhkan pengoptimalan, Anda dapat melakukan beberapa hal pengalokasi untuk meminimalkan realokasi deque. Yaitu, menyimpan dan menggunakan kembali alokasi seperti yang diminta. Jadi dequesepertinya solusi yang sangat memadai untuk masalah ini.
Nicol Bolas
4

Jawaban FIR dan SMA yang Anda terima bagus dalam kasus Anda, namun saya ingin mengambil kesempatan untuk mendorong pendekatan yang lebih umum.

Apa yang Anda miliki di sini adalah aliran data: alih-alih menyusun program Anda dalam 3 langkah besar (dapatkan data, hitung, hasil keluaran) yang mengharuskan pemuatan semua data dalam memori sekaligus, Anda dapat menyusunnya sebagai saluran pipa .

Pipa dimulai dengan aliran, mengubahnya, dan mendorongnya ke wastafel.

Dalam kasus Anda, pipa tampak seperti:

  1. Baca item dari disk, keluarkan item satu per satu
  2. Menerima item satu per satu, untuk setiap item yang diterima memancarkan 5 terakhir yang diterima (di mana buffer bundar Anda masuk)
  3. Terima item 5 setiap kali, untuk setiap grup hitung hasilnya
  4. Terima hasilnya, tulis ke disk

C ++ cenderung menggunakan iterator daripada stream, tetapi jujur ​​aliran lebih mudah untuk dimodelkan (ada proposal untuk rentang yang akan mirip dengan stream):

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;
};

Dan kemudian, pipeline terlihat seperti:

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";
}

Streaming tidak selalu berlaku (mereka tidak bekerja ketika Anda membutuhkan akses acak ke data), tetapi ketika itu, mereka bergoyang: dengan mengoperasikan memori yang sangat sedikit Anda menyimpan semuanya dalam cache CPU.


Pada catatan lain: sepertinya masalah Anda mungkin "paralel memalukan", Anda mungkin ingin membagi file besar Anda menjadi potongan-potongan (perlu diingat, untuk diproses dengan windows 5, bahwa Anda perlu memiliki 4 elemen umum di setiap batas) dan kemudian memproses potongan secara paralel.

Jika CPU adalah penghambat (dan bukan I / O), maka Anda dapat mempercepatnya dengan meluncurkan satu proses per inti yang Anda miliki setelah membagi file dalam jumlah yang kira-kira sama.

Matthieu M.
sumber