13
\$\begingroup\$

The goal of this code is to seat students in a classroom based on a single test score. We want students to be evenly distributed across the class such that every student is positioned next to the greatest amount of peer-assistance they can, avoiding clustering of low or high scores.

The following method seems to work rather well. Modeling scores a force measurement (score1*score2)/r**2 and minimizing mean force across the class, then sorting for each possible arrangement reliably produces really high-quality distributions.

Unfortunately, the complexity of the problem becomes ~\$O(N!)\$ difficult, so class sizes above 7 students are super prohibitive. 8 students is pushing it on my 4 core machine.

I would like to look at more efficient ways of calculating these sets, even if I arrive there separately.

import numpy as np
import pandas as pd
import math
import scipy.special
from functools import reduce
from itertools import permutations, combinations
import matplotlib.pyplot as plt
import time

##########
##Starting a Clock
##########
t0a = time.clock()
t0b = time.time()

##Distance function 
def dist(locarray):
    temp_ar = [None]*len(locarray)
    for i in range(len(locarray)):
        temp_ar[i] = abs(locarray[i][1]-locarray[i][0])

    #print('a = ',locarray[0], '\n','b= ', locarray[1]) #debug step.  Add detection for 2-d layouts.
    return temp_ar

##THE VARIABLE HOW MANY STUDENTS
no_students = 6 #Any number > 6 will take a significant amount of time!
###Generate Test DataSet for 5 students

uar = [None]*no_students

for i in range(no_students):
    uar[i] = ['u'+str(i), int(np.random.rand(1)*70+30)]

#Define Classroom - each cell is a location
loc_1d = np.array(range(no_students))

##Initialize pandas dataframe for holding population data
data_col = ['sample_mean','sample_stddev','seating']
pop_data = pd.DataFrame(columns=data_col)

size = reduce(lambda x, y: x*y, np.shape(loc_1d))

##The counter wahaha
step_count = 0

##Create base class assignment with null locations where applicable
layout_init = [None] * size
for loc_id in range(size):
    try:
        layout_init[loc_id] = uar[loc_id]
    except IndexError:
        layout_init[loc_id] = 'empty'

##Now we can use itertools to generate all possible permutations in the class
perm = permutations(layout_init,size)
loc_space = list(perm)

##Wonderful!  Now we have userid and scores in their respective locations.
##Each row in loc_space is a possible seating arrangement.
n_unique = int(math.factorial(size)/(math.factorial(num_surr)*math.factorial(size-num_surr))) #QC step for unique_diff combos
unique_diff = list(combinations(loc_1d,2)) #yes, itertools is that awesome
distance = dist(unique_diff)

##In creating a progress bar
max_steps = len(loc_space)*len(unique_diff)


#Now, let's use the unique combinations to calculate the force at each node
for a in range(len(loc_space)):
    test_set = loc_space[a] #grab a row of data to work on
    #print('Set of Locations = ', loc_space[a]) #debug print
    force_vec = [None]*len(unique_diff) #clears diff_vec and sets for new row
    for b in range(len(unique_diff)):
        #print('combo is: ', unique_diff[b], '\n', 'debug (distance): ', distance)
        force_vec[b] = np.array((test_set[unique_diff[b][0]][1] * test_set[unique_diff[b][1]][1]) / distance[b]**2 ) #note absolute value, change nearest neighbor
        #print('Force Vector_ALL FORCES =', force_vec)
        step_count = step_count + 1
        print('We are on step ', step_count, ' of max_steps ', max_steps, ' --(', int((step_count/max_steps)*100), ')--')
    #Great!  We now have a vector of differences.  Let's get the mean of the absolute values
    pop_data.loc[len(pop_data)] = [np.average(force_vec), np.std(force_vec), test_set]

print('Operation completed in -- ', step_count, ' --')
#pop_sorted_std = pop_data.sort_values(by='sample_stddev')
pop_sorted_mean = pop_data.sort_values(by='sample_mean')

pop_size = len(loc_space) #THIS COMES IN HANDY

#######
##Plotting to get an idea of the anwer landscape!  
#######

##Extreme means
subset_low = pop_sorted_mean[0:size*2]['seating'].apply(pd.Series).reset_index(drop=True) #lowest means
subset_high = pop_sorted_mean[pop_size-size*2-1:pop_size-1]['seating'].apply(pd.Series).reset_index(drop=True) #Highest means

