Generating all possible postfix expressions

The following Java program returns the list of all possible postfix expressions for a given list of operands and operators. The number of all postfix expressions grows exponentially with the number of operands and is around 5 billion for 10 operands and 4 operators (*,+,/,-). The precise number of all possible postfix expressions is C(n-1)*(noOfOperators^(n-1)) where n is the number of operands and C(n-1) is the n-1th Catalan number.

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class PostfixExpressionGeneratorSansRecursion {
	private static final String [] OPERATORS = new String[] {"*", "+", "/", "-"};
	
	public static void main(String[] args) {
		List<String> x = new ArrayList<String>();
		x.add("1");
		x.add("2");
		x.add("3");
		x.add("4");
		
		for (String ex : generateAllPostfixExpressions(x)){
			System.out.println(ex);
		}
	}
	
	/**
	 * Assumes input is a list of single digit positive numbers.
	 * @param operands
	 * @return list of all possible postfix expressions for the given list of operands
	 */
	private static List<String> generateAllPostfixExpressions(List<String> operands) {
		List<String> allPossiblePostFixExprs = new ArrayList<String>();
		Stack<String> stack = new Stack<String>();
		stack.push(""); //start with a empty partial expression
		int finalPFExprLength = 2*operands.size() - 1;
		int sizeOfOperands = operands.size();
		
		while (!stack.isEmpty()) {
			String partialExpr = stack.pop();
			int partialExprLength = partialExpr.length();
			
			if (partialExprLength == finalPFExprLength) {
				allPossiblePostFixExprs.add(partialExpr);
				continue;
			}
			
			int noOfOprdsConsumed = 0;
			for (char c : partialExpr.toCharArray())
				noOfOprdsConsumed += Character.isDigit(c) ? 1 : 0;
			
			if (2*noOfOprdsConsumed - partialExprLength > 1)
				for (String op : OPERATORS)
					stack.push(partialExpr + op);
			
			if (noOfOprdsConsumed != sizeOfOperands)
				stack.push(partialExpr + operands.get(noOfOprdsConsumed));
		}
		
	    return allPossiblePostFixExprs;
	}
}
Advertisements

Copying large files — BufferedReader vs FileChannel

When copying large files java.nio.channels.FileChannel takes 20% less time than java.io.BufferedReader. On an average FileChannel takes 25 seconds for each run and BufferedReader takes 30 seconds for each run. Here is the code used for the performance test. Size of test.txt is 1 GB. Used a buffer of size 8 KB as it was giving the best results. [Environment – -Windows 7/3GB RAM/i3 CPU M 370 @ 2.40GHz]

import java.io.BufferedInputStream;
import java.io.BufferedOutputStream;
import java.io.File;
import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.nio.ByteBuffer;
import java.nio.channels.FileChannel;

public class CopyFile {
	//Size of the test file is 1GB.
	private static final String INPUT_FILE_PATH = "test.txt";
	private static final String OUTPUT_FILE_PATH_FOR_FILE_CHANNEL = "test1.txt";
	private static final String OUTPUT_FILE_PATH_FOR_BUFFERED_READER = "test2.txt";
	private static final int DEFAULT_BUFFER_SIZE = 1024 * 8;

	public static void main(String[] args) throws Exception {
		Timer t = new Timer();

		t.start();
		copyFileUsingBufferedReader();
		System.out.println("Copying file using buffered reader takes " + t.end() 
                                                         + " milliseconds");

		t.start();
		copyFileUsingFileChannel();
		System.out.println("Reading file using file channel takes " + t.end() 
                                                         + " milliseconds");
	}

	private static void copyFileUsingFileChannel() throws IOException {
		FileChannel source = null;
		FileChannel destination = null;
		
		try {
			source = new FileInputStream(new File(INPUT_FILE_PATH)).getChannel();
			destination = new FileOutputStream(
                        new File(OUTPUT_FILE_PATH_FOR_FILE_CHANNEL)).getChannel();
			
			//This fails with Map Failed exception on large files
			//destination.transferFrom(source, 0, source.size());
			
			ByteBuffer buf = ByteBuffer.allocateDirect(DEFAULT_BUFFER_SIZE);
	        while((source.read(buf)) != -1) {
	                buf.flip();
	                destination.write(buf);
	                buf.clear();
	        }
		} finally {
			if (source != null) {
				source.close();
			}
			if (destination != null) {
				destination.close();
			}
		}
	}

