算法并测试对比进行了性能分析(查找效率)"/>
python散列表实现查找，使用了多种算法并测试对比进行了性能分析(查找效率)
published: true
date: 2022-1-22
tags: ‘算法与数据结构’
散列表实现查找
本章是填补之前文章的坑，对哈希算法进行了实现，使用了平方取中法/除留余数法进行哈希映射，使用开放地址与公共溢出区解决冲突，同时对不同方法进行了性能分析对比，最后进行了总结。
可以转载，但请声明源链接：文章源链接justin3go(有些latex公式某些平台不能渲染可查看这个网站)
Library
import pandas as pd
import numpy as np
import time
读取数据
df = pd.read_excel('重庆市印刷和记录媒介复制业754.xlsx')
df.dropna(axis=0, how='any') # 去除非数
print("表长为：", len(df))
df.head()
表长为： 75
| ID | 企业名称 | 电话 | 企业地址 | |
|---|---|---|---|---|
| 0 | 0 | 万州区永佳路万德印刷厂 | 15178905742 | 重庆市万州区双河口永佳路325号 |
| 1 | 1 | 覃彩虹 | 13594410133 | 重庆市万州区熊家镇古城大道296号 |
| 2 | 2 | 重庆优得利印刷有限公司 | 023-65903102 | 重庆市江津区双福工业园1幢1号 |
| 3 | 3 | 重庆市开州区森美印刷有限公司 | 15608330060 | 重庆市开州区云枫街道平桥社区桔乡路369号门市 |
| 4 | 4 | 吕兴华 | 13896015224 | 重庆市璧山区大路街道天星街23号 |
get_nms
def get_nums(s):'''逐位相加其ASCII码'''s = str(s)nums = 0for s0 in s:if(s0 == '-'):continuetry:nums += ord(s0)except:print("error: ",s)return nums
get_nums("重庆优得利印刷有限公司")
276879
平方取中法
df['nums_电话'] = df['电话'].apply(get_nums)
df['nums_电话^2'] = df['nums_电话'].apply(lambda x: np.square(x))
df['nums_企业名称'] = df['企业名称'].apply(get_nums)
# df['nums_电话^4'] = df['nums_电话^2'].apply(lambda x: np.square(x))
df.head()
| ID | 企业名称 | 电话 | 企业地址 | nums_电话 | nums_电话^2 | nums_企业名称 | |
|---|---|---|---|---|---|---|---|
| 0 | 0 | 万州区永佳路万德印刷厂 | 15178905742 | 重庆市万州区双河口永佳路325号 | 577 | 332929 | 257952 |
| 1 | 1 | 覃彩虹 | 13594410133 | 重庆市万州区熊家镇古城大道296号 | 562 | 315844 | 94053 |
| 2 | 2 | 重庆优得利印刷有限公司 | 023-65903102 | 重庆市江津区双福工业园1幢1号 | 559 | 312481 | 276879 |
| 3 | 3 | 重庆市开州区森美印刷有限公司 | 15608330060 | 重庆市开州区云枫街道平桥社区桔乡路369号门市 | 560 | 313600 | 364365 |
| 4 | 4 | 吕兴华 | 13896015224 | 重庆市璧山区大路街道天星街23号 | 569 | 323761 | 63703 |
def get_mid(x):'''取中间三位数作为地址'''return int(x/10)%1000
df['adr_电话'] = df['nums_电话^2'].apply(get_mid)
df['adr_企业名称'] = df['nums_企业名称'].apply(get_mid)
df.head(100)
| ID | 企业名称 | 电话 | 企业地址 | nums_电话 | nums_电话^2 | nums_企业名称 | adr_电话 | adr_企业名称 | |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 万州区永佳路万德印刷厂 | 15178905742 | 重庆市万州区双河口永佳路325号 | 577 | 332929 | 257952 | 292 | 795 |
| 1 | 1 | 覃彩虹 | 13594410133 | 重庆市万州区熊家镇古城大道296号 | 562 | 315844 | 94053 | 584 | 405 |
| 2 | 2 | 重庆优得利印刷有限公司 | 023-65903102 | 重庆市江津区双福工业园1幢1号 | 559 | 312481 | 276879 | 248 | 687 |
| 3 | 3 | 重庆市开州区森美印刷有限公司 | 15608330060 | 重庆市开州区云枫街道平桥社区桔乡路369号门市 | 560 | 313600 | 364365 | 360 | 436 |
| 4 | 4 | 吕兴华 | 13896015224 | 重庆市璧山区大路街道天星街23号 | 569 | 323761 | 63703 | 376 | 370 |
| ... | ... | ... | ... | ... | ... | ... | ... | ... | ... |
| 95 | 95 | 重庆涵天包装印务有限公司 | 023-72231721 | 重庆市涪陵区太极大道34号负一楼 | 558 | 311364 | 318409 | 136 | 840 |
| 96 | 96 | 垫江县金辉印刷厂 | 13110182246 | 重庆市垫江县周嘉镇迎春路 | 557 | 310249 | 209484 | 24 | 948 |
| 97 | 97 | 重庆凯翔包装印务有限公司 | 13709401186 | 重庆市永川区大安街道办事处大安工业园区 | 568 | 322624 | 321198 | 262 | 119 |
| 98 | 98 | 丰都县蓝图印务有限公司 | 15803661811 | 重庆市丰都县三合街道商业二路117号附2号 | 568 | 322624 | 284565 | 262 | 456 |
| 99 | 99 | 重庆毅然包装印刷有限公司 | 13509402066 | 重庆市綦江区文龙街道大田湾6号 | 564 | 318096 | 323964 | 809 | 396 |
除留余数法
df['adr_电话_1'] = df['nums_电话^2']%1007
df['adr_企业名称_1'] = df['nums_企业名称']%1007
df.head()
| ID | 企业名称 | 电话 | 企业地址 | nums_电话 | nums_电话^2 | nums_企业名称 | adr_电话 | adr_企业名称 | adr_电话_1 | adr_企业名称_1 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 万州区永佳路万德印刷厂 | 15178905742 | 重庆市万州区双河口永佳路325号 | 577 | 332929 | 257952 | 292 | 795 | 619 | 160 |
| 1 | 1 | 覃彩虹 | 13594410133 | 重庆市万州区熊家镇古城大道296号 | 562 | 315844 | 94053 | 584 | 405 | 653 | 402 |
| 2 | 2 | 重庆优得利印刷有限公司 | 023-65903102 | 重庆市江津区双福工业园1幢1号 | 559 | 312481 | 276879 | 248 | 687 | 311 | 961 |
| 3 | 3 | 重庆市开州区森美印刷有限公司 | 15608330060 | 重庆市开州区云枫街道平桥社区桔乡路369号门市 | 560 | 313600 | 364365 | 360 | 436 | 423 | 838 |
| 4 | 4 | 吕兴华 | 13896015224 | 重庆市璧山区大路街道天星街23号 | 569 | 323761 | 63703 | 376 | 370 | 514 | 262 |
创建哈希表(分别使用开发地址与公共溢出区解决冲突)
#初始化为全0# 开放地址法所使用的hash
hash_map_tele = np.zeros(32000)
hash_map_name = np.zeros(8000)# 公共溢出区所使用的hash
hash_map_tele_1 = np.zeros(2100)
hash_map_name_1 = np.zeros(2100)len(hash_map_tele)
400000
#探测开放地址法
def create_hash_map_tele(x, adr, df_ID):try:adr = int(x[adr])except:print('error: ', adr)while(hash_map_tele[adr] != 0):adr += 800hash_map_tele[adr] = x[df_ID]def create_hash_map_name(x, adr, df_ID):try:adr = int(x[adr])except:print('error: ', adr)while(hash_map_name[adr] != 0):adr += 800hash_map_name[adr] = x[df_ID]#使用公共溢出区
count1 = 0
count2 = 0
def create_hash_map_tele1(x, adr, df_ID):global count1if(hash_map_tele_1[x[adr]] == 0):hash_map_tele_1[x[adr]] = x[df_ID]else:hash_map_tele_1[1100 + count1] = x[df_ID]count1 += 1def create_hash_map_name1(x, adr, df_ID):global count2if(hash_map_name_1[x[adr]] == 0):hash_map_name_1[x[adr]] = x[df_ID]else:hash_map_name_1[1100 + count2] = x[df_ID]count2 += 1df.apply(create_hash_map_tele, axis=1, args=('adr_电话', 'ID'))
df.apply(create_hash_map_name, axis=1, args=('adr_企业名称', 'ID'))df.apply(create_hash_map_tele1, axis=1, args=('adr_电话_1', 'ID'))
df.apply(create_hash_map_name1, axis=1, args=('adr_企业名称_1', 'ID'))hash_map_tele
array([0., 0., 0., ..., 0., 0., 0.])
查找流程(平方取中+开发地址探测法)-method1
# 查找
search_method = int(input("请输入你查找关键词的类型：1，电话查找；2，企业名称查找"))
if(search_method == 1):tele = input("请输入你要查找对象的电话号码：")tele = int(tele)time_start = time.time()nums = get_mid(pow(get_nums(tele), 2))print("-----base_nums-----\n",nums)print("-----hash_map_tele_value-----\n", hash_map_tele[nums])print("-----开始查找-----")while(df['电话'][hash_map_tele[nums]] != tele):# print("-----tele-----\n", df['电话'][hash_map_tele[nums]])nums += 800# print('-----add_nums-----\n', nums)if(nums >= 32000):print('查找错误：无该信息')breaktime_end = time.time()if(nums < 32000):print("---------------你查找的信息如下：---------------\n", df.loc[hash_map_tele[nums]])print("---------------本次查找耗时：---------------\n",time_end-time_start)
elif(search_method == 2):name = input("请输入你要查找对象的企业名称：")time_start = time.time()nums = get_mid(get_nums(name))print("-----base_nums-----\n",nums)print("-----hash_map_tele_value-----\n", hash_map_name[nums])print("-----开始查找-----")while(df['企业名称'][hash_map_name[nums]] != name):# print("-----tele-----\n", df['企业名称'][hash_map_name[nums]])nums += 800# print('-----add_nums-----\n', nums)if(nums >= 8000):print('查找错误：无该信息')breaktime_end = time.time()if(nums < 8000):print("---------------你查找的信息如下：---------------\n", df.loc[hash_map_name[nums]])print("---------------本次查找耗时：---------------\n",time_end-time_start)
else:print("请选择正确的查找方式！")
-----base_nums-----370
-----hash_map_tele_value-----4.0
-----开始查找-----
---------------你查找的信息如下：---------------ID 4
企业名称 吕兴华
电话 13896015224
企业地址 重庆市璧山区大路街道天星街23号
nums_电话 569
nums_电话^2 323761
adr_电话 376
nums_企业名称 63703
adr_企业名称 370
Name: 4, dtype: object
---------------查找耗时：---------------0.0009999275207519531
查找流程(除留余数法+公共溢出法)-method2
# 查找
search_method = int(input("请输入你查找关键词的类型：1，电话查找；2，企业名称查找"))
if(search_method == 1):tele = input("请输入你要查找对象的电话号码：")tele = int(tele)time_start = time.time()nums = get_nums(tele)%1007print("-----base_nums-----\n",nums)print("-----hash_map_tele_value-----\n", hash_map_tele_1[nums])print("-----开始查找-----")while(df['电话'][hash_map_tele_1[nums]] != tele):# print("-----tele-----\n", df['电话'][hash_map_tele_1[nums]])nums += 1# print('-----add_nums-----\n', nums)if(nums >= 2100):print('查找错误：无该信息')breaktime_end = time.time()if(nums < 2100):print("---------------你查找的信息如下：---------------\n", df.loc[hash_map_tele_1[nums]])print("---------------本次查找耗时：---------------\n",time_end-time_start)
elif(search_method == 2):name = input("请输入你要查找对象的企业名称：")time_start = time.time()nums = get_nums(name)%1007print("-----base_nums-----\n",nums)print("-----hash_map_tele_value-----\n", hash_map_name_1[nums])print("-----开始查找-----")while(df['企业名称'][hash_map_name_1[nums]] != name):# print("-----tele-----\n", df['企业名称'][hash_map_name_1[nums]])nums += 1# print('-----add_nums-----\n', nums)if(nums >= 2100):print('查找错误：无该信息')breaktime_end = time.time()if(nums < 2100):print("---------------你查找的信息如下：---------------\n", df.loc[hash_map_name_1[nums]])print("---------------本次查找耗时：---------------\n",time_end-time_start)
else:print("请选择正确的查找方式！")
-----base_nums-----262
-----hash_map_tele_value-----4.0
-----开始查找-----
---------------你查找的信息如下：---------------ID 4
企业名称 吕兴华
电话 13896015224
企业地址 重庆市璧山区大路街道天星街23号
nums_电话 569
nums_电话^2 323761
nums_企业名称 63703
adr_电话 376
adr_企业名称 370
adr_电话_1 514
adr_企业名称_1 262
Name: 4, dtype: object
---------------本次查找耗时：---------------0.005001544952392578
性能分析
df.head(10)
| ID | 企业名称 | 电话 | 企业地址 | nums_电话 | nums_电话^2 | nums_企业名称 | adr_电话 | adr_企业名称 | adr_电话_1 | adr_企业名称_1 | |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 万州区永佳路万德印刷厂 | 15178905742 | 重庆市万州区双河口永佳路325号 | 577 | 332929 | 257952 | 292 | 795 | 619 | 160 |
| 1 | 1 | 覃彩虹 | 13594410133 | 重庆市万州区熊家镇古城大道296号 | 562 | 315844 | 94053 | 584 | 405 | 653 | 402 |
| 2 | 2 | 重庆优得利印刷有限公司 | 023-65903102 | 重庆市江津区双福工业园1幢1号 | 559 | 312481 | 276879 | 248 | 687 | 311 | 961 |
| 3 | 3 | 重庆市开州区森美印刷有限公司 | 15608330060 | 重庆市开州区云枫街道平桥社区桔乡路369号门市 | 560 | 313600 | 364365 | 360 | 436 | 423 | 838 |
| 4 | 4 | 吕兴华 | 13896015224 | 重庆市璧山区大路街道天星街23号 | 569 | 323761 | 63703 | 376 | 370 | 514 | 262 |
| 5 | 5 | 重庆海渝包装印刷有限公司 | 13883451070 | 重庆市璧山区奥康工业园金剑路271号 | 568 | 322624 | 323605 | 262 | 360 | 384 | 358 |
| 6 | 6 | 重庆鼎鸿印务有限公司 | 17782279989 | 重庆市永川区来龙四路36号 | 597 | 356409 | 292462 | 640 | 246 | 938 | 432 |
| 7 | 7 | 重庆奔速彩印有限公司 | 023-62802235 | 重庆市九龙坡区歇台子渝州路100号附1-5-1号 | 561 | 314721 | 274268 | 472 | 426 | 537 | 364 |
| 8 | 8 | 重庆市永川区木森印刷有限公司 | 18580704257 | 重庆市永川区三教镇三川路216号 | 575 | 330625 | 361502 | 62 | 150 | 329 | 996 |
| 9 | 9 | 重庆梧桐树印务有限公司 | 023-67980980 | 重庆市渝中区张家花园街206号 | 580 | 336400 | 291369 | 640 | 136 | 62 | 346 |
print("表长为：", len(df))
表长为： 754
32000与8000的来历
print("重复元素最多次数fen'bie为：")
for i in range(500):flag = 0for j in range(800):index = 800*i + jif(hash_map_tele[index] != 0):flag = 1if(flag == 0):print("tele_i:", i)breakfor i in range(500):flag = 0for j in range(800):index = 800*i + jif(hash_map_name[index] != 0):flag = 1if(flag == 0):print("name_i:", i)break
tele_i: 39
name_i: 9
计算method1的ASL
c1 = 0 # 统计总的查找次数
for i in range(500):for j in range(800):index = 800*i + jif(hash_map_tele[index] != 0):c1 += (i+1)
print('method1-tele-asl:', c1/754)
c2 = 0 # 统计总的查找次数
for i in range(500):for j in range(800):index = 800*i + jif(hash_map_name[index] != 0):c2 += (i+1)
print('method1-name-asl:', c2/754)
method1-tele-asl: 12.10079575596817
method1-name-asl: 1.6498673740053051
计算method2的ASL
df1 = df.adr_电话_1.value_counts()
print(df1)
514 39
916 33
329 32
47 31
767 31
187 29
216 29
473 28
619 27
646 26
384 26
62 26
9 25
372 25
175 21
530 20
6 20
852 19
256 18
130 18
780 17
690 17
343 16
917 16
653 15
537 15
685 13
423 12
513 11
891 11
201 10
771 10
311 9
859 7
994 7
93 6
386 5
568 5
938 5
206 4
28 4
688 3
890 3
788 2
119 2
590 1
309 1
752 1
494 1
894 1
434 1
Name: adr_电话_1, dtype: int64
df2 = df.adr_企业名称_1.value_counts()
print(df2)
68 6
90 5
406 5
231 4
979 4..
439 1
768 1
445 1
446 1
1006 1
Name: adr_企业名称_1, Length: 516, dtype: int64
print("有多少个元素在method2-tele基础表中，即只需查一次：",len(df1))
print("有多少个元素在method2-name基础表中，即只需查一次：",len(df2))
有多少个元素在method2-tele基础表中，即只需查一次： 51
有多少个元素在method2-name基础表中，即只需查一次： 516
# 基本表中的元素只需查一次，溢出区的元素和顺序表的查找次数是一样的，所以可以使用等差数列的计算公式进行计算，不过需要注意的就是溢出区的查找次数是从2开始的
print("method2-tele-asl:", (51 + (703*2 + (703*702)/2))/754)
print("method2-name-asl:", (516 + (238*2 + (238*237)/2))/754)
method2-tele-asl: 329.19098143236073
method2-name-asl: 38.720159151193634
最终得出结果
- method1-tele-asl: 12.10079575596817
- method1-name-asl: 1.6498673740053051
- method2-tele-asl: 329.19098143236073
- method2-name-asl: 38.720159151193634
分析
总的来说，重复元素的个数越多，哈希查找的效率就相应越低而法1的开放地址探测法对冲突的解决在本题中查找效率是明显优于公共溢出法的，但相应的占据了更大的存储空间至于平方去中法以及除留余数法在本题中映射出来的地址重复个数基本一致，故不相上下。
更多推荐
python散列表实现查找,使用了多种算法并测试对比进行了性能分析(查找效率)
发布评论