##########
##Print Low
##########
scrim2 = []
y_pos = np.arange(size)

for m in range(len(subset_low)):
    worker_a = subset_low.loc[m]
    scrim1 = []
#    print('worker_a: ', worker_a)
    for n in range(len(worker_a)):
        worker_b = np.array(worker_a[n][1])
        scrim1 = np.append(scrim1,worker_b)
#        print(worker_b) watch out for these prints
    scrim2.append(scrim1)

plt.figure(figsize=(10,5))
for k in range(len(scrim2)):
    plt.bar(y_pos,scrim2[k], alpha=0.08)

plt.show()    

##Time everything took
print('Process time: ',time.clock()-t0a)
print('Wall time: ',time.time()-t0b)
print('\nRaw Results: ', uar)
##Display scoreset
\$\endgroup\$
  • 1
    \$\begingroup\$ Ah. thanks. I was working in spyder which kept an old list in memory. I updated the code to include [None]*no_students initialization \$\endgroup\$ – iVinny Sep 7 '18 at 15:32
  • 1
    \$\begingroup\$ Code doesn't work: num_surr is used without being defined. \$\endgroup\$ – Peter Taylor Jul 3 '19 at 7:25
6
\$\begingroup\$

TL;DR

import numpy as np
import pandas as pd
import math
import scipy.special
from functools import reduce
from itertools import permutations, combinations, zip_longest
import matplotlib.pyplot as plt
import time
from operator import mul

##########
##Starting a Clock
##########
t0a = time.clock()
t0b = time.time()

n = 6

loc_1d = np.array(range(n))

# I'm not declaring that DataFrame yet, you'll see why later
data_col = ['sample_mean','sample_stddev','seating']

size = reduce(lambda x, y: x*y, loc_1d.shape)

step_count = 0

def dist(locarray):
    """
    It's easy to convert this to a generator, just yield the
    result from abs(b-a)
    """
    for a, b in locarray:
        yield abs(b - a)


# You only use uar and layout_init once, so they are easy candidates
# for generators
def create_uar(n):
    for i in range(n):
        # yield tuples, they give you a memory benefit over the mutable
        # list types
        yield (f'u{i}', int(np.random.rand(1)*70+30))


def create_layout(uar):
    for a, b in zip_longest(uar, range(size), fillvalue='empty'):
        yield a

# this iterable will be consumed by the permutations function
uar = create_uar(n)

# this is now just an iterator, much smaller in memory, and we haven't done
# any looping yet
loc_space = permutations(create_layout(uar), size)

# More constants
loc_space_size = math.factorial(n)
pop_size = loc_space_size
unique_diff_size = int(math.factorial(n)/(math.factorial(2) * math.factorial(n-2)))
max_steps = loc_space_size * unique_diff_size

# this will be used to create the dataframe
def create_pop_data(perm, loc_1d):
    """
    Again, no need to pre-allocate the array with None's, 
    simply append to a new list
    """
    for test_set in perm:
        force_vec = []
        # zip these together for easier tracking, you don't need the
        # indices, though we need to call the functions so that the 
        # generators are not consumed on the first iteration
        for (a, b), dst in zip(combinations(loc_1d, 2), 
                               dist(combinations(loc_1d, 2))):
            val = test_set[a][1] * test_set[b][1]
            val /= dst**2
            force_vec.append(np.array(val))

        # so you can iterate over it without waiting for the whole process
        # to complete
        yield [np.average(force_vec), np.std(force_vec), test_set]


pop_sorted_mean = pd.DataFrame([x for x in create_pop_data(loc_space, loc_1d)],
                               columns=data_col).sort_values(by='sample_mean')

subset_low = pop_sorted_mean[0:size*2]['seating'].apply(pd.Series).reset_index(drop=True) #lowest means
subset_high = pop_sorted_mean[pop_size-size*2-1:pop_size-1]['seating'].apply(pd.Series).reset_index(drop=True) #Highest means


plt.figure(figsize=(10,5))
scrim2 = []
y_pos = np.arange(size)

