4
\$\begingroup\$

I have the following code:

import pandas as pd
import numpy as np
import itertools 
from pprint import pprint

# Importing the data
df=pd.read_csv('./GPr.csv', sep=',',header=None)
data=df.values
res = np.array([[i for i in row if i == i] for row in data.tolist()], dtype=object)

# This function will make the subsets of a list 
def subsets(m,n):
    z = []
    for i in m:
        z.append(list(itertools.combinations(i, n)))
    return(z)

# Make the subsets of size 2 
l=subsets(res,2)
l=[val for sublist in l for val in sublist]
Pairs=list(dict.fromkeys(l)) 

# Modify the pairs: 
mod=[':'.join(x) for x in Pairs]

# Define new lists
t0=res.tolist()
t0=map(tuple,t0)
t1=Pairs
t2=mod

# Make substitions
result = []
for v1, v2 in zip(t1, t2):
    out = []
    for i in t0:
        common = set(v1).intersection(i)
        if set(v1) == common:
            out.append(tuple(list(set(i) - common) + [v2]))
        else:
            out.append(tuple(i))
    result.append(out)

pprint(result, width=200)  

# Delete duplicates
d = {tuple(x): x for x in result} 
remain= list(d.values())  

What it does is as follows: First, we import the csv file we want to work with in here. You can see that it is a list of elements, for each element we find the subsets of size two. We then write a modification to the subsets and call it mod. What it does is to take say ('a','b') and convert it to 'a:b'. We then, for each pair, go through the original data and where ever we find the pairs we substitute them. Finally we delete all the duplicates as it is given.

The code works fine for small set of data. Yet the problem is that the file I have, has 30082 pairs where for each the list of ~49000 list should be scanned and pairs being replaced. I run this in Jupyter and after some time the Kernel dies. I wonder how one can optimise this?

\$\endgroup\$
  • \$\begingroup\$ If I don't get this wrong, you expect your double loop to append 30082 * 49000 = 1.4e+9 elements (which are lists of strings, so probably >100 Bytes on average) to your result. That's a lot to hold in memory and to print. Are you sure this code does what you want it to do? \$\endgroup\$ – Matthias Huschle Jul 10 at 17:33
  • \$\begingroup\$ Indeed you're correct about the number. Yes it does work for small sample list. But not for the big dataset I've got. \$\endgroup\$ – William Jul 11 at 8:39
1
\$\begingroup\$

How to resolve the output size issue (many GB in memory and console) is highly specific to your overall setting, i.e. how you want to use the data further, so I restrict my answer to look into possible performance gains.

Performance baseline

I determine the baseline by restricting you original loop logic to the first 20 pairs:

t0=res.tolist()
t0=[tuple(x) for x in t0]
t1=Pairs
t2=mod

def run_loop_original(limit=20):
    # Make substitions
    result = []
    for i_pair, (v1, v2) in enumerate(zip(t1, t2)):
        if i_pair >= limit:
            break
        out = []
        for i in t0:
            common = set(v1).intersection(i)
            if set(v1) == common:
                out.append(tuple(list(set(i) - common) + [v2]))
            else:
                out.append(tuple(i))
        result.append(out)
    return result
    >>> %timeit run_loop_original(20)
    1 loops, best of 3: 1.33 s per loop

Performance Sinks

As far as I can tell, those are:

  • type conversion of string arrays
  • repeated string comparisons to identify the pairs within tuples
  • large nested list construction by double for-loop

Container Type Conversions

Here I simply leave out the tuple conversion in the nested list construction. Your code does not indicate that order of ingredients matters, so the information is equivalent, whether it is a list, tuple, or set.

t0=res.tolist()
t0=[tuple(x) for x in t0]
t1=Pairs
t2=mod

def run_loop_non_tuple(limit=20):
    # Make substitions
    result = []
    for i_pair, (v1, v2) in enumerate(zip(t1, t2)):
        if i_pair >= limit:
            break
        out = []
        for i in t0:
            common = set(v1).intersection(i)
            if set(v1) == common:
                out.append(set(i) - common)
                out[-1].add(v2)
            else:
                out.append(i)
        result.append(out)
    return result
    >>> %timeit run_loop_non_tuple(20)
    1 loops, best of 3: 1.09 s per loop

This is not all, as the conversion of the individual tuples/lists to sets for the pair finding can be done outside the loop:

