Thursday, October 18, 2012

Classic Shell: great replacement for missing windows 8 start menu

http://classicshell.sourceforge.net/
Posted by at No comments:

Pokki constantly Page Faulting

I recently installed Windows 8 in Parallels. I was missing the old start menu, so I installed this app called Pokki. It's a replacement for the missing menu. I was checking out the new OS, going through the Task Manager, when I decided to add the Page Fault Delta and Threads columns under the Details tab, sorted by PF Delta, and noticed that there were two separate Pokki processes. The larger of the two with 29 threads was (is) constantly page faulting:

My mac is overheating, possibly in part due to this (and parallels itself), and I'm not running anything else intensive. I've contacted Pokki help/support, and I'll update with what they say. Edit: They replied saying that this behaviour is normal and should not be a cause for concern. Hm.
Posted by at 1 comment:

Tuesday, October 9, 2012

Demonstrating usage of a Binary Search Tree in Java

What is a Binary Search Tree?

Binary Search Tree (BST) is a tree in which each node has up to two child nodes (subtrees).  If pointers are used, then each node contains references to the left, right, and parent nodes.  Otherwise, like the implementation I found for Java, each node contains a left and right subtree in the form of a left and right node (each of which have their own two subtrees and so on...) along with the data associated with the node.

A BST is said to have a binary-search-tree property:

Let x be a node in a binary search tree. If y is a node in the left subtree of x, then key[y] <= key[x]. If y is a node in the right subtree of x, then key[x] <= key[y].1

Since Java doesn't have pointers that we can use, we won't keep track of keys. We'll work directly with node data.

Cormen et-all mention that BSTs support the following operations:

Search trees are data structures that support many dynamic-set operations, including
SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, and
DELETE. Thus, a search tree can be used both as a dictionary and as a priority
queue.


What are some applications of BST?

This StackOverflow question answers this well:
What are the applications of binary trees?

Apparently, it is also used in the solution to the Traveling Salesman Problem and the related Shortest Path Problem. I'll be checking these out soon.


How do I use a BST in Java?

I found a good Java BST impl here:
BST.java
BSTNode.java