for m in range(len(subset_low)):
    worker_a = subset_low.loc[m]
    scrim1 = []
    # Again, for i in range(len(iterable)) isn't pythonic
    # but I will leave this one for you
    for n in range(len(worker_a)):
        worker_b = np.array(worker_a[n][1])
        # just append, don't use np.append, it's unnecessary
        scrim1.append(worker_b)

    # No need to append to scrim2, you can just add the bar plot here
    plt.bar(y_pos, scrim1, alpha=0.08)

print('Process time: ',time.clock()-t0a)
print('Wall time: ',time.time()-t0b)
print('\nRaw Results: ', uar)

original script

I skipped the plotting part on both, as well as commented out printing in the loop so that the test wasn't influenced by writing to stdout.

# n = 6
python file.py
Process time:  1.8510939999999998
Wall time:  2.018064022064209

Raw Results:  [['u0', 30], ['u1', 80], ['u2', 34], ['u3', 79], ['u4', 51], ['u5', 83]]

# n = 7
python file.py
Process time:  9.259665
Wall time:  9.459089994430542

Raw Results:  [['u0', 93], ['u1', 32], ['u2', 77], ['u3', 35], ['u4', 61], ['u5', 82], ['u6', 50]]

refactored results

# n = 6
python file.py
Process time:  0.7463569999999999
Wall time:  0.9110708236694336

Raw Results:  [('u0', 46), ('u1', 99), ('u2', 89), ('u3', 75), ('u4', 40)]

# n = 7
python file.py
Process time:  1.090624
Wall time:  1.2630760669708252

Raw Results:  [('u0', 57), ('u1', 81), ('u2', 76), ('u3', 45), ('u4', 31), ('u5', 74)]

There's a whole lot going on here, so I'll try and go from top to bottom

iteration over collections of data

It is considered an anti-pattern to iterate over a collection using for i in range(len(iterable)). If you need an index, use enumerate, otherwise, just use for item in iterable. It's cleaner and faster:

python -m timeit -s 'somelist = [x for x in range(100000)]' 'for i in range(len(somelist)): somelist[i]*2'
100 loops, best of 3: 6.74 msec per loop

python -m timeit -s 'somelist = [x for x in range(100000)]' 'for i in somelist: i*2'
100 loops, best of 3: 3.39 msec per loop

Second, there is rarely a need to pre-allocate a list of N items using [None] * N. You can build your list using a list comprehension instead. Your diff function can be modified to look like:

def dist(locarray):
    """
    This pre-allocation doesn't need to occur, and it's better to pass
    an iterator over locarray here, no need to use range
    """
    temp_ar = [abs(b - a) for a, b in locarray]
    return temp_ar

Where locarray is a collection of tuples that can be unpacked in this fashion. Plus, by doing x = [None] * N; for i in range(N): x[i] = ... you are almost iterating twice. I say almost because it's not quite the same, as the binary multiplication of the list of None is quite a bit faster than, say [None for i in range(N)], but you lose speed regardless:

# file.py
def f(N):
    x = [None] * N
    for i in range(N):
        x[i] = i

def g(N):
    x = [i for i in range(N)]
python -m timeit -s 'from file import f, g; N = 100000' 'f(N)'
100 loops, best of 3: 3.75 msec per loop

python -m timeit -s 'from file import f, g; N = 100000' 'g(N)'
100 loops, best of 3: 2.9 msec per loop

You do the same thing when defining uar:

# Go from this
uar = [None]*no_students

for i in range(no_students):
    uar[i] = ['u'+str(i), int(np.random.rand(1)*70+30)]

# to this (the f-string is an addition in python 3.5+)
uar = [[f'u{i}', int(np.random.rand(1)*70+30)] 
       for i in range(no_students)]

zip_longest

When trying to fill out a collection by iterating over something of unequal size, itertools.zip_longest is your friend. It allows you to specify what your missing value is, so you can again avoid the pre-allocation before iteration problem, as well as skipping the try/except:

# go from this
layout_init = [None] * size
for loc_id in range(size):
    try:
        layout_init[loc_id] = uar[loc_id]
    except IndexError:
        layout_init[loc_id] = 'empty'

# to this
layout_init = [a for a, b in zip_longest(uar, range(size), fillvalue='empty')]

A quick demo of how that works:

from itertools import zip_longest
x = list(range(10)) # shorter than the range(15) I use later
for a, b in zip_longest(x, range(15), fillvalue='empty'):
    print(a, b)

