Repository: joke2k/faker
Pull request #792 (2018-08-02 15:40:16)

[Breaking changes] Refactor BaseProvider.random_* methods
Breaking changes:

* `.random_sample_unique` is removed in favor of `.random_sample`
* `.random_sample` now returns a list of unique elements instead of a set.

Non-Breaking changes:
* added `random_choices`

The plan is to release v0.8.18 _without_ this merged in, then merge it and release v1.0.0.

### What does this changes

* `.random_sample()` now returns a list of unique elements instead of a set.
* `.random_sample_unique()` is removed in favor of `.random_sample()`
* added `random_choices()`, `random_elements()` and `random_letters()`
* added `faker.utils.distribution.choices_distribution_unique()`

### What was wrong

Various methods on the `BaseProvider` were implemented with loops or list comprehensions where Python's `random` module already has more optimized methods to returns sequences.

### How this fixes it

The goal of this refactor is to improve performance by removing loops and leveraging `random` more.



fcurella: I'd like for #791 to wait for this
fcurella: The plan is to release `v0.8.18` _without_ this merged in, then merge it and release `v1.0.0`.

Patch:
diff --git a/faker/providers/__init__.py b/faker/providers/__init__.py
index 3a12f97e..38f2903c 100644
--- a/faker/providers/__init__.py
+++ b/faker/providers/__init__.py
@@ -4,7 +4,7 @@ from collections import Counter
 import re
 import string
 
-from faker.utils.distribution import choice_distribution
+from faker.utils.distribution import choices_distribution, choices_distribution_unique
 
 
 _re_hash = re.compile(r'#')
@@ -91,6 +91,13 @@ class BaseProvider(object):
         return self.generator.random.choice(
             getattr(string, 'letters', string.ascii_letters))
 
+    def random_letters(self, length=16):
+        """Returns a random letter (between a-z and A-Z)."""
+        return self.random_choices(
+            getattr(string, 'letters', string.ascii_letters),
+            length=length,
+        )
+
     def random_lowercase_letter(self):
         """Returns a random lowercase letter (between a-z)."""
         return self.generator.random.choice(string.ascii_lowercase)
@@ -99,9 +106,36 @@ class BaseProvider(object):
         """Returns a random letter (between A-Z)."""
         return self.generator.random.choice(string.ascii_uppercase)
 
-    def random_element(self, elements=('a', 'b', 'c')):
+    def random_elements(self, elements=('a', 'b', 'c'), length=None, unique=False):
+        fn = choices_distribution_unique if unique else choices_distribution
+
+        if length is None:
+            length = self.generator.random.randint(1, len(elements))
+
+        if unique and length > len(elements):
+            raise ValueError(
+                "Sample length cannot be longer than the number of unique elements to pick from.")
+
+        if isinstance(elements, dict):
+            choices = elements.keys()
+            probabilities = elements.values()
+        else:
+            if unique:
+                # shortcut
+                return self.generator.random.sample(elements, length)
+            choices = elements
+            probabilities = [1.0 for _ in range(len(choices))]
+
+        return fn(
+            list(choices),
+            list(probabilities),
+            self.generator.random,
+            length=length,
+        )
+
+    def random_choices(self, elements=('a', 'b', 'c'), length=None):
         """
-        Returns a random element from a passed object.
+        Returns a list of random, non-unique elements from a passed object.
 
         If `elements` is a dictionary, the value will be used as
         a weighting element. For example::
@@ -115,41 +149,32 @@ class BaseProvider(object):
             * `variable_4`: 10% probability
 
         """
+        return self.random_elements(elements, length, unique=False)
 
