如何使用嵌套字典使我的模糊匹配代码更高效？
How can I use nested dictionaries to make my fuzzy matching code more efficient?
我有 2 个字典列表 (dictreaders)，看起来像这样：
名字 1
[{'City' :'San Francisco', 'Name':'Suzan', 'id_number' : '1567', 'Street': 'Pearl'},
{'City' :'Boston', 'Name':'Fred', 'id_number' : '1568', 'Street': 'Pine'},
{'City' :'Chicago', 'Name':'Lizzy', 'id_number' : '1569', 'Street': 'Spruce'},
{'City' :'Denver', 'Name':'Bob', 'id_number' : '1570', 'Street': 'Spruce'}
{'City' :'Chicago', 'Name':'Bob', 'id_number' : '1571', 'Street': 'Spruce'}
{'City' :'Boston', 'Name':'Bob', 'id_number' : '1572', 'Street': 'Canyon'}
{'City' :'Boulder', 'Name':'Diana', 'id_number' : '1573', 'Street': 'Violet'}
{'City' :'Detroit', 'Name':'Bill', 'id_number' : '1574', 'Street': 'Grape'}]
和
名字2
[{'City' :'San Francisco', 'Name':'Szn', 'id_number' : '1567', 'Street': 'Pearl'},
{'City' :'Boston', 'Name':'Frd', 'id_number' : '1578', 'Street': 'Pine'},
{'City' :'Chicago', 'Name':'Lizy', 'id_number' : '1579', 'Street': 'Spruce'},
{'City' :'Denver', 'Name':'Bobby', 'id_number' : '1580', 'Street': 'Spruce'}
{'City' :'Chicago', 'Name':'Bob', 'id_number' : '1580', 'Street': 'Spruce'}
{'City' :'Boston', 'Name':'Bob', 'id_number' : '1580', 'Street': 'Walnut'}]
如果您注意到第二个块中的名称与第一个块中的名称拼写不同，但有几个几乎相同。我想使用模糊字符串匹配来匹配这些。我还想缩小到我只比较同一个城市和同一条街道上的名字的地方。目前我正在运行一个看起来像这样的 for 循环
from fuzzywuzzy import fuzz
from fuzzywuzzy import process
from itertools import izip_longest
import csv
name1_file = 'name1_file.csv'
node_file = 'name2_file.csv'
name1 = csv.DictReader(open(name1_file, 'rb'), delimiter=',', quotechar='"')
score_75_plus = []
name1_name =[]
name2_name =[]
name1_city = []
name2_city = []
name1_street = []
name2_street = []
name1_id = []
name2_id = []
for line in name1:
name2 = csv.DictReader(open(name2_file, 'rb'), delimiter=',', quotechar='"')
for line2 in name2:
if line['City'] == line2['City'] and line['Street'] == line['Street']:
partial_ratio = fuzz.partial_ratio(line['Name'], line2['Name'])
if partial_ratio > 75:
name1.append(line['Name'])
name1_city.append(line['City'])
name1_street.append(line['Street'])
name2_name.append(line2['Name'])
name2_city.append(line2['City'])
name2_street.append(line2['Street'])
score_75_plus.append(partial_ratio)
name1_id.append(line['objectid']
name2_id.append(line2['objectid']
big_test= zip(name1_name, name1_city, name1_street, name1_id, name2_name, name2_city, name2_street, name2_id, score_75_plus)
writer=csv.writer(open('big_test.csv', 'wb'))
writer.writerows(big_test)
但是，由于我的文件很大，我认为它需要相当长的时间……也许几天。我想让它更有效率，但还没有弄清楚如何去做。到目前为止，我的想法是将字典重组为嵌套字典，以减少它必须循环检查城市和街道是否相同的数据量。我正在设想这样的事情：
['San Francisco' :
{'Pearl':
{'City' :'San Francisco', 'Name':'Szn', 'id_number' : '1567', 'Street': 'Pearl'} },
'Boston' :
{'Pine':
{'City' :'Boston', 'Name':'Frd', 'id_number' : '1578', 'Street': 'Pine'},
'Canyon': {'City' :'Boston', 'Name':'Bob', 'id_number' : '1572', 'Street': 'Canyon'} },
'Chicago' :
{'Spruce':
{'City' :'Chicago', 'Name':'Lizzy', 'id_number' : '1569', 'Street': 'Spruce'},
{'City' :'Chicago', 'Name':'Bob', 'id_number' : '1571', 'Street': 'Spruce'} },
'Denver' :
{'Spruce':
{'City' :'Denver', 'Name':'Bob', 'id_number' : '1570', 'Street': 'Spruce'}},
'Boulder':
{'Violet':
{'City' :'Boulder', 'Name':'Diana', 'id_number' : '1573', 'Street': 'Violet'}},
'Detroit':
{'Grape':
{'City' :'Detroit', 'Name':'Bill', 'id_number' : '1574', 'Street': 'Grape'}}]
这只需要查看该城市中不同的城市和不同的街道来决定是否应用 fuzz.partial_ratio。我使用 defaultdict 按城市将其拆分，但无法再次将其应用于街道。
city_dictionary = defaultdict(list)
for line in name1:
city_dictionary[line['City']].append(line)
我看过这个 answer 但不明白如何实现它。
抱歉说了这么多细节，我不太确定嵌套字典是否可行，所以我想我会展示大局。
您可以做几件事：
- 不要为第一个 csv 文件中的每一行重新打开第二个文件。使用数据结构（可能是列表）来存储所有信息并在内存中使用它。
- Profile your code 查看大部分时间花在什么地方。
- 如果大部分时间花在 CPU 上，请使用
multiprocessing 模块来使用机器上的所有内核，因为这里的任务似乎是上下文无关的。
- 如果大部分时间花在读取文件上（I/O），使用
threading模块在读取文件的同时做一些处理。您可能希望将文件分成更小的块。
如果这没有帮助，我可以尝试根据您的代码添加更多内容。
编辑：
示例读取第二个文件一次，而不是重新读取第一个文件中的每一行：
# read file once before the loop
file_2_dicts = list(csv.DictReader(open(name2_file, 'rb'), delimiter=',', quotechar='"'))
for line in name1:
# remove old read and use in-memory dicts from first file
# name2 = csv.DictReader(open(name2_file, 'rb'), delimiter=',', quotechar='"')
name2 = file_2_dicts
for line2 in name2:
...
...
ncalls tottime percall cumtime percall filename:lineno(function)
4550 0.055 0.000 0.066 0.000 csv.py:100(next)
9098 0.006 0.000 0.006 0.000 csv.py:86(fieldnames)
4497409 3.845 0.000 54.221 0.000 difflib.py:154(__init__)
4497409 3.678 0.000 50.377 0.000 difflib.py:223(set_seqs)
4497409 3.471 0.000 3.471 0.000 difflib.py:235(set_seq1)
4497409 3.695 0.000 43.228 0.000 difflib.py:261(set_seq2)
4497409 29.130 0.000 39.533 0.000 difflib.py:306(__chain_b)
13356323 78.759 0.000 100.599 0.000 difflib.py:350(find_longest_match)
3123327 1.398 0.000 1.398 0.000 difflib.py:41(_calculate_ratio)
4497409 36.080 0.000 164.628 0.000 difflib.py:460(get_matching_blocks)
3123327 7.450 0.000 128.167 0.000 difflib.py:636(ratio)
7500936 1.673 0.000 1.673 0.000 difflib.py:658(<lambda>)
1374082 16.978 0.000 252.893 0.000 fuzz.py:57(partial_ratio)
1374082 1.172 0.000 1.647 0.000 utils.py:42(make_type_consistent)
3123327 2.587 0.000 4.260 0.000 {_functools.reduce}
23980904 7.633 0.000 7.633 0.000 {built-in method __new__ of type object at 0x100185f40}
4497410 6.525 0.000 16.009 0.000 {map}
1373764 0.496 0.000 0.496 0.000 {max}
32176130 3.231 0.000 3.231 0.000 {method '__contains__' of 'set' objects}
61813598 9.676 0.000 9.676 0.000 {method 'append' of 'list' objects}
72656176 7.728 0.000 7.728 0.000 {method 'get' of 'dict' objects}
13356323 5.311 0.000 5.311 0.000 {method 'pop' of 'list' objects}
33073067 4.927 0.000 4.927 0.000 {method 'setdefault' of 'dict' objects}
4497409 1.568 0.000 1.568 0.000 {method 'sort' of 'list' objects}
我有 2 个字典列表 (dictreaders)，看起来像这样：
名字 1
[{'City' :'San Francisco', 'Name':'Suzan', 'id_number' : '1567', 'Street': 'Pearl'},
{'City' :'Boston', 'Name':'Fred', 'id_number' : '1568', 'Street': 'Pine'},
{'City' :'Chicago', 'Name':'Lizzy', 'id_number' : '1569', 'Street': 'Spruce'},
{'City' :'Denver', 'Name':'Bob', 'id_number' : '1570', 'Street': 'Spruce'}
{'City' :'Chicago', 'Name':'Bob', 'id_number' : '1571', 'Street': 'Spruce'}
{'City' :'Boston', 'Name':'Bob', 'id_number' : '1572', 'Street': 'Canyon'}
{'City' :'Boulder', 'Name':'Diana', 'id_number' : '1573', 'Street': 'Violet'}
{'City' :'Detroit', 'Name':'Bill', 'id_number' : '1574', 'Street': 'Grape'}]
和
名字2
[{'City' :'San Francisco', 'Name':'Szn', 'id_number' : '1567', 'Street': 'Pearl'},
{'City' :'Boston', 'Name':'Frd', 'id_number' : '1578', 'Street': 'Pine'},
{'City' :'Chicago', 'Name':'Lizy', 'id_number' : '1579', 'Street': 'Spruce'},
{'City' :'Denver', 'Name':'Bobby', 'id_number' : '1580', 'Street': 'Spruce'}
{'City' :'Chicago', 'Name':'Bob', 'id_number' : '1580', 'Street': 'Spruce'}
{'City' :'Boston', 'Name':'Bob', 'id_number' : '1580', 'Street': 'Walnut'}]
如果您注意到第二个块中的名称与第一个块中的名称拼写不同，但有几个几乎相同。我想使用模糊字符串匹配来匹配这些。我还想缩小到我只比较同一个城市和同一条街道上的名字的地方。目前我正在运行一个看起来像这样的 for 循环
from fuzzywuzzy import fuzz
from fuzzywuzzy import process
from itertools import izip_longest
import csv
name1_file = 'name1_file.csv'
node_file = 'name2_file.csv'
name1 = csv.DictReader(open(name1_file, 'rb'), delimiter=',', quotechar='"')
score_75_plus = []
name1_name =[]
name2_name =[]
name1_city = []
name2_city = []
name1_street = []
name2_street = []
name1_id = []
name2_id = []
for line in name1:
name2 = csv.DictReader(open(name2_file, 'rb'), delimiter=',', quotechar='"')
for line2 in name2:
if line['City'] == line2['City'] and line['Street'] == line['Street']:
partial_ratio = fuzz.partial_ratio(line['Name'], line2['Name'])
if partial_ratio > 75:
name1.append(line['Name'])
name1_city.append(line['City'])
name1_street.append(line['Street'])
name2_name.append(line2['Name'])
name2_city.append(line2['City'])
name2_street.append(line2['Street'])
score_75_plus.append(partial_ratio)
name1_id.append(line['objectid']
name2_id.append(line2['objectid']
big_test= zip(name1_name, name1_city, name1_street, name1_id, name2_name, name2_city, name2_street, name2_id, score_75_plus)
writer=csv.writer(open('big_test.csv', 'wb'))
writer.writerows(big_test)
但是，由于我的文件很大，我认为它需要相当长的时间……也许几天。我想让它更有效率，但还没有弄清楚如何去做。到目前为止，我的想法是将字典重组为嵌套字典，以减少它必须循环检查城市和街道是否相同的数据量。我正在设想这样的事情：
['San Francisco' :
{'Pearl':
{'City' :'San Francisco', 'Name':'Szn', 'id_number' : '1567', 'Street': 'Pearl'} },
'Boston' :
{'Pine':
{'City' :'Boston', 'Name':'Frd', 'id_number' : '1578', 'Street': 'Pine'},
'Canyon': {'City' :'Boston', 'Name':'Bob', 'id_number' : '1572', 'Street': 'Canyon'} },
'Chicago' :
{'Spruce':
{'City' :'Chicago', 'Name':'Lizzy', 'id_number' : '1569', 'Street': 'Spruce'},
{'City' :'Chicago', 'Name':'Bob', 'id_number' : '1571', 'Street': 'Spruce'} },
'Denver' :
{'Spruce':
{'City' :'Denver', 'Name':'Bob', 'id_number' : '1570', 'Street': 'Spruce'}},
'Boulder':
{'Violet':
{'City' :'Boulder', 'Name':'Diana', 'id_number' : '1573', 'Street': 'Violet'}},
'Detroit':
{'Grape':
{'City' :'Detroit', 'Name':'Bill', 'id_number' : '1574', 'Street': 'Grape'}}]
这只需要查看该城市中不同的城市和不同的街道来决定是否应用 fuzz.partial_ratio。我使用 defaultdict 按城市将其拆分，但无法再次将其应用于街道。
city_dictionary = defaultdict(list)
for line in name1:
city_dictionary[line['City']].append(line)
我看过这个 answer 但不明白如何实现它。
抱歉说了这么多细节，我不太确定嵌套字典是否可行，所以我想我会展示大局。
您可以做几件事：
- 不要为第一个 csv 文件中的每一行重新打开第二个文件。使用数据结构（可能是列表）来存储所有信息并在内存中使用它。
- Profile your code 查看大部分时间花在什么地方。
- 如果大部分时间花在 CPU 上，请使用
multiprocessing模块来使用机器上的所有内核，因为这里的任务似乎是上下文无关的。 - 如果大部分时间花在读取文件上（I/O），使用
threading模块在读取文件的同时做一些处理。您可能希望将文件分成更小的块。
如果这没有帮助，我可以尝试根据您的代码添加更多内容。
编辑：
示例读取第二个文件一次，而不是重新读取第一个文件中的每一行：
# read file once before the loop
file_2_dicts = list(csv.DictReader(open(name2_file, 'rb'), delimiter=',', quotechar='"'))
for line in name1:
# remove old read and use in-memory dicts from first file
# name2 = csv.DictReader(open(name2_file, 'rb'), delimiter=',', quotechar='"')
name2 = file_2_dicts
for line2 in name2:
...
...
ncalls tottime percall cumtime percall filename:lineno(function)
4550 0.055 0.000 0.066 0.000 csv.py:100(next)
9098 0.006 0.000 0.006 0.000 csv.py:86(fieldnames)
4497409 3.845 0.000 54.221 0.000 difflib.py:154(__init__)
4497409 3.678 0.000 50.377 0.000 difflib.py:223(set_seqs)
4497409 3.471 0.000 3.471 0.000 difflib.py:235(set_seq1)
4497409 3.695 0.000 43.228 0.000 difflib.py:261(set_seq2)
4497409 29.130 0.000 39.533 0.000 difflib.py:306(__chain_b)
13356323 78.759 0.000 100.599 0.000 difflib.py:350(find_longest_match)
3123327 1.398 0.000 1.398 0.000 difflib.py:41(_calculate_ratio)
4497409 36.080 0.000 164.628 0.000 difflib.py:460(get_matching_blocks)
3123327 7.450 0.000 128.167 0.000 difflib.py:636(ratio)
7500936 1.673 0.000 1.673 0.000 difflib.py:658(<lambda>)
1374082 16.978 0.000 252.893 0.000 fuzz.py:57(partial_ratio)
1374082 1.172 0.000 1.647 0.000 utils.py:42(make_type_consistent)
3123327 2.587 0.000 4.260 0.000 {_functools.reduce}
23980904 7.633 0.000 7.633 0.000 {built-in method __new__ of type object at 0x100185f40}
4497410 6.525 0.000 16.009 0.000 {map}
1373764 0.496 0.000 0.496 0.000 {max}
32176130 3.231 0.000 3.231 0.000 {method '__contains__' of 'set' objects}
61813598 9.676 0.000 9.676 0.000 {method 'append' of 'list' objects}
72656176 7.728 0.000 7.728 0.000 {method 'get' of 'dict' objects}
13356323 5.311 0.000 5.311 0.000 {method 'pop' of 'list' objects}
33073067 4.927 0.000 4.927 0.000 {method 'setdefault' of 'dict' objects}
4497409 1.568 0.000 1.568 0.000 {method 'sort' of 'list' objects}