Repository: pberkes/big_O

Issue:
TravisCI pull request testing

Discussion:

Patch:
diff --git a/.travis.yml b/.travis.yml
new file mode 100644
index 0000000..4ea1396
--- /dev/null
+++ b/.travis.yml
@@ -0,0 +1,8 @@
+language: python
+python:
+  - "2.7"
+  - "3.4"
+  - "3.5"
+  - "3.6"
+install: "pip install -r requirements.txt"
+script: "python -m unittest discover -v"
diff --git a/MANIFEST.in b/MANIFEST.in
deleted file mode 100755
index f218bf2..0000000
--- a/MANIFEST.in
+++ /dev/null
@@ -1,2 +0,0 @@
-include *.rst
-include *.txt
diff --git a/README.rst b/README.rst
index c1c8674..991b14d 100755
--- a/README.rst
+++ b/README.rst
@@ -99,12 +99,12 @@ Creating an array:
 - `numpy.zeros` is O(n), since it needs to initialize every element to 0:
 
     >>> import numpy as np
-    >>> big_o.big_o(np.zeros, big_o.datagen.n_, max_n=1000000, n_repeats=5) # doctest: +ELLIPSIS
+    >>> big_o.big_o(np.zeros, big_o.datagen.n_, max_n=100000, n_repeats=100)
     (<class 'big_o.big_o.Linear'>, ...)
 
 - `numpy.empty` instead just allocates the memory, and is thus O(1):
 
-    >>> big_o.big_o(np.empty, big_o.datagen.n_, max_n=1000000, n_repeats=5) # doctest: +ELLIPSIS
+    >>> big_o.big_o(np.empty, big_o.datagen.n_, max_n=100000, n_repeats=100)
     (<class 'big_o.big_o.Constant'> ...)
 
 
diff --git a/big_o/big_o.py b/big_o/big_o.py
index d8652ba..1dbeae4 100755
--- a/big_o/big_o.py
+++ b/big_o/big_o.py
@@ -1,14 +1,15 @@
 from __future__ import absolute_import
 
-import numpy as np
 from timeit import Timer
 
+import numpy as np
+
 from big_o.complexities import ALL_CLASSES
 
 
 def measure_execution_time(func, data_generator,
                            min_n=100, max_n=100000, n_measures=10,
-                           n_repeats=1):
+                           n_repeats=1, n_timings=1):
     """ Measure the execution time of a function for increasing N.
 
     Input:
@@ -30,6 +31,9 @@ def measure_execution_time(func, data_generator,
     n_repeats -- Number of times func is called to compute execution time
                  (return the cumulative time of execution)
 
+    n_timings -- Number of times the timing measurement is repeated.
+                 The minimum time for all the measurements is kept.
+
     Output:
     -------
 
@@ -50,11 +54,12 @@ def measure_execution_time(func, data_generator,
 
     # TODO: check that max_n is not larger than max int64
     ns = np.linspace(min_n, max_n, n_measures).astype('int64')
-    time = np.empty(n_measures)
+    execution_time = np.empty(n_measures)
     for i, n in enumerate(ns):
         timer = Timer(func_wrapper(n))
-        time[i] = timer.timeit(n_repeats)
-    return ns, time
+        measurements = timer.repeat(n_timings, n_repeats)
+        execution_time[i] = np.min(measurements)
+    return ns, execution_time
 
 
 def infer_big_o_class(ns, time, classes=ALL_CLASSES, verbose=False):
@@ -104,7 +109,7 @@ def infer_big_o_class(ns, time, classes=ALL_CLASSES, verbose=False):
 
 def big_o(func, data_generator,
           min_n=100, max_n=100000, n_measures=10,
-          n_repeats=1, classes=ALL_CLASSES, verbose=False):
+          n_repeats=1, n_timings=1, classes=ALL_CLASSES, verbose=False):
     """ Estimate time complexity class of a function from execution time.
 
     Input:
