Alas, it would appear the whole idea was a washout.
Preliminary investigation (What is faster: sparse vector or a dictionary? - #12 by PetrKryslUCSD) seemed to indicate that I could get a speedup by using dictionaries, yet in actual application they are much slower than the original approach.