Sunday, June 28, 2015

How to Find Memory Used in Computations

At some point you will need to — or just want to — push the limits of Mathematica and it may be helpful to measure memory consumed during a computation. Here are methods inspired by Wagon, Mathematica in Action (2nd ed., pp 431 et seq.). (See also Memory Management Tools.)

The first method is simple; store the initial MemoryInUse in a variable, do your calc, then subtract it from the current MemoryInUse.

currentMemory=MemoryInUse[];
{(MemoryInUse[]-currentMemory),Plus@@(1./Range@1000000)}

{1368,14.3927}

Second, suppose you want to monitor memory in several places in your code. Initialize the variable currentMemory, then sprinkle

Sow[-currentMemory+(currentMemory=MemoryInUse[])]

through your code like Print statements, and the enclosing Reap will cause each one to output the net memory consumed in bytes between the previous use and the current one. I say 'net' memory consumed because Mathematica is designed to optimize memory use and so clears memory in use every chance it gets. Following the pattern of Timing, I reverse the output to give the memory results first, then the function's output.

currentMemory=MemoryInUse[];
(*initialize s*); s=0;
Reap[Do[If[i<25,Sow[-currentMemory+(currentMemory=MemoryInUse[])]];s+=1./i,{i,1000}];s]//Reverse

{{{3016,11216,16,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}},7.48547}

Did you notice, as Wagon points out, that Do uses minimal memory during a calculation? It cleans up after every iteration.

Like Timing, this third method of checkMemory requires you to wrap your computation in checkMemory, access the result of your computation with First and if desired suppress the output with a semi-colon. Mimicking the structure of a built-in function is an example of a good programming technique. The designers of Mathematica are master programmers and they have created and debugged templates or paradigms of function structures. Often you can follow the structure of built-in functions to create sound ones of your own.

Clear@checkMemory;
checkMemory@computation_:=
Module[{computation1,preComputationMemory},
preComputationMemory=MemoryInUse[];Print["Memory in use at start is ",preComputationMemory];
computation1=computation;
memoryUsedInComputation=MemoryInUse[]-preComputationMemory;
Print["Memory in use at end is ",MemoryInUse[]];{memoryUsedInComputation,computation1}
]

Once it's done, this computation uses 32 bytes of memory and the result is 14.3927.

checkMemory[Sum[1./i,{i,1000000}]]

Memory in use at start is 31286024
Memory in use at end is 31286056
{32,14.3927}

We find the memory use with the function output for a small Table.

s1=0;checkMemory[Table[s1+=1./i,{i,10}]]

Memory in use at start is 31289472
Memory in use at end is 31289752
{280,{1.,1.5,1.83333,2.08333,2.28333,2.45,2.59286,2.71786,2.82897,2.92897}}

Then suppress output, with a semi-colon as is done in Timing, for a large Table.

checkMemory[s1=Table[1./i,{i,10^7}];]

Memory in use at start is 31340688
Memory in use at end is 111344696
{80003992,Null}

I left off the summation of the Table to show MemoryInUse during the calc. If we add Total, we see the max MemoryInUse reclaimed (-80,000,024 bytes).

Timing[checkMemory[s1=Table[1./i,{i,10^7}]//Total]]

Memory in use at start is 31359736
Memory in use at end is 31359864
{0.343202,{128,16.6953}}

Compare memory used in a Do loop. Pretty interesting!

Timing[s1=0;checkMemory[Do[s1+=1./i,{i,10^7}];s1]]

Memory in use at start is 31364400
Memory in use at end is 31364432
{10.296066,{32,16.6953}}

First@%/First@%%

30.0000

So there you have it, Do takes 30 times as long as the functional command Table[...]//Total, but uses a minute fraction of the latter's memory.

Friday, June 26, 2015

How to Query 11 Different Search Engines

You can query a search engine with URLFetch. For the URL you need a String that includes a standard prefix and a suffix that begins with something like "/?q=querykeywords". I have removed some unnecessary junk from most of the query Strings to make them as short and simple as possible.

There are several ways to functionally compose a query for a search engine. This one uses StringJoin. I use Which to handle the cases of 1) a single keyword, 2) multiple keywords, or 3) any other data type, which is an error. Using True as the third test in conditional statements is a standard way to handle 'all else' cases.

