I have code which is matching features within regions. The first thing it does it matches features from one region to an entire database of region features.
I have a mapping from query feature index (
qfx) into database feature index (
A database feature index has associated with it a region id (
rid), region feature index (
fx), feature score (
fs), and feature rank (
There is also a flag marking each of those mappings as valid or invalid.
The problem is that I want to go from this mapping of query_feature_index-to-database_feature_index (
qfx2_ax) into a mapping from region_index-to-feature_match (
I have the following code which does this (cleaned up just a little bit for clarity). On the left hand side is the rough percentage of time each step takes. The bulk of the time seems to be eaten up by appending to the lists in the default dictionaries.
0.0 for qrid in qrid2_nns.iterkeys(): 0.0 (qfx2_ax, _) = qrid2_nns[qrid] 0.0 (qfx2_fs, qfx2_valid) = qrid2_nnfilt[qrid] 0.0 nQKpts = len(qfx2_ax) # Build feature matches 0.0 qfx2_nnax = qfx2_ax[:, 0:K] 0.4 qfx2_rid = ax2_rid[qfx2_nnax] 0.5 qfx2_fx = ax2_fx[qfx2_nnax] 0.2 qfx2_qfx = np.tile(np.arange(nQKpts), (K, 1)).T 0.1 qfx2_k = np.tile(np.arange(K), (nQKpts, 1)) # Pack valid feature matches into an interator 0.4 valid_lists = [qfx2_[qfx2_valid] for qfx2_ in (qfx2_qfx, qfx2_rid, qfx2_fx, qfx2_fs, qfx2_k,)] 0.0 match_iter = izip(*valid_lists) 0.0 rid2_fm = defaultdict(list) 0.0 rid2_fs = defaultdict(list) 0.0 rid2_fk = defaultdict(list) # This creates the mapping I want. Can it go faster? 19.3 for qfx, rid, fx, fs, fk in match_iter: 17.2 rid2_fm[rid].append((qfx, fx)) 17.0 rid2_fs[rid].append(fs) 16.2 rid2_fk[rid].append(fk)
My gut feeling is that I could pass over the data twice, first counting the number of entries per region, then allocating lists of that size, and then populating them, but I'm afraid that indexing into python lists might take a comparable amount of time.
Then I was thinking I could do it with list comprehensions and build a list of (
fk), but then I'd have to unpack them, and I'm unsure about how long that will take.
It seems to me that I can't get much better than this, but maybe someone out there knows something I don't. Maybe there is a numpy routine I'm unaware of?
I'm more looking for guidance and insights than anything else before I start coding up alternatives.