3
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Considering that this is a code review site, I thinks it's worth mentioning that your code is really hard to read, largely due to naming. The first line has qrid and qrid2_nns, for example. Further, it's not runnable and thus not testable, and the types of most things are unknown. A short, runnable sample of the overall algorithm is going to do wonders with getting people to come up with alternate strategies. \$\endgroup\$ – Veedrac Apr 17 '14 at 0:41
  • \$\begingroup\$ As a consideration, sorting match_iter by rid and then grouping it is likely to allow faster methods of creating the lists. Alternatively, consider replacing the three defaultdicts with a single one (of tuples of 3 lists) to remove the number of lookups and misses. It's hard to know much more without knowing what qfx2_[qfx2_valid] does and returns. \$\endgroup\$ – Veedrac Apr 17 '14 at 0:47
  • \$\begingroup\$ @Veedrac, sorting by rid is a great idea. Exactly the kind of thing that I'm looking for. Also, I know the code is hard to read, but its in a pretty deep part of an algorithm, and the names are pretty standardized. as for qfx2_, it is just a temporary numpy array (standing in for each qfx2_qfx, qfx2_rid, qfx2_fx, qfx2_fs, and qfx2_k) which lets me not write out qfx2_qfx[qfx2_valid], qfx2_rid[qfx2_valid] over and over. qfx2_valid is just a numpy array of booleans. \$\endgroup\$ – Erotemic Apr 17 '14 at 15:16
  • \$\begingroup\$ My point was more about making it easy for codereview to help than changing the source. \$\endgroup\$ – Veedrac Apr 17 '14 at 19:14
  • \$\begingroup\$ If you are looking for a full answer, consider shortening your snippet to the core issue(s), rename variables to friendly names and omit any details that shouldn't matter in the answer. \$\endgroup\$ – ojdo Apr 29 '14 at 13:57
1
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.