Class BST contains a root BSTNode node and provides most BST operations (as identified by Cormen et-all). The PREDECESSOR and SUCCESSOR operations are not implemented. Search is implemented, though not exposed directly (it's exposed as isInTree(T el)).

I've slapped together an Eclipse project that demonstrates the usage of this BST implementation. I added some code to BST.java (the one in the Eclipse project) borrowed from this Stanford CS Library page on BSTs. I also borrowed some inspiration from this SO page: How to print binary tree diagram. The class BTreePrinter in the project is pretty much directly from this SO page.

It would be worthwhile to study at least the BST.java and BSTNode.java.

>Download BST_Demo (Eclipse Project)

Here is the output:


>String arrays:
ACEG:  [Aliyah, Chris, Elijah, Gamal]
BDFH:  [Brian, Doug, Farah, Hasan]

>Insert ACEG:
Aliyah Chris Elijah Gamal 

>Insert BDFH:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 

>Removing 'Aliyah':
Brian Chris Doug Elijah Farah Gamal Hasan Aliyah Brian Chris Chris Doug Elijah Elijah Farah Gamal Gamal Hasan 

>Clearing bst.

>Reinserting both arrays:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 

>Search for 'Irene':
false

>Search for 'Aliyah':
true

>Postorder: 
Brian Doug Farah Hasan Gamal Elijah Chris Aliyah 
>Postorder (iterative): 
Brian Doug Farah Hasan Gamal Elijah Chris Aliyah 
>Postorder (Morris): 
Brian Doug Farah Hasan Gamal Elijah Chris Aliyah 

>Preorder: 
Aliyah Chris Brian Elijah Doug Gamal Farah Hasan 
>Preorder (iterative): 
Aliyah Chris Brian Elijah Doug Gamal Farah Hasan 
>Preorder (Morris): 
Aliyah Chris Brian Elijah Doug Gamal Farah Hasan 

>Size:
8

>Max depth:
5

>Min val:
Aliyah

>Max val:
Hasan

Aliyah Brian Chris Doug Elijah ElijahGamal Farah Gamal Hasan 

>Print all root-leaf paths:
Aliyah Chris Brian 
Aliyah Chris Elijah Doug 
Aliyah Chris Elijah Gamal Farah ElijahGamal 
Aliyah Chris Elijah Gamal Hasan 


>Mirroring bst:
Aliyah Brian Chris Doug Elijah ElijahGamal Farah Gamal Hasan 
Hasan Gamal Farah ElijahGamal Elijah Doug Chris Brian Aliyah 

>Doubling bst:
Hasan Hasan Gamal Gamal Farah Farah ElijahGamal ElijahGamal Elijah Elijah Doug Doug Chris Chris Brian Brian Aliyah Aliyah 

>bst:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 
>bst2:
Aliyah Brian Chris Doug Elijah Farah Gamal Hasan 
>bst identical to bst2?:
true

>Possible unique trees given this bst's size: (8)
1430

>Check bst:
true

>Printing bst (bad spacing):
               Aliyah                               
                      \               
                       \              
                        \             
                         \            
                          \           
                           \          
                            \         
                             \        
                       Chris               
                      /      \       
                     /        \      
                    /          \     
                   /            \    
                   Brian       Elijah       
                          /       \   
                         /         \  
                         Doug   Gamal   
                            /      \ 
                            Farah Hasan 
                                                                

>Another bst print:
'- Aliyah
    '- Chris
        '- Brian
        '- Elijah
            '- Doug
            '- Gamal
                '- Farah
                '- Hasan

>Inst and init int bst (unbalanced because of ordered insert):
'- 1
    '- 2
        '- 3
            '- 4

Unbalanced integer tree:
       1               
        \       
         \      
          \     
           \    
           2       
            \   
             \  
             3   
              \ 
              4 
                                

Cleared and intBst.balance(intArr):
'- 2
    '- 1
    '- 3
        '- 4

>Balanced integer tree:
   2       
  / \   
 /   \  
 1   3   
      \ 
      4 
                


1 Introduction to Algorithms Second Edition (Cormen, Leiserson, Rivest, Stein), page 254

Posted by at No comments:

Thursday, October 4, 2012

Synchronization and Thread Safety in Hashtable, Hashmap, ConcurerntHashMap

Coming across blog entry "Who said Java Hashtable is thread safe?", I decided to run the code.  He's right in saying that Hashtable isn't thread safe, though, I don't think such a claim was ever officially made.  Maybe if there is allusion among some that it is, then I suppose it needs dispelling.  Thread safety is a design challenge.  Fully synchronized classes, and even completely thread-safe classes can be used inefficiently, or worse, incorrectly, in a concurrent system.

Here are three examples of thread unsafe usage, followed by three examples of safe usage:

1. Unsafe

package unsafe.demo;

import java.util.HashMap;
import java.util.Map;

import unsafe.threads.Unsafe_Hashmap_NoSynchronized_NotUsingContainsKey;

public class DemoThreadUnsafe {
  private Map<Integer, String> map = new HashMap<Integer, String>();

  public static void main(String[] args) throws InterruptedException {
    for (int j = 1; j < 200; j++) {
      DemoThreadUnsafe demoClass = new DemoThreadUnsafe();
      for (int i = 0; i < 5; i++) {
        new Thread(new Unsafe_Hashmap_NoSynchronized_NotUsingContainsKey(demoClass.map)).start();
      }
      Thread.currentThread().sleep(10);
      System.out.println(demoClass.map.keySet());
      demoClass.map.clear();
    }
  }
}

1. Unsafe cont.

package unsafe.threads;

import java.util.Map;

/**
 * put operation is not safe on the map because its impl in 
 * hashmap (used by calling thread) is not synchronized
 * based on: http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 *
 */
public class Unsafe_Hashmap_NoSynchronized_NotUsingContainsKey implements Runnable {
  private Map<Integer, String> map = null;

  public Unsafe_Hashmap_NoSynchronized_NotUsingContainsKey(Map<Integer, String> map) {
    this.map = map;
  }

  @Override
  public void run() {
    for (int i = 1; i <= 30; i++) {
      try {
        map.put(i, Thread.currentThread().getName());
      } catch (Exception e) {
        System.out.println(e);
      }

    }
  }
}


2. Unsafe
package unsafe.demo;

import java.util.Hashtable;
import java.util.Map;

import unsafe.threads.Unsafe_Hashtable_NoSynchronized_UsingContainsKey;

public class DemoThreadUnsafe2 {
  private static volatile Map<Integer, String> map = new Hashtable<Integer, String>();

  public static void main(String[] args) throws InterruptedException {
    for (int j = 1; j < 200; j++) {
      DemoThreadUnsafe2 demoClass = new DemoThreadUnsafe2();
      for (int i = 0; i < 10; i++) {
        new Thread(new Unsafe_Hashtable_NoSynchronized_UsingContainsKey(demoClass.map)).start();
      }
      Thread.currentThread().sleep(100);
      demoClass.map.clear();
    }
  }
}


2. Unsafe cont.

package unsafe.threads;

import java.util.Map;

/**
 * the sequence of map.containsKey(i) followed by the map.put sequence is not
 * safe because map's impl in hashmap (used by calling thread) is not
 * synchronized based on:
 * http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 * 
 */
public class Unsafe_Hashtable_NoSynchronized_UsingContainsKey implements Runnable {

  private static volatile Map<Integer, String> map = null;

  public Unsafe_Hashtable_NoSynchronized_UsingContainsKey(Map<Integer, String> map) {
    this.map = map;
  }

  @Override
    public void run() {

         for (int i = 1; i <= 30; i++) {
          synchronized(map) {
             if(!map.containsKey(i)) {
                 //some other thread can modify data between the execution of 
                 //above and below lines
                 //try to catch it:
                 if(map.containsKey(i)) {
                   try {
              throw new Exception ("Detected mofification by another thread.");
            } catch (Exception e) {
              // TODO Auto-generated catch block
              e.printStackTrace();
            }
                 }
                 //more modifications can occur any time in above block
                System.out.println( Thread.currentThread().getName() 
                    + "\tInserting new, Key exists: " + map.containsKey(i));
                map.put(i, Thread.currentThread().getName());
             }
             }
        }
    }
}


3. Unsafe

package unsafe.demo;

import java.util.concurrent.ConcurrentHashMap;

import safe.threads.Safe_Hashtable_Synchronized_UsingContainsKey;
import unsafe.threads.Unsafe_ConcurrentHashMap_NoSynchronized_UsingContainsKey;


public class DemoThreadUnsafe3 {

  // private Map<Integer, String> map = new Hashtable<Integer, String>();
  private ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<Integer, String>();

  public static void main(String[] args) throws InterruptedException {

    for (int j = 1; j < 2000; j++) {
      DemoThreadUnsafe3 demoClass = new DemoThreadUnsafe3();

      for (int i = 0; i < 15; i++) {
        new Thread(
            new Unsafe_ConcurrentHashMap_NoSynchronized_UsingContainsKey(demoClass.map))
              .start();
      }

      Thread.currentThread().sleep(1);
      demoClass.map.clear();
    }
  }

}

3. Unsafe cont.

package unsafe.threads;
import java.util.Map;


public class Unsafe_ConcurrentHashMap_NoSynchronized_UsingContainsKey implements Runnable {
 
    private Map<Integer, String> map = null;
 
    public Unsafe_ConcurrentHashMap_NoSynchronized_UsingContainsKey(Map<Integer, String> map) {
         this.map = map;
    }
 
    @Override
    public void run() {

         for (int i = 1; i <= 30; i++) {
           //synchronized(map) {
               if(!map.containsKey(i)) {
                   if(map.containsKey(i)){
                     System.out.println("TRUE?");
                     try {
                throw new Exception("this can't be!");
              } catch (Exception e) {
                e.printStackTrace();
              }
                   }
                  System.out.println( Thread.currentThread().getName() 
                      + "\tInserting new, Key exists: " + map.containsKey(i));
                  map.put(i, Thread.currentThread().getName());
              }
           //}
        }
    }
}


Examples of safe usage:

1. Safe

package safe.demo;

import java.util.Hashtable;

import safe.threads.Safe_Hashtable_NoSynchronize_UsingPut;

/**
 * Thread safe hashmap usage through the use of 'synchronized' keyword. Based
 * on: http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 * 
 */
public class PartiallySafe_BecauseOfHashtable {

  // private Map<Integer, String> map = new Hashtable<Integer, String>();
  private Hashtable<Integer, String> map = new Hashtable<Integer, String>();

  public static void main(String[] args) throws InterruptedException {

    for (int j = 1; j < 100; j++) {
      PartiallySafe_BecauseOfHashtable demoClass = new PartiallySafe_BecauseOfHashtable();

      for (int i = 0; i < 5; i++) {
        new Thread(new Safe_Hashtable_NoSynchronize_UsingPut(demoClass.map)).start();
      }

      Thread.currentThread().sleep(10);
      System.out.println(demoClass.map.keySet());
      demoClass.map.clear();
    }
  }
}


1. Safe cont.

package safe.threads;

import java.util.Map;

/**
 * put operation is not safe on the map because its impl in 
 * hashmap (used by calling thread) is not synchronized
 * based on: http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 *
 */
public class Safe_Hashtable_NoSynchronize_UsingPut implements Runnable {
  private Map<Integer, String> map = null;

  public Safe_Hashtable_NoSynchronize_UsingPut(Map<Integer, String> map) {
    this.map = map;
  }

  @Override
  public void run() {
    for (int i = 1; i <= 30; i++) {
      try {
        map.put(i, Thread.currentThread().getName());
      } catch (Exception e) {
        System.out.println(e);
      }

    }
  }
}

2. Safe


package safe.demo;

import java.util.concurrent.ConcurrentHashMap;

import safe.threads.Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent;

public class Safe_ConcurrentHashMap {

  private ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<Integer, String>(
      80, 0.5f, 200);

  // private Map<Integer, String> map = new HashMap<Integer, String>();

  public static void main(String[] args) throws InterruptedException {

    for (int j = 1; j < 100; j++) {
      Safe_ConcurrentHashMap demoClass = new Safe_ConcurrentHashMap();
      for (int i = 0; i < 5; i++) {
        new Thread(
              new Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent(demoClass.map))
                .start();
      }

      Thread.currentThread().sleep(10);
      System.out.println(demoClass.map.keySet());
      demoClass.map.clear();
    }
  }
}


2. Safe cont.


package safe.threads;

import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
 * Thread safe hashmap usage through the use of 'synchronized' keyword based on:
 * http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 */
public class Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent implements Runnable {

  //private Map<Integer, String> map = null;
  private ConcurrentHashMap<Integer, String> map = null;

  public Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent(
      ConcurrentHashMap<Integer, String> map) {
  //public ThreadSafeMapUsage3(Map<Integer, String> map) {
    this.map = map;
  }

  @Override
  public void run() {
    for (int i = 1; i <= 30; i++) {
      //String result = map.put(i, Thread.currentThread().getName());
      String result = map.putIfAbsent(i, Thread.currentThread().getName());    
    }
  }
}


3. Safe

package safe.demo;

import java.util.concurrent.ConcurrentHashMap;

import safe.threads.Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent;

public class Safe_ConcurrentHashMap {

  private ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<Integer, String>(
      80, 0.5f, 200);

  // private Map<Integer, String> map = new HashMap<Integer, String>();

  public static void main(String[] args) throws InterruptedException {

    for (int j = 1; j < 100; j++) {
      Safe_ConcurrentHashMap demoClass = new Safe_ConcurrentHashMap();
      for (int i = 0; i < 5; i++) {
        new Thread(
              new Safe_ConcurrentHashMap_NoSynchronize_UsingPutIfAbsent(demoClass.map))
                .start();
      }

      Thread.currentThread().sleep(10);
      System.out.println(demoClass.map.keySet());
      demoClass.map.clear();
    }
  }

}


3. Safe cont.

package safe.threads;

import java.util.Map;

/**
 * Thread safe hashmap usage through the use of 'synchronized' keyword based on:
 * http://lovehasija.com/2012/08/16/who-said-java-hashtable-is-thread-safe/
 * 
 * @author sshakil
 */
public class Safe_Hashtable_Synchronized_UsingContainsKey implements Runnable {

  private Map<Integer, String> map = null;

  public Safe_Hashtable_Synchronized_UsingContainsKey(Map<Integer, String> map) {
    this.map = map;
  }

  @Override
  public void run() {

    for (int i = 1; i <= 30; i++) {
      synchronized (map) {
        if (!map.containsKey(i)) {
          if (map.containsKey(i)) {
            System.out.println("TRUE?");
            try {
              throw new Exception("this can't be!");
            } catch (Exception e) {
              e.printStackTrace();
            }
          }
          System.out.println(Thread.currentThread().getName()
              + "\tInserting new, Key exists: "
              + map.containsKey(i));
          map.put(i, Thread.currentThread().getName());
        }
      }
    }
  }
}


 


Posted by at No comments:
Subscribe to: Posts (Atom)