API/ENH: union Categorical
I was looking into #10153 (parsing Categoricals directly) and one thing that seems to be needed
for that is a good way to combine Categoricals.  That part alone is complicated enough
so I decided to do a separate PR for it.

This adds a `union_categoricals` function that takes a list of (identical dtyped, unordered)
and combines them without doing a full factorization again, unioning the categories.

This seems like it might be generically useful, does it belong the public api somewhere and/or
as a method a `Categorical`?  Maybe as on option on `concat`?

Might also be useful for dask? e.g. https://github.com/dask/dask/issues/1040, cc @mrocklin

An example timing below.  Obviously depends on the density of the categories,
but for relatively small numbers of categories, seems to generally be in 5-6x
speed up range vs concatting everything and re-categorizing.

``` python
from pandas.types.concat import union_categoricals

group1 = ['aaaaa', 'bbbbb', 'cccccc', 'ddddddd', 'eeeeeeee']
group2 = group1[3:] + ['fffffff', 'gggggggg', 'ddddddddd']

a = np.random.choice(group1, 1000000).astype('object')
b = np.random.choice(group2, 1000000).astype('object')

a_cat, b_cat = pd.Categorical(a), pd.Categorical(b)

In [10]: %timeit np.concatenate([a,b,a,b,a])
10 loops, best of 3: 82.7 ms per loop

In [12]: %timeit pd.Categorical(np.concatenate([a_cat.get_values(),b_cat.get_values(),
                                                a_cat.get_values(),b_cat.get_values(),
                                                a_cat.get_values()]))
1 loops, best of 3: 344 ms per loop

In [14]: %timeit union_categoricals([a_cat,b_cat,a_cat,b_cat,a_cat])
10 loops, best of 3:  40.9 ms per loop
```

see #9927
 came out of this post: http://stackoverflow.com/questions/29709918/pandas-and-category-replacement

and originally some discussions with @mrocklin
 ## [Current coverage](https://codecov.io/gh/pydata/pandas/pull/13361?src=pr) is **84.23%**

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

``` diff
@@             master     #13361   diff @@
==========================================
  Files           138        138          
  Lines         50724      50742    +18   
  Methods           0          0          
  Messages          0          0          
  Branches          0          0          
==========================================
+ Hits          42726      42744    +18   
  Misses         7998       7998          
  Partials          0          0          
```

> Powered by [Codecov](https://codecov.io?src=pr). Last updated by [103f7d3...ccaeb76](https://codecov.io/gh/pydata/pandas/compare/103f7d31e1b850e532ed85a4b53ef222d1271c54...ccaeb76fbd6a99eb54bc855750abc6059a9ecba4)
 Yeah, I'm definitely guilty of mostly thinking of Categoricals as a "memory efficient string" type.

If I understand your approach in that answer correct, this is what it would look like to concat?  It's faster than re-categorizing the whole set of data, but slower than my `union_categoricals` because (I think) it has to re-hash every element (unless that's possible to avoid?), where I'm reusing the existing integer codes.

``` python
In [50]: %%timeit
    ...: 
    ...: from pandas.types.concat import _concat_categorical
    ...: 
    ...: recoded = []
    ...: new_cats = []
    ...: 
    ...: for i, c in enumerate([a_cat,b_cat,a_cat,b_cat,a_cat]):
    ...:     if i == 0:
    ...:         new_cats = c.categories
    ...:     else:
    ...:         new_cats = c.categories.union(new_cats)
    ...: 
    ...: for c in [a_cat,b_cat,a_cat,b_cat,a_cat]:
    ...:     recoded.append(pd.Categorical(c.get_values(), categories=new_cats))
    ...: 
    ...: _concat_categorical(recoded)
1 loops, best of 3: 299 ms per loop
```
 Here is a much simpler method along the lines of what I had suggested

```
In [66]: def f():
   ....:     cats = Index(a_cat.categories.tolist() + b_cat.categories.difference(a_cat.categories).tolist())
   ....:     new_b = b_cat.set_categories(cats)
   ....:     return pd.Categorical.from_codes(np.concatenate([a_cat.codes,new_b.codes]),cats)
   ....: 

In [72]: %timeit pd.Categorical(np.concatenate([a_cat.get_values(),b_cat.get_values()]))
10 loops, best of 3: 110 ms per loop

n [81]: %timeit f()
10 loops, best of 3: 63.4 ms per loop
```

These are not exactly equal as the categories in the when concatting are in a different order (as they are seen differently; this is the 'expected' result). In fact the 'result' is the correct one here. The categories of all of 1 appear before all of 2.

I am sure this could be optimized further as there are some checks in `set_categories` that are unecessary for this purpose (that is very generic).

This relies on the fact that you don't need to reset the codes in 1 at all (just extend the categories).
 In fact I assert that this could be WAY faster all  you have to do is this.

we construct a union of the new categories (order actually doesn matter, though it happens to be in order). call this `cats` (which is what I construct above)
we know that the codes are going to be 

```
In [101]: dict(zip(range(len(cats)),cats))
Out[101]: 
{0: 'aaaaa',
 1: 'bbbbb',
 2: 'cccccc',
 3: 'ddddddd',
 4: 'eeeeeeee',
 5: 'ddddddddd',
 6: 'fffffff',
 7: 'gggggggg'}
```

Each of the cats that you want to union also has this mapping (but to different codes). All you have to do it map the original code -> new code. Concat then codes and you are done. This is essentially what I am doing above, but It could be a single loop, you can even do it like this.