0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
empty 10
empty 11
empty 12
empty 13
empty 14

Combinations and Permutations

The huge benefit of itertools is that the functions within that module return generators. The benefit here is that they are not aggregating all of your results into memory, which is fast and efficient. Take this example:

# This will run for a very, very long time, but will continue processing
for i in range(100000000000000):
    print(i)

# This will crash before it gets to the print statement because
# list(range(x)) must be evaluated first and fit into memory, which it won't
for i in list(range(100000000000000):
    print(i)

With that in mind, don't do list(permutations) or list(combinations), it defeats the point. Now, to build your distance vector, if you do unique_diff = combinations(loc_1d, 2); distance = dist(unique_diff) you will consume unique_diff and will have to build another one. No matter, though, it costs you effectively nothing in memory to store another generator:

unique_diff = combinations(loc_1d, 2)
distance = dist(combinations(loc_1d, 2))

Because it just produces values, rather than aggregating them all. We will come back to another optimization to this later, but just keep that in mind for now.

No lists... what about len?

Since you have now avoided aggregating the combinations and permutations into memory, you don't have access to len when doing

# that and the NameError on num_surr
n_unique = int(math.factorial(size)/(math.factorial(num_surr)*math.factorial(size-num_surr))) #QC step for unique_diff combos
unique_diff = list(combinations(loc_1d,2))

The number of permutations is simply factorial(n) since you are choosing n from n and you've calculated the number of combinations already, so:

n = no_students # just so I don't have to type this out a ton
loc_space_size = math.factorial(n)
unique_diff_size = int(math.factorial(n)/(math.factorial(2) * 
                       math.factorial(n-2)))
max_steps = loc_space_size * unique_diff_size

Loops

Ok, starting with the first loop, you don't need the index a at all. You only use it to get test_set, so just iterate over the permutations directly:

for test_set in perm:
    # rest of loop

Furthermore, unique_diff appears to be the same length as distance, so you should be able to zip them together for easier iteration:

for test_set in perm:
    # set your force vector here
    force_vec = []

    # unique diff is a collection of two-element tuples, so you can 
    # unpack them, too
    for (a, b), dst in zip(unique_diff, distance):
        # Break this into multiple steps, it helps with readability
        val = test_set[a][1] * test_set[b][1]
        val /= dst**2
        force_vec.append(np.array(val))

As a quick example of that unpacking:

>>> x = [(i, i*2) for i in range(10)]
>>> y = [i**3 for i in range(10)]
>>> for (a, b), c in zip(x, y):
...     print(a,b,c)
...
0 0 0
1 2 1
2 4 8
3 6 27
4 8 64
5 10 125
6 12 216
7 14 343
8 16 512
9 18 729

Reducing Copies of Data

Now, one of the larger problems of this code is that everything stays in scope, so you carry around all of your temp variables and unused values. This chews up memory and impacts performance. You will want to wrap your loops in functions, this will clean up temp variables, as they will drop out of scope when the function ends if they are not explicitly returned.

If you examine the variables you use, you will see that most of them are used once, and only once. So we can make them generators so that the for loops execute as a stream rather than one after the other. The first obvious place to implement this is in the first for loop:

def create_pop_data(perm, unique_diff, distance):
    """
    Again, no need to pre-allocate the array with None's, 
    simply append to a new list
    """
    for test_set in perm:
        force_vec = []
        # zip these together for easier tracking, you don't need the
        # indices
        for (a, b), dst in zip(unique_diff, distance):
            val = test_set[a][1] * test_set[b][1]
            val /= dst**2
            force_vec.append(np.array(val))

        # so you can iterate over it without waiting for the whole process
        # to complete
        yield [np.average(force_vec), np.std(force_vec), test_set]

Now, where does distance come from? Well, it too is produced by a for loop:

def dist(locarray):
    """
    It's easy to convert this to a generator, just yield the
    result from abs(b-a)
    """
    for a, b in locarray:
        yield abs(b - a)

The only issue being that you iterate over distance multiple times, so it might actually be better to call that generator function inside the loop, as you have done before. Since both use loc_1d to create themselves, just set that as the argument of the function and don't create unique_diff and distance yet. You would call these functions like so:

import numpy as np
import pandas as pd
import math
import scipy.special
from functools import reduce
from itertools import permutations, combinations, zip_longest
import matplotlib.pyplot as plt
import time
from operator import mul

##########
##Starting a Clock
##########
t0a = time.clock()
t0b = time.time()

n = 6

uar = [[f'u{i}', int(np.random.rand(1)*70+30)] for i in range(n)]
loc_1d = np.array(range(n))

# I'm not declaring that DataFrame yet, you'll see why later
data_col = ['sample_mean','sample_stddev','seating']

size = reduce(lambda x, y: x*y, loc_1d.shape)

step_count = 0

# You only use uar and layout_init once, so they are easy candidates
# for generators
def create_uar(n):
    for i in range(n):
        # yield tuples, they give you a memory benefit over the mutable
        # list types
        yield (f'u{i}', int(np.random.rand(1)*70+30))


def create_layout(uar):
    for a, b in zip_longest(uar, range(size), fillvalue='empty'):
        yield a

# this iterable will be consumed by the permutations function
uar = create_uar(n)

# this is now just an iterator, much smaller in memory, and we haven't done
# any looping yet
loc_space = permutations(create_layout(uar), size)

# More constants
loc_space_size = math.factorial(n)
unique_diff_size = int(math.factorial(n)/(math.factorial(2) * math.factorial(n-2)))
max_steps = loc_space_size * unique_diff_size

# this will be used to create the dataframe
def create_pop_data(perm, loc_1d):
    """
    Again, no need to pre-allocate the array with None's, 
    simply append to a new list
    """
    for test_set in perm:
        force_vec = []
        # zip these together for easier tracking, you don't need the
        # indices, though we need to call the functions so that the 
        # generators are not consumed on the first iteration
        for (a, b), dst in zip(combinations(loc_1d, 2)), 
                               dist(combinations(loc_1d, 2))):
            val = test_set[a][1] * test_set[b][1]
            val /= dst**2
            force_vec.append(np.array(val))

        # so you can iterate over it without waiting for the whole process
        # to complete
        yield [np.average(force_vec), np.std(force_vec), test_set]

