Speeding up code using Cython

The graph below compares a brute-force depth first search in Sage/Python (red line) to an implementation of the same algorithm in Cython (blue line). Vertical axis is run time in seconds, horizontal axis is number of latin square completions generated:

Cython does pretty well, and the code is far more readable than the earlier C++ version that I wrote.

For more about writing Cython code in Sage, see Chapter 5 of the documentation.

Archived Comments

Date: 2008-03-03 18:38:36 UTC

Author: Robert Samal

Hi, thanks for the interesting comparison.
How does Cython compare to C/C++?

Thanks,

Robert Samal

Using ‘yield’ to simulate a Markov chain

One thing that I really like about Sage is that it uses Python as its underlying language. This means that we get “for free” many nice features of Python. One of these features that I particularly like is the yield keyword. Here is a small example:

def foo():
    i = 0
    while True:
        yield i
        i = i + 1

We can use the foo function as a generator:

sage: g = foo()
sage: print g.next()
0
sage: print g.next()
1
sage: print g.next()
2

In other words, the yield keyword acts as a way to a Python function into a generator. The execution of foo is paused until the next call to g.next(). If we reach the end of the function, the StopIteration exception is raised.

The yield keyword makes it pretty easy to write the skeleton for a Markov chain simulator, using the following basic form:

def markov_chain():
    state = initial_state()
    while True:
        yield state

        state = new_state(state)

        if some_condition: return

For a real example, see the latin_square_generator function in latin.sage which is part of a small library for latin square manipulations in Sage. The Markov chain itself was given by Jacobson and Matthews in “Generating uniformly distributed random Latin squares,” Journal of Combinatorial Designs, vol 4, 1996, no 6, pp 405–437.

MetaPost Examples

2008-10-19: I use PyX instead of Metapost. It’s based on Python so the syntax is clear and straightforward, and is easily used from Sage (install with “sage -python setup.py install” from the PyX source directory).

Introduction

My favourite package for drawing diagrams is MetaPost. Here’s an example, taken from my PhD thesis:

Metapost diagram

The best page for examples is the one by (La)TeX Navigator.

Compiling with LaTeX fonts

Normally MetaPost uses TeX to compile but it is nicer to have access to LaTeX fonts/symbols/etc. To do this put the following at the top of your MetaPost file:

verbatimtex
documentclass[12pt]{article}

usepackage{amsmath}
usepackage{amssymb}
usepackage{amsthm}

begin{document}
etex

Then set the TEX environment variable and compile. For example, in
Bash, you could do:

$ export TEX=latex && mpost case1.mp

My examples

Here are all the MetaPost diagrams from my PhD thesis. There are a few duplicates and some dodgy code, I make no claim of being an expert in MetaPost.

metapostexamples.pdf

Browse files

All files in a compressed
tar archive

Metapost to PDF

A few of my Metapost files use the following TEX function (copied from here):

vardef TEX primary s =
   write "verbatimtex"                    to "mptextmp.mp";
   write "documentclass[12pt]{article}"  to "mptextmp.mp";
   write "usepackage[T1]{fontenc}"       to "mptextmp.mp";
   write "usepackage{amsmath,amssymb}"   to "mptextmp.mp";
   write "begin{document}"               to "mptextmp.mp";
   write "etex"                           to "mptextmp.mp";
   write "btex "&s&" etex"                to "mptextmp.mp";
   write EOF                              to "mptextmp.mp";
   scantokens "input mptextmp"
enddef;

The command mptopdf seems to have trouble with the temporary file mptextmp.mp. In particular I got this error when doing mptopdf bug.mp:

