7
\$\begingroup\$

I need help with optimizing my Python code. I have a bunch of orders and each order has several SKUs. This is what my data looks like:

ORD_KEY  ORD_DT_KEY  ORD_TM_KEY  QTY  SKU_KEY
10001    1           0           1    1
10001    1           0           1    2
10001    1           0           1    3
10002    2           0           1    1
10002    2           0           1    3
10003    3           0           1    4
10004    4           0           1    4
10004    4           0           1    5
10005    5           0           1    1
10006    6           0           1    1
10006    6           0           1    4

I want to group orders in batches and create a "SKU Count" for each order such that, for every order in a batch, only count the SKU if it was not present in any previous orders of that batch. For example, if my batch size is 3 orders and I'm looking at 1st batch having orders 10001, 10002 & 10003, SKU Counts will be as below:

  • 10001 = 3 since it has 3 SKUs {1,2,3}
  • 10002 = 0 since it has 2 SKUs {1,3} but both were part of 10001
  • 10003 = 1 since it has 1 SKU {4} but it was not part of orders 10001 & 10002

Now, in this way, I want to create a matrix called oskupicks of dimensions = [batch size, orders] i.e. each row representing batch size and each column representing an order. Values are the SKU Counts calculated as above. So, for above example, it would look something like this:

Batch size = 1 [...                       ...]
Batch size = 2 [...                       ...]
Batch size = 3 [3, 0, 1                   ...]
       .       .
       .       .
       .       .
               [...                       ...]

I tried few approaches and matrix computations seems to be the fastest one -- current code is as below. However, when I ran it for larger data of 10,000 orders and lot many SKUs possible, run time went into hours. Since I'm very new to Python, I'm wondering if there's an even faster way of achieving this or can we have even better logic?

import pandas as pd
import numpy as np

df_ord = pd.DataFrame(
            [[10001,1,0,1,1],
            [10001,1,0,1,2],
            [10001,1,0,1,3],
            [10002,2,0,1,1],
            [10002,2,0,1,3],
            [10003,3,0,1,4],
            [10004,4,0,1,4],
            [10004,4,0,1,5],
            [10005,5,0,1,1],
            [10006,6,0,1,1],
            [10006,6,0,1,4],
            [10007,7,0,1,3],
            [10007,7,0,1,4],
            [10008,8,0,1,5],
            [10009,9,0,1,1],
            [10009,9,0,1,4],
            [10009,9,0,1,5],
            [10010,10,0,2,1],
            [10010,10,0,2,2],
            [10010,10,0,2,3],
            [10011,11,0,1,1],
            [10011,11,0,1,3],
            [10012,12,0,1,4],
            [10012,12,0,1,5],
            [10013,13,0,1,1],
            [10014,14,0,2,1],
            [10014,14,0,2,4]],
            columns=['ORD_KEY','ORD_DT_KEY','ORD_TM_KEY','QTY','SKU_KEY'])


#Define input parameters
TotalOrders = df_ord['ORD_KEY'].drop_duplicates().count() #Orders
MaxBatchSize = 10 #Total chutes

#Pivot data to flag SKU presence in each order
print 'Creating Order-SKU pivot...'
arr_order_sku_pivot = pd.pivot_table(df_ord, values = 'QTY', index = 'ORD_KEY', columns = 'SKU_KEY').reset_index(drop=True).values
for i in range(0,arr_order_sku_pivot.shape[0]):
    for j in range(0,arr_order_sku_pivot.shape[1]):
        if arr_order_sku_pivot[i][j] > 0:
            arr_order_sku_pivot[i][j] = 1
        else:
            arr_order_sku_pivot[i][j] = 0



print 'Building oskupicks matrix...'
oskupicks_matrix = np.zeros((MaxBatchSize,TotalOrders)) # Create empty matrix
distinct_skus = arr_order_sku_pivot.shape[1] # Count of distinct SKUs

