Expressing Computational Complexity in Job Estimates

The complexity module parses and processes jobestimate or gb_memory parameters that use Big-O notation to make statements about the complexity of the task they are to run. This is not a highly engineered or terribly elegant piece of code, so there are lots of ways to produce ill-diagnosed syntax violations. See Hacks – Egregious.

Syntax:

jobestimate = O(estimate)

estimate can include the following small vocabulary of terms:

Q, unit, function, and operator::

estimate := Q*unit or function(Q*unit) or function(Q+Q*unit)

[The behavior of this one, function(Q+Q*unit), is questionable, sorry]

• Q -> either a TIME, for a jobestimate, or a SPACE, for gb_memory
• unit can be one of samples,chr21,lines,size
• function can be one of log(),sqrt(),square(),cube()
• operator, either + (addition) or * (multiplication)
• TIME is of the form H20M30 or 20:30:00 (in the second form, seconds are required)
• SPACE is a number plus one of the forms MB, GB, or (heaven forfend) TB, e.g., 20GB or 200MB.

The estimate should include Q times a unit at least.

units:

samples -> (number of samples)
chr21 -> length of each human chromosome divided by the length of chromosome 21
lines -> (number of lines in file)/100
size -> (size of file)/10000

functions:

log() -> log base 10 of argument (one of samples,chr21,lines,size)
sqrt() -> square root of argument (one of samples,chr21,lines,size)
square() -> square of argument (one of samples,chr21,lines,size)
cube() -> argument cubed (one of samples,chr21,lines,size)

Examples:

jobestimate = O(H01*samples)
jobestimate = O(M30*square(samples))
gb_memory = O(1GB+1GB*chr21)