-        if isinstance(elements, dict):
-            choices = elements.keys()
-            probabilities = elements.values()
-            return choice_distribution(
-                list(choices),
-                list(probabilities),
-                self.generator.random)
-        else:
-            return self.generator.random.choice(list(elements))
+    def random_element(self, elements=('a', 'b', 'c')):
+        """
+        Returns a random element from a passed object.
 
-    def random_sample(self, elements=('a', 'b', 'c'), length=None):
-        if length is None:
-            length = self.generator.random.randint(1, len(elements))
+        If `elements` is a dictionary, the value will be used as
+        a weighting element. For example::
 
-        return [self.random_element(elements) for _ in range(length)]
+            random_element({"{{variable_1}}": 0.5, "{{variable_2}}": 0.2, "{{variable_3}}": 0.2, "{{variable_4}}": 0.1})
+
+        will have the following distribution:
+            * `variable_1`: 50% probability
+            * `variable_2`: 20% probability
+            * `variable_3`: 20% probability
+            * `variable_4`: 10% probability
 
-    def random_sample_unique(self, elements=('a', 'b', 'c'), length=None):
-        """
-        Returns a `set` of random unique elements for the specified length.
-        Multiple occurances of the same value increase its probabilty to be in the output.
         """
-        elements = Counter(elements)
-        if length is None:
-            length = self.generator.random.randint(1, len(elements))
+        return self.random_elements(elements, length=1)[0]
 
-        if length > len(elements):
-            raise ValueError(
-                "Sample length cannot be longer than the number of unique elements to pick from.")
-        sample = set()
-        for _ in range(length):
-            element = self.random_element(elements)
-            sample.add(element)
-            elements.pop(element)
-        return sample
+    def random_sample(self, elements=('a', 'b', 'c'), length=None):
+        """
+        Returns a list of random unique elements for the specified length.
+        Multiple occurrences of the same value increase its probability to be in the output.
+        """
+        return self.random_elements(elements, length, unique=True)
 
     def randomize_nb_elements(
             self,
diff --git a/faker/providers/internet/__init__.py b/faker/providers/internet/__init__.py
index 8b65a258..0856b267 100644
--- a/faker/providers/internet/__init__.py
+++ b/faker/providers/internet/__init__.py
@@ -320,7 +320,7 @@ class Provider(BaseProvider):
     def uri_path(self, deep=None):
         deep = deep if deep else self.generator.random.randint(1, 3)
         return "/".join(
-            [self.random_element(self.uri_paths) for _ in range(0, deep)]
+            self.random_elements(self.uri_paths, length=deep)
         )
 
     def uri_extension(self):
diff --git a/faker/providers/lorem/__init__.py b/faker/providers/lorem/__init__.py
index 7c25bf82..48276aa5 100644
--- a/faker/providers/lorem/__init__.py
+++ b/faker/providers/lorem/__init__.py
@@ -26,31 +26,30 @@ class Provider(BaseProvider):
     word_connector = ' '
     sentence_punctuation = '.'
 
-    def word(self, ext_word_list=None):
+    def words(self, nb=3, ext_word_list=None):
         """
-        :returns: A random word, eg: 'lorem'
+        :returns: An array of random words. for example: ['Lorem', 'ipsum', 'dolor']
 
+        Keyword arguments:
+        :param nb: how many words to return
         :param ext_word_list: a list of words you would like to have instead of
             'Lorem ipsum'
 
-        :rtype: str
+        :rtype: list
         """
-        if ext_word_list:
-            return self.random_element(ext_word_list)
-        return self.random_element(self.word_list)
+        word_list = ext_word_list if ext_word_list else self.word_list
+        return self.random_choices(word_list, length=nb)
 
-    def words(self, nb=3, ext_word_list=None):
+    def word(self, ext_word_list=None):
         """
-        :returns: An array of random words. for example: ['Lorem', 'ipsum', 'dolor']
+        :returns: A random word, eg: 'lorem'
 
-        Keyword arguments:
-        :param nb: how many words to return
         :param ext_word_list: a list of words you would like to have instead of
             'Lorem ipsum'
 
-        :rtype: list
+        :rtype: str
         """
-        return [self.word(ext_word_list) for _ in range(0, nb)]
+        return self.words(1, ext_word_list)[0]
 
     def sentence(self, nb_words=6, variable_nb_words=True, ext_word_list=None):
         """