This is MetaPost, Version 0.901 (Web2C 7.5.5)
(/usr/share/texmf-texlive/web2c/natural.tcx)
(bug.mp (mptextmp.mp
>> mptextmp.mp
>> mptextmp.mpx
! Unable to make mpx file.
l.5 btex
         1 etex
Transcript written on bug.log.
 error in metapost run : bug.mp:5

        total run time : 0 seconds

MPtoPDF 1.3 : error while processing mp file

On the other hand, this seems to work:

mpost bug.mp
mptopdf bug.1

I’m not sure why this is the case – is this a bug or just undocumented behaviour?

Other stuff

MetaFun looks good. It’s also worth checking out what other peope have tagged as metapost on del.icio.us.

1st Istanbul design theory and combinatorics conference

In June 2008 there will be a design theory and combinatorics conference in Istanbul:

This is the second announcement for The 1st Istanbul Design Theory and Combinatorics Conference in honor of 70th birthday of Curt Lindner that will be held from 16th to 20th of June 2008 at Koç University, Turkey.

Please feel free to FORWARD THIS ANNOUNCEMENT to OTHER COLLEAGUES and STUDENTS that may be interested in attending to the conference.

The web page of the conference was updated recently. You can find more information about the registration, accommodation options and the cost of the conference.

We will be delighted to see all of you in Istanbul. Please fill in the pre-registration form in the webpage of the conference as soon as possible if you haven’t done so. There is no obligations attached to filling the Pre-Registration form. This information is very important for us to have an estimate on the number of participants.

For more information please refer to the conference webpage.

For all other questions please e-mail to: design@ku.edu.tr

Yours Sincerely

SULE YAZICI and SELDA KUCUKCIFCI

Installing Minion Pro fonts

Introduction

This post describes how to install Minion Pro fonts. It was originally written for Ubuntu 7.04/7.10 but seems to work on systems as new as Debian Wheezy, ElementaryOS, and Linux Mint 15. It should work for any modern Linux distribution with TexLive. Some readers have been able to adapt these instructions for OSX (see the comments at the end of this post and also http://jklukas.blogspot.com/2010/02/installing-minionpro-tex-package.html). Also, someone has translated this post into Japanese. Cool 🙂 And here is a shell script: https://github.com/jonkeane/MinionProforLaTeX.

We will install to /usr/local/share/texmf. Check that this matches the definition of TEXMFLOCAL in your installation:

$ kpsexpand '$TEXMFLOCAL'
/usr/local/share/texmf

It is vital that you install to the right path in /usr/local.

Install mnsymbol

Click on mnsymbol and download the entire directory as mnsymbol.zip.

unzip mnsymbol.zip
cd mnsymbol/tex
latex MnSymbol.ins
mkdir -p /usr/local/share/texmf/tex/latex/MnSymbol/
mkdir -p /usr/local/share/texmf/fonts/source/public/MnSymbol/
mkdir -p /usr/local/share/texmf/doc/latex/MnSymbol/
cp MnSymbol.sty /usr/local/share/texmf/tex/latex/MnSymbol/MnSymbol.sty
cd ..
cp source/* /usr/local/share/texmf/fonts/source/public/MnSymbol/
cp MnSymbol.pdf README /usr/local/share/texmf/doc/latex/MnSymbol/
mkdir -p /usr/local/share/texmf/fonts/map/dvips/MnSymbol
mkdir -p /usr/local/share/texmf/fonts/enc/dvips/MnSymbol
mkdir -p /usr/local/share/texmf/fonts/type1/public/MnSymbol
mkdir -p /usr/local/share/texmf/fonts/tfm/public/MnSymbol
cp enc/MnSymbol.map /usr/local/share/texmf/fonts/map/dvips/MnSymbol/
cp enc/*.enc /usr/local/share/texmf/fonts/enc/dvips/MnSymbol/
cp pfb/*.pfb /usr/local/share/texmf/fonts/type1/public/MnSymbol/
cp tfm/* /usr/local/share/texmf/fonts/tfm/public/MnSymbol/

Regenerate the indexes and enable MnSymbol:

mktexlsr
updmap-sys --enable MixedMap MnSymbol.map

You should be able to compile mnsymbol-test.tex with no errors.

Install the MinionPro package

We will need a few files from here: http://www.ctan.org/tex-archive/fonts/minionpro/.

Download scripts.zip and unpack it:

mkdir minionpro-scripts
cd minionpro-scripts
unzip ../scripts.zip

Copy your OTF fonts into the local directory.

find /youradobefonts/ -iname '*minion*pro*otf' -exec cp -v '{}' otf/ ';'

Hint: Adobe Reader ships with some Minion Pro fonts.

Make sure you have the latest version of lcdf-typetools and then convert the fonts:

sudo apt-get install lcdf-typetools
./convert.sh

Install the fonts:

mkdir -p /usr/local/share/texmf/fonts/type1/adobe/MinionPro/
cp pfb/*.pfb /usr/local/share/texmf/fonts/type1/adobe/MinionPro/

Determine which version of the Adobe fonts you have. For example, I have the “002.000” family:

$ otfinfo -v ~/Desktop/minionpro-scripts/otf/MinionPro-Regular.otf
Version 2.015;PS 002.000;Core 1.0.38;makeotf.lib1.7.9032

You need to download one of the following encoding files:

Version | Encoding file
------------------------
001.000 | enc-v1.000.zip
001.001 | enc-v1.001.zip
002.000 | env-v2.000.zip

The last few steps:

cd /usr/local/share/texmf
unzip ~/Desktop/metrics-base.zip
unzip ~/Desktop/metrics-full.zip
unzip ~/Desktop/enc-X.XXX.zip        (pick your version)

Edit /etc/texmf/updmap.d/10local.cfg and add the following line:

Map MinionPro.map

Regenerate all indexes:

mktexlsr
update-updmap
updmap-sys

You should see a line like this:

updmap-sys: using map file `/usr/local/share/texmf/fonts/map/dvips/MnSymbol/MnSymbol.map'

You should now be able to compile minionpro-test.tex with no errors.

You might see this error on large documents:

Font OMS/MnSymbolS/m/n/17.28=MnSymbolS12 at 17.28pt not loaded: Not enough room left.

On texlive-2009 systems, you may be able to edit /etc/texmf/texmf.d/95NonPath.cnf and change

font_mem_size = 500000

to

font_mem_size = 5000000

or some other large value. Then run

update-texmf

I’m not sure about newer versions of TexLive, e.g. http://tug.org/pipermail/tex-live/2012-November/032677.html.

Archived Comments

Date: 2008-11-23 05:59:10 UTC

Author: Marcello

I wanted to install minionpro fonts in order to use them
in my thesis document.
Your instructions are great and simplify alot a quite complicated procedure. Thank you very much Carlo!!!

Date: 2009-02-06 00:34:09 UTC

Author: Marc

Hi from Paris/France,
Thanks a lot for this tutorial. I strictly followed your instructions and everything went fine.
My system : Debian Lenny on 386 and a classic latex installation via aptitude.
On debian, Adobe fonts are in /usr/lib/Adobe, so it’s on this directory I had to “find”.
Real great job ! Thx !
Marc

Date: 2009-04-06 10:17:06 UTC

Author: Alex

Dear Carlo,

it works like a charm! Thanks a lot!

Mail me your address, i’ll send you some selfmade wine.

Thank you so much!
Alex

Date: 2009-05-12 09:01:18 UTC

Author: Noel Dela Cruz

thanks

Date: 2009-05-12 09:02:01 UTC

Author: Noel Dela Cruz

This is great hope to used it regularly

Date: 2009-06-11 06:02:02 UTC

Author: svat

Thanks a lot for this detailed tutorial! Although I’m using Mac OS X with TexLive (MacTeX) 2008, it worked perfectly for me, with only minor modifications:
* I used ~Library/texmf instead of /usr/local/share/texmf everywhere
* Some of the commands required sudo
* There was no update-updmap, nor was there a /etc/texmf/updmap.d/, but running “sudo updmap-sys –enable Map=MinionPro.map” did the trick.

I’m amazed by how well it all worked; thanks again for the perfectly clear instructions!

Date: 2009-07-27 09:32:56 UTC

Author: John

Thanks! Very clear!
Some people might also need to unzip the opticals file (I think).
Oh, for the mac it’s “- – enable” (there two dashes there).

Date: 2009-09-15 13:03:58 UTC

Author: lydia

I am more or less a Latex noob and am not that familiar to working with the terminal. I use mac os x. I managed to do the copying but when I try to do the mtexlsr (what’s that for anyways?) it echoes command not found, the same with udpmap-sys.
thx for your help!

Date: 2009-12-22 11:39:17 UTC

Author: Jamie Bullock

I also used these fonts for my PhD thesis, and this tutorial was a lifesaver! Many many thanks!

Date: 2011-12-04 22:06:31 UTC

Author: Thomas

I still don’T know how to use it in my latex document.

usepackage{minion} doesn’t work.

————-

I ran latex on a file called ‘MinionPro.dtx’. Or was it ‘MinionPro.ins’? Anyway, it was contained in the MinionPro Source.Zip Package from CTAN. Namely, in they subdirectory called “tex”.

Date: 2013-03-14 02:01:50 UTC

Author: Dane

Thanks for this write-up. When you link to mnsymbol, you should leave off the trailing slash, otherwise the link to download it as a zip archive isn’t available (CTAN’s server is a little finicky)

Date: 2013-03-14 07:24:08 UTC

Author: carlo

Dane: fixed, thanks. It looks like CTAN changed their web design recently. Never noticed the trailing-slash issue before.

Date: 2013-10-29 12:49:32.326749 UTC

Author: John

Also Carlo, if you are updating anyway i found a small change. updmap has been updated and running update-updmap returns that it is an outdated process and should use updmap-sys instead. It does include it still but says to expect inconsistencies.

Thanks for the great tutorial, really, really, really thankful.

Date: 2013-11-28 10:34:08.960239 UTC

Author: Sascha

Thanks for the guide! You saved my live.

Just a small update:

I use Ubuntu 13.10 and /etc/texmf/updmap.d/10local.cfg does not exist anymore. I created it but update-updmap throws the following warning:

Old configuration style found in /etc/texmf/updmap.d

For now these files have been included, but expect inconsistencies.

In the end it worked for me but maybe one should edit the file /var/lib/texmf/updmap.cfg-DEBIAN instead (on Ubuntu 13.10).

Also, I never saw this line: updmap-sys: using map file `/usr/local/share/texmf/fonts/map/dvips/MnSymbol/MnSymbol.map’

Date: 2015-03-28 05:49:23.528116 UTC

Author: exl

Everything works to the point of

sudo mktexlsr

Then when I try the last command, I get this error:

updmap: resetting $HOME value (was /Users/xx) to root’s actual home (/var/root).
updmap is using the following updmap.cfg files (in precedence order):
/var/root/Library/texlive/2014/texmf-config/web2c/updmap.cfg
/usr/local/texlive/2014/texmf-config/web2c/updmap.cfg
/usr/local/texlive/2014/texmf-dist/web2c/updmap.cfg
updmap is using the following updmap.cfg file for writing changes:
/var/root/Library/texlive/2014/texmf-config/web2c/updmap.cfg
/var/root/Library/texlive/2014/texmf-config/web2c/updmap.cfg unchanged. Map files not recreated.
updmap: Updating ls-R files.
[Macintosh-25:texlive/2014/texmf-config] xxlin%
[Macintosh-25:texlive/2014/texmf-config] xxlin%

So close, but not working. Any guidance would be much appreciated!