```
In [129]: indexer = cats.get_indexer(b_cat.categories)

In [130]: indexer
Out[130]: array([3, 5, 4, 6, 7])

In [131]: new_indexer = np.empty(len(cats),dtype=int)

In [132]: new_indexer.fill(-1)

In [133]: new_indexer[-len(b_cat.categories):] = indexer

In [134]: new_indexer
Out[134]: array([-1, -1, -1,  3,  5,  4,  6,  7])
```

Now you have a direct map from b_cat codes -> cat codes.
 Thanks.  That's actually almost exactly what I'm doing, but my code is way more complex than it needs to be because I'm directly messing with the hash tables, rather than using the index set ops and `get_indexer`.

Here's a MUCH simpler impl based on your ideas that gets to similar performance 

``` python
In [105]: to_union = [a_cat,b_cat,a_cat,b_cat,a_cat]

In [106]: %timeit union_categoricals(to_union)
10 loops, best of 3: 53.5 ms per loop

In [107]: def simple_union_cat(to_union):
     ...:     for i, c in enumerate(to_union):
     ...:         if i == 0:
     ...:             cats = c.categories
     ...:         else:
     ...:             cats = cats.union(c.categories)
     ...:     new_codes = []
     ...:     for c in to_union:
     ...:         indexer = cats.get_indexer(c.categories)
     ...:         new_codes.append(indexer.take(c.codes))
     ...:     codes = np.concatenate(new_codes)
     ...:     return pd.Categorical.from_codes(codes, cats)

In [108]: %timeit simple_union_cat(to_union)
10 loops, best of 3: 73.2 ms per loop
```
 @chris-b1 great!

I would move the API to `core/categorical.py` (or maybe `types/concat.py`)
 I think instead of .union on the categories it makes sense to append in order (so make lists out of them as Union sorts)
 this should raise if any of the cats are ordered I think
 prob want an asv for this as well.
 lgtm. pls add a whatsnew entry. I think maybe a tiny doc-mention is `categorical.rst` would be good as well.
 @jreback - I updated this with a doc note
 cc @janschulz 
@jorisvandenbossche 
 I'm actually pretty far along (well, in terms of it basically working, not necessarily docs/tests/etc) on #10153, so if you'd prefer to review it all at once, I can push those changes onto this branch.

``` python
group = ['aaaaaaaa', 'bbbbbbbb', 'cccccc', 'ddddddd', 'eeeeeeee']
df = pd.DataFrame({'a': np.random.choice(group, 10000000).astype('object'),
                   'b': np.random.choice(group, 10000000).astype('object'),
                   'c': np.random.choice(group, 10000000).astype('object')})
df.to_csv('strings.csv', index=False)


In [1]: %timeit df = pd.read_csv('strings.csv').apply(pd.Categorical);
1 loops, best of 3: 6.39 s per loop

In [2]: %timeit pd.read_csv('strings.csv', dtype='category')
1 loops, best of 3: 3.65 s per loop
```
 let's do that in a separate branch (u can do it on top of this one)
 Seems that people want Categoricals mostly as memory efficient strings :-)/:-( I like that it is not part of the categorical API but a helper function (see https://github.com/pydata/pandas/issues/9927#issuecomment-94552631).
 yeah I think people are really wanting `pd.String`, but `pd.Categorical` is working (mostly)
 Alright, updated for those comments, let me know if you see anything else.  Thanks for fastpath suggestion @janschulz, that ends up making a decent performance impact.
 @shoyer, @jreback - updated for your comments
 can u post timings?
 I also updated my comment at the top.  Hard to say if this is "good," but 8x faster than the really naive approach, so that's something.

``` python

In [10]: %timeit np.concatenate([a,b,a,b,a])
10 loops, best of 3: 82.7 ms per loop

In [12]: %timeit pd.Categorical(np.concatenate([a_cat.get_values(),b_cat.get_values(),
                                                a_cat.get_values(),b_cat.get_values(),
                                                a_cat.get_values()]))
1 loops, best of 3: 344 ms per loop

In [14]: %timeit union_categoricals([a_cat,b_cat,a_cat,b_cat,a_cat])
10 loops, best of 3:  40.9 ms per loop
```
 xref #10186. We can fix `CategoricalIndex.union` as the same after this PR.
 thanks @chris-b1 nice enhancement!
 Quick follow-up question: do we really want to encourage users importing this from `pandas.types.concat`? If we don't want to expose that implementation detail as API, we probably should export it to the main namespace.
 > Quick follow-up question: do we really want to encourage users importing this from pandas.types.concat? If we don't want to expose that implementation detail as API, we probably should export it to the main namespace.

👍 

Or `pd.Categorical.union(*cats)` or similar
 I like the class method `pd.Categorical.union(cats)`
 Why as a class method? As far as I remember we also don't encourage to use `Categorical` directly but usually as `s.astype("category")` -> `pd.union_categorical(a, b)`? [Edit] ok, this doesn't work because the functions does only take `Categorical` and not Series of type category[/]

[Edit] Or is that analog to the "constructor" `Categorical.from_codes()`, like `Categorical.from_union(*cats)`?

Another thought is that the (public) usecase for this is mainly to use categoricals as a memory efficient string type ("I don't care about the meaning of the categories, just concat them"), so I guess if ever there is a `pd.String`, this function is then mostly unneeded (the internal usecase in reading in cats directly shouldn't need a public API). From that perspective a `pandas.types.concat.union_categorical(a,b)` is also fine...

[edit]
My new favorite is `Categorical.from_union()`.

BTW: should that method take only `Categorical`s or also Series of type cat?
 actually, maybe we ought to just hijack `pd.concat`, this could be a fast-path that just calls `union_categoricals` if all of the inputs are `Categoricals` in the first place. From an API perspective it feels right, there is a little bit of added code complexity inside `Concat` though.
 so I like @janschulz `Categorical.from_union()` as well
