3

I am looking for an optimized tool in python to perform an array manipulation task that I find myself doing over and over. If the tool already exists, for example in numpy or pandas, I would rather implement that rather continue using my own cythonized for loop.

I have two arrays of the same length, A and B, storing some data about grouped data. The ith entry of array A tells me some property of group i; the jth entry of array B tells me how many members there are in group j; A stores floats, B stores ints. So, for definiteness, if A[5]=100.4 & B[5]=7, then group 5 has a mass equal to 100.4, and there are 7 members of that group.

My goal is to create a new array of floats, C, of length B.sum(), which is the expansion of the above dataset. So C[0:B[0]] = A[0], C[B[0]:B[1]] = A[1], and so forth. Is there an optimized solution to do this in an existing library such as pandas?

My existing solution is to initialize an empty array C, and then run a for loop over the elements of A, indexing the common elements of C as above. I have been writing and compiling the for loop in cython, for speed. But this particular operation is the single biggest bottleneck in my code, and it seems like an awfully common array manipulation when working with tabular data, so I'm wondering if there is a heavily optimized algorithm out there to do it already.

4 Answers 4

5

Numpy has repeat() for that type of thing.

Given two arrays

A = np.array([100.4,98.3,88.5])
B = np.array([7,3,10])
np.repeat(A,B)

will give you

array([ 100.4,  100.4,  100.4,  100.4,  100.4,  100.4,  100.4,   98.3,
         98.3,   98.3,   88.5,   88.5,   88.5,   88.5,   88.5,   88.5,
         88.5,   88.5,   88.5,   88.5])
5
  • 1
    This is by far the fastest solution of all proposed, about 7 times faster than a list comprehension for an array with 1e6 elements. Wow, I had no idea this kind of speed was even possible. Thanks, bob!
    – aph
    Dec 23, 2014 at 17:03
  • Good to hear. Yes, numpy is pretty amazing. Dec 23, 2014 at 17:12
  • I am pretty blown away. This numpy solution is exactly what I was looking for: one line of code so intuitive that its meaning is completely self-expressive, and a factor of ~30 speedup.
    – aph
    Dec 23, 2014 at 17:14
  • 1
    @aph, the test results you describe here and below are quite illuminating. I would upvote a self-answer that collects the data from your tests.
    – senderle
    Dec 23, 2014 at 21:35
  • agreed with @senderle, it'd be nice to see tests Dec 24, 2014 at 9:02
2
In [58]: A = [100.4, 50.0]

In [59]: B = [7, 5]

In [60]: [A[i] for i in range(len(B)) for _ in range(B[i])]
Out[60]: [100.4, 100.4, 100.4, 100.4, 100.4, 100.4, 100.4, 50.0, 50.0, 50.0, 50.0, 50.0]
5
  • Elegant solution, inspectorG4dget, but a pure python list comprehension will certainly be slower than a cythonized for loop, and what I'm optimizing for is performance, rather than lines of code.
    – aph
    Dec 23, 2014 at 14:10
  • @aph -- "A pure python list comprehension will certainly be slower than a cythonized for loop." I worry about the "certainly" in your comment. It makes me think you haven't tested. But my experience has been that python list comprehensions can be very fast for some applications, approaching c speed. You should test this solution if you haven't.
    – senderle
    Dec 23, 2014 at 14:22
  • I just tested it. For a single attribute A, you are right that a list comprehension does indeed approach the speed of cython. However, when I try to implement this solution for a large data set in which I'm aggregating more data than just A, my cython version is still a lot faster. So, suppose I have A1, A2, and A3. Then the following riff on inspectorG4dget's solution is a lot slower than my cython method: [(A1[i], A2[i], A3[i]) for i in range(len(B)) for _ in range(B[i])]
    – aph
    Dec 23, 2014 at 14:42
  • 1
    @aph: what if you zip(A1, A2, A3) as a preprocessing step? In python3, zip is an iterator, anyways, so that shouldn't require extra space Dec 23, 2014 at 14:45
  • 1
    Great idea @inspectorG4dget - zipping the A-N arrays entirely fixed the overhead in pure python I was seeing as N increased. It looks like your list comprehension coupled with zip is basically as fast as compiled cython. Nice work!
    – aph
    Dec 23, 2014 at 14:53
1

One of the possible ways to do this is to create iterator with itertools functions:

>>> A = np.array([100.4,98.3,88.5])
>>> B = np.array([7,3,10])
>>>
>>> from itertools import chain, izip, repeat
>>> res = chain(*(repeat(*x) for x in izip(A,B)))
>>> list(res)
[100.4, 100.4, 100.4, 100.4, 100.4, 100.4, 100.4,
 98.3, 98.3, 98.3,
 88.5, 88.5, 88.5, 88.5, 88.5, 88.5, 88.5, 88.5, 88.5, 88.5]

update