for OrdersPerBatch in range(1,MaxBatchSize+1): 
    print '\n\nOrders per batch =', OrdersPerBatch, ' out of', MaxBatchSize

    #Batches required
    if TotalOrders % OrdersPerBatch == 0: 
        Batches = TotalOrders//OrdersPerBatch 
    else: 
        Batches = TotalOrders//OrdersPerBatch + 1
    print 'Total batches needed =', Batches, '\nProcessing batch...'

    for b in range(0,Batches): #Batch ids are from 0 to (Batches-1)
        print b+1, '...',
        o_min = b*OrdersPerBatch #Starting order number for (b+1)th batch
        o_max = min((b+1)*OrdersPerBatch-1, TotalOrders-1) #Ending order number for (b+1)th batch
        for o in range(o_min,o_max+1):
            arr_sum = np.sum(arr_order_sku_pivot[o_min:o+1], axis = 0)
            for s in range(0,distinct_skus):
                if arr_sum[s] != 1: arr_sum[s] = 0
            arr_curr_order = arr_order_sku_pivot[o]
            arr_dot = np.dot(arr_sum, arr_curr_order)

            oskupicks_matrix[OrdersPerBatch-1][o] = arr_dot
\$\endgroup\$
4
\$\begingroup\$

Two warnings before I give my suggestions:

  1. I'm no expert with pandas, numpy or this domain. There could be a one line solution that has a nice name and has been implemented already. If there is I don't know it.

  2. I'm testing the code I provide with python 3.6.6, numpy 1.15.0, and pandas 0.23.4. These are guaranteed to be different versions than what you are using, so check every line, does what you want it to do.

Onto the review.


TotalOrders = df_ord['ORD_KEY'].drop_duplicates().count() #Orders

I found the function nunique in the panda docs, which I believe does exactly what you want. As the comment here doesn't do much, I'd drop it.

TOTAL_ORDERS = df_ord['ORD_KEY'].nunique()

Nitpick: According to the python style guide, there are a few different naming conventions that are recognised. I would usually associate CamelCase names with classes. I'd expect this variable to fall under the category of a GLOBAL_VARIABLE (if you were to reorganise the code or write it in another language) so that convention may be more appropriate. This is up to you so go with whatever you like. Once it is consistent it is easier to read.


arr_order_sku_pivot = pd.pivot_table(df_ord, values = 'QTY', index = 'ORD_KEY', columns = 'SKU_KEY').reset_index(drop=True).values
for i in range(0,arr_order_sku_pivot.shape[0]):
    for j in range(0,arr_order_sku_pivot.shape[1]):
        if arr_order_sku_pivot[i][j] > 0:
            arr_order_sku_pivot[i][j] = 1
        else:
            arr_order_sku_pivot[i][j] = 0

There is too much happening on the first line. Since you are just pulling the values out of the dataframe there isn't much point here resetting the index.

arr_order_sku_pivot = pd.pivot_table(df_ord, values='QTY', index='ORD_KEY', columns='SKU_KEY')

The loops lead me on to my bit of advice with pandas (and numpy). If you can do it with the library rather than with python, it is usually much better. So try every function you can find before resorting to manually coding whatever it is you are doing. The intuition behind it is that every time you move from one to the other, you have to spend a whole bunch of time converting the data back and forth.

So lets try re-doing these loops in pandas. From a high level, the loop goes through the df, and puts 1 anywhere there was a positive number. Everywhere else gets a 0. To save brain overhead lets just call arr_order_sku_pivot df for now.

(df > 0)

Ok, that now has a True everwhere that was greater than 0, and False everywhere else (including the nans). We want them to be 1s and 0s though.

(df > 0).astype(int)

There, that is almost everthing. To keep from modifying code further down we can now pull the values out too.

(df > 0).astype(int).values

Done. We are down to two lines, which should be much easier to comment.

arr_order_sku_pivot = pd.pivot_table(df_ord, values='QTY', index='ORD_KEY', columns='SKU_KEY')
arr_order_sku_pivot = (arr_order_sku_pivot > 0).astype(int).values
# Make a 2d array where each row is an order, and each column is the sku.
# A 1 in a column indicates the sku was part of the order.