queryTemplateDuckDuckGo="https://duckduckgo.com/?q=";
keyword1="longevity";
keywords2={"machine","learning","algorithm"};

Clear@searchEngineQuery;
searchEngineQuery[searchEnginePrefix_String, keywords_] := 
 Module[{url},
  Which[
   Head@keywords === String, 
   url = StringJoin[searchEnginePrefix, keywords],
   Head@keywords === List, 
   url = StringJoin[searchEnginePrefix, 
     Table[i <> "+", {i, Most@keywords}], Last@keywords],
   True, Print@"Error: wrong data type."];
  Print@url;
  URLFetch@url
  ]

We test it on a single keyword (I omit the full output, which you can try at home).

searchEngineQuery@keyword1

https://duckduckgo.com/?q=longevity

We try it on a List of keywords.

searchEngineQuery@keywords2

https://duckduckgo.com/?q=machine+learning+algorithm

We try it on a wrong data type.

searchEngineQuery[queryTemplateDuckDuckGo, 5]

Error: wrong data type.

And here are sample fetches for the search engines. Again, I omit the full output but you can try them yourself. I precede each sample with a rating the quality of 'cleanliness' of results by StringLength, the idea being that the shorter length results Strings have less junk in them and more of the actual results. By that measure DuckDuckGo, Blekko and Alhea give the 'cleanest' output for further processing. But don't misconstrue that measure as a quality rating of the results themselves.

StringLength/@{%365,%366,%368,%370,%372,%374,%376,%378,%380,%382,%384}

{42192,11496,80722,94714,164072,117642,19161,42104,14660,104627,21239}


11 Search Engines Queried



Google: 42,192


URLFetch["https://www.google.com/search?q=atherosclerosis"]

DuckDuckGo: 11,496


URLFetch["https://duckduckgo.com/?q=atherosclerosis"]

Bing: 80,722


URLFetch["http://www.bing.com/search?q=atherosclerosis"]

Ask.com: 94,714


URLFetch["http://www.ask.com/web?qsrc=1&o=2545&l=dir&q=\
atherosclerosis"]

AOL: 164,072


URLFetch["http://search.aol.com/aol/search?s_it=searchbox.webhome&v_t=\
na&q=atherosclerosis"]

Wow: 117,642


URLFetch["http://www.wow.com/search?s_it=search-thp&v_t=na&q=\
atherosclerosis&s_qt=ac"]

InfoSpace: 19,161


URLFetch["http://search.infospace.com/search/web?q=atherosclerosis&\
searchbtn=Search"]

Info: 42,104


URLFetch["http://www.info.com/search?qcat=web&r_cop=xxx&qkw=\
atherosclerosis"]

Blekko: 14,660


URLFetch["http://blekko.com/#ws/?q=atherosclerosis"]

DogPile: 104,627


URLFetch["http://www.dogpile.com/info.dogpl/search/web?fcoid=417&fcop=\
topnav&fpid=27&q=atherosclerosis&ql="]

Alhea: 21,239

URLFetch["http://www.alhea.com/search/web?fcoid=417&fcop=topnav&fpid=\
27&q=atherosclerosis&ql="]


Thursday, June 25, 2015

Recursive Programming on Lists (Arrays): Map

Here is a simple recursive mapping function. This is a recursion on Lists (arrays) with arbitrary argument types, not numbers.

Recall that Map is a classic functional-style, 'structural' command since it leads us to think in terms of applying a function to an entire structure, such as an array (a List in Mathematica). The Map function saves us the trouble of 'deconstructing' the array with a Do or For loop as in procedural programming.

We define a base case and a recursive case:

1. Base case: If the source List is empty, just return it

2. Recursive case: Call itself on the Rest of each successively smaller sub-List

Clear@recursiveMap;
recursiveMap[function_,aList_List]:=
If[aList=={},{},
Prepend[recursiveMap[function,Rest@aList],function@First@aList]]