diff --git a/faker/providers/misc/__init__.py b/faker/providers/misc/__init__.py
index 52c38905..1eb4c662 100644
--- a/faker/providers/misc/__init__.py
+++ b/faker/providers/misc/__init__.py
@@ -176,7 +176,7 @@ class Provider(BaseProvider):
             required_tokens) <= length, "Required length is shorter than required characters"
 
         # Generate a first version of the password
-        chars = [self.generator.random.choice(choices) for _ in range(length)]
+        chars = self.random_choices(choices, length=length)
 
         # Pick some unique locations
         random_indexes = set()
diff --git a/faker/providers/python/__init__.py b/faker/providers/python/__init__.py
index bba6100c..9f7df7e2 100644
--- a/faker/providers/python/__init__.py
+++ b/faker/providers/python/__init__.py
@@ -29,14 +29,15 @@ class Provider(BaseProvider):
         :return: String. Random of random length between min and max characters.
         """
         if min_chars is None:
-            return "".join(self.random_letter() for i in range(max_chars))
+            return "".join(self.random_letters(length=max_chars))
         else:
             assert (
                 max_chars >= min_chars), "Maximum length must be greater than or equal to minium length"
             return "".join(
-                self.random_letter() for i in range(
-                    0, self.generator.random.randint(
-                        min_chars, max_chars)))
+                self.random_letters(
+                    length=self.generator.random.randint(min_chars, max_chars),
+                )
+            )
 
     def pyfloat(self, left_digits=None, right_digits=None, positive=False):
         if left_digits is not None and left_digits < 0:
diff --git a/faker/utils/distribution.py b/faker/utils/distribution.py
index 3e39f59a..af0d1e53 100644
--- a/faker/utils/distribution.py
+++ b/faker/utils/distribution.py
@@ -17,18 +17,49 @@ def cumsum(it):
         yield total
 
 
-def choice_distribution(a, p, random=None):
+def choices_distribution_unique(a, p, random=None, length=1):
+    # As of Python 3.7, there isn't a way to sample unique elements that takes
+    # weight into account.
+    if random is None:
+        random = mod_random
+
+    assert len(a) == len(p)
+    assert len(a) >= length, "You can't request more unique samples than elements in the dataset."
+
+    choices = []
+    items = list(a)
+    probabilities = list(p)
+    for i in range(length):
+        cdf = list(cumsum(probabilities))
+        normal = cdf[-1]
+        cdf2 = [float(i) / float(normal) for i in cdf]
+        uniform_sample = random_sample(random=random)
+        idx = bisect.bisect_right(cdf2, uniform_sample)
+        item = items[idx]
+        choices.append(item)
+        probabilities.pop(idx)
+        items.pop(idx)
+    return choices
+
+
+def choices_distribution(a, p, random=None, length=1):
     if random is None:
         random = mod_random
 
     assert len(a) == len(p)
 
     if hasattr(random, 'choices'):
-        return random.choices(a, weights=p)[0]
+        choices = random.choices(a, weights=p, k=length)
+        return choices
     else:
+        choices = []
+
         cdf = list(cumsum(p))
         normal = cdf[-1]
         cdf2 = [float(i) / float(normal) for i in cdf]
-        uniform_sample = random_sample(random=random)
-        idx = bisect.bisect_right(cdf2, uniform_sample)
-        return a[idx]
+        for i in range(length):
+            uniform_sample = random_sample(random=random)
+            idx = bisect.bisect_right(cdf2, uniform_sample)
+            item = a[idx]
+            choices.append(item)
+        return choices


Test patch:
diff --git a/tests/test_factory.py b/tests/test_factory.py
index f9d6624c..39ed0084 100644
--- a/tests/test_factory.py
+++ b/tests/test_factory.py
@@ -586,32 +586,28 @@ class FactoryTestCase(unittest.TestCase):
 
         # Too many items requested
         with self.assertRaises(ValueError):
-            provider.random_sample_unique('abcde', 6)
-
-        # Duplicate inputs reduced to unique set
-        with self.assertRaises(ValueError):
-            provider.random_sample_unique('aabcd', 5)
+            provider.random_sample('abcde', 6)
 
         # Same length
-        sample = provider.random_sample_unique('aabcd', 4)
-        self.assertEqual(sample, set('abcd'))
+        sample = provider.random_sample('abcd', 4)
+        self.assertEqual(sorted(sample), list('abcd'))
 
-        sample = provider.random_sample_unique('abcde', 5)
-        self.assertEqual(sample, set('abcde'))
+        sample = provider.random_sample('abcde', 5)
+        self.assertEqual(sorted(sample), list('abcde'))
 
         # Length = 3
-        sample = provider.random_sample_unique('abcde', 3)
+        sample = provider.random_sample('abcde', 3)
         self.assertEqual(len(sample), 3)
-        self.assertTrue(sample.issubset(set('abcde')))
+        self.assertTrue(set(sample).issubset(set('abcde')))
 
         # Length = 1
-        sample = provider.random_sample_unique('abcde', 1)
+        sample = provider.random_sample('abcde', 1)
         self.assertEqual(len(sample), 1)
-        self.assertTrue(sample.issubset(set('abcde')))
+        self.assertTrue(set(sample).issubset(set('abcde')))
 
         # Length = 0
-        sample = provider.random_sample_unique('abcde', 0)
-        self.assertEqual(sample, set())
+        sample = provider.random_sample('abcde', 0)
+        self.assertEqual(sample, [])
 
     def test_random_number(self):
         from faker.providers import BaseProvider
diff --git a/tests/utils/test_utils.py b/tests/utils/test_utils.py
index 6e8e4b01..d38ecb40 100644
--- a/tests/utils/test_utils.py
+++ b/tests/utils/test_utils.py
@@ -1,5 +1,5 @@
 from faker.utils.loading import find_available_locales
-from faker.utils.distribution import choice_distribution
+from faker.utils.distribution import choices_distribution, choices_distribution_unique
 from faker.utils.datasets import add_dicts
 from faker.config import PROVIDERS
 from faker.generator import random
@@ -18,7 +18,7 @@ class UtilsTestCase(unittest.TestCase):
         a = ('a', 'b', 'c', 'd')
         p = (0.5, 0.2, 0.2, 0.1)
 
-        sample = choice_distribution(a, p)
+        sample = choices_distribution(a, p)[0]
         self.assertTrue(sample in a)
 
         with open(os.path.join(TEST_DIR, 'random_state.json'), 'r') as fh:
@@ -26,7 +26,7 @@ class UtilsTestCase(unittest.TestCase):
         random_state[1] = tuple(random_state[1])
 
         random.setstate(random_state)
-        samples = [choice_distribution(a, p) for i in range(100)]
+        samples = choices_distribution(a, p, length=100)
         a_pop = len([i for i in samples if i == 'a'])
         b_pop = len([i for i in samples if i == 'b'])
         c_pop = len([i for i in samples if i == 'c'])
@@ -42,6 +42,15 @@ class UtilsTestCase(unittest.TestCase):
         self.assertTrue(boundaries[2][0] > c_pop > boundaries[2][1])
         self.assertTrue(boundaries[3][0] > d_pop > boundaries[3][1])
 
+    def test_choices_distribution_unique(self):
+        a = ('a', 'b', 'c', 'd')
+        p = (0.25, 0.25, 0.25, 0.25)
+        with self.assertRaises(AssertionError):
+            choices_distribution_unique(a, p, length=5)
+
+        samples = choices_distribution_unique(a, p, length=4)
+        self.assertEqual(len(set(samples)), len(samples))
+
     def test_add_dicts(self):
         t1 = {'a':1, 'b':2}
         t2 = {'b':1, 'c':3}