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,
            doSplit,
            splitCombs,
            makeNewPrefix,
            lessThanX,
            filterCombs;

    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 );
    end;

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

    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 ) )):
    end;

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

end:

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.

Darin

-- Kernel Developer Maplesoft

FilterComb.mw


Please Wait...