I must admit I have stared at your function for almost an hour now, and I still struggle to comprehend how it works. I think I get the gist of it, but.. Yeah.
Readability
Global variables are bad in any programming language and hurts readability. See https://stackoverflow.com/a/19158418/1048781 for a deeper dive into it.
When I run your code I get this
Dupe draw stats
(200, 193, 0.96, 168, 0.84)
(2.0259067357512954, 23273809523809526, 20, 15)
401
================================================================================================================
What does any of this mean? What are your testcases? How does this test how random your draw is? My biggest struggle with your code is figuring out what it does. Would you be able to figure out what your code does in 1 month, let alone 1 year? It can be very wise to write out a battle plan before writing any code. Then you can ponder on the algorithm used instead of gluing together half broken ideas along the way.
In addition it is strongly encouraged to include docstrings and comments. One important concept in programming is intent. What is your code intended to do, e.g how fast can someone not familiar with your code recognize what it does. This is usually done in steps.
- Modules (Logical classes etc).
- Single purpose functions
- Clear docstrings
- Clear variable names
- Comments
In that order. We start at the top, and if the intent is not clear we work our way down. Only when we can not express the intent of our code through single purpose functions, clear docstring and variable names should we add comments to clear things up. The other points you should always try to do =)
Avoid redundant code (this can be helped using a proper editor, which will yell at you). For instance the function below is never used
def getCompSymbol(val1, val2):
if val1 > val2:
return " > "
if val1 < val2:
return " < "
else:
return " = "
The Python way and nitpicking
PEP 8 - Style Guide for Python Code
Just as learning a new language it is important to learn its grammar. Your speech can be technically correct and understandable, but one can tell it is not your mother tongue. It looks like you have experience from a different language, and I would recommend getting familiar with Python's grammar. When we talk about grammar in the sense of programming languages, we refer to this as syntax. And proper syntax (think of this as proper grammar) is achieved following a style guide
PEP 8 recommends the following naming-conventions:
CAPITALIZED_WITH_UNDERSCORES for constantsUpperCamelCase for class nameslowercase_separated_by_underscores for other names
So your functions should not follow cammelCase.
f-strings
f-strings are the new way of formatting strings in Python, and you should usually use them. While your code, in your current state, does not benefit much from them look at my answer to see how to space out the testing data.
max line width = 79
Python recommends a maximum linewidth of 79. While some prefer this to be a little longer (around 110 or so), it is clear that setting a limit is good for readability.
if __name__ == "__main__":
Put the parts of your code that are the ones calling for execution behind a if __name__ == "__main__": guard. This way you can import this python module from other places if you ever want to, and the guard prevents the main code from accidentally running on every import.
Small example of a refactor
Note that a refactor should first and foremost be to make the intent of the code clearer. I would start with the algorithm used, but here is just another tiny example that highlights some of the points made above. The code below
print((sum(nondupeIntervals) / len(nondupeIntervals), sum(nondupeIntervals2) / len(nondupeIntervals2), max(nondupeIntervals), max(nondupeIntervals2))) # Avg/max distance between non-dupes.
has two issues. The line below is too long, and the comment is not visible unless we scroll. Using the end keyword, we can restructure the code as follows
# Avg/max distance between non-dupes.
print(sum(nondupeIntervals) / len(nondupeIntervals) ), end="")
print(sum(nondupeIntervals2) / len(nondupeIntervals2), end="")
print(max(nondupeIntervals), max(nondupeIntervals2))))
Where end="" prevents a newline from being written. The next step
is to notice we have code duplication, we are performing the same actions on nondupeIntervals and nondupeIntervals (which again should have snake_case according to PEP8.) If we refactor this into a function and sprinkle some f-strings on top we obtain
def print_intervals(intervals):
avg_dist_text = f"{'Average distance':>20}"
max_dist_text = f"{'Maximum distance':>20}"
interval_text = "interval"
linebreak = "=" * 79
print(linebreak)
print(f" Testing of average distance and maximum distance")
print(linebreak)
print(f" {interval_text}{avg_dist_text}{max_dist_text}")
for i, interval in enumerate(intervals):
average_distance = sum(interval) / len(interval)
print(f" {i:>{len(interval_text)}}", end="")
print(f"{average_distance:{len(avg_dist_text)}f}", end="")
print(f"{max(interval):{len(max_dist_text)}}")
Which you would invoke by doing
print_intervals([nondupeIntervals, nondupeIntervals2])
and would print
===============================================================================
Testing of average distance and maximum distance
===============================================================================
interval Average distance Maximum distance
0 2.083333 18
1 2.366864 22
===============================================================================
Which in my eyes is much prettier and more importantly readable. Can we refactor too far? In fact it is very easy to do so! Three signs that you have gone too far
- You have not checked that there exists a library / external solution that can solve the problem.
- Is the code way more general than what is asked for?
- Is the code heavily optimized for speed before you have profiled the code for bottlenecks?
As an example of a refactor gone too far of the code above would be something like
def results_2_table(
results,
title,
headers,
indent=2,
space_between=4,
post=None,
pre=None,
symbol="~.",
hlines=[True, True, True],
):
headers_ = {}
if isinstance(post, str):
post = [post for _ in range(len(results[0]))]
if isinstance(pre, str):
pre = [pre for _ in range(len(results[0]))]
for i, header in enumerate(headers):
headers_[header] = dict()
headers_[header]["pre"] = "" if pre is None else pre[i]
headers_[header]["post"] = "" if post is None else post[i]
headers_[header]["formating"] = str(len(header))
between_str = " " * space_between
indent_str = " " * indent
header_str = indent_str + between_str.join(headers)
title = indent_str + title
linebreak_length = max(len(header_str), len(title)) + indent
times, remainder = divmod(linebreak_length, len(symbol))
linebreak = symbol * times + (symbol[0:remainder] if remainder else "")
toprule, midrule, bottomrule = hlines
table = []
if toprule:
table.append(linebreak)
table.append(title)
if midrule:
table.append(linebreak)
table.append(header_str)
for row in results:
line = []
for head, value in zip(headers_, row):
column = headers_[head]
line.append(f"{value:{column['pre']}{column['formating']}{column['post']}}")
table.append(indent_str + between_str.join(line))
if bottomrule:
table.append(linebreak)
return "\n".join(table)
def intervals_2_results(intervals):
average = lambda x: sum(x) / len(x)
results = [
(i, average(interval), max(interval)) for i, interval in enumerate(intervals)
]
return results
intervals = [nondupeIntervals, nondupeIntervals2]
results = intervals_2_results(intervals)
title = "Testing of average distance and maximum distance"
headers = ["Interval", "Average Distance", "Maximum Distance"]
symbol = "~"
# symbol = "¯\_(ツ)_/¯"
print(
results_2_table(results, title, headers, post=["", "f", ""], pre=">", symbol=symbol)
)
I dare you to uncomment the shrug Emoji line
Here we have extracted the construction of results from intervals into its own function (Good!). We have also written a pretty decent function for writing a pretty table for printing the results (Bad!). Why is the results_2_table bad? It has four flaws, the three last ones being worse than the first one
- It is a very general piece of code that does not inherently rely on any piece of existing code (A good sign that it could be extracted into its own module / function)
- It is far more advanced than what is needed. Meaning it would be far more expensive to maintain for a company.
- There exists existing solutions for this problem already. See beautifultable.
- Writing too advanced general code and not relying on external libraries tend to lead to bugs. See if you can find any in the
results_2_table function, it should not be too hard.
Do not reinvent the wheel except for educational purposes =)
An attempt at improvement
Unfortunately I do not have time to salvage your code, and this is left as
an exercise for the reader. The most maintainable, readable, and fastest code is no code. Which is why before you start writing your own code, always do a deep search if an existing solution exists. In this case it almost does
numpy.random.choice
This can be used as numpy.random.choice(elements, p = weights) note that
weights now have to sum to 1 for it to be a proper probability distribution. The only thing we are left with is increasing the probability for every element we have not picked. But wait.. Why not just decrease the probability for the element we picked? This seems much simpler to implement
def update_weights(elements, choice, weights)
new_weights = weights.copy()
choice_index = np.where(elements == choice)[0][0]
new_weights[choice_index] *= 0.5
return new_weights / sum(new_weights)
Again I encourage you to always read the documentation of new functions you encounter. Such as numpy.where. Since we are using numpy for the randomization there is no reason not to use numpy arrays throughout our code.
For instance to generate the initial weights we can simply do
weights = np.full(len(elements), 1/len(elements))
Where you of course could have precomputed len(elements) if you feel inclined to do so. To make it more readable it could be better to include everything in a class
class DrawWeighted:
def __init__(self, elements, prob_change_on_draw=0.9):
self.elements = elements
self.weights = self.default_weights()
self.prob_change_on_draw = prob_change_on_draw
def draw(self, times=1):
choices = [""] * times
for i in range(times):
choice = np.random.choice(self.elements, p=self.weights)
choices[i] = choice
self.update_weights(choice)
return choices[0] if len(choices) == 1 else choices
def default_weights(self):
return np.full(len(self.elements), 1 / len(self.elements))
def update_weights(self, choice):
new_weights = self.weights.copy()
choice_index = np.where(self.elements == choice)[0][0]
new_weights[choice_index] *= self.prob_change_on_draw
self.weights = new_weights / sum(new_weights)
Where I leave it to you to add proper docstrings and sprinkle in comments only where you feel the intent of the code is not clear.
A change of perspective
The code above is not particularly fast. We still have to update the weights on every draw and yeah, it is actually not the best way to do this.
If you can accept some pseudorandomness there are better ways of doing this.
I will show that you essentially end up with the same distribution at the end as well.. Our new algorithm will look as follows
- We create a
pool_size which will have size of some multiple of how many items we have (Example pool_size = 5 * len(elements)).
- We shuffle our list of elements
k times where k is our pool_size.
These new lists are concatenated (put together) to form our pool.
If elements = [1,2,3] and pool_size = 2 we could for instance have pool = [1, 2, 3, 3, 1, 2].
- When we make a draw we pick the
n'th element from pool and increase n.
- If
nis smaller than some value, or have reached the end of our pool, we generate a new pool and start the process over again.
This makes it possible to predict the next outcome, but the same can be said for your algorithm. The benefits of this is of course we do not have to make a random selection on every draw, but only when performing our shuffle. Since every element shows up an equal number of times, no element will be left behind. E.g not chosen for a long time (depends on your pool_size of course). A simple implementation is
class DrawShuffled:
def __init__(self, elements, pool_size=[5, 10], minimal_pool=1):
self.elements = elements
self.elements_size = len(elements)
self.min_pool = pool_size[0]
self.max_pool = pool_size[1]
self.minimal_pool = minimal_pool * self.elements_size + 1
self.index = 0
self.generate_pool()
def generate_pool(self):
self.size = np_random.integers(self.min_pool, self.max_pool)
pool = []
for _ in range(self.size):
pool.extend(np_random.permutation(self.elements))
self.pool = np_random.permutation(pool)
self.pool_size = len(self.pool)
self.index = 0
def draw(self, times=1):
choices = [""] * times
for i in range(times):
if self.index > self.pool_size - self.minimal_pool:
self.generate_pool()
choices[i] = self.pool[self.index]
self.index += 1
return choices[0] if len(choices) == 1 else choices
However.. If all we care about is a fast uniform distribution why not reduce the entire code into one line?
np.random.choice(letters, 200, replace=True)
Note that here you could run into the problem of some elements appearing more often than others.
Testing
Whenever one is rewriting code it is a great idea to have some simple testcases.
I chose to use the alphabet as my list to pull from
import string
TEST_DATA = np.array(list(string.ascii_lowercase))
which generates TEST_DATA = ['a', 'b', ..., 'z']. I will then draw 10^x items from each class / method, and compare the least frequent and most frequent drawn item.
numpy weighted shuffled
X most least most least most least
-------- ------ ------- ------ ------- ------ -------
````10 2 0 2 0 2 0
```100 7 1 7 1 6 1
``1000 50 23 44 34 46 34
`10000 422 360 388 379 404 373
100000 3956 3719 3851 3842 3896 3793
From the testing it is clear that
numpy (This is what we call np.random.choice(letters, draws, replace=True)) leads to a slightly higher varianceDrawShuffled and DrawWeighted are indistinguishable.
From an implementation standpoint we have
DrawWeighted > DrawShuffled >>> numpy for execution speed, but
numpy > DrawShuffled > DrawWeighted for space complexity (how big are lists we have to store in memory). For me personally, unless there was a very strong reason not to, would just go with the numpy oneliner. Otherwise DrawShuffled seems random enough.
EDIT: Based on the comments I realized I had a small error in my testing data. This is now fixed. I have also included a bigger table which shows variance and the least picked element
numpy weighted shuffled
X var least var least var least
----- -------- ------- ------- ------- ------- -------
``2 0.071 0 0.071 0 0.071 0
``7 0.274 0 0.274 0 0.197 0
`12 0.402 0 0.556 0 0.402 0
`17 0.534 0 0.38 0 0.611 0
`22 0.746 0 0.592 0 0.822 0
`27 0.96 0 0.652 0 1.268 0
`32 1.485 0 1.485 0 1.024 0
`37 1.321 0 1.013 0 0.859 0
`42 1.929 0 0.852 0 1.775 0
`47 1.925 0 1.155 0 2.155 0
`52 1.615 0 1.538 0 1.308 0
`57 1.771 0 1.771 0 1.155 0
`62 1.929 0 1.698 0 1.544 0
`67 3.859 0 1.706 1 1.09 1
`72 3.87 0 2.639 0 2.331 0
`77 4.652 0 2.652 1 1.729 0
`82 2.13 1 2.207 0 1.592 1
`87 2.996 1 1.765 1 1.149 1
`92 3.864 0 2.556 1 1.402 0
`97 4.043 1 3.735 1 1.812 1
102 3.148 1 2.686 1 2.994 1
107 5.025 1 3.256 1 2.871 1
112 3.059 1 3.905 1 1.905 2
117 4.481 2 5.404 1 0.788 3
122 2.213 2 4.059 1 1.598 2
127 7.487 0 2.102 2 2.179 2
132 3.994 1 4.456 1 1.763 2
137 4.12 2 3.428 2 1.197 3
142 5.402 1 3.325 2 2.556 2
147 2.688 2 4.842 1 3.457 3
152 7.669 1 3.669 2 2.438 2
157 3.806 3 4.729 2 0.806 4
162 6.178 1 3.793 2 0.947 4
167 5.706 1 4.167 0 2.936 3
172 4.544 2 3.237 1 2.467 4
177 7.617 1 2.771 3 1.232 5
182 5.538 3 4.0 4 2.615 2
187 5.54 3 4.617 3 3.848 3
192 5.006 3 4.314 4 2.391 5
197 4.629 3 3.629 4 3.783 4
202 7.254 3 3.562 3 3.793 3
207 5.883 4 4.114 3 1.96 4
212 11.746 3 7.207 2 2.053 6
217 5.226 4 4.303 4 3.072 4
222 8.402 3 5.095 3 3.633 5
227 6.658 3 5.351 4 3.197 5
232 8.84 2 4.225 6 4.302 4
237 9.025 2 5.564 3 2.794 6
242 12.059 4 3.982 6 3.751 5
247 7.404 5 4.865 3 3.865 6
252 5.905 4 8.213 4 0.982 8
257 12.256 4 8.102 5 1.256 8
Do note that in my actual implementation I use
from numpy.random import default_rng
np_random = default_rng()
np_random. (function goes here)
instead of
import numpy as np
np.random. (function goes here)
per numpy's recommendation. Similarly my actual printing of tables is for the most part done with beautifultables.
Things left for the reader to explore:
Code with testing
import string
import collections
import numpy as np
from numpy.random import default_rng
from beautifultable import BeautifulTable
np_random = np.random.default_rng()
TEST_DATA = np.array(list(string.ascii_lowercase))
class DrawWeighted:
def __init__(self, elements, prob_change_on_draw=0.90):
self.elements = elements
self.weights = self.default_weights()
self.prob_change_on_draw = prob_change_on_draw
def draw(self, times=1):
choices = [""] * times
for i in range(times):
choices[i] = np_random.choice(self.elements, p=self.weights)
self.update_weights(choices[i])
return choices[0] if len(choices) == 1 else choices
def default_weights(self):
return np.full(len(self.elements), 1 / len(self.elements))
def update_weights(self, choice):
new_weights = self.weights.copy()
choice_index = np.where(self.elements == choice)[0][0]
new_weights[choice_index] *= self.prob_change_on_draw
self.weights = new_weights / sum(new_weights)
class DrawShuffled:
# Regenerates poolsize if less than 1 * minimal pool
def __init__(self, elements, pool_size=[5, 10], minimal_pool=1):
self.elements = elements
self.elements_size = len(elements)
self.min_pool = pool_size[0]
self.max_pool = pool_size[1]
self.minimal_pool = minimal_pool * self.elements_size + 1
self.index = 0
self.generate_pool()
def generate_pool(self):
self.size = np_random.integers(self.min_pool, self.max_pool)
pool = []
for _ in range(self.size):
pool.extend(np_random.permutation(self.elements))
self.pool = np_random.permutation(pool)
self.pool_size = len(self.pool)
self.index = 0
def draw(self, times=1):
choices = [""] * times
for i in range(times):
if self.index > self.pool_size - self.minimal_pool:
self.generate_pool()
choices[i] = self.pool[self.index]
self.index += 1
return choices[0] if len(choices) == 1 else choices
def numpy_draw(draws):
return np_random.choice(TEST_DATA, draws, replace=True)
def run_testcases(test_cases, methods, data=TEST_DATA):
results = {}
for test_case in test_cases:
results[test_case] = []
for method in methods:
counts = collections.Counter(dict.fromkeys(data, 0))
for draw in method(test_case):
counts[draw] += 1
results[test_case].append(sorted(counts.values(), reverse=True))
return results
def average(data):
return sum(data) / len(data)
def variance(data):
n = len(data)
mean = sum(data) / n
deviations = [(x - mean) ** 2 for x in data]
variance = sum(deviations) / n
return variance
def pretty_print(test_cases, test_results, method_names):
avg = lambda x: sum(x) / len(x)
def improve_table():
table.set_style(BeautifulTable.STYLE_COMPACT)
# The entire purpose of this part is to center "numpy, weighted and shuffled"
header, *body = str(table).split("\n")
space = body[0].find(" ")
header, body = "X".center(space + 1) + header[space + 1 :], "\n".join(body)
starts = [i for i, char in enumerate(header) if char == "m"]
stops = [
i for i, char in enumerate(header) if char == "t" and i - 3 not in starts
]
extra_header = " " * len(header)
for i, (start, end) in enumerate(zip(starts, stops)):
extra_header = (
extra_header[:start]
+ method_names[i].center(end - start)
+ extra_header[end + 1 :]
)
return "\n".join([extra_header, header, body])
longest_case = len(str(max(test_cases)))
# print("=" * 79)
print(f"Draws X elements from '{string.ascii_lowercase}' and")
print("compares the most frequent and least frequent element drawn\n")
table = BeautifulTable()
table.columns.header = ["most", "least"] * len(method_names)
table.rows.header = [
f"{'`' * (longest_case - len(str(case)))}{case}" for case in test_cases
]
first, last = 0, -1
for i, row in enumerate(test_results):
table.rows[i] = row
table.columns.alignment = BeautifulTable.ALIGN_RIGHT
print(improve_table())
if __name__ == "__main__":
test_cases = [10 ** i for i in range(1, 6)]
data = TEST_DATA
methods = [numpy_draw, DrawWeighted(data).draw, DrawShuffled(data).draw]
method_names = ["numpy", "weighted", "shuffled"]
test_draw = run_testcases(test_cases, methods, data)
results = []
for draw in test_draw.values():
row = []
for method_result in draw:
# Feel free to change max/min to average/variance
row.append(max(method_result))
row.append(min(method_result))
results.append(row)
pretty_print(test_cases, results, method_names)
