2
\$\begingroup\$

I have two datasets:

  1. A list containing about 4200 string elements
  2. A list containing about 119,000 string elements

I'm taking each element from list 1 and looping through each element in list 2 using the jaro-winkler algorithm to find a "good" match based on a desired confidence threshold. I know that this process will work, but it will take way too long. Does anyone have any suggestions on a better way to do this to speed the process up?

def get_jw_match(data, target):
    """Uses the jaro-winkler algorithm to match strings(names) from the   target(the set from which you want to find matches) to the data(the set for which you are trying to find matches."""
    temp_list = []
    for i, item_data in enumerate(target):
        max = 0
        temp_list.append(0)
        for j, item_target in enumerate(data):
            jw = jellyfish.jaro_winkler(item_data, item_target)
            if (jw > confidence):
                temp_list[i] = jw
    return temp_list
\$\endgroup\$

migrated from stackoverflow.com Oct 9 '15 at 16:01

This question came from our site for professional and enthusiast programmers.

  • \$\begingroup\$ If you get a match, should you break out of the inner loop? Multiple matches are overriding the same array index. \$\endgroup\$ – Brian Pendleton Sep 25 '15 at 23:13
  • \$\begingroup\$ If I get 100% match, then yes, I will break out of the loop, otherwise I must find the highest match possible. It's unlikely that I will get 100% match for most or any of the elements. \$\endgroup\$ – gatherer Sep 25 '15 at 23:19
  • \$\begingroup\$ postgresql has a pg_similarity extension that supposts this algorithm. I've never used it but I hope you find it slightly faster. \$\endgroup\$ – e4c5 Sep 25 '15 at 23:50
  • \$\begingroup\$ What kind of strings are these? Are they, for example, DNA nucleotide sequences? \$\endgroup\$ – 200_success Oct 9 '15 at 21:35
  • \$\begingroup\$ On what basis did you calculate confidence for matching strings from 2 datasets? \$\endgroup\$ – user202168 Jun 3 at 16:23
2
\$\begingroup\$

Code Style Review:

  1. Use of Redundant variables: I cannot find any use for max in your script. Remove it
  2. Better naming: jw could be better described as jw_score. Max is built_in name, don't use it.
  3. Unnecessary enumerate. You are not using index in inner loop. Remove enumerate.
  4. I am assuming confidence is global scope. Bad practice. Pass confidence value as argument. If you must use confidence as global constant, declare it as CONFIDENCE (caps indicate constant)
  5. Since you are inserting zero as initial value for temp_list there are better ways to achieve that instead of appending zero in loop.
  6. Use item_data while iterating data, and vice-versa. Your naming convention right now is confusing

Code Design Review

I am having hard time understanding what you wanted to return. Right now, if any of strings for data matches target, your temp_list will have a value for it. But it will have value for "last_matched" only.

If you only care about any good match, then as soon as any value match, break out from inner loop, and your average running time should reduce drastically:

def get_jw_match(data, target, confidence):
    """Uses the jaro-winkler algorithm to match strings(names) from the   target(the set from which you want to find matches) to the data(the set for which you are trying to find matches."""
    score_list = [0] * len(target)
    for i, item_target in enumerate(target):
        for item_data in data:
            jw_score = jellyfish.jaro_winkler(item_data, item_target)
            if (jw_score > confidence):
                score_list[i] = jw_score
                break
    return score_list

Now you would know for which elements in target you have good match, but you don't know any element in data for which you have good match. For that, instead of assigning score, you can assign index for data. Also, you can then ditch list, and use dictionaries:

def get_jw_match(data, target, confidence):
    """Uses the jaro-winkler algorithm to match strings(names) from the   target(the set from which you want to find matches) to the data(the set for which you are trying to find matches."""
    score_dict = dict()
    for i, item_target in enumerate(target):
        for j, item_data in enumerate(data):
            jw_score = jellyfish.jaro_winkler(item_data, item_target)
            if (jw_score > confidence):
                score_dict[i] = j
                break
    return score_dict

Advantage of this is that you can create reverse dict also. Which also means, that you should be able to swap inner-outer loops reducing time further. (In general, use inner loop for bigger data, when it short circuit, you save much more time)

If I think, there might be further time-reduction optimizations, but for practical purposes, this would shorten your average running time by magnitude.

\$\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.