Leo-20181118.md

Leo Lei | 雷雨

Nov 18, 2018

1. Leetcode

Random Pick with Weight

Given an array w of positive integers, where w[i] describes the weight of index i, write a function pickIndex which randomly picks an index in proportion to its weight.

Analysis

There is random.choices() method for such task Since Python 3.6. The source code can be found here.

The algorithm is like:

• getting the accumulated weights,
• randomly picking up a number that <= max(accumulated weights),
• finding the insertion index for the random number in the list of the accumulated weights, say i,
• returning population[i]. For this question, we can just return i.

Usually, a binary search(bisec) is used to find the insertion index, which costs O(logN).

Btw, numpy also provides a similar method: numpy.random.choice.

Implementation

class Solution:

    def __init__(self, w):
        """
        :type w: List[int]
        """
        from itertools import accumulate
        self.cumdist = list(accumulate(w))
        
        

    def pickIndex(self):
        """
        :rtype: int
        """
        r = random.random() * self.cumdist[-1]
        return bisect.bisect(self.cumdist, r)


# Your Solution object will be instantiated and called as such:
# obj = Solution(w)
# param_1 = obj.pickIndex()

2. Article and comment

Python 3 Random Module

Almost all module functions depend on the basic function random(), which generates a random float uniformly in the semi-open range [0.0, 1.0). Python uses the Mersenne Twister as the core generator. It produces 53-bit precision floats and has a period of 2**19937-1. The underlying implementation in C is both fast and threadsafe.

Functions for integers

• random.randrange(stop)
• random.randrange(start, stop[, step])
• random.randint(a, b), Return a random integer N such that a <= N <= b

Functions for sequences

• random.choice(seq)
• random.choices(population, weights=None, *, cum_weights=None, k=1)
• random.shuffle(x[, random]), Shuffle the sequence x in place.
• random.sample(population, k), Return a k length list of unique elements chosen from the population sequence or set. Used for random sampling without replacement.

Real-valued distributions

• random.random(), Return the next random floating point number in the range [0.0, 1.0).
• random.uniform(a, b)
• random.gauss(mu, sigma)
• random.normalvariate(mu, sigma)

3. New skill/tool

source code of Python random module

4. Share an article

What is the difference between a process and a thread?