We test the base case:

recursiveMap[f,{}]

{}

We test some recursive cases:

recursiveMap[f,{a,b,c}]

{f[a],f[b],f[c]}

recursiveMap[f,Range@5]

{f[1],f[2],f[3],f[4],f[5]}

How does it work? You can go through the Trace, but essentially by calling itself repeatedly on the Rest of list (via the first, recursive 'clause' of recursiveMap, recursiveMap[function,Rest@list]), it constructs successively smaller sub-Lists and eventually hits the empty List, which is the base case. 

Then it begins 'unwinding' and Prepend and the second clause of recursiveMap is repeatedly invoked (function@First@list). Starting with the last List of a single element (c in this Trace), it applies the function f to the First element of each sub-List and Prepends it to a growing List of results until the First element of the entire list is Prepended.

Trace@recursiveMap[f,{a,b,c}]

{recursiveMap[f,{a,b,c}],If[{a,b,c}=={},{},Prepend[recursiveMap[f,Rest[{a,b,c}]],f[First[{a,b,c}]]]],{{a,b,c}=={},False},If[False,{},Prepend[recursiveMap[f,Rest[{a,b,c}]],f[First[{a,b,c}]]]],Prepend[recursiveMap[f,Rest[{a,b,c}]],f[First[{a,b,c}]]],{{Rest[{a,b,c}],{b,c}},recursiveMap[f,{b,c}],If[{b,c}=={},{},Prepend[recursiveMap[f,Rest[{b,c}]],f[First[{b,c}]]]],{{b,c}=={},False},If[False,{},Prepend[recursiveMap[f,Rest[{b,c}]],f[First[{b,c}]]]],Prepend[recursiveMap[f,Rest[{b,c}]],f[First[{b,c}]]],{{Rest[{b,c}],{c}},recursiveMap[f,{c}],If[{c}=={},{},Prepend[recursiveMap[f,Rest[{c}]],f[First[{c}]]]],{{c}=={},False},If[False,{},Prepend[recursiveMap[f,Rest[{c}]],f[First[{c}]]]],Prepend[recursiveMap[f,Rest[{c}]],f[First[{c}]]],{{Rest[{c}],{}},recursiveMap[f,{}],If[{}=={},{},Prepend[recursiveMap[f,Rest[{}]],f[First[{}]]]],{{}=={},True},If[True,{},Prepend[recursiveMap[f,Rest[{}]],f[First[{}]]]],{}},{{First[{c}],c},f[c]},Prepend[{},f[c]],{f[c]}},{{First[{b,c}],b},f[b]},Prepend[{f[c]},f[b]],{f[b],f[c]}},{{First[{a,b,c}],a},f[a]},Prepend[{f[b],f[c]},f[a]],{f[a],f[b],f[c]}}

Source: David Wagner


Wednesday, June 24, 2015

Using Recursion to Define a Periodic Function

I'm working my way through Heikki Ruskeepaa's book, Mathematica Navigator and found this elegant one-liner that shows how to define a periodic function with recursion. Note that the base case required to stop the recursion is not a single value but the condition 0 <= t <= 2.

Clear@sawtooth;sawtooth[time_,scale_:1]:=If[0<=time<=2,scale time,sawtooth[scale (time-2)]]
Plot[sawtooth@t,{t,0,10}]



How does the recursion work? If t => 2, sawtooth keeps subtracting 2 from t recursively until t is back in the range 0 <= t <= 2 and uses the computes that value for y. We can see sample values of a function plotted with DiscretePlot.

DiscretePlot[sawtooth@t,{t,0,6,0.2},PlotTheme->"Web"]



Of course a faster way of defining the domain is to use Mod, but there is a lesson here. We don't need the speed of Mod, so either implementation is fine - using Mod for the most compact and fast function, or using an elegant new recursive technique to learn it. This function omits the values at multiples of 2, but is effectively the same function:

Clear@sawtooth2;sawtooth2[time_,scale_:1]:=scale Mod[time,2]

