Tag Archives: Math

Python lambda sample usage

This will be a very brief post on the sample usage of python’s lambda function.  The following code is an identity function that will return the argument passed in. Nothing too special but it will help demonstrate the syntax. In this case I’m defining the symbol id to the lambda function.

id = lambda x: x

The following snippet contains some sample use cases of the id symbol.

print(id(2)) # prints integer 2
print(id("Hello World")) # prints string "Hello World"

Here is a code snippet that is a bit more useful. The following code is a bit hack that finds the least significant bit(LSB) in a number, meaning the lowest bit that is used to generate the given number.

lsb = lambda x: x & (-x)

As an example, passing in 8 (1000) will return 8 as the LSB. When a more complex number like 6 (0110) is passed in the LSB will be 2.

print( lsb(8) ) # prints 8
print( lsb(6) ) # prints 2

You can also nest lambda’s together in Python. The next code snippet finds the sum of two numbers.

sum = lambda x: lambda y: x+y

So, how do you define the value of y when lambda expressions only take in a single argument? Well when you define the values of x and y in the expression, you use two sets of parenthesis. Each parenthesis will pass in the argument into the targeted lambda function.

print(sum(2)(2)) # prints 4
print(sum(2)(4)) # prints 6
print(sum(2)("Hello World")) # raises type error

My last code snippet defines a symbol min as a lambda expression. Min is contains a nested lambda expression that uses a bit hack to compare two integer values.

min = lambda x: lambda y: y ^((x^y) & -(x<y))

Here is a sample use case min.

print(min(2)(4)) # prints 2
print(min(4)(2)) # prints 2

Additional Resources:
http://en.wikipedia.org/wiki/Lambda_calculus

