0
\$\begingroup\$

I am writing a triple for loop in Python. Since the data set is larger, it takes more than 1.5 hours to finish. Is there any fast way to avoid the loop?

idx = []
for key, value in bid_img.iteritems():
    for v in value:
        loc = 0
        for pid in pid_lst:
            loc += 1
            if v == pid:
                idx.append(loc)

What I have:

  1. bid_img a dictionary that contain multiple values per key.
  2. pid_lst a list.

I want to index items for values in dic, if they match with list provided, then store them in idx and loc for index.

Sample input:

bid_img = {'123': ['4123','12312','1231234'], '2312':['413','112','12334']}; 

Sample output:

idx = [5, 11,62, 32]
  1. The input is larger than \$10^6\$.
  2. The order of output is very important; I want the exact order.
  3. I want to find the index or location (for each value in dict) in list pid_lst.
\$\endgroup\$
4
  • 2
    \$\begingroup\$ As we all want to make our code more efficient or improve it in one way or another, try to write a title that summarizes what your code does, not what you want to get out of a review. \$\endgroup\$
    – Jamal
    Apr 9, 2016 at 20:49
  • \$\begingroup\$ Thanks! Does my summarization meet the community standard? Anything I can improve? \$\endgroup\$ Apr 9, 2016 at 20:53
  • 3
    \$\begingroup\$ But big_img is a dictionary, and iteritems() on a dictionary doesn't guarantee any particular order. Can you please explain your motivation further? \$\endgroup\$ Apr 9, 2016 at 22:10
  • \$\begingroup\$ Are the values in the bid_img dictionary sorted? And do you care about duplicates? If the values are sorted using binary search to find the values of pid_lst in the values array could be faster than doing a linear search through both arrays. \$\endgroup\$
    – Pitt
    Apr 10, 2016 at 1:27

1 Answer 1

2
\$\begingroup\$

First, the outer loop can be optimised. You're using

for key, value in bid_img.iteritems():

But key is unused. Suggestion:

for value in bid_img.itervalues():

The inner loop can be optimised as well:

    loc = 0
    for pid in pid_lst:
        loc += 1
        if v == pid:
            idx.append(loc)

Suggestion:

    for loc, pid in enumerate(pid_lst, start=1):
        if v == pid:
            idx.append(loc)

The repeated calls to idx.append can be costly. Why not:

    idx.extend(loc for loc, pid in enumerate(pid_lst, start=1) if v == pid)

(Hope I didn't make any typo's, typing from my phone)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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