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?
V
bukan 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.Jawaban:
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.
sumber
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.sumber
std::deque
adalah cara untuk pergideque
. Yaitu, menyimpan dan menggunakan kembali alokasi seperti yang diminta. Jadideque
sepertinya solusi yang sangat memadai untuk masalah ini.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:
C ++ cenderung menggunakan iterator daripada stream, tetapi jujur aliran lebih mudah untuk dimodelkan (ada proposal untuk rentang yang akan mirip dengan stream):
Dan kemudian, pipeline terlihat seperti:
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.
sumber