if TotalOrders % OrdersPerBatch == 0: 
    Batches = TotalOrders//OrdersPerBatch 
else: 
    Batches = TotalOrders//OrdersPerBatch + 1

This is doing division and rounding up. To get the number of batches you could also use

batches = int(np.ceil(float(TotalOrders) / OrdersPerBatch))

Some small points here, you can use np.ceil over math.ceil since it is already imported. If you ever transition to python3 (which is a good thing to think about doing) you wont even need to cast TotalOrders to a float, as the single slash is a floating point division.


o_min = b*OrdersPerBatch #Starting order number for (b+1)th batch
o_max = min((b+1)*OrdersPerBatch-1, TotalOrders-1) #Ending order number for (b+1)th batch
for o in range(o_min,o_max+1):
    ...

Nitpick: Why subtract 1 from each term of the min? You can just move it outside the min function.

min(a - 1, b - 1) == min(a, b) - 1

You then go on to add 1 back to it for the for the loop.

range(start, min(a, b) - 1 + 1) = range(start, min(a, b))

So hopefully that makes things a little easier to read.

arr_sum = np.sum(arr_order_sku_pivot[o_min:o+1], axis = 0)
for s in range(0,distinct_skus):
    if arr_sum[s] != 1: arr_sum[s] = 0
arr_curr_order = arr_order_sku_pivot[o]
arr_dot = np.dot(arr_sum, arr_curr_order)

oskupicks_matrix[OrdersPerBatch-1][o] = arr_dot

This is probably the bit that slows down everything. This is in a third nested loop, which then goes into a forth nested loop. If you can move these loops into numpy or pandas you should get a decent speed up. The other place here I believe is causing a slowdown is the condition. Lets try and rewrite this bit, keeping in mind that numpy should be doing all the work.

My proposal is to keep an array of all the SKUs we haven't seen, and use that to work out the unique ones. Then we can use the nice trick of getting the dot product between the array of unseen SKUs and the current row to get the number of unique SKUs. There is a little house keeping to do, like to mark off SKUs as seen, we invert the current row and bitwise and it to mark them off. This could be done other ways, but the implementation is below. Do note that to do the invert the row trick we has to set the elements to be ints rather than floats. This is fine as they were set to ints earlier.

for b in range(batches):
    batch_start = b * orders_per_batch
    batch_end = min(batch_start + orders_per_batch, TOTAL_ORDERS)

    unseen = 1 - arr_order_sku_pivot[batch_start]
    # 1 - a is a trick to flip all the 1s and 0s in an array
    # NOTE: This assumes there is at least one order per batch
    unique_SKUs = arr_order_sku_pivot[batch_start].sum()
    oskupicks_matrix[OrdersPerBatch-1][batch_start] = unique_SKUs

    for i in range(batch_start + 1, batch_end):
        unique_SKUs = np.dot(unseen, arr_order_sku_pivot[i])
        unseen &= 1 - arr_order_sku_pivot[i]
        oskupicks_matrix[OrdersPerBatch-1][i] = unique_SKUs

I've made a few minor changes like o -> i as i is a far more common name for a throwaway variable in a loop. I've also changed how the ending index of a batch is calculated, checking if you can move by the batch size makes more sense to me.


Some closing remarks, this is definitely not even close to perfect. There are a couple of loops that could be changed to functions which are then apply-ied for more parallelism. The main matrix we are working with is converted from floats to bools to ints, but it probably could have stayed as bools.

I hope there is enough in this that you can actually work on and improve upon yourself, good luck and please post a follow up question!

\$\endgroup\$
0
\$\begingroup\$

EDIT: my previous answer gave me the idea to do it this way:

# define the parameter of number of batch
MaxBatchSize = 10
# first create the the pivot array:
arr_ord_pivot = np.clip(df_ord.pivot(index='ORD_KEY', columns='SKU_KEY',values='QTY').fillna(0).values,0,1)
# get the number of unique ORDER_KEY and SKU_KEY
nb_ORD_KEY, nb_SKU_KEY = arr_ord_pivot.shape

