VoseAliasSampling slow for many samples

[M-Lampert]

The VoseAliasSampling implementation migrated from the older PathPy versions does as far as I am aware the same thing as torch.multinomial or np.random.choice. Both are an order of magnitude faster for large values and similarly fast for one sample. The following MWE shows this:

import torch

from pathpyG.processes import VoseAliasSampling

weights = torch.randint(0, 10, (3000,)).float()
sampler = VoseAliasSampling(weights.tolist())

Using the Jupyter cell magic %timeit, we get the following runtimes for each of them:

• Pathpy 1 sample:

  >>> %timeit sampler.sample()
  1.79 µs ± 23.3 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

• Torch 1 sample:

  >>> %timeit torch.multinomial(weights, 1, replacement=True)
  31.5 µs ± 2.14 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

• Torch 1 sample (interestingly, sampling 2 samples and only using one is 3x faster than sampling one):

  >>> %timeit torch.multinomial(weights, 2, replacement=True)[0]
  9.1 µs ± 106 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

• Pathpy 1000 samples:

  >>> %timeit [sampler.sample() for _ in range(1000)]
  1.77 ms ± 36.6 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

• Torch 1000 samples:

  >>> %timeit torch.multinomial(weights, 1000, replacement=True)
  30.1 µs ± 193 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

Although there is a small runtime benefit for single samples, I propose to remove this class altogether in favor of using torch.multinomial, since our goal is to speed up the code that would be using this sampler with torch anyway.