DataFrame.sort_values(inplace=True) is slow and eats too much memory

[liori]

Code Sample, a copy-pastable example if possible

Save as test.py:

import pandas
import numpy
import resource
import sys

variant, nrows, ncols = sys.argv[1:4]

numpy.random.seed(0)
df = pandas.DataFrame(numpy.random.randn(int(nrows), int(ncols)))

if variant == '1':
        df.sort_values(by=list(df.columns), inplace=True)
elif variant == '2':
        order = numpy.lexsort(
                [df[col].values for col in reversed(list(df.columns))])
        for col in list(df.columns):
                df[col] = df[col].values[order]

usage = resource.getrusage(resource.RUSAGE_SELF)
print 'Time:', usage.ru_utime
print 'Memory:', usage.ru_maxrss
print 'Result hash:', hash(df.values.tobytes())

Problem description

Stumbled upon this one when working on a data frame that barely fits RAM. DataFrame.sort_values (variant 1 in the code above) is needlessly slow and eats way too much memory. It is easily possible to make it work faster and with little memory (see variant 2).

The difference can already be seen for: for i in 0 1 2; do python test.py $i 1000000 10; done (on i7 2600):

Time: 0.644
Memory: 120668
Result hash: -2365191988694623552
Time: 6.54
Memory: 869680
Result hash: 7653301644290849024
Time: 3.432
Memory: 148236
Result hash: 7653301644290849024

Changing df[col] = df[col].values[order] into df[col].values[:] = df[col].values[order] offers additional small speedup, but probably changes semantics. Not sure.

Output of pd.show_versions()

In [2]: pandas.show_versions()

INSTALLED VERSIONS

commit: None
python: 2.7.9.final.0
python-bits: 64
OS: Linux
OS-release: 4.8.0-0.bpo.2-amd64
machine: x86_64
processor:
byteorder: little
LC_ALL: None
LANG: pl_PL.utf8
LOCALE: None.None

pandas: 0.19.2
nose: None
pip: 9.0.1
setuptools: 34.2.0
Cython: None
numpy: 1.12.0
scipy: None
statsmodels: None
xarray: None
IPython: 5.2.2
sphinx: None
patsy: None
dateutil: 2.6.0
pytz: 2016.10
blosc: None
bottleneck: None
tables: None
numexpr: None
matplotlib: None
openpyxl: None
xlrd: None
xlwt: None
xlsxwriter: None
lxml: None
bs4: None
html5lib: 0.9999999
httplib2: None
apiclient: None
sqlalchemy: None
pymysql: None
psycopg2: None
jinja2: 2.9.5
boto: None
pandas_datareader: None

[jreback]

an easy to repro example

np.random.seed(1234)
df = pandas.DataFrame(numpy.random.randn(10000, 100)) 

we have used this technique in several places (e.g. #15245) since the original pandas.core.groupby._lexsort_indexer was written. This could be adapted, taking care that the wrapper code still needs to be there to handle myriad of cases (nan placement & nulls).

So would be in favor of making this change.

@liori if you'd like to submit a PR that fully passes the tests suite would be great. This is how things get fixed quickly!

[jreback]

@liori I isolated these kinds of things a bit here.

certainly would take a PR!

[nabinkhadka]

So anything about this?

[TomAugspurger]

@nabinkhadka are you interested in investigating further?

[Quetzalcohuatl]

This allowed me to sort my very large dataframe. Variant 2 should be implemented for large dataframes where RAM is tight. It was also extremely fast on my 4 numeric columns I was using for ordering.

[tommedema]

@liori one problem with this approach is that it ignores the index, i.e. the index is not preserved after sorting

I tried to fix this as follows (requires pandas 1.5):

def pdSortValuesInPlaceFast(df, allColumnsOrdered):
    # Must specify all columns for this to work
    if not np.array_equal(sorted(list(df.columns)), sorted(allColumnsOrdered)):
        raise Exception('cannot sort fast without specifying all columns')
    
    indexNames = df.index.names
    df.reset_index(names = '_index', inplace = True)
    allColumnsOrdered.append('_index')
    
    order = np.lexsort([df[col].values for col in reversed(allColumnsOrdered)])
    
    for col in allColumnsOrdered:
        df[col] = df[col].values[order]
        
    df.set_index('_index', inplace = True, drop = True)
    df.index.names = indexNames

[liori]

I only rarely use pandas, I'm more of an R guy. As such, I'm not really in position to offer PRs to a project I barely know. Preserving indices makes sense, I probably didn't need them when I initially investigated the issue.