1
\$\begingroup\$

I was wondering if there was a better way of writing this...

I have a CSV file (about 6640 lines). After reading through the file, the values for the DFN_Network are stored in a list. After that the values of the DFN_Network are matched with their corresponding existence in the values of the dictionary all_dictionary. After that I create a new dictionary that matches k (line number) and the list of numbers where is occurs in the all_dictionary.

h is used to make the exact match for the number case.

len(DFN_Network) = 2720

len(all_dictionary) = keys (1000)

len(all_dictionary) = values (6000)

Currently to iterate through the above it takes 192secs. Note this is only for 1,000 keys, I am planning to have over 25,000 keys.

        while k in range(len(DFN_Network)):
            listed = []
            for q in range(len(all_dictionary.values())):
                for w in range(len(all_dictionary.values()[q])):
                    h = '^' + str(k) + '$'
                    match = re.search(h, (all_dictionary.values()[q][w]))
                    if match:
                        abc = all_dictionary.keys()[q]
                        listed.append(abc)
            diction[k] = listed
            k += 1

DFN_Network = ['1', '2', '3', '4', '5', '6', '7', '8', '9', '10', '11', '12', '13', '14', '15', '16', '17', '18', '19', '20', '21', '22', '23', '24', '25', '26', '27', '28', '29', '30', '31', '32', '33', '34', '35', '36', '37', '38', '39', '40', '41', '42', '43', '44', '45', '46', '47', '48', '49', '50', '51', '52', '53', '54', '55', '56', '57', '58', '59', '60', '61', '62', '63', '64', '65', '66', '67', '68', '69', '70', '71', '72', '73', '74', '75', '76', '77', '78', '79', '80', '81', '82', '83', '84']

all_dictionary = {'24': ['77', '78', '23', '57'], '25': ['33', '79', '80', '6', '81'], '26': ['43', '59', '26', '72'], '27': ['34', '81', '9', '74'], '20': ['54', '71', '24', '70', '48', '67'], '21': ['20', '39', '44', '72', '31', '73', '74', '8'], '22': ['68', '25', '71', '53'], '23': ['15', '76', '75', '4', '69'], '28': ['76', '14', '45', '40', '82'], '29': ['11', '84', '83', '61'], '1': ['2', '3', '4', '1'], '3': ['10', '11', '12', '13'], '2': ['6', '5', '7', '8', '9'], '5': ['19', '20', '7', '18'], '4': ['14', '15', '16', '17'], '7': ['26', '27', '28', '29', '30', '31'], '6': ['22', '23', '21', '24', '25'], '9': ['39', '19', '38', '37', '40', '41'], '8': ['33', '34', '35', '36', '32'], '11': ['13', '47', '48', '46'], '10': ['17', '42', '43', '44', '41', '45'], '13': ['52', '53', '54', '55', '28'], '12': ['36', '49', '50', '51'], '15': ['27', '59', '42', '60'], '14': ['2', '56', '57', '22', '58'], '17': ['51', '65', '62', '64'], '16': ['12', '61', '62', '63', '47'], '19': ['68', '52', '60', '16', '69', '3', '58'], '18': ['50', '66', '29', '55', '67', '63', '65'], '30': ['66', '49', '35', '73', '30']}

