current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
up vote 9 down vote favorite
2

I'm developing a physics simulation, and as I'm rather new to programming, I keep running into problems when producing large programs (memory issues mainly). I know about dynamic memory allocation and deletion (new / delete, etc), but I need a better approach to how I structure the program.

Let's say I'm simulating an experiment which is running for a few days, with a very large sampling rate. I'd need to simulate a billion samples, and run over them.

As a super-simplified version, we'll say a program takes voltages V[i], and sums them in fives:

i.e. NewV[0] = V[0] + V[1] + V[2] + V[3] + V[4]

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

then NewV[2] = V[2] + V[3] + V[4] + V[5] + V[6] ...and this goes on for a billion samples.

In the end, I'd have V[0], V[1], ..., V[1000000000], when instead the only ones I'd need to store for the next step are the last 5 V[i]s.

How would I delete / deallocate part of the array so that the memory is free to use again (say V[0] after the first part of the example where it is no longer needed)? Are there alternatives to how to structure such a program?

I've heard about malloc / free, but heard that they should not be used in C++ and that there are better alternatives.

Thanks very much!

tldr; what to do with parts of arrays (individual elements) I don't need anymore that are taking up a huge amount of memory?

share|improve this question
1  
You can't deallocate part of an array. You could re-allocate it to a smaller array somewhere else, but this may prove to be expensive. You could use a different data structure such as a linked list instead, possibly. Maybe you could also store the steps into V instead of in a new array. Fundamentally, though, I think your issue is either in your algorithms or your data structures, and since we don't have any details, it's hard to know how to do it efficiently. – Vincent Savard 17 hours ago
2  
Side note: SMA's of arbitrary length can be calculated particularly fast with this recurrence relation: NewV[n] = NewV[n-1] - V[n-1] + V[n+4] (your notation). But keep in mind that these aren't particularly useful filters. Their frequency response is a sinc, which is pretty much never what you want (really high sidelobes). – Steve Cox 15 hours ago
    
SMA = simple moving average, for anyone wondering. – Charles 14 hours ago
1  
@SteveCox, the way he wrote it, he's got an FIR filter. Your recurrence is the equivalent IIR form. Either way, you get to maintain a circular buffer of the last N readings. – John R. Strohm 13 hours ago
    
@JohnR.Strohm the impulse response is identical, and finite – Steve Cox 9 hours ago
up vote 35 down vote accepted

What you describe, "smoothing by fives", is a finite impulse response (FIR) digital filter. Such filters are implemented with circular buffers. You keep only the last N values, you keep an index into the buffer that tells you where the oldest value is, you overwrite the current oldest value with the newest one at each step, and you step the index, circularly, each time.

You keep your collected data, that you are going to crunch down, on disk.

Depending on your environment, this may be one of those places where you're better off getting experienced help. At a university, you put a note up on the bulletin board in the Computer Science Department, offering student wages (or even student consulting rates) for a few hours of work, to help you crunch your data. Or maybe you offer Undergraduate Research Opportunity points. Or something.

share|improve this answer
5  
A circular buffer indeed seems to be what I'm looking for! I've now installed the boost C++ libraries and included boost/circular_buffer.hpp, and is working as expected. Thanks, @John – Drummermean 15 hours ago
1  
only very short FIR filters are implemented in direct form in software, and SMA's almost never are. – Steve Cox 15 hours ago
    
@SteveCox: The edges-of-window formula you used is quite effective for integer and fixed-point filters, however it's incorrect for floating-point, where operations are not commutative. – Ben Voigt 10 hours ago
    
@BenVoigt i think you meant to respond to my other comment, but yes, that form introduces a limit cycle around a quantization which can be very tricky. thankfully though, this particular limit cycle happens to be stable. – Steve Cox 9 hours ago
up vote 11 down vote

Every problem can be solved by adding an additional level of indirection. So do that.

You can't delete part of an array in C++. But you can create a new array holding just the data you want to keep, then delete the old one. So you can build a data structure that allows you to "remove" elements you don't want from the front. What it will actually do is create a new array and copy the unremoved elements to the new one, then delete the old.

Or you could just use std::deque, which can effectively do this already. deque, or "double-ended queue", is a data structure intended for cases where you're deleting elements from one end while adding elements to the other.

share|improve this answer
18  
Every problem can be solved by adding an additional level of indirection ... except to many levels of indirection. – YSC 15 hours ago
8  
@YSC: and spelling :) – Lightness Races in Orbit 13 hours ago
    
for this particular problem std::deque is the way to go – davidbak 6 hours ago
1  
@davidbak -- What? There's no need to be constantly allocating and releasing memory. A fixed size circular buffer that is allocated once at initialization time is a much better fit to this problem. – David Hammen 4 hours ago
1  
@DavidHammen: Perhaps, but 1) The standard library doesn't have a "fixed-size circular buffer" in its toolkit. 2) If you really need such an optimization, you can do some allocator stuff to minimize reallocations through deque. That is, storing and re-using allocations as requested. So deque seems a perfectly adequate solution to the problem. – Nicol Bolas 2 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.