Use of HashSet
Use of HashSet
Base Code
Base Code
In[]:=
MultiwayGrowthList[rule_,init_List,t_]:=Last/@NestList[Function[s,{Join[First[s],#],#}&[Complement[Union[Flatten[StringReplaceList[Last[s],rule]]],First[s]]]],{{},init},t]
In[]:=
Length/@MultiwayGrowthList[{"AA""ABBAB","BAB""A"},{"ABAAA"},200]
Out[]=
HashSet Version
HashSet Version
In[]:=
MultiwayGrowthListHashSet[rule_,init_List,t_]:=Last/@NestList[Function[s, {Join[First[s],#],#}&[Module[{list,hashSet}, Normal[CreateDataStructure["HashSet"]["Union",Flatten[StringReplaceList[Last[s],rule]]]["Complement",First[s]]]]]],{{},init},t]
In[]:=
Length/@MultiwayGrowthList[{"AA""ABBAB","BAB""A"},{"ABAAA"},200]===Length/@MultiwayGrowthListHashSet[{"AA""ABBAB","BAB""A"},{"ABAAA"},200]
Out[]=
True
In[]:=
Length/@MultiwayGrowthList[{"AA""ABBAB","BAB""A"},{"ABAAA"},200];//AbsoluteTiming
Out[]=
{0.148661,Null}
In[]:=
Length/@MultiwayGrowthListHashSet[{"AA""ABBAB","BAB""A"},{"ABAAA"},200];//AbsoluteTiming
Out[]=
{0.051112,Null}
In[]:=
Length/@MultiwayGrowthList[{"AA""ABBAB","BAB""A"},{"ABAAA"},600];//AbsoluteTiming
Out[]=
{4.71229,Null}
In[]:=
Length/@MultiwayGrowthListHashSet[{"AA""ABBAB","BAB""A"},{"ABAAA"},600];//AbsoluteTiming
Out[]=
{0.836839,Null}
In[]:=
Length/@MultiwayGrowthList[{"AA""ABBAB","BAB""A"},{"ABAAA"},800];//AbsoluteTiming
Out[]=
{12.9475,Null}
In[]:=
Length/@MultiwayGrowthListHashSet[{"AA""ABBAB","BAB""A"},{"ABAAA"},800];//AbsoluteTiming
Out[]=
{1.89701,Null}
In[]:=
Length/@MultiwayGrowthList[{"AA""ABBAB","BAB""A"},{"ABAAA"},1200];//AbsoluteTiming
Out[]=
{61.136,Null}
In[]:=
Length/@MultiwayGrowthListHashSet[{"AA""ABBAB","BAB""A"},{"ABAAA"},1200];//AbsoluteTiming
Out[]=
{7.5148,Null}