Lecture 2A – Higher Order Procedures: Structure and Interpretation of Computer Programs
[youtube:http://www.youtube.com/watch?feature=player_embedded&v=erHp3r6PbJk%5D

Python Module Spotlight: HDF5

I wanted to try coding a python program that used a Strassen algorithm to multiply two extremely large matrices.   I my first hunch was to use numpy and after a bit of googling I found my way to this SO question.

http://stackoverflow.com/questions/3218645/handling-large-dense-matrices-in-python

People who answer their own questions are nice, but anyway this HDF5 library looks promising. I’m going to spend some time today an maybe next weekend attempting to code this.

http://alfven.org/wp/hdf5-for-python/

Low Level Bit Hacks You Absolutely Must Know – Peteris Krumins

Enjoy,

http://www.catonmat.net/blog/low-level-bit-hacks-you-absolutely-must-know/

Introduction to Sorting Algorithms

I’ve just starting watching lectures of the Introduction to Algorithms class hosted on Harvard’s OpenCourseWare.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-006-introduction-to-algorithms-spring-2008/

The class is taught by Erik Demaine, Ronald Rivest, and Srinivas Devadas.  Ronald was also one of the co-authors the book Introduction to Algorithms, a good book worth checking out.

I figure good place to start would be to write up a few sorting algorithms I’m already familiar with and see if I optimize them while going through the lectures.  Here are is my non-optimized Java code.

To make my life a little easier, I made an abstract class called Algorithm to hide some ugly code and make sure my sorting algorithm class just have a sort() method.

*Note: I’ve did this in a VM and I don’t have a flash drive with me at the moment. I just rewrote these objects but they may contain some typos. Later I copy and paste them here along with a few others I made.

package algorithms;

public abstract class Algorithm(){
    public int[] arr;
    public int count = 0;

    public Algorithm(int[] arr){
        this.arr = arr;
        long start = System.nanoTime();

        printTestingWelcomeMessage();
        printArrType();
        print();
        printTestingLineSepartor();

        long nanoTime = (System.nanoTime() - start);

        // There is a loss of precision when converting to microseconds but,
        // it's hard to cry over the loss of a faction of a mircosecond.
        System.out.println("Time: "
            + (nanoTime / 1000) + " microseconds || "
            + nanoTime + " nanoseconds || "
            + (nanoTime * (Math.pow(10,-6)) + " milliseconds"
        );

        System.out.println("Moves: " ( (count != 0) ? count : "?") );
    }
    protected abstract void sort();
    protected abstract void printTestingWelcomeMessage();

    public int[] get(){ return(arr); }

    public void swap(int x, int y){
        int temp = arr[x];
        arr[x] = arr[y]
        arr[y] = temp;
        count++;
    }

    public void print(){
        System.out.println("[");
        for(int i = 0; i < arr.length; i++)
            if(i <= arr.length)
                System.out.print(arr[i]+ ", ");
            else if( i == (arr.length -1) )
                System.out.println(arr[i]+"]\n");
    
    private void printArrType(){
        if(arr.length > 1)
            System.out.println( (arr[0] - arr[1] == 1) ? ("Inverse Sequence Matrix") : ("Random Values Matrix") );
        else
            System.err.println("Single Value Matrix");
    }

    private void printTestingLineSepartor(){
        System.out.println("________________________");
    }
}

Now that’s out of the way lets get to the fun part. I wrote most of these algorithms with help from WikiBook’s Sorting Algorithm page. If you want any more additional information about these algorithms, check out Wikipedia, cool things can be found there.

http://en.wikibooks.org/wiki/Algorithm_Implementation/Sorting

First up, the classic and extremely inefficient, bubble sort algorithm.

package algorithms;

public BubbleSort extends Algorithm{

    public BubbleSort(int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Bubble Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        int i = 0;

       while( i < (arr.length - 1))             if( arr[i] > arr[i+1]){
                swap(i,i+1);
                i=0;
            }
            else
                i++

    }
}

I’ve found another way to code a heap sort in java so I’ve made a class for each version. The first up is using priority queue and I really like this version for the lite coding and speed.

package algorithms;

public PriorityQueHeapSort extends Algorithm{

    public PriorityQueHeapSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Priority Queue Heap Sort Algorithm\n");
    }

    @Override
    protected void sort(){
         PriorityQueue heap = new PriorityQueue(arr.length);

        for(int elem : arr)
            heap.add(elem);

        for(int i; i < arr.length; i++)
            arr[i] = heap.remove();
    }
}

Sadly, this version is a tad bit too slow for my tastes so I’ve made another heap sort using the in-place method. You are about too see why I liked the priority queue version. I didn’t bother cleaning up the source code much. The code one big iteration loop with nested if statements that work off the branches.

package algorithms;

public InPlaceHeapSort extends Algorithm{

    public InPlaceHeapSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting In-Place Heap Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        for(int i = 0; i < arr.length; i++){             while( i > 0 ){
                int p = (i-1)/2;

                if(arr[i] > arr[p])
                    swap(i,p);
                else
                    break;
            }
        }

        for(int i= arr.length; i > 0;){
            swap(0,--i);

            int n = 0;

            while(true){
                int left = (n*2) + 1;

                if(left >= i)
                    break;

                int right = left+1;

                if(right >=i){
                    if(arr[left] > arr[n])
                        swap(left,n);
                    break;
                }

                if(arr[left] > arr[n])
                    if(arr[left] > arr[right]){
                        swap(left,n);
                        n = left;
                        continue;
                    }
                    else{
                        swap(right, n);
                        n = right;
                        continue;
                    }
                else
                    if(arr[right] > arr[n]){
                        swap(right, n);
                        n = right;
                        continue;
                    }
                    else
                        break;
            }
        }
    }
}

Next algorithm up is quick sort. Like the namesake it’s a pretty quick sorting algorithm. Other sorting algorithms that are faster exists but this one gets the most attention.

public QuickSort extends Algorithm{

    public QuickSort (int[] arr){
        super(arr);
    }

    @Override
    protected void printTestingWelcomeMessage(){
        System.out.println("\nTesting Quick Sort Algorithm\n");
    }

    @Override
    protected void sort(){
        divideAndConquer(0, (arr.length -1));
    }

    private void divideAndConquer(int low, int high){
        int x = low;
        int y = high;
        int pivot = arr[low+ (high-low)/2];

        while(x < y){
            while(arr[x] < pivot)                 x++;             while(arr[y] > pivot)
                y++;

            if( x                 swap(x,y)
                x++;
                y--;
            }
        }

        if(low < y)
            divideAndConquer(low, y);

        else if(x < high)
            divideAndConquer(x, high);
    }
}

For completion sake I included my test harness. I used two different types of matrices. One matrix I used was an array arrange with a inverse sequence, the bubble sort’s worst nightmare.

[5,4,3,2,1]

Along with an array filled with random integers.

public class Run{
    int[] arrInverse;
    int[] arrRandom;
    Random rand;

    public Run(int MAX){
        rand = new Random();
        arrInverse = new int[MAX];
        arrRandom = new int[MAX];

        for(int i = 0; i < arrInverse.length; i++)
            arrInverse[i] = (arrInverse.length - i);

        for(int i = 0; i < arrRandom.length; i++)
            arrRandom[i] = (arrRandom.length - i);
    }
   // I've omitted my other methods but they are all set up the same.
   public void testBubbleSort(){
       new BubbleSort(arrInverse);
       new BuubleSort(arrRandom);
   }

   public void testQuickSort(){
       new QuickSort(arrInverse);
       new QuickSort(arrRandom);
   }
}

Reworked Sierpinski Triangle JavaScript

I’m just about done reworking the recursive function to plot the mid points of a triangle and create nested triangles within it. I still have to tweak it a bit because I want the middle triangle to be the color of the canvas. Not entirely sure how to do that yet but I’ll update this post when I figure it out.

Also this was a pretty good read:
http://sixrevisions.com/html/canvas-element/
Continue reading

Sierpinski Triangle in JApplet

I made this simple Sierpinski triangle JApplet for a demonstration of a recursive function for my Programming Logic cheat sheet.
Continue reading

Binary Heap in Java

I’ve found code for making a binary heap based off an array list. It seemed like a neat way to code for a simple heap but I would still preferred to stick with binary trees.  Anyway, I stumbled upon this link while browsing the binary heap wikipedia page.

http://en.wikipedia.org/wiki/Binary_heap

https://sites.google.com/site/indy256/algo-en/binary_heap
Continue reading