t0=[set(i) for i in res.tolist()]
t1=Pairs
t2=mod

def run_loop_sets(limit=20):
    # Make substitions
    result = []
    for i_pair, (v1, v2) in enumerate(zip(t1, t2)):
        if i_pair >= limit:
            break
        v1 = set(v1)
        out = []
        for i in t0:
            common = v1.intersection(i)
            if v1 == common:
                out.append(i - common)
                out[-1].add(v2)
            else:
                out.append(i)
        result.append(out)
    return result
    >>> %timeit run_loop_sets(20)
    1 loops, best of 3: 460 ms per loop

Repeated String Comparisons

Two things might help speeding up:

  • instead of comparing strings individually, an index can be built to find the relevant entries
  • there is a very limited amount of words overall, so they can be mapped to integers for faster matching

Let's start with a word mapping:

from itertools import chain
all_words = np.array(list(set(chain(*t0))))
word_mapping = {word: i for i, word in enumerate(all_words)}
    >>> len(all_words)
    381

There is no need to convert everything beforehand. Just go directly for creating an index. This can be realized as a numpy 2D-array, where we have a row per element of t0 and a column per all_words. The values are just True/False values as uint8 (1 Byte per value).

word_index = np.zeros(shape=(len(t0), len(all_words)), dtype=np.uint8)
for i_row, row in enumerate(t0):
    for word in row:
        word_index[i_row, word_mapping[word]] = 1
    >>> word_index.shape, word_index.sum()
    ((48983, 381), 416041)

You can now lookup which rows have a pair of words by using the & operator:

    >>> word_index[:, word_mapping[Pairs[0][0]]] & word_index[:, word_mapping[Pairs[0][1]]]
    array([0, 0, 0, ..., 0, 0, 0], dtype=uint8)

So we rebuild the loop with this advantage:

t0=[set(i) for i in res.tolist()]
t1=[set(x) for x in Pairs]
t2=mod

def run_loop_indexed(limit=20):
    # Make substitions
    result = []
    for i_pair, (v1, v2) in enumerate(zip(t1, t2)):
        if i_pair >= limit:
            break
        i1 = [word_mapping[x] for x in v1]
        ix_contain_pair = word_index[:, i1[0]] & word_index[:, i1[1]]
        out = []
        for row, contains_pair in zip(t0, ix_contain_pair):
            if contains_pair:
                out.append(row - v1)
                out[-1].add(v2)
            else:
                out.append(row)
        result.append(out)
    return result
    >>> %timeit run_loop_indexed(20)
    1 loops, best of 3: 216 ms per loop

Double for Loop

It would still help to avoid the nested list construction via the double loop. What helps there is, that the nested lists are identical to t0 if the pair is missing, and it is missing in the majority of cases. So we first construct a copy of t0 and then replace the rows that contain the pair.

To get the indices in t0, flatten and use np.nonzero:

    >>> np.ravel(np.nonzero(word_index[:, word_mapping[Pairs[0][0]]] & word_index[:, word_mapping[Pairs[0][1]]]))
    array([ 1915,  1987,  8062, 10593, 10614, 10663, 10879, 11235, 12021,
   12096, 13445, 13805, 14630, 17658, 17701, 18865, 20712, 22560,
   23573, 23840, 25379, 25487, 27338, 27690, 28630, 32266, 33259,
   33884, 34309, 34412, 35430, 35463, 35968, 36326, 36977, 39477,
   40292, 42138], dtype=int64)
t0=[set(i) for i in res.tolist()]
t1=[set(x) for x in Pairs]
t2=mod

def run_loop_indexed_2(limit=20):
    # Make substitions
    result = []
    for i_pair, (v1, v2) in enumerate(zip(t1, t2)):
        if i_pair >= limit:
            break
        i1 = [word_mapping[x] for x in v1]
        ix_contain_pair = np.ravel(np.nonzero(word_index[:, i1[0]] & word_index[:, i1[1]]))
        out = t0[:]
        for i in ix_contain_pair:
            out[i] = out[i] - v1
            out[i].add(v2)
        result.append(out)
    return result
    >>> %timeit run_loop_indexed_2(20)
    10 loops, best of 3: 43.1 ms per loop

I still expect you to run into memory limits on the full set and/or to crash your notebook connection trying to print the results.

\$\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.