How do I sample without replacement using a sampling-with-replacement function? [推广有奖]

I vaguely recall from grad school that the following is a valid approach to do a weighted sampling without replacement:

• Start with an initially empty "sampled set".
• Draw a (single) weighted sample with replacement with whatever method you have.
• Check whether you have already picked it.
• If you did, ignore it and move to the next sample. If you didn't, add it to your sampled set.
• Repeat 2-4 until the sampled set is of the desired size.
  

Will this give me a valid weighted sample?

(Context: for very large samples, R's sample(x,n,replace=FALSE,p) takes a really long time, much longer than implementing the strategy above.)

UPDATE 2012-01-05

Thank you everyone for your comments and responses! Regarding code, here's an example that faithfully reproduces what I'm trying to do (although I'm actually calling R from Python with RPy, but it seems the runtime characteristics are unchanged).

First, define the following function, which assumes a sufficiently long sequence of with-replacement samples as input:

It simply does a binary search for the number of non-unique samples needed to get enough unique samples. Now, in the interpreter:

As you can see, even for just 500 elements the difference is dramatic. I'm actually trying to sample 106 indices from a list of about 1.2×107, which takes hours using replace=FALSE.