Mathematica has built-in functions to produce various canonical waveforms  such as SawtoothWave. We are working with sawtooth and triangle waves in the lab since, interestingly, there is a lot of nonlinearity at the electrode-tissue interface and in the kHz+ frequency range, a rectangular wave is transformed by what is called partial half-wave rectification into something like a triangle offset in the negative (cathodic) direction from V = 0. We believe this is a key to understanding how biphasic neuromodulation works in the kHz+ frequency range.

Plot[SquareWave[{-50,50},t],{t,0,10},ExclusionsStyle->Dotted,AxesLabel->{"time (mS)","mV"},PlotLabel->"Electric potential at the electrode"]




Plot[TriangleWave[{-40,10},t],{t,0,10},AxesLabel->{"time (mS)","mV"},PlotLabel->"Electric potential seen by the axon"]




Saturday, June 20, 2015

Recursive Programming: The General Principle

Recursion, where a function calls itself, is a fundamental programming method. Recursion is a different way of iterating over a List than using a loop. Recurse is from the Latin recurrere, to run back (I picture a dog retrieving a stick over and over).

There are two principles of writing a recursive function, which is piecewise:
  1. Recursive case: Define a function f(n+1) recursively in terms of f(n), or equivalently, f(n) in terms of f(n-1)
  2. Base case: Define one or more base cases, which are stopping points for the recursion, so that it doesn't become infinite. 
An elementary example is exponentiation defined this way:

x= x•x(n-1)

First we define the base case, so that Mathematica will match it to prevent an infinite recursive loop. Let's just consider positive integers and zero. The base case is any integer raised to the 0th power equals 1.

exponentiation[x_,0]:=1;

The recursive case is:

exponentiation[x_,n_Integer/;x>0]:=x exponentiation[x,n-1]

Start testing a recursive function with the simplest examples:

exponentiation[0,0]
1

exponentiation[1,0]
1

exponentiation[1,1]
1

Let's make sure the Condition requiring x > 0 works; it does.

exponentiation[1,-1]
exponentiation[1,-1]

Trace shows the exponentiation hitting the base case and stopping.

exponentiation[1,1]//Trace
{exponentiation[1,1],1 exponentiation[1,1-1],{{1-1,0},exponentiation[1,0],1},1 1,1}

To compute 22, the function calls itself to computer 22-1 i.e. 21, which in turn calls itself to compute 20, which is the base case, 1. Once it has recursed down to the base case, it has a value to substitute in the preceding computations and the recursion 'unwinds.' All recursive functions work this way.

exponentiation[2,2]//Trace
{exponentiation[2,2],2 exponentiation[2,2-1],{{2-1,1},exponentiation[2,1],2 exponentiation[2,1-1],{{1-1,0},exponentiation[2,0],1},2 1,2},2 2,4}

exponentiation[2,10]
1024

exponentiation[2,100]
1267650600228229401496703205376

exponentiation[2,1000]
10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

Use Block for Large Recursions and Debugging


You may run into the built-in default recursion limit, $RecursionLimit, of 1024 when performing a large recursion.

In[584]:= exponentiation[2,10000]
During evaluation of In[584]:= $RecursionLimit::reclim: Recursion depth of 1024 exceeded. >>
Out[584]= Hold[exponentiation[2,8978-1]]

The safe way to exceed the limit is using Block. Block temporarily changes the value of a Global or System variable. I've suppressed the output here since it is 3,011 digits long, but you can try this safely at home without "//IntegerDigits//Length".

Block[{$RecursionLimit=10050},exponentiation[2,10000]]//IntegerDigits//Length
3011

Mathematica will warn you and stops an infinite recursion with a default recursion limit specified by $RecursionLimit ($IterationLimit is used similarly to stop infinite loops).

{$RecursionLimit,$IterationLimit}
{1024,4096}

Just as you can use Block to temporarily exceed $RecursionLimit, you can use Block to temporarily 'tighten up' $RecursionLimit while writing a recursive function.

