Approximately matching strings to elements in an array

Question

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

Answer 1

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.