Python3中高度平衡螺纹绳数据结构的实现
pyropes的Python项目详细描述
绳索
高度平衡螺纹绳数据结构
pip install pyropes^{pr2}$
学分
为了使这个项目成功，我们使用了以下来源，并进行了修改。我承认并感谢这些开发者。在
- 测试套件：用于最终测试的测试套件属于Marshall Ward（https://github.com/marshallward）
- Display API：在堆栈溢出（https://stackoverflow.com/a/54074933）时，J.V.
关于
本文档展示了“Height Balanced threading Rope Data Structure”的用例。 rope是用于字符串处理的可变数据结构。像split、insert、delete这样的操作在rope中的时间O（logn）中执行，而传统的字符串具有O（n）时间复杂性。串联是在rope（O（logn）中的O（1）中完成的，带有线程和平衡）。然而，在一个索引处的访问值在ropes中是O（logn），而在常规字符串中是O（1）。 Ropes的这个实现是^{str1}$“Height Balanced With Threads”。高度平衡的动机来自于AVL树和线程附加到所有叶节点，以使遍历快速，其动机来自线程二叉树。在
这个库的目的是帮助学生（或任何学习者）学习绳索、高度平衡、树上穿线、编写和维护大型python代码，所有这些都可以可视化（是的！你在纸上画的树）可以很容易地跟踪代码中发生的事情。在
功能和使用
构造函数
- Rope() -> new empty Rope object.
- Rope(string, leafsize=4) -> Create a Rope from string with leafsize=4 , (default leafsize is 8)
- Rope([string1, string2, string3]) -> Equivalent to Rope(string1 + string2 + string3) *Any container can be used above but should have string type elements
详细示例
>>>frompyropesimportRope>>>raw="This_is_a_test_string_for_Rope_DataStructure">>>rope1=Rope(raw)>>>rope2=Rope(raw,leafsize=12)>>>rope1,rope2
(Rope('This_is_a_test_string_for_Rope_DataStructure'),
Rope('This_is_a_test_string_for_Rope_DataStructure'))
>>>rope1.display()
___________________(22)____________________
/ \
________(11)_________ ________(11)_________
/ \ / \
___(6)___ ___(6)___ ___(6)___ ___(6)___
/ \ / \ / \ / \
(This_i) (s_a_t) (est_st) (ring_) (for_Ro) (pe_Da) (taStru) (cture)
>>>rope2.display()
______________(22)_______________
/ \
______(11)______ ______(11)______
/ \ / \
(This_is_a_t) (est_string_) (for_Rope_Da) (taStructure)
>>>raw=["Thi","s_is","_a_test","_stri","ng_for","_Rope_Data","Str","ucture"]>>>rope1=Rope(raw)>>>rope2=Rope(raw,leafsize=10)>>>rope1.display()>>>rope1
___________________(25)___________________
/ \
__________(14)________ ________(10)______
/ \ / \
____(7)____ ___(5)____ ___(5)___ __(3)____
/ \ / \ / \ / \
(This_is) (_a_test) (_stri) (ng_for) (_Rope) (_Data) (Str) (ucture)
Rope('This_is_a_test_string_for_Rope_DataStructure')
>>>rope2.display()>>>rope2
________(19)_________________________
/ \
__________(14)___ _____________(16)_____
/ \ / \
____(7)____ (_stri) ___(6)______ (Structure)
/ \ / \
(This_is) (_a_test) (ng_for) (_Rope_Data)
Rope('This_is_a_test_string_for_Rope_DataStructure')
>>>(rope1[1],rope2[1]),(rope1[2:5],rope2[2:5])
((Rope('h'), Rope('h')), (Rope('is_'), Rope('is_')))
>>>rope1[:8],rope2[:8]
(Rope('This_is_'), Rope('This_is_'))
>>>rope2.display()
___________________(19)_________________________
/ \
____(8)_________ _____________(16)_____
/ \ / \
(This_is_) ___(6)___ ___(6)______ (Structure)
/ \ / \
(a_test) (_stri) (ng_for) (_Rope_Data)
>>>rope1[::2]
Rope('Ti_sats_tigfrRp_aatutr')
Ropes are considered equal if they represent same string.
(True, False)
>>>rope3=rope1.copy()>>>rope1==rope3,rope1isrope3
(True, False)
>>>new=rope1.append(rope2)>>>rope1,new,rope1==new,rope1isnew
Note: rope2 is sharing memory with rope1(or new) so any change made in rope2 will be reflected in rope1. To overcome this, use '+' operator instead
(Rope('This_is_a_test_string_for_Rope_DataStructureThis_is_a_test_string_for_Rope_DataStructure'),
Rope('This_is_a_test_string_for_Rope_DataStructureThis_is_a_test_string_for_Rope_DataStructure'),
True,
True)
>；现在让我们看看更多的操作，但在一些较小的字符串上，这些字符串可以很容易地显示在屏幕上
>>>rope1=Rope('abcde',leafsize=3)>>>rope1,print(rope1)
abcde
(Rope('abcde'), None)
>>>rope2=rope1+Rope("_I'm a ROPE")>>>rope1,rope2,rope1isrope2
Note: here, rope2 is NOT SHARING memory with any of rope1 or Rope("_I'm a ROPE"). Alwasys,'+' returns a copy of Rope on Right side
(Rope('abcde'), Rope('abcde_I'm a ROPE'), False)
type(rope3) is also Rope despite of concatnating string as operand
(Rope('abcde'), Rope('abcde_I'm a string'), False)
>>>rope4=rope1*3>>>rope1,rope4,rope1>rope4
(Rope('abcde'), Rope('abcdeabcdeabcde'), False)
clearly shows that rope1 and rope1*4 are NOT SHARING any memory. Note: index based slicing do NOT update rope structure
(Rope('ab*de'), Rope('abcd#abcdeabcde'))
>>>show=lambdax:f"( {x.valifx.valelsex.weight}, {x.height} )"
'show' will governs what will Rope.display() shows
>>>rope1=Rope("abcdefghi",leafsize=3)>>>rope1,rope1.display(show)
________(5,2)________
/ \
___(3,1)___ __(2,1)___
/ \ / \
(abc,0) (de,0) (fg,0) (hi,0)
(Rope('abcdefghi'), None)
>>>rope1[2:5]="_I'M_INSERTED_">>>rope1,rope1.display(show)
Each internal node will show (weight,height) while leaves showing (value,height)
___________________(13,4)_________
/ \
____________________(9,3)________ ___(3,2)________
/ \ / \
________(4,2)________ __(2,1)___ (ED_,0) __(2,1)___
/ \ / \ / \
__(2,1)___ __(2,1)___ (SE,0) (RT,0) (fg,0) (hi,0)
/ \ / \
(ab,0) (_I,0) ('M,0) (_IN,0)
(Rope('ab_I'M_INSERTED_fghi'), None)
>>>rope1.leafsize=5>>>rope1.display(show)
changing leafsize will implicitly calls rope.refresh()
__________(13,3)_________
/ \
___________(9,2)____ ___(3,1)____
/ \ / \
___(4,1)____ (SERT,0) (ED_,0) (fghi,0)
/ \
(ab_I,0) ('M_IN,0)
>>>rope=Rope(["This ","Rope_will"," be splitted in"])+"_to_two_parts">>>rope,rope.display()
_________________(14)________________________
/ \
___(5)________ __________(15)__________
/ \ / \
(This ) ___(5)___ ____(8)____ ____(7)____
/ \ / \ / \
(Rope_) (will) ( be spli) (tted in) (_to_two) (_parts)
(Rope('This Rope_will be splitted in_to_two_parts'), None)
>>>left_rope,right_rope=rope.split(18)>>>left_rope,left_rope.display()
________(10)_____
/ \
___(5)___ (will be )
/ \
(This ) (Rope_)
(Rope('This Rope_will be '), None)
>>>right_rope,right_rope.display()
__________(11)__________
/ \
__(4)____ ____(7)____
/ \ / \
(spli) (tted in) (_to_two) (_parts)
(Rope('splitted in_to_two_parts'), None)
>>>left_rope==rope,left_ropeisrope
^{pr51}$shows that left_rope and rope are pointing to same rope
>；Rope对象也可以初始化为空。见下文：
>>>rope1=Rope(leafsize=5)>>>rope1,rope1.display()^{pr53}$ ^{pr54}$ ^{pr55}$
>>>rope1.delete(2)>>>rope1,rope1.display()
______________(11)______________
/ \
___(5)______ ______(6)______
/ \ / \
(I_m_a) __(3)__ __(3)__ __(3)__
/ \ / \ / \
(dde) (d_t) (o_e) (mpt) (y_r) (ope)
(Rope('I_m_added_to_empty_rope'), None)
>>>rope2=rope1.delete(3,11)>>>rope1,rope1.display()
________(8)______
/ \
__(3)___ __(3)__
/ \ / \
(I_m) (_empt) (y_r) (ope)
(Rope('I_m_empty_rope'), None)
>>>rope2,rope2.display()^{pr61}$
>>>rope2[0:0]="Added_IN_FRONT">>>rope2,rope1
^{63}$Look that memory isn't shared between deleted rope and remaining rope
>>>rope2.reverse()>>>rope2,rope2.display()
________(9)_______________
/ \
__(4)___ _______(7)______
/ \ / \
(ot_d) (edda_) __(3)___ __(3)___
/ \ / \
(TNO) (RF_N) (I_d) (eddA)
(Rope('ot_dedda_TNORF_NI_deddA'), None)
>>>rope2.reverse()#To bring original after previous rope2.reverse()>>>rope2.split_merge(5,13,11)>>>rope2,rope2.display()
split_merge(i,j,k) will extract rope from [i:j] (both inclusive) and insert it before kth index in remaining Rope
______(13)_______________
/ \
________(10)__ ______(7)__
/ \ / \
___(5)___ (d_I) __(4)__ (_to)
/ \ / \
(Added) (_adde) (N_FR) (ONT)
(Rope('Added_added_IN_FRONT_to'), None)
>；现在字符串上的一些常见操作（以后将发布更多操作）
>>>rope1=Rope("ABcdefGh").lower()>>>rope2=Rope("ABcdefGh").upper()>>>rope3=Rope("ABcdefGh").swapcase()>>>rope4=Rope("ABcdefGh").capitalize()>>>rope1,rope2,rope3,rope4
(Rope('abcdefgh'), Rope('ABCDEFGH'), Rope('abCDEFgH'), Rope('Abcdefgh'))
>>>(rope1.islower(),rope1.isupper()),(rope2.islower(),rope2.isupper())
((True, False), (False, True))
(True, False, True)
>>>rope1.isdecimal(),Rope("123").isdecimal()
(False, True)
仍然有很多功能和用法，但是我鼓励您浏览所有可用的函数并阅读它们的doc字符串，以了解更多关于它们的信息。在
最后一句话：
尽管我在创建rope和编写此文档时已经非常小心，但是如果您发现任何bug，请报告它。 我们衷心欢迎任何改进代码/文档的建议。在
- 项目
标签：
欢迎加入QQ群-->： 979659372