@@ -126,6 +131,9 @@ def big_o(func, data_generator,
     n_repeats -- Number of times func is called to compute execution time
                  (return the cumulative time of execution)
 
+    n_timings -- Number of times the timing measurement is repeated.
+                 The minimum time for all the measurements is kept.
+
     classes -- The complexity classes to consider. This is a list of subclasses
                of `big_o.complexities.ComplexityClass`.
                Default: all the classes in `big_o.complexities.ALL_CLASSES`
@@ -144,5 +152,6 @@ def big_o(func, data_generator,
     """
 
     ns, time = measure_execution_time(func, data_generator,
-                                      min_n, max_n, n_measures, n_repeats)
+                                      min_n, max_n, n_measures, n_repeats,
+                                      n_timings)
     return infer_big_o_class(ns, time, classes, verbose=verbose)
diff --git a/big_o/datagen.py b/big_o/datagen.py
index ee46786..b26403b 100755
--- a/big_o/datagen.py
+++ b/big_o/datagen.py
@@ -26,7 +26,7 @@ def large_integers(n):
             for _ in range(n)]
 
 
-def strings(n, chars=string.letters):
+def strings(n, chars=string.ascii_letters):
     """ Return random string of N characters, sampled at random from `chars`.
     """
     return ''.join([random.choice(chars) for i in xrange(n)])
diff --git a/requirements.txt b/requirements.txt
new file mode 100644
index 0000000..24ce15a
--- /dev/null
+++ b/requirements.txt
@@ -0,0 +1,1 @@
+numpy


Test patch:
diff --git a/big_o/test/test_big_o.py b/big_o/test/test_big_o.py
index bb46ceb..4147402 100755
--- a/big_o/test/test_big_o.py
+++ b/big_o/test/test_big_o.py
@@ -42,27 +42,39 @@ class TestBigO(unittest.TestCase):
             assert_array_almost_equal(coeff, res_class.coeff, 2)
 
     def test_big_o(self):
+        def dummy_linear_function(n):
+            for i in range(n):
+                # Dummy operation with constant complexity.
+                8282828 * 2322
+
+        def dummy_quadratic_function(n):
+            for i in range(n):
+                for j in range(n):
+                    # Dummy operation with constant complexity.
+                    8282828 * 2322
+
+        # In the best case, TimSort is linear, so we fix a random array to
+        # make sure we hit a close-to-worst case scenario, which is
+        # O(n*log(n)).
+        random_state = np.random.RandomState(89342787)
+        random_array = random_state.rand(100000)
+
+        # Each test case is a tuple
+        # (function_to_evaluate, expected_complexity_class, range_for_n)
         desired = [
-            (lambda n: [i for i in xrange(n*100)], compl.Linear),
-            (lambda n: 1., compl.Constant),
-            (lambda n: [i+j for i in xrange(n) for j in xrange(n)],
-             compl.Quadratic),
-            (lambda n: sorted(np.random.randn(n*100)), compl.Linearithmic),
+            (dummy_linear_function, compl.Linear, (100, 10000)),
+            (lambda n: 1., compl.Constant, (1000, 10000)),
+            (dummy_quadratic_function, compl.Quadratic, (50, 200)),
+            (lambda n: np.sort(random_array[:n], kind='mergesort'),
+             compl.Linearithmic, (100, random_array.shape[0])),
         ]
-        for func, class_ in desired:
+        for func, class_, n_range in desired:
             res_class, fitted = big_o.big_o(
                 func, datagen.n_,
-                min_n=100, max_n=1000, n_repeats=5,
+                min_n=n_range[0],
+                max_n=n_range[1],
+                n_measures=25,
+                n_repeats=10,
+                n_timings=10,
             )
             self.assertEqual(class_, res_class.__class__)
-
-    def test_compute(self):
-        x = np.linspace(10, 100, 100)
-        y = 3.0 * x + 2.0
-        linear = compl.Linear()
-        linear.fit(x, y)
-        assert_array_almost_equal(linear.compute(x), y, 10)
-
-    def test_not_fitted(self):
-        linear = compl.Linear()
-        self.assertRaises(compl.NotFittedError, linear.compute, 100)
diff --git a/big_o/test/test_complexities.py b/big_o/test/test_complexities.py
new file mode 100644
index 0000000..3935c88
--- /dev/null
+++ b/big_o/test/test_complexities.py
@@ -0,0 +1,19 @@
+import unittest
+import numpy as np
+from numpy.testing import assert_array_almost_equal
+
+from big_o import complexities
+
+
+class TestComplexities(unittest.TestCase):
+
+    def test_compute(self):
+        x = np.linspace(10, 100, 100)
+        y = 3.0 * x + 2.0
+        linear = complexities.Linear()
+        linear.fit(x, y)
+        assert_array_almost_equal(linear.compute(x), y, 10)
+
+    def test_not_fitted(self):
+        linear = complexities.Linear()
+        self.assertRaises(complexities.NotFittedError, linear.compute, 100)