In[592]:= Block[{$RecursionLimit=20},factorial@x_:=x*factorial[x-1];factorial@2]
During evaluation of In[592]:= $RecursionLimit::reclim: Recursion depth of 20 exceeded. >>
Out[592]= Hold[factorial[-14-1]]

Always remember to write the base case rule!

In[593]:= Block[{$RecursionLimit=20},factorial@x_:=x*factorial[x-1];factorial@0=1;factorial@2]
Out[593]= 2

Now we may safely compute the factorial of larger numbers:

factorial@200

788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000

Note all the zeroes at the end. They must be from each time a multiple of 10 is incorporated into the factorial.

Tuesday, June 9, 2015

File Operations: Find and Print Files in Mathematica

It's easy to find files in Mathematica with FindFiles and wildcards. The only thing you have to remember is that the 2nd argument, which specifies the directories to search must be a List even if you only specify one directory.

What did I put in my init.m files to automatically load Packages? Let's find and print init.m. A directory intended for a user's init.m file $UserBaseDirectory<>Kernel.

folderToSearch=FileNameJoin@{$UserBaseDirectory,"Kernel"}
C:\Users\kwcarlso\AppData\Roaming\Mathematica\Kernel

The wildcard will retrieve all files in the directory.

filePath=FileNames["*",folderToSearch]
{C:\Users\kwcarlso\AppData\Roaming\Mathematica\Kernel\init.m}

We use FilePrint to print it. Use First@ or Sequence@@ to remove the unnecessary List brackets around the filepath.

FilePrint@First@filePath
(*
(** User Mathematica initialization file **)

Print@"Hello World from your kernel init.m file! I'm located in:\n
C:\\Users\\kwcarlso\\AppData\\Roaming\\Mathematica\\Kernel.\n"

Print@"Loading C:\\Users\\kwcarlso\\AppData\\Roaming\\Mathematica\\Scribble.m\n"
<<"C:\\Users\\kwcarlso\\AppData\\Roaming\\Mathematica\\Scribble.m"

Print@"Loading C:\\Users\\kwcarlso\\Dropbox\\Mathematica\\Initialization\\Pre-Load Functions.txt.\n"
<<"C:\\Users\\kwcarlso\\Dropbox\\Mathematica\\Initialization\\Pre-Load Functions.txt"

(* put this in Pre-Load Functions at some point? 
On[General::newsym] *)

Print@"Loading C:\\Program Files\\Wolfram Research\\Mathematica\\9.0\\AddOns\\ExtraPackages\\Utilities\\cleanSlate.m\n"
<<"C:\\Program Files\\Wolfram Research\\Mathematica\\9.0\\AddOns\\ExtraPackages\\Utilities\\cleanSlate.m"
*)

Suppose we wanted to search for all files of a given type in Mathematica's default List of filepaths, $Path, like "init.m". Important! Note that $Path includes the root directory "." and my user root directory "C:\Users\kwcarlso." We don't want to search those so we find their Positions in $Path (need to add a backslash to the path separators since a single backslash tells Mathematica to treat the following character specially and a double backslash is treated as a single backslash).

