It almost always makes sense to include Tom Minka's Lightspeed toolbox (http://research.microsoft.com/en-us/um/people/minka/software...) right from the beginning.
Also perhaps Netlab (http://www1.aston.ac.uk/eas/research/groups/ncrg/resources/n...) although it is beginning to get rather dated.
You can only spend so much time optimizing on memory/CPU-times with smart data chunkings or low-dimensional representations or approximation operations. EC2 time and space is relatively cheap, but Python on a single machine with the multiprocessing module can only speed up by a multiple of < [# of Cores]...
Disclaimer: I have yet to use either, but I've heard good things.
[1] http://www.picloud.com/ [2] http://musicmachinery.com/2011/09/04/how-to-process-a-millio...