Trie vs arrayList vs LinkedList performance while inserting thousands and thousands of words and then searching a random word

Code For Trie and TrieNode Class that would be handling inserting and searching

class TrieNode {
    TrieNode[] arr;
    boolean isEnd;
    int count;
    // Initialize your data structure here.
    public TrieNode() {
        this.arr = new TrieNode[26];
    }

}

public class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Inserts a word into the trie.
    public void insert(String word) {
        TrieNode p = root;
        for(int i=0; i<word.length(); i++){
            char c = word.charAt(i);
            int index = c-'a';
            if(p.arr[index]==null){
                TrieNode temp = new TrieNode();
                p.arr[index]=temp;
                p = temp;
            }else{
                p=p.arr[index];
            }
        }
        p.isEnd=true;
    }

    // Returns if the word is in the trie.
    public boolean search(String word) {
        TrieNode p = searchNode(word);
        if(p==null){
            return false;
        }else{
            if(p.isEnd)
                return true;
        }

        return false;
    }

    // Returns if there is any word in the trie
    // that starts with the given prefix.
    public boolean startsWith(String prefix) {
        TrieNode p = searchNode(prefix);
        if(p==null){
            return false;
        }else{
            return true;
        }
    }

    public TrieNode searchNode(String s){
        TrieNode p = root;
        for(int i=0; i<s.length(); i++){
            char c= s.charAt(i);
            int index = c-'a';
            if(p.arr[index]!=null){
                p = p.arr[index];
            }else{
                return null;
            }
        }

        if(p==root)
            return null;

        return p;
    }
}

Test class for testing performance of Trie as compared to linked list and arrayList

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

public class TrieTest {

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

Trie trie = new Trie();

List<String> arrayList = new ArrayList<String>();
List<String> linkedList = new LinkedList<String>();

// Load the words from the resource file
InputStream in = TrieTest.class.getResourceAsStream("/words_en.txt");
BufferedReader reader = new BufferedReader(new InputStreamReader(in));
ArrayList<String> words = new ArrayList<>(150000);
do {
String line = reader.readLine();
if (line == null) {
break;
}
if (line.matches("[a-z]+")) {
words.add(line);
}
} while (true);
reader.close();


System.out.println("Inserting 109583 words");
long startForTrieInsert = System.currentTimeMillis();
words.stream().forEach(word -> trie.insert(word));
System.out.println("Completed in " + (System.currentTimeMillis() - startForTrieInsert) + " ms.");

long startForArrayListInsert = System.currentTimeMillis();
words.stream().forEach(word -> arrayList.add(word));
System.out.println("Completed in " + (System.currentTimeMillis() - startForArrayListInsert) + " ms.");

long startForLinkedListInsert = System.currentTimeMillis();
words.stream().forEach(word -> linkedList.add(word));
System.out.println("Completed in " + (System.currentTimeMillis() - startForLinkedListInsert) + " ms.");

String testWord = "zyzzyvas";
// Create the three vocabularies
long startTrieSearching = System.currentTimeMillis();
int found = 0;
if (trie.search(testWord)) {
found++;
}
System.out.println("Seraching " + testWord);
System.out.println("Completed in " + (System.currentTimeMillis() - startTrieSearching) + " ms. Found " + found);

long startArrayList = System.currentTimeMillis();
found = 0;
if (arrayList.contains(testWord)) {
found++;
}

System.out.println("Completed in " + (System.currentTimeMillis() - startArrayList) + " ms. Found " + found);

long startLinkedList = System.currentTimeMillis();
found = 0;
if (linkedList.contains(testWord)) {
found++;
}

System.out.println("Completed in " + (System.currentTimeMillis() - startLinkedList) + " ms. Found " + found);
}
}

outputs 

Order of printing is Trie, ArrayList and then LinkedList

Inserting 109583 words

Completed in 67 ms.

Completed in 0 ms.

Completed in 7 ms.

Seraching zyzzyvas

Completed in 0 ms. Found 1

Completed in 4 ms. Found 1

Completed in 4 ms. Found 1

Inserting 109583 words

Completed in 129 ms.

Completed in 0 ms.

Completed in 16 ms.

Seraching zyzzyvas

Completed in 0 ms. Found 1

Completed in 0 ms. Found 1

Completed in 15 ms. Found 1

Inserting 109583 words

Completed in 62 ms.

Completed in 8 ms.

Completed in 5 ms.

Seraching zyzzyvas

Completed in 0 ms. Found 1

Completed in 5 ms. Found 1

Completed in 4 ms. Found 1

Inserting 109583 words

Completed in 98 ms.

Completed in 15 ms.

Completed in 0 ms.

Seraching zyzzyvas

Completed in 0 ms. Found 1

Completed in 16 ms. Found 1

Completed in 0 ms. Found 1

