Match data in 1 column and count unique data in another column based on matches

given version (XL2013) and the sample data (where A is seemingly sorted Asc) then you might try switching to:

C3:
=IF($A3=$A2,$C2,SUMPRODUCT(1/COUNTIF($B3:INDEX($B:$B,MATCH($A3,$A:$A)),$B3:INDEX($B:$B,MATCH($A3,$A:$A))&"")))
copied down

the above (c/o Col A being sorted)

a) only calculates the unique number once per item A (the other A items use the previously calculated result)
b) switches from multi criteria COUNTIFS to single criteria -- this has a big impact on performance (for COUNTIFS - specifically) aside the most recent XL versions (which fix the 'bug')
c) limits the range of each COUNTIF calc such that it very small {c/o binary search based MATCH}

so, with the above changes, you should find the performance improves a fair bit when applied to a large dataset

D3 , Array formula , Copy and drag down

HTML Code: 

Thanks XLent, Bo_Ry & wk9128 Really appreciate your formula suggestions! Thanks so much!