Python – 余数分布|Hash（python中求余数的符号）

off999 2024-10-07 12:10 32 浏览 0 评论

这篇文章主要是在计算LeetCode-706设计哈希映射时，碰到关于计算余数的问题，用seaborn夈表观察一下质数的余数分布情况。

会涉及以下几方面内容:

质数和余数
Seaborn绘制swarmplot和lineplot
Pandas的pivot_table的计算

在数据处理的一些敏感信息，我用xxxxxx进行了替代，但不影响整理代码阅读

主要参考的相关网站有以下几个:

https://seaborn.pydata.org/tutorial/function_overview.html

1. LeetCode题解
#------------------------LeetCode-706|设计哈希映射---------------------------
"""
用一个大质数将key取余，将数据分成不同bucket;
分bucket将[key,value]记入列表;再进行相应操作;
"""
class MyHashMap2:
#用余数进行bucket分类，分别获取hash.table的内容
#用较大质数，将数据平均分布在bucket中
def __init__(self):
  #定义初始化hash.table
  self.prime=1093 #定义一个质数
  self.table=[[] for _ in range(self.prime)] #初始化hash.table

def put(self, key: int, value: int) -> None:
  #分两种情况：1.原key存在，更新值；2.原key不存在，添加值
  bucket=key%self.prime #余数,表示bucket区域
  for item in self.table[bucket]: #key存在
    if item[0]==key:
      item[1]=value
      return #return跳出put功能
     self.table[bucket].append([key,value]) #key不存在，添加值

def get(self, key: int) -> int:
  #1.key存在，返回value;2.key不存在，返回-1
  bucket=key%self.prime #余数,表示bucket区域
  for idx,val in self.table[bucket]: #key存在
    if idx==key:
      return val
  return -1

def remove(self, key: int) -> None:
  bucket=key%self.prime #余数,表示bucket区域
  for idx,item in enumerate(self.table[bucket]): #key存在bucket
    if item[0]==key:
      self.table[bucket].pop(idx)

1. 质数的余数分布

"""
在做LeetCode-706设计哈希映射的时候，在处理余数时；
想观察一下不质数和合数在处理余数时的分布
prime table/质数表 <1000
primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997]
"""
import os
import numpy as np
import pandas as pd
import seaborn as sns
import matplotlib.pyplot as plt
path=r'C:\Users\02279074\OneDrive - Elanco\Lilly_OneDrive\C\TZ\Algorithm'
# --------------generate data-----------------------
# prime table/质数表 <100
#primes=[ 3, 13, 23, 43,53] #选取一些质数
primes=[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
nums=pd.Series(np.random.randint(1,100,size=500)) #n个随机整数
# nums=pd.Series(np.arange(1,101,step=1)) #生成数列
dfList=[]
for prime in primes:
  df=pd.DataFrame([nums,nums%prime]).T #生成余数表
  df['type']='prime-'+str(prime)
  dfList.append(df)
dfs=pd.concat(dfList) #合并成一个df
dfs.columns=['nums','remain','type']
# -------------generate pivot_table------------------
pvt=pd.pivot_table(dfs,
          index='remain',
          columns='type',
          values='nums',
          aggfunc='count',
          fill_value=0)
output_f=os.path.join(path,'remind_distribution.xlsx')
with pd.ExcelWriter(output_f) as writer:
  dfs.to_excel(writer,sheet_name='table',index=True)
  pvt.to_excel(writer,sheet_name='pvt',index=True)
# ----------------扰动图--------------------------
#fig为画布,ax为子图对象
fig,ax=plt.subplots(figsize=(12,8),dpi=120) #图表布局
ax=sns.swarmplot(data=dfs, #数据
          x="remain",
          y="nums",
          hue="type", #分类
          # jitter=0.25, #抖动幅度
          )
plt.grid(True) #添加网格线
file1=os.path.join(path,'swarmplot.png')
plt.savefig(file1)
plt.close()
# ----------------柱状图--------------------------
#fig为画布,ax为子图对象
fig,ax=plt.subplots(figsize=(12,8),dpi=120) #图表布局
ax=sns.lineplot(data=pvt,
					)
xlabels=[int(x) for x in ax.get_xticks()] #x轴整数
ax.set_xticklabels(xlabels)
plt.grid(True) #添加网格线
file2=os.path.join(path,'lineplot.png')
plt.savefig(file2)
plt.close()
print("all done".center(50,"*"))

生成两个图形：

1.扰动图swarmplot: x轴为余数，y轴为随机数；

2.线形图lineplot: x轴为余数，y轴为余数的计数和；

观察lineplot可以看到，随着prime的值不变增加，每个余数remain的计数和更加趋于平均；就这表示质数越大，分布在余数上的值就更平均。

python取余数