diction = {0: [], 1: ['1'], 2: ['1', '14'], 3: ['1', '19'], 4: ['23', '1'], 5: ['2'], 6: ['25', '2'], 7: ['2', '5'], 8: ['21', '2'], 9: ['27', '2'], 10: ['3'], 11: ['29', '3'], 12: ['3', '16'], 13: ['3', '11'], 14: ['28', '4'], 15: ['23', '4'], 16: ['4', '19'], 17: ['4', '10'], 18: ['5'], 19: ['5', '9'], 20: ['21', '5'], 21: ['6'], 22: ['6', '14'], 23: ['24', '6'], 24: ['20', '6'], 25: ['22', '6'], 26: ['26', '7'], 27: ['7', '15'], 28: ['7', '13'], 29: ['7', '18'], 30: ['7', '30'], 31: ['21', '7'], 32: ['8'], 33: ['25', '8'], 34: ['27', '8'], 35: ['8', '30'], 36: ['8', '12'], 37: ['9'], 38: ['9'], 39: ['21', '9'], 40: ['28', '9'], 41: ['9', '10'], 42: ['10', '15'], 43: ['26', '10'], 44: ['21', '10'], 45: ['28', '10'], 46: ['11'], 47: ['11', '16'], 48: ['20', '11'], 49: ['12', '30'], 50: ['12', '18'], 51: ['12', '17'], 52: ['13', '19'], 53: ['22', '13'], 54: ['20', '13'], 55: ['13', '18'], 56: ['14'], 57: ['24', '14'], 58: ['14', '19'], 59: ['26', '15'], 60: ['15', '19'], 61: ['29', '16'], 62: ['17', '16'], 63: ['16', '18'], 64: ['17'], 65: ['17', '18'], 66: ['18', '30'], 67: ['20', '18'], 68: ['22', '19'], 69: ['23', '19'], 70: ['20'], 71: ['20', '22'], 72: ['26', '21'], 73: ['21', '30'], 74: ['27', '21'], 75: ['23'], 76: ['23', '28'], 77: ['24'], 78: ['24'], 79: ['25'], 80: ['25'], 81: ['25', '27'], 82: ['28'], 83: ['29']}

So lets take diction.key() = 79 exists in all_dictionary.itemvalues() for key() = 25 ONLY.

So lets take diction.key() = 81 exists in all_dictionary.itemvalues() for key() = 25 & 27 ONLY.

ADDITIONAL DESCRIPTION: Real situation explanation:

I have a rectangle, this rectangle is divided into small polygons of 6 sides each (Keys in All_dictionary)

These polygons are divided by lines (DFN_Network)

I am trying to match the line shared between the polygons {DFN_Network : [Keys in All_dictionary]}

Hence, every line will be an entry in the diction. And i need it this way because later on in the code, i match the Keys in All_dictionary to their corresponding “names”

\$\endgroup\$
  • 3
    \$\begingroup\$ So that we can give you better advice, I suggest that you post an entire working program as well as some sample input. It's harder to tell what's going on based on just this excerpt. \$\endgroup\$ – 200_success Apr 15 '16 at 20:09
  • \$\begingroup\$ @200_success: Added some sample data, hope they make sense. \$\endgroup\$ – Aly Abdelaziz Apr 17 '16 at 12:58
  • \$\begingroup\$ Thanks for everyone, the improvement in time is impressive... I think the initial iteration was too lengthy as it reads through the entire dictionary more then once. \$\endgroup\$ – Aly Abdelaziz Apr 18 '16 at 20:02
1
\$\begingroup\$

Your original algorithm is very inefficient and also error prone as mentioned with dictionaries being unordered and slow when converting keys and values to lists. Though I would not go this approach (see further down for a better example), here are some things about your current code.

First, you are getting all_dictionary.values() many times! Once for each DNF_Network iteration times the number of values in the dictionary times the number of numbers in the value list!!! WOW! This is unnecessary and should have been moved outside loops, only retrieved once. The same thing goes for all_dictionary.keys(), every time a match is found, it will have to generate a new list of keys!

Next you are regular expressions which are slower than string comparisons. I don't see you needing this in your example.

In your description, you said you were using the values read from a file into a list DNF_Network but I do not see in your example code you using any value from that list. All I see you using the index of the DNF_Network list and not the the value at that index. If the DNF_Network list has values [2,5,8,20], then you would only be looking in all_dictionary for 0,1,2,3. So something doesn't make sense there.

Here is what I would do which should be simple and efficient. Though if performance is important, you should profile the code to see where the bottlenecks are.