	private static void copyFileUsingBufferedReader() throws IOException {

		BufferedInputStream source = new BufferedInputStream(
                new FileInputStream(new File(INPUT_FILE_PATH)));
		BufferedOutputStream destination = new BufferedOutputStream(
                new FileOutputStream(new File(OUTPUT_FILE_PATH_FOR_BUFFERED_READER)));
		byte[] buffer = new byte[DEFAULT_BUFFER_SIZE];

		try {
	        int n = 0;
	        while (-1 != (n = source.read(buffer))) {
	        	destination.write(buffer, 0, n);
	        }
	        destination.flush();
		} finally {
			if (source != null) {
				source.close();	
			}
			if (destination != null) {
				destination.close();				
			}
		}
	}

}

class Timer {
	long s;

	public Timer() {
	}

	public long start() {
		s = System.currentTimeMillis();
		return s;
	}

	public long end() {
		return System.currentTimeMillis() - s;
	}
}

Weak-reference copy-on-write set for Java

This is related to my stackoverflow answer Is there an open-source implementation of a weak-reference copy-on-write set for Java? This implementation is loosely based on the copy on write array list implementation here ClientList.One of the decisions I had to make here is to decide whether to call removeReleased method in remove method or to call it in iterator method and I chose to call it in remove. This makes the iterator method much faster at the cost of returning some null elements.

public class CopyOnWriteWeakReferenceSet<E> extends AbstractSet<E> {

    private static final long serialVersionUID = 1L;

    private CopyOnWriteArraySet<WeakReference<E>> items;

    public CopyOnWriteWeakReferenceSet() {
        items = new CopyOnWriteArraySet<WeakReference<E>>();
    }

    public CopyOnWriteWeakReferenceSet(Collection<E> c) {
        items = new CopyOnWriteArraySet<WeakReference<E>>();
        addAll(c);
    }

    public boolean add(E element) {
        if (contains(element)) return false;
        return items.add(new WeakReference<E>(element));
    }

    @Override
    public boolean remove(Object o) {
        boolean removed = false;
        E element = null;
        for (WeakReference<E> ref : items) {
            element = ref.get();
            if (element != null && element.equals(o)) {
                ref.clear();
                removed = true;
                break;
            }
        }
        if (removed) removeReleased();
        return removed;
    }

    @Override
    public boolean contains(Object o) {
        List<E> list = new ArrayList<E>();
        for (WeakReference<E> ref : items) {
            if (ref.get() != null) {
                list.add(ref.get());
            }
        }
        boolean contains = list.contains(o);
        list.clear();
        list = null;
        return contains;
    }

    public int size() {
        removeReleased();
        return items.size();
    }

    private void removeReleased() {
        for (WeakReference<E> ref : items) {
            if (ref.get() == null) {
                items.remove(ref);
            }
        }
    }

    @Override
    public Iterator<E> iterator() {
        final Iterator<WeakReference<E>> iter = items.iterator();
        return new Iterator<E>() {

            @Override
            public boolean hasNext() {
                return iter.hasNext();
            }

            @Override
            public E next() {
                return iter.next().get();
            }

            @Override
            public void remove() {
                iter.remove();
            }
        };
    }
}

Implementation of an undirected graph in java

A minimal implementation of an undirected graph in Java :

import java.util.*;

/**
 * @author Narendra Yadala
 * Implementation of undirected graph represented using adjacency list.
 */
public final class UndirectedGraph<T> implements Iterable<T>{
	private final Map<T, Set<T>> graph = new HashMap<T, Set<T>>();

	public boolean addNode(T node) {
	 if (graph.containsKey(node))
	  return false;

	 graph.put(node, new HashSet<T>());
	 return true;
	}

	public void addEdge(T start, T dest) {
	 if (!graph.containsKey(start) || !graph.containsKey(dest))
	  throw new Exception("No such nodes in the graph.");
	 
	 graph.get(start).add(dest);
	 graph.get(dest).add(start);
	}

	public void removeEdge(T start, T dest) {
	 if (!graph.containsKey(start) || !graph.containsKey(dest))
	  throw new Exception("No such nodes in the graph.");

	 graph.get(start).remove(dest);
	 graph.get(dest).remove(start);
	}

	public boolean isEdgeExists(T start, T end) {
	 if (!graph.containsKey(start) || !graph.containsKey(end))
	  throw new Exception("No such nodes in the graph.");

	 return graph.get(start).contains(end);
	}

	public Set<T> getNeighbors(T node) {
	 Set<T> neighbors = graph.get(node);
	 if (neighbors == null)
	  throw new Exception("No such node in the graph.");

	 return Collections.unmodifiableSet(neighbors);
	}

	public Iterator<T> iterator() {
	 return graph.keySet().iterator();
	}
	public Iterable<T> getNodes() {
	 return graph.keySet();
	}
	public int size() {
	 return graph.size();
	}
	public boolean isEmpty() {
	 return graph.isEmpty();
	}
}