Now the reason I didn't create that DataFrame is that you can use the create_pop_data function to create the dataframe with a list comprehension, and then transform that in the same line to get your pop_sorted_mean without dragging two dataframes around in memory:

# This is the first time we have done any loops
pop_sorted_mean = pd.DataFrame([x for x in create_pop_data(loc_space, loc_1d)],
                               columns=data_col).sort_values(by='sample_mean')

This is where you will save most of your time, because now all of those loops are executing simultaneously, rather than waiting for one after another:

 def f():
     return [i for i in range(1000000)]

 def g():
     return [a*2 for a in f()]

python -m timeit -s 'from file import f, g' 'g()'
2 loops, best of 5: 113 msec per loop

# versus generators
 def f():
     yield from range(1000000)

 def g():
     return [a*2 for a in f()]

python -m timeit -s 'from file import f, g' 'g()'
5 loops, best of 5: 89.2 msec per loop

It's not massive in this example (~20%), but it's definitely something. If you extend this to multiple loops, you aren't having to wait for f() to complete before you start g(), because the loop in g will call next(f), and the loops continue together.

Now, we've already defined pop_size, it's loc_space_size, remember? To keep your naming the same:

pop_size = loc_space_size # this just adds another name referring to the value of loc_space_size, it doesn't duplicate the variable

Plotting

The only other major optimization I can see is that, again, you are iterating more times than you need to:

plt.figure(figsize=(10,5))
scrim2 = []
y_pos = np.arange(size)

for m in range(len(subset_low)):
    worker_a = subset_low.loc[m]
    scrim1 = []
    # Again, for i in range(len(iterable)) isn't pythonic
    # but I will leave this one for you
    for n in range(len(worker_a)):
        worker_b = np.array(worker_a[n][1])
        # just append, don't use np.append, it's unnecessary
        scrim1.append(worker_b)

    # No need to append to scrim2, you can just add the bar plot here
    plt.bar(y_pos, scrim1, alpha=0.08)

plt.show()

##Time everything took
print('Process time: ',time.clock()-t0a)
print('Wall time: ',time.time()-t0b)
print('\nRaw Results: ', uar)
```
\$\endgroup\$

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.