Functional Lagrange Interpolation

I recently implemented Lagrange’s interpolation method in python, and I thought I would share it here. I’m posting it because I think it’s the most nested functions I ever used in python. I would have like to use partial functions, but python doesn’t support those (well not without using functools), so I made do with nested functions...

Probably don’t use the code in a production environment or for anything serious because it’s probably very slow. I’m 90% sure numpy has a better implementation.

# Tested on Windows 7 and Python 2.7

# the code
def lagrangian_interpolate(samples):
    """
    Takes some samples as a list of tuples and returns a function that's
    a lagrangian interpolation of all the samples.
    """
    X = 0 # the tuple index of the X variable in the samples
    Y = 1 # the tuple index of the Y variable in the samples
    n = len(samples)
    # define the L function as a function generator that generates L functions
    # for a given i
    def L(i):
        "This function generates an L function for a given x_i"
        def L_gen(x):
            ret = []
            for j in xrange(n):
                if j != i:
                    ret.append((x - samples[j][X])/(samples[i][X] - samples[j][X]))
            return reduce(lambda a,b: a*b, ret)
        return L_gen

    return lambda x: sum(L(i)(x) * samples[i][Y] for i in xrange(n))

# main
prob_1 = lagrangian_interpolate([(2,1.4142),(2.5,1.5811),(3.0,1.7321)])
print prob_1(2.2)

prob_1_b = lagrangian_interpolate([(2,1.4142),(2.5,1.5811),(2.7,1.6432)])
print prob_1_b(2.2)

prob_2 = lagrangian_interpolate([(2.0,1.4142),(2.5,1.5811),(3.0,1.7321),(3.5,1.8708)])
print prob_2(2.8)

Python super_split()

I recently needed some code that splits python strings based on multiple delimitors, so I wrote a quick function to do so. I figured it’s generally useful so I’m posting it here.

def super_split(string, delim):
    segment = ''
    for c in string:
        if c in delim:
            yield segment
            segment = ''
        else:
            segment += c
    yield segment

DMOZ Scraper

I’m really only posting this code so I can check out the syntax highlighter in jekyll.

It’s a class that scrapes URLs from Dmoz given a search term. Not fancy, I’m just using it for a machine learning project. It does what I need for now.

import mechanize
from BeautifulSoup import BeautifulSoup

class Dmoz(object):
    def __init__(self):
        self.br = mechanize.Browser()

    def get_page_urls(self, term):
        result = self.br.open("http://www.dmoz.org/search?q="+term)
        result_html = result.read()
        soup = BeautifulSoup(result_html)
        sites_obj = soup.find('ol', {"class": "site"})
        if sites_obj:
            sites = sites_obj('li')
            urls = [x('a', recursive=False)[0]['href'] for x in sites]
            return urls
        else:
            return []

def main():
    # eg:
    dm = Dmoz()
    print dm.get_page_urls("Computer Science")

if __name__ == "__main__":
    main()