I made a function using LibraryLink. It uses the same algorithm as the one in J.M.'s answer, i.e. algorithm P by Knuth. Here is the C code
#include "WolframLibrary.h"
#include <stdlib.h>
#include <stdbool.h>
static char* charbuf;
static mint curword;
static mint zz;
/* Return the version of Library Link */
DLLEXPORT mint WolframLibrary_getVersion( ) {
return WolframLibraryVersion;
}
/* Initialize Library */
DLLEXPORT int WolframLibrary_initialize( WolframLibraryData libData) {
return LIBRARY_NO_ERROR;
}
/* Uninitialize Library */
DLLEXPORT void WolframLibrary_uninitialize( WolframLibraryData libData) {
return;
}
DLLEXPORT int set_permup_buf(WolframLibraryData libData,
mint Argc, MArgument *Args, MArgument Res){
// '[' = 0 and ']' = 1
curword = 0;
zz = MArgument_getInteger(Args[0]);
mint qq = MArgument_getInteger(Args[1]);
//sizeof(char) == 1 is guaranteed by the C standard.
charbuf = malloc(qq * (zz + 1));
mint mm = zz - 1;
mint jj;
char aAr[zz + 1];
int rowNum = 0;
char b = 1;
char* aPtr = aAr;
// p1
for(int kk = 0; kk <= zz; kk++){
*aPtr = b;
aPtr++;
b = !b;
}
p2: {
for(int dd = 0; dd < zz; dd++){
charbuf[(zz + 1)*rowNum + dd] = 91 + 2 * aAr[dd+1];
}
charbuf[(zz+1)*rowNum + zz] = '\0';
rowNum++;
}
//p3
aAr[mm] = 1;
if(aAr[mm-1]){
aAr[mm-1] = 0;
mm--; goto p2;
}
//p4
jj = mm - 1;
int kk = zz - 1;
while(! aAr[jj]){
aAr[jj] = 1;
aAr[kk] = 0;
jj--;
kk-=2;
}
//p5
if(jj){
aAr[jj] = 0;
mm = zz - 1;
goto p2;
}
return LIBRARY_NO_ERROR;
}
DLLEXPORT int get_permup_str(WolframLibraryData libData,
mint Argc, MArgument *Args, MArgument Res)
{
MArgument_setUTF8String(Res, charbuf + curword*(zz+1));
curword++;
return LIBRARY_NO_ERROR;
}
DLLEXPORT int cleanup(WolframLibraryData libData,
mint Argc, MArgument *Args, MArgument Res)
{
free(charbuf); //seems magical, doesn't it?
return LIBRARY_NO_ERROR;
}
Loading the function
Save the code above at file at the path yourFileName (maybe the name of the file should end in .c) .
<< CCompilerDriver`
libName = "dyckwordlib";
lib2 = CreateLibrary[File@yourFileName, libName, "Debug" -> True];
setBuf = LibraryFunctionLoad[libName,
"set_permup_buf", {_Integer, _Integer}, "Void"];
getStr = LibraryFunctionLoad[libName, "get_permup_str", {},
"UTF8String"];
cleanup = LibraryFunctionLoad[libName, "cleanup", {}, "Void"];
dyckWordsLibl[kwnn_] :=
Module[{kn, qq, res}
,
qq = CatalanNumber[kwnn];
setBuf[2 kwnn, qq];
res = Table[
getStr[]
,
qq
];
cleanup[];
res
]
Timings and naive memory tracking.
We see that the LibraryLink solution is fast. It also does not consume much memory, although I am pretty sure the memory monitoring tools of Mathematica don't accurately track the memory used.
MaxMemoryUsed[dyckWordsLibl[12]]
resJac = dyckWordsLibl[12]; // RepeatedTiming // First
MaxMemoryUsed[dyckWordsCc[24]]
resCc = dyckWordsCc[24]; // RepeatedTiming // First
MaxMemoryUsed[f[12]]
resWiz = f[12]; // RepeatedTiming // First
14978472
0.10
159753824
0.34
16641256
1.397
Of course the results are the same
Sort[resJac] === Sort[resCc] === Sort[resWiz]
True
Using (slight adaptations of) definitions from especially Mr.Wizards answer, we get the following BenchmarkPlot
Needs["GeneralUtilities`"]
BenchmarkPlot[{wizf, f2, cw, dyckWordsCcDouble, dyckWordsLibl}, # &,
Range[2, 15], "IncludeFits" -> True, TimeConstraint -> 10]
Considerations about MaxMemoryUsed
Considering that on most platforms a char is encoded in one byte (and on mine in particular), the real memory used by our function is the following (a bit more than Mr.Wizard's function)
With[{kwnn = 12,
qq = CatalanNumber[kwnn]},
ByteCount@resJac + qq * (2 kwnn + 1) ]
20177244
Below, we will show below that MaxMemoryUsed does not track all the memory used by comparing the value MaxMemoryUsed[setBuf[2 kwnn, qq]], which is very small, with an alternative measurement.
We can track the increase in memory using a performance monitoring tool, in my case on OSX I used Activity Monitor. The increase in memory used by the WolframKernel process closely corresponds to the amount of memory we asked for using malloc. We set before and after to correspond to the values we see in activity monitor. We increase kwnn to 16 to make the memory use stand out even more.
before = Quantity[52.2, "Megabytes"];
kwnn = 16;
qq = CatalanNumber[kwnn];
MaxMemoryUsed[setBuf[2 kwnn, qq]]
112
Of course this number 112 does not really make sense. We look again in activity monitor
after = Quantity[1.14, "Gigabytes"];
Incidentally, using the tool we can now see that cleanup works
cleanup[]; (*look in the tool after this command*)
Now we compare
Module[{kwnn = 16,
qq },
qq = CatalanNumber[kwnn];
N@UnitConvert[qq * (2 kwnn + 1) Quantity[1, "Bytes"] ,
Quantity[1, "Megabytes"]]]
after - before
1166.8 MB
1087.8 MB
We see that we memory we used roughly corresponds to the memory we asked for. Furthermore, using the tool (activity monitor) we can see that cleanup works and all our memory is returned to us, so thats nice.