omitPaths=Position[$Path,#]&/@{".","C:\\Users\\kwcarlso"}
{{{8}},{{9}}}

Using Drop to lose the directories at the two Positions we found, we search the remaining ones but still get far too many files. You can evaluate this command in your Notebook if you wish.

tooManyFiles=FileNames["init.m",Drop[$Path,Flatten@omitPaths],Infinity];

So let's just specify the directories that we want with the inner List in Part.

desiredDirectories=$Path[[{2,3,5}]]
{C:\Users\kwcarlso\AppData\Roaming\Mathematica\Kernel,C:\Users\kwcarlso\AppData\Roaming\Mathematica\Autoload,C:\ProgramData\Mathematica\Kernel}

autoloadFileNames=FileNames["*",desiredDirectories]
{C:\ProgramData\Mathematica\Kernel\init.m,C:\Users\kwcarlso\AppData\Roaming\Mathematica\Autoload\PacletManager,C:\Users\kwcarlso\AppData\Roaming\Mathematica\Kernel\init.m}

To search all subdirectories in the directories, add a third argument, "Infinity", or an integer to limit the depth searched.

autoloadFileNames=FileNames["*",desiredDirectories,Infinity];

Use Block to Temporarily Block Global Variables

The main Mathematica scoping function to learn is Module. For occasional special purposes, use Block to temporarily store and then restore Global variables, and use With to fix local variables so they can't be accidentally changed inside of With.

Use any Doc Center page for a scratchpad (not Block), since all variable names and values are localized to that page and are automatically cleaned up when you leave the page.

Block does two things:
  1. Temporarily stores a Global variable value and then restore it
  2. Uses a local value for the variable in the Block if you give it one
Here is a step-by-step example of how Block works.

x=17;
Block[{x=4},x^2]
16

x
17

Step
Effect
x = 17;
Variable x is Set to 17 in the Global` Context
Block[{x=4},x^2]
A Block is entered using specifying a local variable with the same name as the Global one (x = 4)
Within Block: x$23 = x
Local, temporary variable x$23 is Set to x’s global value of 17
Within Block: x = 4
Local, temporary variable x is Set to 4
Within Block: x^2
In Power[x, 2] x replaced by 4: Power[x, 2] /. x -> 4
Block returns 4^2 = 16
Locally with Block Power[x, 2] evaluates to 16, which is returned
Block Sets x = x$23 and exits
The Global value of x is restored
x
The Global values of x is called
17
The Global value of x is returned

Typical Uses of Block

Block is used to scope and protect the iterators in Table, Do, Sum, etc. If you write a function with an iterator you can use Block.

More typical uses of Block are to change the value of system environment variables such as decreasing $RecursionLimit or $IterationLimit to prevent infinite looping while you're debugging a function, or increasing them to solve a deeply nested or iterated calculation.

An interesting combinatorial series arises from the number of partitions of integer sets, the Bell number. Pemmaraju and Skiena compute it recursively. To let the function solve for indefinitely large sets, $RecursionLimit is temporarily set to Infinity within the Block and automatically restored to its default value after execution.

Clear[bellB,bellB1];

bellB@n_Integer:=bellB1@n;
bellB1@0=1;(*base case*)

bellB1@n_:=Block[
{$RecursionLimit=Infinity},
bellB1@n=Sum[Binomial[n-1,k]*bellB1@k,{k,0,n-1}] (*memo function*)
]

bellB/@Range@10
{1,2,5,15,52,203,877,4140,21147,115975}

$RecursionLimit

1024

Why Block Might Not Seem to Work

Again, if you understand that Block will 1) temporarily store a Global variable value and then restore it, and 2) use a local value for the variable in the Block only if you give it one, you will understand the following examples. First, we Set x equal to 25 in Global`.

x=25;

Here x isn't scoped and so isn't Blocked; Mathematica can't just assume you wanted it localized.

Block[{},x]
25

Here x is scoped but we didn't assign it a new value. So while its global value of 25 was stored in a temporary variable it was also used in Block.

Block[{x},x]
25

Now we assign a value to x in Block's scope, or in its body. Block works as intended.

Block[{x=5},x]
5

Block[{x},x=5]
5

And x's Global value was restored as Block closed itself out. All is good in the universe :-)

x
25


Block Compared with Module and With

Block and Module let us change scoped variable values in the body of their code.

Block[{x=5},Print@x;x=50;x]
5
50

Module[{x=15},Print@x;x=100;x]
15
100

But With does not; we get an error message. When we try to Set x to 8, Mathematica sees "2 = 8":

With[{x=2},Print@x;x=8;x^2]
2
Set::setraw: Cannot assign to raw object 2. >>
Out[292]= 4

Block and Module immediately use scoped variable values, so here Mathematica sees "5^2 /. 5 -> 6", evaluates 5^2 as 25 and thus sees "25 /. 5 ->6"; there's no x to replace.

Block[{x=5},x^2/.x->6]
25

Module works by creating a special local variable name for each scoped variable. Here, within the Module, x lives on under the new name "x$485":

Module[{x},Print@x]
x$485