ListBuffer, a procedure for efficiently building arbitrarily sized lists

January 16 2006 Joe Riel 6371

7

dcasimir asks for an efficient way to create a list of the first n primes, without invoking nextprime, etc. An easy way to do this is to use a do loop to build up a sequence term by term. However, as Alec points out, this is not an efficient technique in Maple. It runs as O(n^2), where n is the number of items in the sequence. A way to avoid the inefficiency is to forego building a sequence and instead insert the items into a table. Then, after exiting the loop, convert the table to a list. Nota bene: The inefficiency of building up a sequence term by term, in Maple, though real, is not necessarily significant. For lists under a 1000 terms you may not be able to discern the difference unless it were inside an inner loop. However, for large lists it is significant To simplify this activity I wrote a procedure, ListBuffer, patterned after StringTools:-StringBuffer, that constructs a module that can be used to initialize, build, modify, and return aribitrarily sized lists. This functionality might be usefully added to the ListTools package. Here is how it could be used to solve dcasimir's request:
Nprimes := proc(n::posint)
local i,lb;
    lb := ListBuffer();
    for i while lb:-length() < n do
        if isprime(i) then
            lb:-append(i);
        end if;
    end do;
    return lb:-value();
end proc:
Download the Maple script for the procedure by clicking here.
Please Wait...