2
\$\begingroup\$

I tried to implement a weighted draw. The idea of which is, you can have disproportionate probabilities of drawing different items. In this particular case, I want to cumulatively bias the probability towards drawing undrawn items. That is, the longer an item hasn't been drawn, the higher its chances become.

I'm a python newb and I come from a background of more traditional languages, so I wrote it using generic constructs borrowed from what I'm familiar with (e.g. a prolific use of index-based loops). I'm curious what a more "pythonic" version would look like.

Also, I'm looking for performance optimizations.
The most obvious one I can spot is, the draw can be turned into a binary search taking it down from O(n) to O(log n). Another point is - when you make it "pythonic" don't make it slower.

(There's a bit of extra, not strictly necessary code related to debugging and some interesting algorithmic stats. For example a comparison to a normal, uniformly random draw. Also, it seems to take 2-2.5x the pool size to draw all items once, using the default weight modifier. Feel free to add insights.)

#!/usr/bin/python3

import random


# Draw is [) aka >= start, < end
def draw():
    # randy = random.randint(0, startPoints[-1] + weights[-1])
    randy = random.random() * startPoints[-1] + weights[-1]  # Makes drawing 0 more unlikely than above. But allows multiplication of weights.
    for i, startPoint in enumerate(startPoints):
        if randy >= startPoint and randy < startPoints[i] + weights[i]:
        # if startPoint >= randy: # This works, except for returning the last index (which we can using python's for-else)
            return i


def adjustWeight(weight):
    return weight + 1  # Varying addition doesn't seem to affect things, but multiplication scales with value.


def adjustWeights(drawnIdx):
    for i, weight in enumerate(weights):
        if i == drawnIdx:
            weights[i] = 1
        else:
            weights[i] = adjustWeight(weights[i])

        if i != 0:
            startPoints[i] = startPoints[i-1] + weights[i-1]


def doRound():
    global lastnonDupe  # Why TF does this need global, but the others dont
    singleDraw = draw()
    drawn.append(singleDraw)
    adjustWeights(singleDraw)

    # Independent rando and dupe stats
    seenRando()
    if singleDraw in seen:
        seen[singleDraw] = seen[singleDraw] + 1
        # print("Dupe draw " + str(singleDraw) + " after " + str(len(drawn)) + " draws; Len of seen: " + str(len(seen)) + getCompSymbol(len(seen), len(seen2)) + str(len(seen2)))
    else:
        seen[singleDraw] = 1
        nondupeIntervals.append(len(drawn) - lastnonDupe)
        lastnonDupe = len(drawn)


def seenRando():
    global lastnonDupe2
    randy = random.randint(0, poolSize-1)
    if randy in seen2:
        seen2[randy] = seen2[randy] + 1
    else:
        seen2[randy] = 1
        nondupeIntervals2.append(len(drawn) - lastnonDupe2)
        lastnonDupe2 = len(drawn)


def getCompSymbol(val1, val2):
    if val1 > val2:
        return " > "
    if val1 < val2:
        return " < "
    else:
        return " = "


poolSize = 200
weights = list(range(1, poolSize+1))
startPoints = list(range(0, poolSize))
drawn = []

for idx, weight in enumerate(weights):
    weights[idx] = 1

extra = []
maxTotal = 0

# Independent rando and dupe stats
seen = {}
seen2 = {}
nondupeIntervals = []
nondupeIntervals2 = []
lastnonDupe = 0
lastnonDupe2 = 0


for x in range(400):
    prevTotal = sum(weights)
    # print(startPoints)
    doRound()
    currTotal = sum(weights)
    newMax = max(maxTotal, currTotal)
    extra.append((sum(weights), sum(weights) - prevTotal, newMax, newMax > maxTotal))
    maxTotal = newMax

print("Dupe draw stats")
print((poolSize, len(seen), round(len(seen) / poolSize, 2), len(seen2), round(len(seen2) / poolSize, 2)))
print((sum(nondupeIntervals) / len(nondupeIntervals), sum(nondupeIntervals2) / len(nondupeIntervals2), max(nondupeIntervals), max(nondupeIntervals2)))  # Avg/max distance between non-dupes.
print(max(weights))
# print(nondupeIntervals)
# print(nondupeIntervals2)
print("==================================================================================================================================================================")
# print(drawn)
# print(seen)
# print(weights)
# print(extra)
```
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Please give a specific formula for what weights you want. Your problem is a little vague, so it will help while reading the code. \$\endgroup\$ Aug 7, 2021 at 1:34
  • \$\begingroup\$ @ZacharyVance Formula's right there, second function from the top. \$\endgroup\$
    – martixy
    Aug 7, 2021 at 2:23

1 Answer 1

3
\$\begingroup\$

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 constants
  • UpperCamelCase for class names
  • lowercase_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

  1. You have not checked that there exists a library / external solution that can solve the problem.
  2. Is the code way more general than what is asked for?
  3. 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

  1. numpy (This is what we call np.random.choice(letters, draws, replace=True)) leads to a slightly higher variance
  2. DrawShuffled 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)
\$\endgroup\$
10
  • \$\begingroup\$ First, a question: Should I have left out the debug code? Much of your answer centers on it, when it is largely tangential and makes code significantly harder to understand. I tried to separate it from the algorithm implementation (which based on your feedback did not appreciably increase readability). Though it did yield relevant suggestions. Would have used f-strings everywhere, had I known they existed. (I'm not sure subjecting you to code comprehension torture is worth that one insight. My apologies.) I never leave debug code around because a week later I will have no idea what it does. \$\endgroup\$
    – martixy
    Aug 7, 2021 at 23:18
  • \$\begingroup\$ On style: I will have to disagree with you on global variables. "Global" is a matter of scope. A more correct advice is "Declare variables in the scopes you intend to use them in." Which is what I have done. I have merely dispensed with the boilerplate of a class and use the file/module as a scope. You didn't answer this, but I think I found why some of my globals require the global keyword and others don't - reassigning requires it. All this is hacking things together in my spare time for educational purposes (hence wheel reinventing) and is not intended to resemble enterprise-grade code. \$\endgroup\$
    – martixy
    Aug 7, 2021 at 23:41
  • \$\begingroup\$ On the meat of the problem: You encourage me to look up unfamiliar functions, but that is the LEAST problem there. update_weights hides so much numpy arcana. You fail to even hint at how it overloads the comparison and division operators. Note that your algorithm isn't strictly equivalent to mine (yours is like weight *= 2 in my code). And you can't do simple addition (though arguably that's also the least interesting weight adjustment). Your alternative algo is an interesting idea. Do you have any insights on the O() complexity? What's np.random.choice? Continued... \$\endgroup\$
    – martixy
    Aug 8, 2021 at 0:33
  • \$\begingroup\$ The shuffle also changes the behaviour (if I'm reading it correctly) - you always draw each element once before you can draw a duplicate of it. If you have 200 elements and 200 draws, you will never get a duplicate. If you have 400 elements, you will always get 2 dupe draws. Also, I think you have an error - no way you ran 1e+100000 iterations of these algorithms. \$\endgroup\$
    – martixy
    Aug 8, 2021 at 0:49
  • \$\begingroup\$ You also seem to be missing the point of the exercise. Where the weighted algorithm's performance is most interesting is when the draw count is similar to the pool size. Draws orders of magnitudes higher obliterates the differences and just makes you essentially draw sets of shuffled elements. Basically the weighted draw emulates the behaviour of the shuffle for draws >>> pool size. In a sense the misleading part is your 0.5 weight modifier, which is incredibly heavy. \$\endgroup\$
    – martixy
    Aug 8, 2021 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.