BUG/PERF: Sort mixed-int in Py3, fix Index.difference
State: closed

- [x] fixes some issues from #13432
- [x] closes #12044
- [x] closes #12814
- [x] tests added / passed
- [x] passes `git diff upstream/master | flake8 --diff`
- [x] whatsnew entry

---
1. Added an internal `safe_sort` to safely sort mixed-integer
   arrays in Python3.
2. Changed Index.difference and Index.symmetric_difference
   in order to:
   - sort mixed-int Indexes (#13432)
   - improve performance (#12044)
3. Fixed DataFrame.join which raised in Python3 with mixed-int
   non-unique indexes (issue with sorting mixed-ints, #12814)
4. Fixed Index.union returning an empty Index when one of
   arguments was a named empty Index (#13432)

Benchmarks (for `index_object` only):

```
]$ asv compare bf47 a02f -f 1.5 -s 
Benchmarks that have improved:
    before     after       ratio
  [bf47    ] [a02f    ]
-  155.66ms    10.32ms      0.07  index_object.index_datetime_set_difference.time_index_datetime_difference
-  154.66ms     2.98ms      0.02  index_object.index_datetime_set_difference.time_index_datetime_difference_disjoint
-  391.45ms    10.65ms      0.03  index_object.index_datetime_set_difference.time_index_datetime_symmetric_difference
-  195.55ms    88.95ms      0.45  index_object.index_int64_set_difference.time_index_int64_difference
-  440.93ms   103.65ms      0.24  index_object.index_int64_set_difference.time_index_int64_symmetric_difference
-    8.77ms     4.88ms      0.56  index_object.index_str_set_difference.time_str_symmetric_difference
```


Labels:
name: Indexing
description: Related to indexing on series/frames, not to indexes themselves
name: Performance
description: Memory or execution speed performance
name: Dtype Conversions
description: Unexpected or buggy dtype conversions
name: Compat
description: pandas objects compatability with Numpy or Python functions

Comments:
xref #13504 

@jreback Thanks for the comments.

## [Current coverage](https://codecov.io/gh/pydata/pandas/pull/13514?src=pr) is **84.39%**

> Merging [#13514](https://codecov.io/gh/pydata/pandas/pull/13514?src=pr) into [master](https://codecov.io/gh/pydata/pandas/branch/master?src=pr) will increase coverage by **0.01%**

``` diff
@@             master     #13514   diff @@
==========================================
  Files           142        142          
  Lines         51223      51278    +55   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          43224      43276    +52   
- Misses         7999       8002     +3   
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last updated by [043879f...3a96089](https://codecov.io/gh/pydata/pandas/compare/043879fbb7de71605eed87991eb037c1917bace1...3a96089d5ad61727011756b8d63a42083da19f31?src=pr)

@pijucha looking really good. just a couple of comments.

@sinhrks if you can have a look.

I just noticed that `Index.sort_values` may benefit from `safe_sort`. So maybe I'll rewrite it too.

---

Also, I was thinking about MultiIndex #13504. I see two possible solutions:
1. make MultiIndex use `Index.difference` and `symmetric_difference`, and probably modify `MultiIndex._shallow_copy` (or `.from_tuples`)
2. just copy `Index.difference` to `MultiIndex.difference` but without the sorting block (I think it's not needed, `sortlevel` will do the job).
Solution 2 means some code duplication but it's faster.
I don't want to interfere with the other PR, so I'll probably add a separate comment there.

ok @pijucha looks good. minor doc updates. ping when green. other changes leave to other PR's

@jreback Done

@pijucha pls rebase, merging lots of stuff. ping when green. I think this lgtm.

@jreback Updated

@jreback I see several merges have been made in the meantime. Should I rebase again?

yes

@jreback Rebased, tests green.

@pijucha looks really good. just some tests splitting, minor corrections.

ping on green.

@jreback OK, cleaned some tests. It's green.

minor doc change. ping on green.

some failures on windows.  we ultimately test on appveyor.com (you just need a free account), but its very slow. so easiest to spin up a vm if you can.

these are prob because you need to use `_ensure_platform_int` when you are using an indexer (on windows things like `.take` and `.putmask` take a `int32` rather than standard `int64`. in this particular case you actually need to `_ensure_int64` (as you actually have platform ints up front).

```
(pandas3.5) C:\Users\conda\Documents\pandas3.5>nosetests pandas/tests/indexes
..........................................................................................................................................
..........................................................................................................................................
..........................................................................................................................................
.........................................................................S................................................................
......................................................................................................E...................................
................................................E...............................................
======================================================================
ERROR: test_join_non_unique (pandas.tests.indexes.test_numeric.TestInt64Index)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "C:\Users\conda\Documents\pandas3.5\pandas\tests\indexes\test_numeric.py", line 755, in test_join_non_unique
    joined, lidx, ridx = left.join(left, return_indexers=True)
  File "C:\Users\conda\Documents\pandas3.5\pandas\indexes\base.py", line 2635, in join
    return_indexers=return_indexers)
  File "C:\Users\conda\Documents\pandas3.5\pandas\indexes\base.py", line 2720, in _join_non_unique
    sort=True)
  File "C:\Users\conda\Documents\pandas3.5\pandas\tools\merge.py", line 909, in _get_join_indexers
    return join_func(lkey, rkey, count, **kwargs)
  File "pandas\src\join.pyx", line 51, in pandas.algos.left_outer_join (pandas\algos.c:33321)
    def left_outer_join(ndarray[int64_t] left, ndarray[int64_t] right,
ValueError: Buffer dtype mismatch, expected 'int64_t' but got 'long'

======================================================================
ERROR: test_join_non_unique (pandas.tests.indexes.test_range.TestRangeIndex)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "C:\Users\conda\Documents\pandas3.5\pandas\tests\indexes\test_range.py", line 524, in test_join_non_unique
    res, lidx, ridx = self.index.join(other, return_indexers=True)
  File "C:\Users\conda\Documents\pandas3.5\pandas\indexes\range.py", line 435, in join
    return super(RangeIndex, self).join(other, how, level, return_indexers)
  File "C:\Users\conda\Documents\pandas3.5\pandas\indexes\base.py", line 2642, in join
    return_indexers=return_indexers)
  File "C:\Users\conda\Documents\pandas3.5\pandas\indexes\base.py", line 2720, in _join_non_unique
    sort=True)
  File "C:\Users\conda\Documents\pandas3.5\pandas\tools\merge.py", line 909, in _get_join_indexers
    return join_func(lkey, rkey, count, **kwargs)
  File "pandas\src\join.pyx", line 51, in pandas.algos.left_outer_join (pandas\algos.c:33321)
    def left_outer_join(ndarray[int64_t] left, ndarray[int64_t] right,
ValueError: Buffer dtype mismatch, expected 'int64_t' but got 'long'

----------------------------------------------------------------------
Ran 796 tests in 10.849s

FAILED (SKIP=1, errors=2)
```

OK, I think I've found the problem but need some time to test it on windows.

@jreback The fix was straightforward and it should be ok now.

However, I'm getting these two errors on windows (64bit)  - also on the master branch, so they're independent of this PR. Either I messed up the windows setup or it's not being tested thoroughly.

```
======================================================================
FAIL: test_next (pandas.io.tests.test_common.TestMMapWrapper)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "D:\GitHub\pandas-pijucha\pandas\io\tests\test_common.py", line 141, in t
est_next
    self.assertEqual(next_line, line)
AssertionError: 'a,b,c\r\n' != 'a,b,c\n'
- a,b,c
?      -
+ a,b,c

======================================================================
FAIL: test_alignment_non_pandas (pandas.tests.frame.test_operators.TestDataFrame
Operators)
----------------------------------------------------------------------
Traceback (most recent call last):
  File "D:\GitHub\pandas-pijucha\pandas\tests\frame\test_operators.py", line 120
2, in test_alignment_non_pandas
    Series([1, 2, 3], index=df.index))
  File "D:\GitHub\pandas-pijucha\pandas\util\testing.py", line 1157, in assert_s
eries_equal
    assert_attr_equal('dtype', left, right)
  File "D:\GitHub\pandas-pijucha\pandas\util\testing.py", line 882, in assert_at
tr_equal
    left_attr, right_attr)
  File "D:\GitHub\pandas-pijucha\pandas\util\testing.py", line 1021, in raise_as
sert_detail
    raise AssertionError(msg)
AssertionError: Attributes are different

Attribute "dtype" are different
[left]:  int32
[right]: int64None
```

2nd is already fixed
make sure u r rebased
first was fixed a while back as well 

Ah, then it's probably ok. I tested 0.18.1+202.g0a70b5f on windows.
(This commit is already rebased to the current master. I'll check on windows in a minute.)

Yes, everything is all right.
The second error is fixed, and the first one was apparently due to my git `autocrlf` config.

is #13432 completely closed by this? if not pls make checkboxes in the top (and tick off the things that are done and leave open things that are not).

thanks @pijucha pretty awesome!

@jreback Thanks.

As for #13432, the issues with `difference` and `symmetric_difference` are solved. But `union` and `intersection` are still open. I'll comment there soon.

thanks!

@pijucha this is failing on windows / py2.7 (3 is clean), and only windows: https://ci.appveyor.com/project/jreback/pandas-465/build/1.0.762/job/ghokkwmadwog983y

not sure what is going on

@jreback
This is strange. It's not windows because I'm getting it now on linux (py2.7, numpy 1.11.0). I guess travis tests mostly older numpies and I missed it too.

According to [test_categorical.py](https://github.com/pydata/pandas/blob/master/pandas/tests/test_categorical.py#L104-L112), numpy (>= 1.10) should sort mixed int-datetime array. But it doesn't:

``` python
In [3]: arr = np.array([1, 2, datetime.now(), 0, 3], dtype='O')

In [4]: np.sort(arr)
/home/users/piotr/workspace/pandas-pijucha/pandas_dev_python2/lib/python2.7/site-packages/numpy/core/fromnumeric.py:825: RuntimeWarning: tp_compare didn't return -1 or -2 for exception
  a.sort(axis, kind, order)
Out[4]: array([1, 2, datetime.datetime(2016, 7, 19, 9, 49, 28, 214675), 0, 3], dtype=object)

In [6]: np.__version__
Out[6]: '1.11.0'
```

Ipython probably interferes here because in pure python2.7 I'm getting 

```
TypeError: can't compare datetime.datetime to int
```

In the old code in `factorize`, there was a list comprehension similar to this:

``` python
ordered = [np.sort(np.array([e for e in arr if f(e)], dtype=object))
           for f in [lambda x: True, lambda x: False]]
```

I haven't yet caught it precisely but it looks as if it sometimes swallowed an exception. (New code in `safe_sort` is simpler - sorts each of the two arrays separately, but still with `np.sort`.)

It looks to me that `Categorical.from_array(arr, ordered=True)` should always raise now. And maybe `test_constructor_unsortable` from `test_categorical.py` needs to be rewritten. (I'll check later in the evening if it works.)

ok can u make a new issue about this? (pretty much copy your above comment(

Sure, i will.