Find palindromic words using Multi threading in Java Source Code

By Hassnain Jamil - Monday 15 February 2016 - No Comments

Specification:

Develop a parallel multithreaded program to solve the following problem. There is A dictionary file “words.txt”, which contains 25,143 words. A palindrome is a word or phrase that reads the same in either direction, i.e. if you reverse all the letters you get the same word or phrase. Your task is to find all palindromic words in the dictionary. A word is palindromic if its reverse is also in the dictionary. For example, "noon" is palindromic, because it is a palindrome and hence it's reverse is trivially in the dictionary. A word like "draw" is palindromic because "ward" is also in the dictionary. Do the input and output phases sequentially and the rest in parallel. Your program should write the palindromic words to a result file.

Implementation details:

Palindrome main file reads the dictionary file and creates a bag of tasks (which is a Hashmap in our case). Hashmap contains key, value pairs. In our case all the words which have the same length, they will be assigned same key and key will be the length of the word.
HashMap<String, ArrayList<String>>
Here String is type for Key (in our case, it will be length of the word)
ArrayList is type for Value ( in our case, it contains all the words which have the same length)
So all the words having the same length, they will be under the same key.
Example code:
HashMap<String, ArrayList<String>> mapBagOfTasks = HashMap<String, ArrayList<String>> ();
ArrayList<String> arrFirstBag = new ArrayList<String> ();
//words of same length will be put in same ArrayList.
//For example, let suppose we put all words of the same length (let say of length 4) in arrFirstBag.
Now put this array list in the map where the key will be 4.

mapBagOfTasks.put(4, arrFirstBag);

In this way, we have prepared a bag of tasks.
After we have the bag of tasks, there is need to spawn worker threads. We create w (input by the user) worker threads. (PalindromeWorker.java)

There is another writer thread(PalindromeWriter.java), which polls palindrome words from the shared Task Queue and writes in the output file.

The worker threads, which find the palindromes from their assigned task, they put these palindrome words in the shared Task Queue in the critical region.

TaskQueue object which is accessed by worker threads and writer thread is shared resource and it has locking mechanism whenever data is put or polled.

At the end when worker threads find the bag empty, they send palindromes count to the writer.
Writer waits until all the threads finish their work. At the end, the writer has all the information about the activity done by all threads and it writes the information in the file.

Sample output:

Your result file output should be similar to “results.txt”. Your program should also print how much each thread has found palindromes. For example, as shown in file “result.txt”

Worker name: Thread 5, palindrome_count: 14
Worker name: Thread 4, palindrome_count: 15
…….
Total count for Palindromes = 299

News Ticker

.