>>> A1 = ['A', 3, [1,2]]
>>> A2 = [len, lambda x: x * 3, sum]
>>> B = [2, 3, 4]
>>>
>>> c = chain(*(repeat((a1, a2(a1)), b) for a1, a2, b in izip(A1, A2, B)))
>>> list(c)
[('A', 1), ('A', 1),
 (3, 9), (3, 9), (3, 9),
 ([1, 2], 3), ([1, 2], 3), ([1, 2], 3), ([1, 2], 3)]

The good thing about this solution is that you don't have to actually store all this elements, you can just fetch it from the iterator

You can also use imap instead of generator:

>>> from itertools import chain, izip, repeat, imap
>>> A1 = ['A', 3, [1,2]]
>>> A2 = ['C', 4, 12]
>>> B = [2, 3, 4]
>>> for x in chain(*imap(repeat, izip(A1, A2), B)):
...     print x
... 
('A', 'C')
('A', 'C')
(3, 4)
(3, 4)
(3, 4)
([1, 2], 12)
([1, 2], 12)
([1, 2], 12)
([1, 2], 12)
4
  • Same question as the above: suppose I want the algorithm to be extensible to multiple group properties such as A1, A2, ..., AN. How would you use itertools to run this loop to include the expansion of multiple A arrays?
    – aph
    Dec 23, 2014 at 15:29
  • @aph well you can use as many A as you want, updated an answer. I've used list(c) only for purposing of showing actual data, in your application you can just fetch elements from iterator Dec 23, 2014 at 15:36
  • 1
    For len(A)=1e6, I find that the itertools solution is about three times slower than the list comprehension. The itertools syntax is also awfully hard to read in comparison. I could live with the ugly syntax if there were a performance benefit, but for this problem there doesn't seem to be.
    – aph
    Dec 23, 2014 at 16:58
  • good to know, now I'm interested too :) have to do some testing Dec 23, 2014 at 20:42
0

Ok, thanks again everyone for chiming in, this has been an exceptionally useful and instructive thread for my work. I'm back from the holidays and will now post the results of my tests, as requested by senderle - please chime in if I have not optimally coded up any of the proposed solutions.

First, here is my fake data, trading verbosity for clarity (tips welcome for making the multi-line formatting more clear):

Ngrps=int(1.e6)
grp_prop1=np.random.random(Ngrps)
grp_prop2=np.random.random(Ngrps)
grp_prop3=np.random.random(Ngrps)
grp_prop4=np.random.random(Ngrps)
grp_prop5=np.random.random(Ngrps)
grp_prop6=np.random.random(Ngrps)
grp_occupation=np.random.random_integers(0,5,size=Ngrps)

Now let's start with what I found to be the fastest algorithm, the numpy solution, which takes 0.15 seconds on my laptop, suggested by Bob Haffner

mmbr_prop1=np.repeat(grp_prop1, grp_occupation)
mmbr_prop2=np.repeat(grp_prop2, grp_occupation)
mmbr_prop3=np.repeat(grp_prop3, grp_occupation)
mmbr_prop4=np.repeat(grp_prop4, grp_occupation)
mmbr_prop5=np.repeat(grp_prop5, grp_occupation)
mmbr_prop6=np.repeat(grp_prop6, grp_occupation)

The next fastest, at 1.21 seconds, is a zipped list comprehension, suggested by inspectorG4dget

zipped_grps = zip(grp_prop1, grp_prop2, grp_prop3, grp_prop4, grp_prop5, grp_prop6)
zipped_mmbr_props = [zipped_grps[i] for i in range(len(grp_occupation)) for _ in range(grp_occupation[i])]

The act of zipping up the groups alone has over a factor of 2 speedup. When I do not zip up the group data, the list comprehension solution takes 2.71 seconds:

z=[(grp_prop1[i], grp_prop2[i], grp_prop3[i], grp_prop4[i], grp_prop5[i], grp_prop6[i]) for i in range(len(grp_occupation)) for _ in range(grp_occupation[i])]

The itertools solution suggested by Roman Pekar takes 2.4 seconds:

zipped_grps = izip(grp_prop1, grp_prop2, grp_prop3, grp_prop4, grp_prop5, grp_prop6, grp_occupation)
c = chain(*(repeat((p1, p2, p3, p4, p5, p6), n) for p1, p2, p3, p4, p5, p6, n in zipped_grps))

Finally, the for loop I had originally written takes 4.8 seconds:

Ntot_mbrs = grp_occupation.sum()
data=np.zeros(Ntot_mbrs*6).reshape(6, Ntot_mbrs)
first_index=0
for i in range(len(grp_occupation)):
    data[0][first_index:first_index+grp_occupation[i]] = grp_prop1[i]
    data[1][first_index:first_index+grp_occupation[i]] = grp_prop2[i]
    data[2][first_index:first_index+grp_occupation[i]] = grp_prop3[i]
    data[3][first_index:first_index+grp_occupation[i]] = grp_prop4[i]
    data[4][first_index:first_index+grp_occupation[i]] = grp_prop5[i]
    data[5][first_index:first_index+grp_occupation[i]] = grp_prop6[i]
    first_index += grp_occupation[i]

So, because of the suggestions made in this thread, I have sped up my code by over a factor of 30. Many thanks, everyone!

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.