# create empty result array
arr_result = np.zeros((MaxBatchSize, nb_ORD_KEY))

# fill arr_result with values
for batch_size in range(1,MaxBatchSize+1): #loop over batch size
    # create an temp array with initial data from arr_ord_pivot
    # add enough rows to not be bothered by summing not same shape array
    arr_temp = np.vstack([arr_ord_pivot.copy(), 
                          np.zeros((batch_size-nb_ORD_KEY % batch_size,
                                    nb_SKU_KEY))])
    # create the list all previous subarray
    list_arr = [arr_temp[i::batch_size] for i in range(0,batch_size-1)]
    # loop over each subarray to substract all previous ORDER_KEY in same batch
    for k in range(batch_size-1, 0,-1):
        arr_temp[k::batch_size] -= sum(list_arr[:k])
    #fill the result and keep only the good size
    arr_result[batch_size-1] = np.clip(arr_temp,0,1).sum(1)[:nb_ORD_KEY]

so what I called arr_result is actually your oskupicks_matrix.

I did some timeit, and my method seems 3 times faster than yours for your data.

EDIT 2: To extend the time comparison, I generate a data with around 10K orders over 2K different ORD_KEY and 50 different SKU_KEY like this:

df_ord = pd.DataFrame({'ORD_KEY':[10000+i for i in range(2000)]*5,
                       'SKU_KEY':np.random.randint(0,50,10000),
                       'QTY':1}).drop_duplicates()

Note: If you have duplicates over the couple (ORD_KEY, SKU_KEY), the pivot method won't work, so drop_duplicates is mandatory here with this generating.

As a result, the method above is about 45 time faster than yours with this larger data.

Old answer

I think you can do it this way:

# first create the pivot table
df_ord_pivot = df_ord.pivot(index='ORD_KEY', columns='SKU_KEY',values='QTY').fillna(0)

Then you want to know if the SKU_KEY is contained in the ORD_KEYs before, depending on the batch size. So you can do it this way for a batch size = 2 for example:

print (np.clip(df_ord_pivot.rolling(2).apply(lambda x: x[-1]-x[:-1].sum(), raw=True)
                   .fillna(0).values,0,1).sum(1))
array([0., 0., 1., 1., 1., 1., 1., 1., 2., 2., 0., 2., 1., 1.])

for example you see that the second value is 0, like in you example with ORD_KEY=10002 if the batch size is at least 2, and you can do it for any size of batch

list_arr_diff = [df_ord_pivot.values.sum(1)] +\
                [np.clip(df_ord_pivot.rolling(size).apply(lambda x: x[-1]-x[:-1].sum())
                                     .fillna(0).values,0,1).sum(1) 
                for size in range(2,MaxBatchSize +1)]

Now, you need for each size of batch, to replace each value i+n*size from 1 to size by the corresponding value in the rolling substraction created before.

list_batch = []
for size in range(1,MaxBatchSize +1):
    temp_arr = list_arr_diff[0].copy()
    for i in range(1,size):
        temp_arr[i::size] = list_arr_diff[i][i::size]
    list_batch.append(temp_arr)

So at the end, you have: oskupicks_matrix = np.array(list_batch)

For small dataset like yours, not sure it's faster but bigger, I hope it is and I'm sure you can even get it better with more numpy knowledge than I have

\$\endgroup\$
  • \$\begingroup\$ Thank you for the suggestions. I haven't tried this out yet since there are a some new functions which I couldn't follow owing to my small knowledge-base of pandas and numpy, but it is growing! :) Will let you know how it functions in the larger code once I'm able to test it out. The other answer I received worked very well and brought down run-time very significantly, but not sure how it would compare to your solution. \$\endgroup\$ – Crypticlight Aug 9 '18 at 21:04
  • \$\begingroup\$ @Crypticlight the other solution gave a lot of more information on how to improve your orignal code! Good luck in learning pandas and numpy :) \$\endgroup\$ – Ben.T Aug 9 '18 at 21:12

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.