Here we can see that while inserting, Trie takes alot of time, but when searching for a random word, it always returns the search in 0ms. While ArrayList and LinkedList seaching varies. Hence for searching Trie has the best performance.

Accessing SOAP Web Services Using JAX WS

1. The 3rd Party has published its Web service and shared the wsdl, Lets saythe wsdl is named
http://testws.omer.co.in/apiservice/ApiService.svc?wsdl

2. As a Consumer of the above wsdl, first the Entities and Services need to be extracted from the wsdl provided

This can be done using a tool which is a part of JDK i.e. wsimport

The command that is to be executed is as below :

C:\>wsimport -keep -verbose http://testws.omer.co.in/apiservice/ApiService.svc?wsdl
parsing WSDL...

generating code...
com\omer\ws\ApiService.java
com\omer\ws\IApiService.java

ApiService.java -> would contain all the connection details which would be used to connect to server at the 3rd Party server

IApiService -> this would contain the services that are to be used by the Consumer

Below is the piece of Client code

@Component

@Service("rDC2Client")

public class RDC2ClientImpl<T, R> implements RDC2Client<T, R> {



 private static final Logger LOG = LoggerFactory.getLogger(RDC2ClientImpl.class);



 private static final String WS_URL = "http://testws.omer.co.in/apiservice/ApiService.svc?wsdl";



 @WebServiceRef(wsdlLocation = WS_URL)

 ApiService apiService;



 @SuppressWarnings("rawtypes")

 public R processingRequest(final T object, final Class<R> clazz) throws RemoteException, SOAPException {



  LOG.info("Starting ..processingRequest");



  apiService = new ApiService();

  // Retrieves a proxy to the service, also known as a port, by invoking getBasicEndpoint on //the service. 

// The name of the endPoint / Port may vary through out Web Services depending on how they have been written

  IApiService iApiService = apiService.getBasicEndpoint();

  

  String entryResponse = iApiService.enterIdea(ideaXml, null, null);



  R result = jaxbMarshallingService.unMarshalling(entryResponse, clazz);




  return result;

 }



}




String Utilities

How to capitalize the first character of each word in a string

If you have a String like : today is a good day, then use the WordUtils.capitalize(str) from apache commons-lang.

If you need tODay is GOOd DaY to to become Today Is Good Day, then use capitalizeFully(str) instead.

Java 8 Collections Utilities

Multiple Sort using streams

Prior to java 8 when you tried to sort by several comparators, it got ugly fast. So you might of created a single comparator with logic to compare various fields and the code readability goes down the tube. What is neat about java 8 is it implemented a way to concatenate or combine multiple comparators together by calling Comparator.thenComparing.


We will first create two comparators byFirstName and byLastName. Since we want first name sorted first we will call the thenComparing method on the byFirstName comparator. The thenComparing method will then return a comparator which we will pass into the sort method.

@Test
public void multiple_sort() {

    Comparator<Employee> byFirstName = (e1, e2) -> e1
            .getEmployeeFirstName().compareTo(e2.getEmployeeFirstName());

    Comparator<Employee> byLastName = (e1, e2) -> e1.getEmployeeLastName()
            .compareTo(e2.getEmployeeLastName());

    employees.stream().sorted(byFirstName.thenComparing(byLastName))
            .forEach(e -> System.out.println(e));
}

or we can write the comparator as

@Test
public void multiple_sort() {

    Comparator<Employee> byFirstName = Comparator.comparing(Employee::getEmployeeFirstName);

    Comparator<Employee> byLastName = Comparator.comparing(Employee::getEmployeeLastName);

    employees.stream().sorted(byFirstName.thenComparing(byLastName))
            .forEach(e -> System.out.println(e));
}

Comparing the Keys of Two Maps and storing in a new Map

Here we can use a Comparable as well as a Comparator depending based on the ordering required

To sort in reverse order, pass Comparator.reverseOrder() as parameter to comparingByValue.

To get a LinkedHashMap, you must specifically request one with the 4-argument toMap(). If you don't specify what kind of a map you want, you will get whatever the default is, which currently happens to be a HashMap. Since HashMap doesn't preserve the order of elements, it will definitely not do for you.

myMap.entrySet().stream()
        .sorted(Map.Entry.comparingByKey(Comparator.reverseOrder()))
        .collect(Collectors.toMap(
                Map.Entry::getKey, 
                Map.Entry::getValue, 
                (x,y)-> {throw new AssertionError();},
                LinkedHashMap::new
        ));

Similarly for comparing the values of two maps, we can use




myMap.entrySet().stream()
        .sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
        .collect(Collectors.toMap(
                Map.Entry::getKey, 
                Map.Entry::getValue, 
                (x,y)-> {throw new AssertionError();},
                LinkedHashMap::new
        ));