一组用C编写的数据结构的python模块
structpie的Python项目详细描述
结构派
一组用于数据结构的python模块。所有数据结构都用C编写,并使用cython导入python。不需要使用python代码来快速构建数据结构。在
这个想法是扩展python数据结构,以增加更多的灵活性,并包含更多的数据结构,以帮助不同的情况。在
上还有一个StructPie项目sourceforge.net包含所有这些数据结构作为C共享库,可以很容易地在C项目中使用。这些库可以从here下载。
快速入门
安装库
pip install structpie
从python内部测试不同的数据结构
哈希表
Separate Chaining支持快速查找和搜索的哈希映射。 它有助于按“value”O(1)进行搜索,而python字典在知道密钥时启用O(1)搜索。在
对于list、dict和HashTable之间的完整比较,请尝试运行^{str1}$示例.py在/hash_table/文件夹中编写脚本。在
要启动哈希表,应指定大小和类型。它支持“int”、“float”和“str”
^{pr2}$如果表是“str”类型,则输入字符串应转换为bytes,以便Cython能够将其转换为C char*。在
# insert data into the tableforiinarr:ht.insert_val(i.encode())# print the tableht.display()# index(0): Hello# index(1):# index(2):# index(3): Konnichiwa# index(4): Ola# index(5): Ciao# index(6):# index(7): Hola# index(8): Merhaba Salam# index(9): Privetstviye
检查表的大小以及有多少索引被占用。在
print("size of the table is %d while number of filled indices is %d"%(ht.length(),ht.occupied()))# size of the table is 10 while number of filled indices is 7
在表中搜索值,删除并按索引搜索:
print("try now to search for and delete some values: (0 means False while 1 is True)")# try now to search for and delete some values: (0 means False while 1 is True)print("search for value Merhaba --> %d"%ht.search_value("Merhaba".encode()))# search for value Merhaba --> 1print("search for value Namaste --> %d"%ht.search_value("Namaste".encode()))# search for value Namaste --> 0print("search by index 3 --> value %s found"%ht.search_by_index(3))# search by index 3 --> value Konnichiwa foundprint("remove value Ola --> %d"%ht.val_del("Ola".encode()))# remove value Ola --> 1print("search again for value Ola --> %d"%ht.search_value("Ola".encode()))# search again for value Ola --> 0print("try again to remove value Ola --> %d"%ht.val_del("Ola".encode()))# try again to remove value Ola --> 0
再次打印
ht.display()# index(0): Hello# index(1):# index(2):# index(3): Konnichiwa# index(4):# index(5): Ciao# index(6):# index(7): Hola# index(8): Merhaba Salam# index(9): Privetstviye
获取特定值的索引
ht.get_index(b"Hello")# 0ht.get_index(b"Salam")# 8
我们也可以得到特定索引中的所有值
ht.search_index(8)# ['Merhaba', 'Salam']ht.search_index(1)# []ht.search_index(ht.get_index(b"Salam"))# ['Merhaba', 'Salam']
使用display方法显示第一个特定数量的索引。类似于python数据帧中的head:
ht.display(5)##specifying how many indices to display# index(0): Hello# index(1):# index(2):# index(3): Konnichiwa# index(4):
有一些空的未使用的索引,这是因为字符串使用的哈希函数目前非常简单,但在将来的版本中会有更好的实现。
同时在<;int>;哈希表中发现此问题的可能性较小。
后进先出与先进先出堆栈
fromstructpieimport*# initiate a stack of type "int"st=Stack("int")# push values into the stackst.push(13)st.push(11)st.push(19)st.push(91)# print the stackst.display()# [13 11 19 91 ]# pop from right (LIFO)st.pop()# 91# pop from left (FIFO)st.popleft()# 13# check lengthst.length()# 2 # print against.display()# [11 19 ]
堆栈还可以包含“float”和“str”类型的数据。
二叉搜索树
二叉搜索树是一种在插入新数据时快速搜索和动态排序的数据结构。它被广泛应用于许多应用程序中,例如在数据库中为快速查找建立索引。在
Struct Pie提供了一个C编写的二进制搜索树,以便在python中使用。在
插入比附加到python列表慢一点,但是搜索要快得多。在
Struct Pie BST节点可以容纳3个数据片段(intindex,char*info1,float info2)。这将很快得到扩展,以保存更多的数据。在
让我们尝试一下关于欧洲冠军联赛历史进球者的一些样本数据的二叉搜索树。每行代表(进球数、名称、进球/比赛比率)。在
# initiate bstreebst=BSTree()importpandasaspddata=pd.read_csv("./binary_search_tree/example_data.csv",header=None)data# 0 1 2#0 130 Cristiano Ronaldo 0.76#1 115 Lionel Messi 0.80#2 71 Raul Gonzalez 0.50#3 68 Robert Lewandowski 0.76#4 65 Karim Benzema 0.54#5 56 Ruud van Nistelrooy 0.77#6 50 Thierry Henry 0.45#7 49 Alfredo Di Stefano 0.84#8 48 Andriy Shevchenko 0.48#9 48 Zlatan Ibrahimovic 0.40#10 46 Thomas Muller 0.40
让我们把数据插入树中
foriinrange(data.shape[0]):bst.insert(data.iloc[i,0],data.iloc[i,1].encode(),data.iloc[i,2])# check that all data was inserteddata.shape[0]==bst.node_count()# True
树上的一些操作;(顺序)打印、搜索和删除
# print inorder bst.inorder()# 46 -> 48 -> 48 -> 49 -> 50 -> 56 -> 65 -> 68 -> 71 -> 115 -> 130 -># search for an indexbst.search(40)# "node doesn't exist"bst.search(48)# (48, b'Andriy Shevchenko', 0.48)bst.search(46)# (46, b'Thomas Muller', 0.4)bst.search(49)# (49, b'Alfredo Di Stefano', 0.84)# delete a nodebst.remove(48)# new order after deletionbst.inorder()# 46 -> 48 -> 49 -> 50 -> 56 -> 65 -> 68 -> 71 -> 115 -> 130 ->bst.node_count()# 10bst.remove(71)bst.node_count()# 9bst.inorder()# 46 -> 48 -> 49 -> 50 -> 56 -> 65 -> 68 -> 115 -> 130 ->bst.search(65)# (65, b'Karim Benzema', 0.54)
具有二进制搜索树的哈希表
实现hash table数据结构,使用单独链接来避免冲突。{str{str}>使用一个比{str}>更快速的查找{str}>索引,而不是使用^/str}索引来实现{str}的索引。在
插入比在链接列表中插入慢,但搜索更快。在
fromstructpieimport*size=5type="int"hbst=HashBSTree(size,type)arr=[13,11,19,91,22,12,19,94]foriinarr:hbst.insert_val(i)hbst.display()# index(0):# index(1): 11 -> 91 -># index(2): 12 -> 22 -># index(3): 13 -># index(4): 19 -> 19 -> 94 ->(hbst.length(),hbst.occupied())# (5, 4)hbst.search_value(94)# 1hbst.search_value(15)# 0hbst.search_by_index(3)# '13'hbst.val_del(91)hbst.search_value(91)# 0hbst.val_del(91)# The value does not existhbst.get_index(19)# 4hbst.get_index(11)# 1
优先级队列
优先级队列是一种很好的数据结构,用于插入新的值,并根据一定的优先级对队列进行排序,这样在弹出消息时,即使后面插入了更重要的值,也会先弹出。在
pq=PQ()pq.display()# The queue is Empty
目前,PQ接受两个输入(char*name,int priority)。这肯定会很快扩大。在
cchar*在python中用字节表示。所以在插入字符串时,应该先将它们编码成字节。
让我们插入一些任务和优先级:
pq.push(b"exercise",3)pq.push(b"sleep",2)pq.push(b"repeat",1)pq.push(b"code",5)pq.display()# (# {code, 5}# {exercise, 3}# {sleep, 2}# {repeat, 1}# )
队列是根据优先级动态排序的。在
现在让我们来:
pq.pop()# (code) with priority (5) has been removed# 'code'
请注意,pop方法打印一条确认消息,并以字符串形式返回任务名称
some=pq.pop()# (exercise) with priority (3) has been removedprint(some)# exercisepq.display()# (# {sleep, 2}# {repeat, 1}# )pq.pop()# (sleep) with priority (2) has been removed# 'sleep'pq.pop()# (repeat) with priority (1) has been removed# 'repeat'## when trying to pop from an empty queue, an empty string '' is returned.pq.pop()# The queue is empty# ''pq.display()# The queue is Empty
很快将支持更多数据结构。
- 项目
标签: