PERF: improves performance and memory usage of DataFrame.duplicated
State: closed

on master:

```
In [1]: np.random.seed(2718281)

In [2]: n = 1 << 20

In [3]: t = pd.date_range('2015-01-01', freq='S', periods=n // 64)

In [4]: xs = np.random.randn(n // 64).round(2)

In [5]: df = DataFrame({'a':np.random.randint(- 1 << 8, 1 << 8, n),
   ...:                 'b':np.random.choice(t, n),
   ...:                 'c':np.random.choice(xs, n)})

In [6]: %timeit df.duplicated()
1 loops, best of 3: 8.03 s per loop

In [7]: %memit df.duplicated()
peak memory: 461.79 MiB, increment: 356.10 MiB
```

on branch:

```
In [6]: %timeit df.duplicated()
1 loops, best of 3: 259 ms per loop

In [7]: %memit df.duplicated()
peak memory: 154.62 MiB, increment: 49.36 MiB
```

benchmarks:

```
-------------------------------------------------------------------------------
Test name                                    | head[ms] | base[ms] |  ratio   |
-------------------------------------------------------------------------------
frame_duplicated                             | 308.4060 | 7809.8300 |   0.0395 |
frame_drop_duplicates                        |  16.1637 |  28.8030 |   0.5612 |
frame_drop_duplicates_na                     |  17.1696 |  28.3937 |   0.6047 |
multiindex_duplicated                        | 136.1593 | 141.6107 |   0.9615 |
series_drop_duplicates_int                   |   1.1793 |   1.1443 |   1.0306 |
series_drop_duplicates_string                |   0.7900 |   0.7540 |   1.0479 |
-------------------------------------------------------------------------------
Test name                                    | head[ms] | base[ms] |  ratio   |
-------------------------------------------------------------------------------

Ratio < 1.0 means the target commit is faster then the baseline.
Seed used: 1234

Target [76459d2] : performance improvement in DataFrame.duplicated
Base   [ef48c6f] : Merge pull request #9377 from cmeeren/patch-1

DOC: Clarify how date_parser is called (GH9376)
```


Labels:
name: Performance
description: Memory or execution speed performance

Comments:
Nice! I noticed the other day that duplicated did not use the klib hashtable, which seemed strange, but I didn't have the time to dig into it.

Can you safely get ride of `pandas.lib.duplicated` with this change?

> Can you safely get ride of pandas.lib.duplicated with this change?

`lib.duplicated` is still used in `base.duplicated`. you can implement a duplicated function for objects using `kh_pyset_t` but in my tests the performance would be the same; ( expectedly so, as [the underlying hash function](https://github.com/pydata/pandas/blob/484f66814a32324248e3d03203ea991ed896fd7a/pandas/src/klib/khash_python.h#L26) is the same. )

@behzadnouri if you could refactor this a bit to make the use of the hashtables to be a separate function isolated in core/algos.py would be gr8

@jreback honestly I do not see how to do this in a way i am comfortable with. this is a very special usage where only the number of unique values matter not their actual values;

I meant someting like this: https://github.com/jreback/pandas/commit/923e35c2ce9c3fd0c5dac5c6f281d470e98072ff

@shoyer 

I still feel the current PR is cleaner and avoid the unnecessary type check/manipulation in [here](https://github.com/pydata/pandas/blob/1d94dd2ada7d0af57c245b083d26d60b8649a04e/pandas/core/algorithms.py#L128) and [here](https://github.com/pydata/pandas/blob/1d94dd2ada7d0af57c245b083d26d60b8649a04e/pandas/core/algorithms.py#L164); but, if you like to make these changes, plz do.

merged via https://github.com/pydata/pandas/commit/7da9178dad2c4b000c2446e5cc58ff0613a631c1

thanks @behzadnouri