# Yet another resampling algorithm

 1 I searched for some resampling algorithms here and didn't find one similar enough to the one I'm going to post here. I don't think it's the fastest but it is simple enough to give it a shot. Anyway, I will show first the "basic" version, then a slight modification to make the "upgraded" one. I haven't benchmarked it but I think the "basic" is O(N logN) and the "upgraded" is O(N). I could be wrong though. p3 = [] probs = [] wsum = sum(w) for i in range(len(p)): probs.append(random.uniform(0,1)) w[i]=w[i]/wsum x = w[0] k = 0 j = 0 probs.append(1.0) probs = sorted(probs) while kprobs[j]: p3.append(p[k]) j=j+1 else: k=k+1 x=x+w[k] print p3  It can be seen that the slow part is probs = sorted(probs), which is O(N logN). But probs can be assigned from this array for a faster implementation: [1/N, 2/N, ... ,N-1/N, 1]. The "upgraded" version of the algorithm, would look like this in code: for i in range(len(p)): probs.append(i/len(p))  Leaving the rest almost untouched, making the algorithm faster (because the array is already sorted). One problem is that it doesn't follow the premise of "random" sampling of particles. Nonetheless, for N big it's not a problem I think, keeping the resampling fairly accurate. Finally, there are other parts that can be optimized. For example tweaking the code a bit, it isn't necessary to normalize w. But that's for another discussion :) This question is marked "community wiki". asked 22 Mar '12, 23:21 Francisco-3 11●4 accept rate: 0%
Be the first one to answer this question!
Question text:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

×5,185
×89
×57
×38