Use of HashSet
Use of HashSet
Base Code
Base Code
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]
In[]:=
Out[]=
HashSet Version
HashSet Version
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]
In[]:=
True
Out[]=
Length/@MultiwayGrowthList[{"AA""ABBAB","BAB""A"},{"ABAAA"},200];//AbsoluteTiming
In[]:=
{0.148661,Null}
Out[]=
Length/@MultiwayGrowthListHashSet[{"AA""ABBAB","BAB""A"},{"ABAAA"},200];//AbsoluteTiming
In[]:=
{0.051112,Null}
Out[]=
Length/@MultiwayGrowthList[{"AA""ABBAB","BAB""A"},{"ABAAA"},600];//AbsoluteTiming
In[]:=
{4.71229,Null}
Out[]=
Length/@MultiwayGrowthListHashSet[{"AA""ABBAB","BAB""A"},{"ABAAA"},600];//AbsoluteTiming
In[]:=
{0.836839,Null}
Out[]=
Length/@MultiwayGrowthList[{"AA""ABBAB","BAB""A"},{"ABAAA"},800];//AbsoluteTiming
In[]:=
{12.9475,Null}
Out[]=
Length/@MultiwayGrowthListHashSet[{"AA""ABBAB","BAB""A"},{"ABAAA"},800];//AbsoluteTiming
In[]:=
{1.89701,Null}
Out[]=
Length/@MultiwayGrowthList[{"AA""ABBAB","BAB""A"},{"ABAAA"},1200];//AbsoluteTiming
In[]:=
{61.136,Null}
Out[]=
Length/@MultiwayGrowthListHashSet[{"AA""ABBAB","BAB""A"},{"ABAAA"},1200];//AbsoluteTiming
In[]:=
{7.5148,Null}
Out[]=