Building a dict/list of lists

Question

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 (ax). A database feature index has associated with it a region id (rid), region feature index (fx), feature score (fs), and feature rank (fk). 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 (rid2_fm, rid2_fs, and rid2_fk)

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 (qfx, fx, fs, and 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.

Answer 1

What would you think of

match_iter = izip(*valid_lists)
rid2 = defaultdict(list)
for qfx, rid, fx, fs, fk in match_iter:
    rid2[rid].append(qfx, fx, fs, fk)

Seems like that might cut the time in the final loop by almost 50%. The extraction from match_iter doesn't change, so it will take the same amount of time. The append will take about the same amount of time as one of the appends you're already doing. Since two appends will be eliminated, I think the time they're taking will go away.