Draw small sample from large set with discrete distribution efficiently

I have two lists, both the same size, let's call them elements and weights. I want to choose one element of the elements list with discrete probability distribution given by weights. weight[i] corresponds to the probability of choosing elements[i]. elements never changes, but after every sample taken, weights changes (only the values, not the size).

I need an efficient way to do this with large lists.

I have an implementation in Python with numpy.random.choice(elements, p=weights) but taking a sample of size k from a set of size n where k << n is extremely inefficient. An implementation in any language is welcome, but I am working primarily in Python.

(This is used in a social network simulation with networkx. I have a weighted graph and a node i and I want to choose a node j from i's neighbors where the probability for each node is proportional to the weight of the edge between i and the given node. If I set the probability to 0 for non-neighbors, I don't have to generate the list of neighbors every time, I just need a list of all nodes.)

It will be used like this:

elements = [...]
weights = [...]

for(...):
    element = sample(elements, weights)
    *Some calculation with element and changing the values of weights*

Any contribution is appreciated!

Regards,

naroslife