6
\$\begingroup\$

I have a dataframe in pandas like this

Date         cell         tumor_size (assume it is three dimensional)
25/10/2015    113           [51, 52, 55]
22/10/2015    222           [50, 68, 22]
22/10/2015    883           [45, 23, 67]
20/10/2015    334           [35, 23, 76]

What I want to do is compare the size of the tumors detected on the different days. Let's consider the cell 222 as an example; I want to compare its size to different cells but detected on earlier days e.g. I will not compare its size with cell 883, because they were detected on the same day. Or I will not compare it with cell 113, because it was detected later on. As my dataset is too large, I have iterate over the rows. Here is my sample code:

# These will be our lists of pairs and size differences.
pairs = []
diffs = []

# Loop over all unique dates
for date in df.Date.unique():
    # Only take dates earlier then current date.
    compare_df =df.loc[df.Date < pd.Timestamp(date).to_pydatetime()].copy()
    # Loop over each cell for this date and find the minimum
    for row in df.loc[df.Date ==  pd.Timestamp(date).to_pydatetime()].itertuples():
        # If no cells earlier are available use nans.
        if compare_df.empty:
            pairs.append(float('nan'))
            diffs.append(float('nan'))
        # Take lowest absolute value and fill in otherwise
        else:
            compare_df['distance'] = compare_df['tumor_size'].map(lambda x: np.linalg.norm(x - row.tumor_size))
            row_of_interest = compare_df.loc[compare_df.distance == compare_df.distance.min()]
            cell = row.cell
            Date = row.Date
            most_similar_to = row_of_interest.cell.values[0]
            similarity = row_of_interest.distance.values[0]
            with open('final_csv', "a", newline="") as f:
                writer = csv.writer(f, dialect="excel-tab")
                writer.writerow([cell, Date, most_similar_to, similarity])

How could I improve the speed of the code? I have over one million cells.

\$\endgroup\$
6
\$\begingroup\$

There are a few quick improvements you can make. First, always remove as many things as possible from for loops. In this case, the date formatting and the open file lines can be removed.

Dates. Format the dates in your dataframe before the first for loop with something like

df['Date'] = pd.to_datetime(df['Date']).dt.date

Notice I’m converting the datetime into a date only since I don’t think you need to know the time.

This way you can write

compare_df = df.loc[df.Date < date].copy()

and

for row in df.loc[df.Date == date].itertuples():

It's faster to use Pandas series functions rather than calculate/convert something like pd.Timestamp(date).to_pydatetime() while looping through rows. I really liked this article which explains the fastest way to do things in Python.

Saving to file. Inside of the second for loop you have

with open('final_csv.csv',"a", newline="") as f:
    writer = csv.writer(f, dialect="excel-tab")

which is opening and closing the file every time through the for loop. So for a million records, the file is being opened and closed a million times. Opening it once at the beginning by moving those two lines to the beginning of the script should save a significant amount of time. When I time it for the four rows you gave in your example, it looks like the time is cut in half just by moving the with two lines above outside of the for loops.

Also, ‘final_csv’ has no extension, so the file is being saved as type ‘file’. If you want to save as a csv, then write

with open('final_csv.csv', "a", newline="") as f:
    writer = csv.writer(f)

I removed dialect="excel-tab" from the second line above so that columns are separated by commas and appear in separate columns when opened up in Excel.

If you run your script more than once the final_csv file that you already created will be added onto, and so you might end up with duplicate entries. To avoid this, write

with open('final_csv.csv', "w", newline="") as f

where “a” has been replaced with “w”, so that a new file will be created each time your script is run.

The pairs and diffs lists that you create are never used, so remove them. As your code is right now, when there is no prior date, the last most_similar_to and similarity are being written to the file a second time rather than ‘nan’. To fix this, remove

cell = row.cell
Date = row.Date

from the conditional statement and instead put these two lines right after the second for statement. Then replace

pairs.append(float('nan'))
diffs.appen(float('nan'))

after the if statement with

most_similar_to = float('nan')
similarity = float('nan')

Algorithm. Your use of map and lambda function is clever.

Another method to consider all together is using NumPy and calculating distances with matrix operations. Here is how I rewrote your code using NumPy (including all changes I mentioned above):

import pandas as pd
import numpy as np
import csv

df['Date'] = pd.to_datetime(df['Date']).dt.date 

with open('final_csv.csv',"w", newline="") as f:
    writer = csv.writer(f)
    for row in df.itertuples():
        cell = row.cell
        Date = row.Date
        compare_df = df.loc[df.Date < row.Date].copy()
        if compare_df.empty: 
            most_similar_to = float('nan')
            similarity = float('nan')
        else:
            sizes = np.array(list(compare_df['tumor_size']))
            diff = sizes - np.array(row.tumor_size).transpose()
            square = np.multiply(diff,diff)
            sums = np.sum(square, axis=1)
            distances = np.sqrt(sums).round(decimals=2)
            similarity = min(distances)
            ind = np.where(distances == similarity)[0][0]
            most_similar_to = list(compare_df['cell'])[ind]
        writer.writerow([cell, Date, most_similar_to, similarity])

