0

My program reads 4.2 million unsigned integers into an array (pulses) from a binary file using array.fromfile(). It then iterates over these integers and appends them into the appropriate list position (zones) based on a modulus operation. Currently the loop below takes ~2 seconds, but I'm hoping it can be done faster. I have spent hours trying different numpy approaches, some of which ended up being slower. I have clocked the various functions and this is definitely the bottleneck. Any ideas? 

        for idx,val in enumerate(pulses):
            if (idx + 1)%nZones == 0 and idx != 0:
                zones[zone].append(val)            
                zone = 0
            else:
                zones[zone].append(val)
                zone += 1

Ex: There are 200 zones, pulse 1 goes to zone 1, pulse 2 to zone 2, etc until we get to 200th pulse, and pulse 201 goes to zone 1.

scald
  • 729
  • 1
  • 7
  • 10
  • Have you tried preallocating the lists? Explained for example here: http://stackoverflow.com/questions/311775/python-create-a-list-with-initial-capacity/5533598#5533598 – BartoszKP Oct 19 '13 at 16:26
  • Just a guess, but maybe iterate over the zones instead of the pulses, to eliminate the plus and the mod. – Tzach Oct 19 '13 at 16:36
  • @BartoszKP: The master "zones" list is preallocated, but are you thinking preallocate the individual lists within it? So if each zone has 24,000 pulses, preallocate and then set on the key vs appending? – scald Oct 19 '13 at 16:36
  • @scald Yes. Although the link says that the difference might be 1/1000 th of a millisecond for million iterations it should become significant. You don't have to set on key - just insert into subsequent indices (well an index is some kind of key I guess). – BartoszKP Oct 19 '13 at 16:39
  • 1
    I'm not quite on it today but can't you avoid the looping by reshaping `pulses` to have shape `(nZones, something)` and then create your list of lists from that? – YXD Oct 19 '13 at 16:43
  • @MrE: yeah, I think it's basically `pulses.reshape(-1,200).T` (or the other way 'round) with some possible padding. You want to write it up? – DSM Oct 19 '13 at 16:46
  • @DSM I think your comment is as good an answer as possible without seeing the input :) You should post it below – YXD Oct 19 '13 at 16:49

4 Answers4

2

It appears that you are effectively splitting your longer signal into equal-length chunks. A different way of thinking about this is reshaping your vector into an array.

On my machine that approach is three orders of magnitude faster (using iPython's cell magics):

Setup:

pulses = random_integers(0, 1000, 4.2e6)
nZones = 200
zones = [[] for i in range(nZones)]

Your method for reference

%%timeit
zone = 0
for idx,val in enumerate(pulses):
    if (idx + 1)%nZones == 0 and idx != 0:
        zones[zone].append(val)            
        zone = 0
    else:
        zones[zone].append(val)
        zone += 1

1 loops, best of 3: 1.63 s per loop

%%timeit
zones = reshape(pulses, (len(pulses)/nZones, nZones)).T

100000 loops, best of 3: 2.04 µs per loop

If you really want a list of lists you pay quite a bit for the conversion. You probably really don't need a list of lists if you're concerned about speed.

%%timeit
zones = reshape(pulses, (len(pulses)/nZones, nZones)).T.tolist()

1 loops, best of 3: 102 ms per loop

chthonicdaemon
  • 19,180
  • 2
  • 52
  • 66
  • Works great! You're right, I really don't need a list of lists, I can still get the pulses by zone index which is what the end result calls for. – scald Oct 19 '13 at 17:06
1

np.reshape is fast, but it doesn't result in lists.

Some setup:

N_ZONES = 200
MAX_VALUE = 100
N_VALUES = 4.2e6 + np.random.randint(N_ZONES) # Ensure a random number

# Random set of ~4.2 million values
pulses = np.random.randint(0, MAX_VALUE, (N_VALUES))

Since we don't know that the total number of pules is divisible by 200, we may need to pad the array.

# Pad pulses with negatives to have a size divisible by 200
PADDING = N_ZONES - pulses.shape[0] % N_ZONES
pulses_padded = np.hstack((pulses, np.zeros(PADDING)-1))

# Reshape
zones = pulses_padded.reshape((-1, N_ZONES)).T

The last row will have PADDING negative values at the end of it

You can then convert back to a list of lists, though this is slow

# Convert back to lists (though this is slow)
zone_lists = [ [value for value in row if value >= 0] for row in zones]
Geoff
  • 7,935
  • 3
  • 35
  • 43
  • 1
    (1) Doesn't this assign the values in the opposite direction? `pulses[0]` and `pulses[1]` both go into `zone_lists[0]`. (2) That last conversion to lists, if needed, would probably be faster as `zone_lists = [ row[row >= 0].tolist() for row in zones]` or something. – DSM Oct 19 '13 at 17:02
  • Thanks @DSM. You're right on both suggestions, though the conversion to lists should probably be done all-but-last column, then the last column separately for a real speed-up. – Geoff Oct 21 '13 at 15:55
0

FWIW, here's a pure Python version (show with smaller values for testing). The pulse values used are a progression starting with 1 for identification purposes.

from itertools import cycle, izip
from math import ceil

nPulses = 100
pulses = range(1, nPulses+1)
nZones = 20
nZoneSize = int( ceil(len(pulses) / float(nZones)) )
zones = [[None for _ in xrange(nZoneSize)] for z in xrange(1, nZones+1)]

for i, (p, z) in enumerate(izip(pulses, cycle(zones))):
    z[i / nZones] = p

for zone in zones:
    print zone

Output: 

[1, 21, 41, 61, 81]  
[2, 22, 42, 62, 82]  
[3, 23, 43, 63, 83]  
[4, 24, 44, 64, 84]  
[5, 25, 45, 65, 85]  
[6, 26, 46, 66, 86]  
[7, 27, 47, 67, 87]  
[8, 28, 48, 68, 88]  
[9, 29, 49, 69, 89]  
[10, 30, 50, 70, 90] 
[11, 31, 51, 71, 91] 
[12, 32, 52, 72, 92] 
[13, 33, 53, 73, 93] 
[14, 34, 54, 74, 94] 
[15, 35, 55, 75, 95] 
[16, 36, 56, 76, 96] 
[17, 37, 57, 77, 97] 
[18, 38, 58, 78, 98] 
[19, 39, 59, 79, 99] 
[20, 40, 60, 80, 100]
martineau
  • 119,623
  • 25
  • 170
  • 301
0

Try:

for idx,val in enumerate(pulses):
    zones[zone%nZones].append(val)
    zone+=1
Steve Barnes
  • 27,618
  • 6
  • 63
  • 73