# fill a default dictionary with keys from DNF_Network with empty lists as values. We could use collections defaultdict but this is to ensure that the dictionary has all values represented from DNF_Network in case all_dictionary does not contain it.
DFN_network_dict = dict([(i,[]) for i in DFN_Network])
for key, value in all_dictionary.iteritems(): # for Python 2.x otherwise use .items
    for v in value:
        try:
            DFN_network_dict[v].append(key)
        except KeyError:
            # looks like this value isn't in DFN_Network, ignore it
            pass
\$\endgroup\$
  • \$\begingroup\$ @ scottiedoo, thanks. I do not expect an error as the numbering is 1 through to the end so all numbers are guaranteed to be matched. \$\endgroup\$ – Aly Abdelaziz Apr 18 '16 at 17:10
  • \$\begingroup\$ The current code does not match the DFN_Network to its corresponding key, but rather iterates through the entire list, outputting the keys equivalent to the number of items() in the all_dictionary. {'56': ['11', '11', '11', '11', '11', '10', '10', '10', '10', '10', '10', '13', '13', '13', '13', '13', '13', '12', '12', '12', '12', '12', '15', ...],....} \$\endgroup\$ – Aly Abdelaziz Apr 18 '16 at 17:12
  • \$\begingroup\$ Strange, I don't think Python's dictionary was handling the default list value from dict.fromkeys. So I changed it to a list comprehension which seems to fix the issue. Try it gain. \$\endgroup\$ – scottiedoo Apr 18 '16 at 17:45
  • \$\begingroup\$ This seems to do the trick. Its a much better improvement in terms of time then @zondo. \$\endgroup\$ – Aly Abdelaziz Apr 18 '16 at 19:59
  • \$\begingroup\$ For 1000 points.... Time is about 0.05 secs \$\endgroup\$ – Aly Abdelaziz Apr 18 '16 at 20:00
1
\$\begingroup\$

In Python 3, range(), .values(), and .keys() return iterators, but in Python 2, they don't. In Python 2, you should use xrange(), .itervalues() and .iterkeys().

Instead of getting the indices and then accessing the key and value at that index, use enumerate().

Your naming is not ideal. I need to look back at previous lines to know what k, q, w, and h are.

You don't need regular expressions. When you use the pattern ^SOMETEXT$ where ^ and $ are the only special characters used, you should just check the string's equality with SOMETEXT. Since you are checking equality with each item, use the in operator.

Order obviously doesn't matter because you are iterating through a dictionary. In that case, use a set instead of a list.

Your code converted to my style:

for index in xrange(len(DFN_Network)):
    matches = set()
    for key, value in all_dictionary.iteritems():
        if str(index) in value:
            matches.add(key)
    diction[index] = matches

You could even use a set comprehension:

for index in xrange(len(DFN_Network)):
    diction[index] = {key for key, value in all_dictionary.iteritems()
                      if str(index) in value}
\$\endgroup\$
  • \$\begingroup\$ thanks for the detailed reply. For the naming, i understand, it just helps me understand which part of the code i am in. regular expression: if i use the 'in' it searches the complete string, so if it looks for '1' it would also return '12', '13', '61', and so on. I only wishes it to return 1. Currently i do not have access to my computer, i will try your block code and let you know. Thanks. \$\endgroup\$ – Aly Abdelaziz Apr 17 '16 at 13:00
  • \$\begingroup\$ @AlyAbdelaziz: The difference is that value is a list, not a string. 't' in ['a', 'this'] will not match, but 't' in ['a', 't', 'his'] will. \$\endgroup\$ – zondo Apr 17 '16 at 13:30
  • \$\begingroup\$ Thanks @zondo for the reply, it Works. For 1000 points.... Time is about 0.95 secs. I chose the other answer as it is faster. But thank you. \$\endgroup\$ – Aly Abdelaziz Apr 18 '16 at 20:00

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.