For a small number of tumor sizes, I see an additional 2x increase in speed using NumPy. However, Python can only seem to easily handle a 10,000 by 10,000 square matrix. Anything much larger will drastically slow down a laptop with 8 GB RAM and core i7 processor. Below is the graph of the processing times as the size of the matrix increases.

enter image description here

It’s not clear to me if every cell size should be compared to all cell sizes from every previous date going back indefinitely. If you're able to limit the number of cells that each row has to be compared to (like maybe only going back a certain number of days, for example), you will save on time. If you do need to compare all cell sizes to all previous cell sizes, it may be possible to chunk the matrices and store in hdf5 files using PyTables.

Good luck!

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

You repeat a lot of work in each loop. A simple one is extracting the tumor_sizes from the lists. Each row you do sizes = np.array(list(compare_df['tumor_size'])). If you do tumor_sizes = df["tumor_size"].apply(pd.Series) at the beginning of the calculation, you have a series with all tumorsizes, indexed the same as your df.

You can save your results in a DataFrame, and then write this to a csv afterwards. If you want to do some further analysis, you have the DataFrame handy.

result = pd.DataFrame(
    {
        "cell": df["cell"],
        "Date": df["Date"],
        "most_similar_to": None,
        "similarity": None,
    },
    index=df.index,
)

I

To iterate over the different days, you can use DataFrame.groupby:

for date, data in df.groupby(pd.Grouper(key="Date", freq="d")):
    if data.empty:
        continue
    #     print(data)
    previous_samples = df["Date"] < date
    compare_df = df.loc[previous_samples]
    compare_sizes = tumor_sizes.loc[previous_samples]
    if compare_df.empty:
        continue

iterates over all dates. it skips the ones where there were no samples, or no previous samples.

Then you can iterate over every row

    for row in data.itertuples():
        distances = pd.Series(
            data=np.linalg.norm(
                compare_sizes - tumor_sizes.loc[[row.Index]].values, axis=1
            ),
            index=compare_sizes.index,
        )
        most_similar_index = distances.idxmin()
        result.loc[row.Index, ["most_similar_to", "similarity"]] = [
            compare_df.loc[most_similar_index, "cell"],
            distances[most_similar_index],
        ]
result

Then you can write the result to csv

result.to_csv(<filename>, **<format_options>)

more vectorized

instead of the for-loop, you can use scipy.spatial.distance_matrix on chuncks of the data. Like that you don't have to compute the whole spacial matrix, but only per day for example, reducing the memory need

from scipy.spatial import distance_matrix
result2 = pd.DataFrame(
    {
        "cell": df["cell"],
        "Date": df["Date"],
        "most_similar_to": None,
        "similarity": None,
    },
    index=df.index,
)
for date, data in df.groupby(pd.Grouper(key="Date", freq="d")):
    if data.empty:
        continue
    #     print(data)
    previous_samples = df["Date"] < date
    compare_df = df.loc[previous_samples]
    compare_sizes = tumor_sizes.loc[previous_samples]
    if compare_df.empty:
        continue
    distances = pd.DataFrame(
        distance_matrix(tumor_sizes.loc[data.index], compare_sizes),
        index=data.index,
        columns=compare_sizes.index,
    )
    most_similar_indices = distances.idxmin(axis=1)
    result2.loc[
        most_similar_indices.index, ["most_similar_to", "similarity"]
    ] = pd.DataFrame(
        {
            "most_similar_to": compare_df.loc[
                most_similar_indices, "cell"
            ].values,
            "similarity": distances.min(axis=1).values,
        },
        index=data.index,
    )

An alternative which stays more in numpy-land, and less in pandas:

result3 = pd.DataFrame(
    {
        "cell": df["cell"],
        "Date": df["Date"],
        "most_similar_to": None,
        "similarity": None,
    },
    index=df.index,
)
for date, data in df.groupby(pd.Grouper(key="Date", freq="d")):
    if data.empty:
        continue
    #     print(data)
    previous_samples = df["Date"] < date
    compare_df = df.loc[previous_samples]
    compare_sizes = tumor_sizes.loc[previous_samples]
    if compare_df.empty:
        continue
    distances = distance_matrix(tumor_sizes.loc[data.index], compare_sizes)

    most_similar_indices = distances.argmin(axis=1)
    most_similar_to = compare_df["cell"].values[most_similar_indices]
    similarities = np.choose(most_similar_indices, distances.T)

    result3.loc[data.index, "most_similar_to"] = most_similar_to
    result3.loc[data.index, "similarity"] = similarities
| improve this answer | |
\$\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.