I made a small change to the Task Filtering code I uploaded a few weeks ago.  The new code has better memory performance and, most importantly has more stable memory usage which means it can actually run very large examples.  Here is the new version of the code:

FilterCombPara := module( )
    local ModuleApply,

    lessThanX := proc( x, i ) x<=i; end;

    doSplit := proc( i::integer, prefix::set(posint), rest::set(posint),
                                                k::posint, filter::appliable, $ )
        splitCombs( prefix union {i}, remove( lessThanX, rest, i ), k-1, filter );

    splitCombs := proc( prefix::set(posint), rest::set(posint), k::posint,
                                                                filter::appliable, $ )
        if ( numelems( rest ) < k ) then
        elif ( k = 1 ) then
            filterCombs( prefix, rest, filter );
            op( Threads:-Map( doSplit, rest, prefix, rest, k, filter ) );

    makeNewPrefix := proc( i, prefix ) { i, op( prefix ) } end;
    filterCombs := proc( prefix::set(posint), rest::set(posint), filter::appliable, $ )
        local i, f;

        op(select( filter, map( makeNewPrefix, rest, prefix ) )):

    ModuleApply := proc( n::posint, k::posint, filter::appliable, $ )
        [ splitCombs( {}, {seq( i,i=1..n )}, k, filter ) ];


This code has the small mapping functions as module members instead of declared inline.  This means that less memory is churned as this code is excuted.  For a long runs, this helps keeps the memory stable.

As an example, I ran the following example:

> CodeTools:-Usage( FilterCombPara( 113,7, x->false ) );
memory used=17.39TiB, alloc change=460.02MiB, cpu time=88.52h, real time=20.15h

It used 88 CPU hours to run, but only 20 hours of real time (go parallelism!)  It used 17 Terabytes of memory, but only allocated 500 M.  This example is pretty trival, as the filter returned false for all combinations, so it did not collect any matches during the run.  However as long as the number of matches is small, that shouldn't be an issue.  If the number of matches is too large to fit in memory, then this code may need to be modified to write the matches out to disk instead of trying to hold them all in memory at once.


-- Kernel Developer Maplesoft


Please Wait...