PERF: Improve performance of CategoricalIndex.is_unique
State: closed

``CategoricalIndex.is_unique`` creates an extraneous boolean array. By changing ``CategoricalIndex.is_unique`` to use ``CategoricalIndex._engine.is_unique`` instead, this array creation is avoided. We simultaneously get to set ``is_monotonic*`` for free, and therefore will save time, if that property is called later.

Demonstration
==========

Setup:

```python
>>> n = 1_000_000
>>> ci = pd.CategoricalIndex(list('a' * n + 'b' * n + 'c' * n))
```

Currently, ``ci.is_unique`` is about the same (disregarding``@readonly_cache``) as:

```python
>>> from pandas._libs.hashtable import duplicated_int64
>>> not duplicated_int64(ci.codes.astype('int64')).any()
False
>>> %timeit duplicated_int64(ci.codes.astype('int64')).any()
46.7 ms ± 4.18 ms per loop (mean ± std. dev. of 7 runs, 10 loops each)
```

Notice that the ``duplicated_int64()`` creates an boolean array, which is not needed and slows the operation down.

If we instead use ``ci._engine.is_unique`` to check for uniqueness, the check is roughly similar to:
```python
>>> from pandas._libs.algos import is_monotonic_int64
>>> is_monotonic_int64(ci.codes.astype('int64'), False)
(True, False, False)  # (is_monotonic_inc, is_monotonic_dec, is_unique)
>>> %timeit is_monotonic_int64(ci.codes.astype('int64'), False)
23.3 ms ± 364 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)
```

This is faster than the other version, as the intermediate boolean array is not created in this version. Also, is it (IMO) more idiomatic, as ``index._engine`` is in general supposed to be used for this kind of index content checks.



Labels:
name: Performance
description: Memory or execution speed performance
name: Categorical
description: Categorical Data Type

Comments:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21107?src=pr&el=h1) Report
> Merging [#21107](https://codecov.io/gh/pandas-dev/pandas/pull/21107?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/e033c0616158d3ba974456b4f84810492936b1fe?src=pr&el=desc) will **not change** coverage.
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/21107/graphs/tree.svg?src=pr&height=150&width=650&token=eZ4WkYLtcO)](https://codecov.io/gh/pandas-dev/pandas/pull/21107?src=pr&el=tree)

```diff
@@           Coverage Diff           @@
##           master   #21107   +/-   ##
=======================================
  Coverage   91.83%   91.83%           
=======================================
  Files         153      153           
  Lines       49498    49498           
=======================================
  Hits        45458    45458           
  Misses       4040     4040
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.23% <100%> (ø)` | :arrow_up: |
| #single | `41.88% <0%> (ø)` | :arrow_up: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/21107?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/category.py](https://codecov.io/gh/pandas-dev/pandas/pull/21107/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9jYXRlZ29yeS5weQ==) | `97.03% <100%> (ø)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21107?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21107?src=pr&el=footer). Last update [e033c06...06aef54](https://codecov.io/gh/pandas-dev/pandas/pull/21107?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

``is_unique`` is a cached property, so I don't think an ASV makes sense in this case. (I assume ``setup`` in ASV is called once for each time method, but not once for every call to the time method, haven't checked).

So this PR improves first-time calls to ``is_unique`` and also makes calling ``is_unique`` and  ``is_monotonic*`` in succesion faster, as both are set simultaneously. So e.g. ``ci.is_monotonic_increasing and ci.is_unique`` will be much faster (on the first call, on subsequent calls both are cached).
how does this diminish the value of an asv?

sure if the subsequent calls are cached the mean time is lower but this should still show an asv improvement yes?
My impression has been that these neasurement are done in a “best of 3” style (like %timeit). For such tests the uncached version always loses.

Haven’t looked into how asv does it, so I could be mistaken here.
It seems to me that ASV does "best of X" style of testing. from the [docs](https://asv.readthedocs.io/en/latest/writing_benchmarks.html#timing):

> The timing itself is based on the Python standard library’s timeit module, with some extensions for automatic heuristics shamelessly stolen from IPython’s %timeit magic function

I could add the timing tests, but I assume these improvement is not seen well in repeated calls to ``is_unique``. You want them added still?
we do have asv's for others. sure if can tag so these are run once is better (not sure if that is possible)


```
(pandas) bash-3.2$ grep -r is_unique asv_bench/benchmarks/
asv_bench/benchmarks//algorithms.py:        # cache is_unique
asv_bench/benchmarks//algorithms.py:        self.idx_int_dup.is_unique
```
 > we do have asv's for others. sure if can tag so these are run once is better (not sure if that is possible)
>
> (pandas) bash-3.2$ grep -r is_unique asv_bench/benchmarks/
> asv_bench/benchmarks//algorithms.py:        # cache is_unique
> asv_bench/benchmarks//algorithms.py:        self.idx_int_dup.is_unique

Those two are in a setup method, so timing are not done on them:

```python
class DuplicatedUniqueIndex(object):

    goal_time = 0.2

    def setup(self):
        N = 10**5
        self.idx_int_dup = pd.Int64Index(np.arange(N * 5))
        # cache is_unique
        self.idx_int_dup.is_unique

     def time_duplicated_unique_int(self):
```

So currently there is no tests for ``is_unique`` in asv_bench, and it probably doesn't make sense  IMO, as ``is_unique`` is a cached property and timing it will just return the cached value, and not time the speed of the algorithm.
hmm ok. can you open a new issue to create asv's in some form or another for this (and is_unique in general). w/o asv's someone will ineveitable change something which breaks this.

maybe should just temporary turn cached_properties off with a context manager when running them.
> maybe should just temporary turn cached_properties off with a context manager when running them.

Is there currently a context manager or option for this in Pandas?
no i think would need to create one for purposes of measuring cached properties