With the acceleration of the CPU speeds slowing down the only way to get more power out of our machines is to effectively use all the processing power that is available.<\/p>\n
Today the ability to take advantage of the underlying hardware is so much easier now than it has been in the past. \u00a0The past is obviously when the IT guys were trying to take full advantage of machines with multiple single core processors.<\/p>\n
Quicksort<\/h2>\n
Normal Java programs are just a regular single threaded processes. \u00a0One of the main problems with multi-threaded programs\u00a0is you need to have a problem that can easily be broken down into independent pieces.<\/p>\n
I wanted to come up with a real world solution not just a couple of threads running independently sending some interleaved output to the console.<\/p>\n
The only programming task that came to mind that was small enough to easily get an overview on was sorting a list- specifically the Quicksort method. \u00a0The Quicksort method splits up the list into smaller sub lists\u00a0while swapping items that are on\u00a0the wrong side of the pivot spot. \u00a0More information about Quicksort can be found in a lot computer science books or other web sites but a nice description of the Quicksort <\/a>can also be found on wikipedia.<\/p>\n The sort is really efficient and much faster when compared to other sorting methods, but pretty much as expected it only uses one of the four cores that is available on my computer.<\/p>\n Quicksort code at bottom of page<\/p><\/div>\n <\/p>\n Despite the bad wrap that Java has received over efficiency when compared to other compiled languages it does offer quite a lot to the developer right out of the box.<\/p>\n In this case, Java provides the Thread class which provides the infrastructure to allow anyone to run multiple tasks simultaneously, well to the best ability of the underlying hardware.<\/p>\n The Thread class is actually just another java object. \u00a0There are a number of methods that\u00a0are available to help control your thread.<\/p>\n The run method is actually the implementation the interface Runnable. \u00a0This is the actual starting point for the execution of the thread. \u00a0What might seem a bit counter intuitive is that you don’t actually call this method yourself. \u00a0If you call the run method directly then you are simply executing another method call from your program.<\/p>\n The actual starting of the thread is done by calling the start method. \u00a0Java will then do all the necessary work to create a thread, either for your virtual machine or using a OS native thread.<\/p>\n The next and perhaps one of the most important methods is join. \u00a0This method call will cause the calling thread, or the main program, to block until the called thread is finished.<\/p>\n The threaded Quicksort that I have developed actually doesn’t really need to check if the threads are alive due to how it was was programmed. \u00a0The program simply creates threads as it recursively processes the data. \u00a0If your problem were somewhat differently structured you might be starting a number of parallel threads and look at a later point if they have finished by using the isAlive method.<\/p>\n The last three methods on my list are really about controlling if a thread is running or should be blocked. \u00a0The interrupt method is a way to force a thread to block. \u00a0The yield method is almost the same thing. \u00a0You are causing a thread to block itself to allow another waiting thread with the same priority to run.<\/p>\n The last method on the list is sleep. \u00a0This is another way to block a thread, albeit in a slightly different manner. \u00a0This method causes the thread to sleep for a given number of milliseconds. \u00a0This at least tacitly implies that although it is giving someone else a shot at the system resources it will be run again after the sleep period is finished.<\/p>\n How threads are run and when they are blocked really depends on the scheduler. \u00a0This would be dependent on both the operating system and Java virtual machine.<\/p>\n The easiest way to take advantage of threading is to simply to create your own class to extend the Thread. \u00a0When this is done the only thing the developer needs to implement is his own run method.<\/p>\n The neat thing about the Quicksort algorithm is that it is recursive. \u00a0Sorting the entire list looks just like sorting any sub-part of the list.<\/p>\n The change to my sample quick sort program is simply to do each sub-list as a different thread. \u00a0The code is actually hardly different at all, but does it actually work?<\/p>\n multi-threaded quicksort code at bottom of page<\/p><\/div>\n It works really well. \u00a0This screenshot shows a spike on all four cores\u00a0when I run the threaded version of the program.<\/p>\n single threaded multi threaded It is important to remember that Java passes it variables to methods by value. \u00a0If this is the case, how can this sort routine work?<\/p>\n The thread example works because in Java variables are passed by value, but things are a bit special in the case of arrays. \u00a0In this case, the value being passed is the reference to the array.<\/p>\n Yet when we manipulate the individual elements of the array\u00a0those changes will be reflected at the source, so the passing of the\u00a0array around “willy nilly” between threads works.<\/p>\n This entire solution also works because the Quicksort partitions the data into mutually\u00a0exclusive data sets. \u00a0This is why the program doesn’t have any semaphores to prevent us from corrupting our data by having two or more processes changing things simultaneously.<\/p>\n Finally it works because we are not changing what the “array” points to.\u00a0If we did that, this would not be changed in the calling method as the array reference was passed by value. That would be exactly the same as passing in a integer to a method\u00a0and changing it (while expecting it to change in the calling method)<\/p>\n It does four threads but can it do more? \u00a0I ran the program on another computer that could run eight threads simultaneously\u00a0and the program ran as expected. \u00a0 single threaded multi threaded If a little threading is good then a lot of threading must be better? Right?<\/p>\n The limit of threading is somewhat controlled in the Quicksort method. \u00a0I only start a threaded version of the Quicksort if there are at least two\u00a0million values in the list. \u00a0This is because there is overhead associated with creating a thread.<\/p>\n The reason why this threaded application looks so simple is because it is definitely not production quality code. \u00a0Just like memory or disk space there are limits to how many threads that can be created or run at one time.<\/p>\n The threaded version of the Quicksort doesn’t do any checks to ensure that it doesn’t over step the limits of the computer. \u00a0The limits are dependent on a number of factors such as the operating system and the resources available.<\/p>\n Yes and no. \u00a0Why don’t I have a lot of threaded programs laying about that can be used as examples. \u00a0There are a number of reasons.<\/p>\n I needed a lot of data in order to keep my computer busy for five seconds utilizing a single thread. \u00a0The flip side of the argument to using threads is that creating threads also take resources. \u00a0If I create a thread for each recursion when using\u00a0small data sets, the overall runtime is longer for the threaded version of the program. \u00a0This extra run time is exclusively due to overhead for threads.<\/p>\n In order to get a good test, I created a small program to generate 40 million integers just to keep the CPU busy for a few seconds.<\/p>\n The threaded version of the program run about 3.6 seconds faster than the single threaded approach. \u00a0If the additional development time to add only the threading was calculated to be one hour, the program might\u00a0need to be run almost a thousand times or more to offset the extra development costs versus the single threaded version. \u00a0This is might be fine for a task that runs every minute but perhaps a poor investment for a task that runs once a day.<\/p>\n Perhaps 30 years ago computer scientists got excited about sorting algorithms, but that was due to a lot of factors. \u00a0Computing time was quite expensive and resources were very limited. \u00a0There are a lot of things that are possible with a lot of cheap CPU, ram or disk space that would have made these old time developers cry about the inefficiency of some of the modern solutions.<\/p>\n Just for fun, I did a bubble sort and used the built in java sort to get some other numbers.<\/p>\n Java sort Bubble sort Bubble sorting is known to be perhaps the easiest to understand for beginners but the most inefficient. \u00a0The time required to sort 40 million integers was excessive and my lack of patients only lasted 2 1\/2 days. \u00a0I did some smaller runs which also ran fairly slowly, ten thousand integers were sorted in less than half a second while one million integers took about 70 minutes. \u00a0The runtimes did not have\u00a0a perfectly linear increase but based on some of the calculations it might take about 4 days to sort\u00a0through ten million integers.<\/p>\n Parallel processing has to be part of the new reality and in the right situation it can indeed make a tremendous difference. \u00a0Yet one of the real solutions is to use efficient algorithms, the right tool for the right situation and knowing when further optimizations are not adding value.<\/a><\/p>\n Note<\/strong>: \u00a0It is quite unfair to the java sort to accuse it of taking such a\u00a0long time to sort this data. \u00a0The other sorts were using simple integers and a simple array. \u00a0To use the build in sort it was necessary to use the Integer class and a collection. \u00a0In any case, 55 seconds is probably a reasonable sort time on an old laptop for 40 million integers.<\/p>\n Code\u00a0<\/strong><\/p>\n <\/p>\n <\/p>\n Flashback to 2002 Technology is amazing. \u00a0Pretty much since personal computers were created the speed of their processors have been increasing at almost a linear rate of doubling in speed every two years. \u00a0This is awesome but it is also … Continue reading ![\"cpu-singlethread\"](\"http:\/\/blog.paranoidprofessor.com\/wp-content\/uploads\/2016\/09\/cpu-singlethread.png\")
<\/a>Java helps out<\/h2>\n
\n
Converting over to threaded algorithm<\/h2>\n
![\"cpu-maxthread\"](\"http:\/\/blog.paranoidprofessor.com\/wp-content\/uploads\/2016\/09\/cpu-maxthread.png\")
<\/a>
\ntook 5495\u00a0milli seconds<\/p>\n
\ntook 2783\u00a0milli seconds<\/p><\/blockquote>\nWhy does this work ?<\/h2>\n
![\"linux-multithread\"](\"http:\/\/blog.paranoidprofessor.com\/wp-content\/uploads\/2016\/09\/linux-multithread.png\")
<\/a>The cpu was saturated for a brief time. \u00a0The threaded version, as expected, does run faster when provided with more CPU resources.<\/p>\n
\ntook 4901 milli seconds<\/p>\n
\ntook 1318 milli seconds<\/p><\/blockquote>\nOther important facts<\/h2>\n
Is this really worth the effort<\/h2>\n
\n
Parting shot<\/h2>\n
\n55730 milliseconds<\/p>\n
\n*****\u00a0milliseconds<\/p><\/blockquote>\nSingle threaded Quicksort<\/strong><\/h4>\n
package singlethreaded;\r\n\r\n\/*\r\n * this example is an implementation of the quicksort\r\n * algorithm described in wikipedia entry.\r\n * \r\n * https:\/\/en.wikipedia.org\/wiki\/Quicksort\r\n * \r\n *\/\r\nimport java.io.FileInputStream;\r\nimport java.io.FileNotFoundException;\r\nimport java.io.IOException;\r\nimport java.io.ObjectInputStream;\r\n\r\npublic class Quicksort \r\n{\r\n\tint datalist[] = { 12, 16, 333, 50, 1000, 5, 897, 1, 3, 66, 13 };\r\n\r\n\tpublic void quicksort(int datatosort[], int lo, int hi) \r\n\t{\r\n\t\tif (lo < hi)\r\n\t\t{\r\n\t\t\tint partidx = partition(datatosort, lo, hi);\r\n\t\t\tquicksort(datatosort, lo, partidx);\r\n\t\t\tquicksort(datatosort, partidx + 1, hi);\r\n\t\t}\r\n\t}\r\n\r\n\t\/*\r\n\t * Hoare partition scheme\r\n\t *\/\r\n\tpublic int partition(int datatosort[], int lo, int hi)\r\n\t{\r\n\t\tint pivot = datatosort[lo];\r\n\t\tint i = lo - 1;\r\n\t\tint j = hi + 1;\r\n\r\n\t\twhile (true)\r\n\t\t{\r\n\t\t\tdo {\r\n\t\t\t\ti = i + 1;\r\n\t\t\t} while (datatosort[i] < pivot); \r\n\r\n\t\t\tdo {\r\n\t\t\t j = j - 1; \r\n\t\t\t} while (datatosort[j] > pivot);\r\n\r\n\t\t\tif (i >= j) \r\n\t\t\t\tbreak;\r\n\r\n\t\t\tswap(datatosort,i,j); \r\n\t\t}\r\n\t\treturn j;\r\n\t}\r\n\r\n\tvoid swap( int datatosort[], int left, int right)\r\n\t{\r\n\t\tint temp = datatosort[left];\r\n\t\tdatatosort[left] = datatosort[right];\r\n\t\tdatatosort[right] = temp;\r\n\t}\r\n\r\n\tpublic void load()\r\n\t{\r\n\t\tString filename = \"testdata.bin\";\r\n\t\tObjectInputStream inputStream = null;\r\n\t\ttry {\r\n\t\t\tinputStream = new ObjectInputStream(new FileInputStream(filename));\r\n\t\t} catch (FileNotFoundException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t} catch (IOException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t}\r\n\t\t\r\n\t\ttry {\r\n\t\t\tdatalist = (int[])inputStream.readObject();\r\n\t\t} catch (ClassNotFoundException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t} catch (IOException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t}\r\n\t\t\r\n\t\ttry {\r\n\t\t\tinputStream.close();\r\n\t\t} catch (IOException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t}\r\n\t}\r\n\r\n\tpublic void sort ()\r\n\t{\r\n\t\tquicksort(datalist,0,datalist.length - 1);\r\n\t}\r\n\r\n\tpublic static void main(String args[])\r\n\t{\r\n\t\tQuicksort sorter = new Quicksort();\r\n\t\tsorter.load();\r\n\t\tlong nanoStart = System.nanoTime();\r\n\t\tsorter.sort();\r\n\t\tlong nanoEnd = System.nanoTime();\r\n\t\tlong nanoseconds = (nanoEnd - nanoStart);\r\n\t\tSystem.out.println(\"took \" + nanoseconds + \" nano seconds\");\r\n\t\tSystem.out.println(\"took \" + nanoseconds \/ 1000000 + \" milli seconds\");\r\n\t}\r\n}\r\n<\/code><\/pre>\n<\/div>\nThreaded controller<\/strong><\/h4>\n
package multithreaded;\r\n\r\nimport java.io.FileInputStream;\r\nimport java.io.FileNotFoundException;\r\nimport java.io.IOException;\r\nimport java.io.ObjectInputStream;\r\n\r\npublic class Threadcontroller {\r\n\r\n\tint datalist[];\r\n\t\r\n\tpublic void sort ()\r\n\t{\r\n\t\tThreadquicksort sorter = new Threadquicksort();\r\n\t\tsorter.setupThread(datalist,0,datalist.length-1);\r\n\t\tsorter.start();\r\n\r\n\r\n\t\t\/\/ wait for it to finish\r\n\t\ttry {\r\n\t\t\tsorter.join();\r\n\t\t} catch (InterruptedException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t}\r\n\t}\r\n\r\n\tpublic void load()\r\n\t{\r\n\t\tString filename = \"testdata.bin\";\r\n\t\tObjectInputStream inputStream = null;\r\n\t\ttry {\r\n\t\t\tinputStream = new ObjectInputStream(new FileInputStream(filename));\r\n\t\t} catch (FileNotFoundException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t} catch (IOException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t}\r\n\t\t\r\n\t\ttry {\r\n\t\t\tdatalist = (int[])inputStream.readObject();\r\n\t\t} catch (ClassNotFoundException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t} catch (IOException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t}\r\n\t\t\r\n\t\ttry {\r\n\t\t\tinputStream.close();\r\n\t\t} catch (IOException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t}\r\n\t}\r\n\t\r\n\tpublic void print(boolean small)\r\n\t{\r\n\t\tString output = \"\";\r\n\t\t\r\n\t\tif (small == true)\r\n\t\t{\r\n\t\t\tfor (int idx = 0; idx < datalist.length; idx++)\r\n\t\t\t\toutput = output + datalist[idx] + \" \";\r\n\r\n\t\t\tSystem.out.println(output);\r\n\t\t}\r\n\t\telse\r\n\t\t{\r\n\t\t\tfor (int idx = 0; idx < datalist.length; idx++)\r\n\t\t\t\tSystem.out.println(datalist[idx]);\r\n\t\t}\r\n\t}\r\n\t\r\n\tpublic static void main(String args[])\r\n\t{\r\n\t\tThreadcontroller controller = new Threadcontroller();\r\n\r\n\t\tcontroller.load();\r\n\t\tlong nanoStart = System.nanoTime();\r\n\t\tcontroller.sort();\r\n\t\tlong nanoEnd = System.nanoTime();\r\n\t\tlong nanoseconds = (nanoEnd - nanoStart);\r\n\t\tSystem.out.println(\"took \" + nanoseconds + \" nano seconds\");\r\n\t\tSystem.out.println(\"took \" + nanoseconds \/ 1000000 + \" milli seconds\");\r\n\t}\r\n}\r\n<\/code><\/pre>\n<\/div>\n<\/h3>\n
Threaded sort<\/strong><\/h4>\n
package multithreaded;\r\n\r\npublic class Threadquicksort extends Thread\r\n{\r\n\tint referenceToDatalist[];\r\n\tint start, end;\r\n\r\n\tpublic void setupThread(int datalist[], int start, int end)\r\n\t{\r\n\t\tthis.start = start;\r\n\t\tthis.end = end;\r\n\t\treferenceToDatalist = datalist;\r\n\t}\r\n\r\n\tpublic void run()\r\n\t{\r\n\t\tquicksort(referenceToDatalist,start,end);\r\n\t}\r\n\r\n\tpublic void quicksort(int datatosort[], int lo, int hi) \r\n\t{\r\n\t\tif (hi - lo < 2000000)\r\n\t\t{\r\n\t\t\t\/\/ there must be a border where creating threads costs more than it solves.\r\n\t\t\tif (lo < hi)\r\n\t\t\t{\r\n\t\t\t\tint partidx = partition(datatosort, lo, hi);\r\n\t\t\t\tquicksort(datatosort, lo, partidx);\r\n\t\t\t\tquicksort(datatosort, partidx + 1, hi);\r\n\t\t\t}\r\n\t\t}\r\n\t\telse\r\n\t\t{\r\n\t\t\tint partidx = partition(datatosort, lo, hi);\r\n\t\t\tThreadquicksort lowerhalf = new Threadquicksort();\r\n\t\t\tThreadquicksort upperhalf = new Threadquicksort();\r\n\t\t\t\r\n\t\t\t\/\/ tell them what to do\r\n\t\t\tlowerhalf.setupThread(datatosort, lo, partidx);\r\n\t\t\tupperhalf.setupThread(datatosort, partidx + 1, hi);\r\n\t\t\t\r\n\t\t\t\/\/ send them on their merry way\r\n\t\t\tlowerhalf.start();\r\n\t\t\tupperhalf.start();\r\n\t\t\t\r\n\t\t\t\/\/ wait for them to finish.\r\n\t\t\ttry {\r\n\t\t\t\tlowerhalf.join();\r\n\t\t\t} catch (InterruptedException e) {\r\n\t\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\t\te.printStackTrace();\r\n\t\t\t}\r\n\t\t\ttry {\r\n\t\t\t\tupperhalf.join();\r\n\t\t\t} catch (InterruptedException e) {\r\n\t\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\t\te.printStackTrace();\r\n\t\t\t}\r\n\t\t}\r\n\t}\r\n\r\n\t\/*\r\n\t * Hoare partition scheme\r\n\t *\/\r\n\tpublic int partition(int datatosort[], int lo, int hi)\r\n\t{\r\n\t\tint pivot = datatosort[lo];\r\n\t\tint i = lo - 1;\r\n\t\tint j = hi + 1;\r\n\r\n\t\twhile (true)\r\n\t\t{\r\n\t\t\tdo {\r\n\t\t\t\ti = i + 1;\r\n\t\t\t} while (datatosort[i] < pivot); \r\n\r\n\t\t\tdo {\r\n\t\t\t j = j - 1; \r\n\t\t\t} while (datatosort[j] > pivot);\r\n\r\n\t\t\tif (i >= j) \r\n\t\t\t\tbreak;\r\n\r\n\t\t\tswap(datatosort,i,j); \r\n\t\t}\r\n\t\treturn j;\r\n\t}\r\n\r\n\tvoid swap( int datatosort[], int left, int right)\r\n\t{\r\n\t\tint temp = datatosort[left];\r\n\t\tdatatosort[left] = datatosort[right];\r\n\t\tdatatosort[right] = temp;\r\n\t}\r\n}\r\n<\/code><\/pre>\n<\/div>\nBubble sort\u00a0<\/strong><\/h4>\n
package singlethread;\r\n\r\nimport java.io.FileInputStream;\r\nimport java.io.FileNotFoundException;\r\nimport java.io.IOException;\r\nimport java.io.ObjectInputStream;\r\n\r\npublic class Bubblesort \r\n{\r\n\tint datalist[] = { 12, 16, 333, 50, 1000, 5, 897, 1, 3, 66, 13 };\r\n\r\n\tpublic void bubblesort()\r\n\t{\r\n\t\tSystem.out.println(\"starting bubble sort for \" + datalist.length + \" items \");\r\n\t\tint totalswaps = 0;\r\n\t\tboolean swapped = false;\r\n\t\t\r\n\t\tdo\r\n\t\t{\r\n\t\t\tswapped = false;\r\n\t\t\tfor (int left = 0; left < datalist.length -1; left++) \r\n { \r\n int right = left + 1; if (datalist[left] > datalist[right])\r\n\t\t\t\t{\r\n\t\t\t\t\tint temp = datalist[left];\r\n\t\t\t\t\tdatalist[left] = datalist[right];\r\n\t\t\t\t\tdatalist[right] = temp;\r\n\t\t\t\t\tswapped = true;\r\n\t\t\t\t\ttotalswaps++;\r\n\t\t\t\t}\r\n\t\t\t}\t\r\n\t\t}\r\n\t\twhile (swapped == true);\r\n\r\n\t\tSystem.out.println(\"total swaps \" + totalswaps);\r\n\t}\r\n\r\n\tpublic void load()\r\n\t{\r\n\t\tString filename = \"testdata.bin\";\r\n\t\tObjectInputStream inputStream = null;\r\n\t\ttry {\r\n\t\t\tinputStream = new ObjectInputStream(new FileInputStream(filename));\r\n\t\t} catch (FileNotFoundException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t} catch (IOException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t}\r\n\t\t\r\n\t\ttry {\r\n\t\t\tdatalist = (int[])inputStream.readObject();\r\n\t\t} catch (ClassNotFoundException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t} catch (IOException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t}\r\n\t\t\r\n\t\ttry {\r\n\t\t\tinputStream.close();\r\n\t\t} catch (IOException e) {\r\n\t\t\t\/\/ TODO Auto-generated catch block\r\n\t\t\te.printStackTrace();\r\n\t\t}\r\n\t}\r\n\r\n\tpublic void print(boolean small)\r\n\t{\r\n\t\tString output = \"\";\r\n\t\t\r\n\t\tif (small == true)\r\n\t\t{\r\n\t\t\tfor (int idx = 0; idx < datalist.length; idx++)\r\n\t\t\t\toutput = output + datalist[idx] + \" \";\r\n\r\n\t\t\tSystem.out.println(output);\r\n\t\t}\r\n\t\telse\r\n\t\t{\r\n\t\t\tfor (int idx = 0; idx < datalist.length; idx++)\r\n\t\t\t\tSystem.out.println(datalist[idx]);\r\n\t\t}\r\n\t}\r\n\r\n\tpublic void test()\r\n\t{\r\n\t\t\/\/Bubblesort sorter = new Bubblesort();\r\n\r\n\t\tload();\r\n\t\t\r\n\t\tlong nanoStart = System.nanoTime();\r\n\t\tbubblesort();\r\n\r\n\t\tlong nanoEnd = System.nanoTime();\r\n\t\tlong nanoseconds = (nanoEnd - nanoStart);\r\n\r\n\t\tSystem.out.println(\"took \" + nanoseconds + \" nano seconds\");\r\n\t\tSystem.out.println(\"took \" + nanoseconds \/ 1000000 + \" milli seconds\");\r\n\t\t\/\/print(false);\r\n\t}\r\n\t\r\n\tpublic static void main(String args[])\r\n\t{\r\n\t\tBubblesort sorter = new Bubblesort();\r\n\r\n\t\tsorter.test();\r\n\t}\r\n}\r\n<\/code><\/pre>\n<\/div>\nJava sort<\/strong><\/h4>\n
package singlethreaded;\r\n \r\nimport java.util.ArrayList;\r\nimport java.util.Collections;\r\nimport java.util.List;\r\nimport java.util.Random;\r\n \r\npublic class Javasort {\r\n \r\n List datalist = new ArrayList();\r\n \r\n public void create(int len)\r\n { \r\n Random rand = new Random();\r\n \r\n long nanoStart = System.nanoTime();\r\n for (int idx = 0; idx < len; idx++)\r\n {\r\n \/\/ nextInt is normally exclusive of the top value,\r\n \/\/ so add 1 to make it inclusive\r\n int randomNum = rand.nextInt(10000001); \/\/ numbers 0 - 1000000\r\n datalist.add(new Integer(randomNum));\r\n \r\n \/\/System.out.println(idx + \". \" + randomNum);\r\n }\r\n long nanoEnd = System.nanoTime();\r\n \r\n long nanoseconds = (nanoEnd - nanoStart);\r\n System.out.println(nanoseconds);\r\n }\r\n public void sort()\r\n {\r\n Collections.sort(datalist);\r\n }\r\n \r\n public void print()\r\n {\r\n int i=0;\r\n for(Integer temp: datalist){\r\n System.out.println(\"item \" + ++i + \" : \" + temp);\r\n }\r\n }\r\n \r\n public static void main(String args[])\r\n {\r\n Javasort gendata = new Javasort();\r\n gendata.create(40000000);\r\n \r\n long nanoStart = System.nanoTime();\r\n \r\n gendata.sort();\r\n \r\n long nanoEnd = System.nanoTime();\r\n long nanoseconds = (nanoEnd - nanoStart);\r\n \r\n System.out.println(\"took \" + nanoseconds + \" nano seconds\");\r\n System.out.println(\"took \" + nanoseconds \/ 1000000 + \" milli seconds\");\r\n }\r\n}<\/code><\/pre>\n<\/div>\nGenerate sort data<\/strong><\/h4>\n
package singlethreaded;\r\n \r\nimport java.io.FileNotFoundException;\r\nimport java.io.FileOutputStream;\r\nimport java.io.IOException;\r\nimport java.io.ObjectOutputStream;\r\nimport java.util.Random;\r\n \r\npublic class GenerateData {\r\n \r\n int datalist[] = null;\r\n \r\n public void create(int len)\r\n { \r\n datalist = new int[len];\r\n Random rand = new Random();\r\n \r\n long nanoStart = System.nanoTime();\r\n for (int idx = 0; idx < len; idx++)\r\n {\r\n \/\/ nextInt is normally exclusive of the top value,\r\n \/\/ so add 1 to make it inclusive\r\n int randomNum = rand.nextInt(10000001); \/\/ numbers 0 - 1000000\r\n datalist[idx] = randomNum;\r\n \/\/System.out.println(idx + \". \" + randomNum);\r\n }\r\n long nanoEnd = System.nanoTime();\r\n \r\n long nanoseconds = (nanoEnd - nanoStart);\r\n System.out.println(nanoseconds);\r\n }\r\n \r\n public void save()\r\n {\r\n String filename = \"testdata.bin\";\r\n ObjectOutputStream outputStream = null;\r\n \r\n try {\r\n outputStream = new ObjectOutputStream(new FileOutputStream(filename ));\r\n } catch (FileNotFoundException e) {\r\n \/\/ TODO Auto-generated catch block\r\n e.printStackTrace();\r\n } catch (IOException e) {\r\n \/\/ TODO Auto-generated catch block\r\n e.printStackTrace();\r\n }\r\n \r\n try {\r\n outputStream.writeObject(datalist);\r\n } catch (IOException e) {\r\n \/\/ TODO Auto-generated catch block\r\n e.printStackTrace();\r\n }\r\n \r\n try {\r\n outputStream.close();\r\n } catch (IOException e) {\r\n \/\/ TODO Auto-generated catch block\r\n e.printStackTrace();\r\n }\r\n }\r\n \r\n public static void main(String args[])\r\n {\r\n GenerateData gendata = new GenerateData();\r\n gendata.create(40000000);\r\n gendata.save();\r\n }\r\n}<\/code><\/pre>\n<\/div>\nAnt build script<\/strong><\/h4>\n
<project name=\"quicksort\" default=\"world\" basedir=\".\">\r\n\r\n\t<property file=\"project.properties\"\/>\r\n\r\n\t<property name=\"version.num\" value=\"3.15.047\"\/>\r\n\t<property name=\"build.num\" value=\"6\"\/>\r\n\t<property name=\"mainclass\" value=\"singlethreaded.Quicksort\"\/>\r\n\t<property name=\"lib.dir\" value=\"${basedir}\/libs\"\/>\r\n\t<property name=\"src.dir\" value=\"${basedir}\/src\"\/>\r\n\t<property name=\"build.dir\" value=\"${basedir}\/bin\"\/>\r\n\t<property name=\"jar.dir\" value=\"${basedir}\/final\"\/>\r\n\r\n\t<path id=\"classpath\">\r\n\t\t<fileset dir=\"${lib.dir}\" includes=\"**\/*.jar\"\/>\r\n\t<\/path>\r\n \r\n\t<target name=\"clean\" description=\"remove anything we created\">\r\n\t\t<echo>\"cleaning ...\"<\/echo>\r\n\t\t<delete dir=\"${class.dir}\"\/>\r\n\t\t<delete dir=\"${build.dir}\"\/>\r\n\t<\/target>\r\n\r\n\t<target name=\"compile\" description=\"compile source code\">\r\n\t\t<echo>\"compiling ...\"<\/echo>\r\n\t\t<mkdir dir=\"${build.dir}\"\/>\r\n\t\t<javac srcdir=\"${src.dir}\" destdir=\"${build.dir}\" classpathref=\"classpath\" \/>\r\n\t<\/target>\r\n \r\n\t<target name=\"jarfile\" depends=\"compile\" description=\"generate jar file\">\r\n\t\t<echo>\"build jar ...\"<\/echo>\r\n\t\t<mkdir dir=\"${jar.dir}\"\/>\r\n \r\n\t\t<tstamp>\r\n\t\t\t<format property=\"today.timestamp\" pattern=\"yyyy-MM-dd HH:mm:ss\" \/>\r\n\t\t<\/tstamp>\r\n \r\n\t\t<jar destfile=\"${jar.dir}\/${jarname}.jar\" basedir=\"${build.dir}\">\r\n\t\t\t<manifest>\r\n\t\t\t<attribute name=\"Built-By\" value=\"${user.name}\" \/>\r\n\t\t\t<attribute name=\"Main-Class\" value=\"${mainclass}\" \/>\r\n\t\t\t<attribute name=\"Implementation-Version\" value=\"${version.num} build #${build.num}\"\/>\r\n\t\t\t<attribute name=\"Built-Date\" value=\"${today.timestamp}\"\/>\r\n\t\t\t<\/manifest>\r\n\t\t<\/jar>\r\n\t<\/target>\r\n \r\n\t<target name=\"world\" depends=\"jarfile\">\r\n\t\t<echo>\"build script version 1.00\"<\/echo>\r\n\t<\/target>\r\n \r\n<\/project>\r\n<\/code><\/pre>\n<\/div>\n","protected":false},"excerpt":{"rendered":"