Reducing hash table resizing cost

I found the approach outlined here to be an interesting approach to reducing the cost of hash table resizing: Hash_table#Monotonic_keys:

"If it is known that key values will always increase (or decrease) monotonically, then a variation of consistent hashing can be achieved by keeping a list of the single most recent key value at each hash table resize operation. Upon lookup, keys that fall in the ranges defined by these list entries are directed to the appropriate hash function—and indeed hash table—both of which can be different for each range. Since it is common to grow the overall number of entries by doubling, there will only be O(lg(N)) ranges to check, and binary search time for the redirection would be O(lg(lg(N))). As with consistent hashing, this approach guarantees that any key's hash, once issued, will never change, even when the hash table is later grown."

Consistent hashing appears to be used widely in dealing with this cost.  I can imagine something similar of the sorts must be used to keep consistent large sets of data by search engines.

Notable comment on article documenting progress of GrassHopper VTVL

I found this comment to be worth saving and sharing.  I don't know the author.  It touches on the development of flight, its impact, and the future of space flight and the potential it holds for the human species. 

Source link: http://www.engadget.com/2012/09/22/spacexs-grasshopper-vertical-takeoff-vertical-landing-rocke/

Author: "lagrangia"

"It is true that others- notably Delta Clipper - have preceded GrassHopper. The point however is that these precursors were and were intended to be research vehicles. Grasshopper is intended from the start to convert an already active commerical space programme into a mass market operation, driven by rising order books. Also, the task of retrofitting already proven hardware to VTVL multiple usage is revolutionary. If the eventual performance is as Musk projects we are looking at a 10-100 fold reduction in costs of space missions. Maybe today's short hop  was a "small fart" , but  the Wright Borthers' Flyer in 1903 was no big deal in commercial aviation. In a decade, this could be seen as a game changing step in the aspirations of thousands of Space advocates over many generations- the birth of a true cosmic Diaspora.As Musk, Professor Stephen Hawking and many others have realised, our civilisation requires an expansion beyond our womb planet for its survival and further evolution.The alternatives on offer by opponents of space expansion - namely De Growth and De-Peopling of our civilisation to "Save the Planet"  are only worth consideration by committed misanthropes who wish to diffuse hopelessness and acceptance of authoritarian regimes, which are widely expected to grow on a planet with diminishing food, resources and energy .

 History shows us that ALL Authoritrian regimes are lethal, unscrupulous, careless of all except their own lust for power and domination,  fail, and alwasys cause more suffering than the dangers they claim to be trying to solve In recent years, the calls for suppression of hardwon liberties, righs and living standards to "Save the Planet" are becoming more open, and smell of a modern form of Aztec human sacrifice, which was justly  rewarded by the arrival of Hernan Cortez.

One of the few certainties is that, however plausible, antihuman "Green" dictatorships will do no good, and will be worse than any conceivable alternative. Access to vast resources of solar energy raw materials, and opportunity beyond Earth can  cut off future ideological aspiring despotisms at the knees. For our descendants this is essential, and we would never be forgiven if we fail to take full advantage of the future the New Space pioneers are pointing to.For the sake of unborn billions, we must wish Elon Musk, Robert Bigelow, and Alan Bond et al God speed. They, not the fatuous celebrities of popular media, are the true heroes of our time."

Optimized Trial Division Prime Number Checking

Wikipedia definition of a prime number: "A prime number (or a prime) is a natural number greater than 1 that has no positive divisorsother than 1 and itself."  On that page, if you scroll down a bit, you'll see "Testing Primality...".  The following is a little 'Trial Division' method of determining if an entered int is a prime.  It is obviously limited to small numbers (java int), and it is not as efficient as the 'deterministic' algorithms mentioned on that page (which are O(logⁱ(n) [iterative logarithmic], better than the presented code's ~ O(n^1/2)).  It does, however, skip over all even and numbers divisible by 3 (other than 2 and 3, which are valid input).

import java.util.Scanner; /**  * Checks if a given number is prime  * @author sshakil  *  */ public class PrimeNumberChecker {   public static void main(String[] args) {          Scanner input = new Scanner( System.in );      int a;     do {       a = input.nextInt();       System.out.println(isPrime(a));     } while(a!=0);   }      private static boolean isPrime(int a){     if (a!= 2 && a!=3 && (a%2==0  || a%3==0))       return false;     int sqrRoot = (int) Math.ceil(Math.sqrt(a));     int i = 2;     for (; i <= sqrRoot && i%2 !=0 ; i++) {       if(a%i == 0)         return false;     }     return true;   } }

Yet another bubble sort comparison

Bubble sort isn't a very efficient algorithm, with O(n²) average and worse-case performance.  Anyway, here are some of the algorithm's original and optimized implementations in Java that I've googled up.  This computer club blog has a nice impl in java, python, and c++.  The Algorithmist wiki, which appears to be a nice and concise resource for prep work, also has a couple of optimizations.

/**  * Sbubble sort impls  *   * @author sshakil  *   */ public class BubbleSort {   private static int array[] = { 9, 1, 8, 10, 4, 1 };   public static void main(String args[]) {     System.out.print("Bubble Sort: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     int[] sorted = bubbleSort(array.clone());     System.out.print("Sorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }     // Optimized     System.out.print("\n\nBubble Sort Optimized: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     sorted = bubbleSortOptimized(array.clone());     System.out.print("Sorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }     // Optimized 2     System.out.print("\n\nBubble Sort Optimized 2: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     sorted = bubbleSortOptimized2(array.clone());     System.out.print("Sorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }     // Optimized 3     System.out.print("\n\nBubble Sort Optimized 3: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     sorted = bubbleSortOptimized3(array.clone());     System.out.print("Sorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }          // Optimized 4     System.out.print("\n\nBubble Sort Optimized 4: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     sorted = bubbleSortOptimized4(array.clone());     System.out.print("Sorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }   }   /**    * Bubble sort, original    *     * @param arr    * @return    */   private static int[] bubbleSort(int[] arr) {     int i, j, temp;     int swaps = 0;     int iters = 0;     for (i = 0; i < arr.length; i++) {       for (j = 0; j < (arr.length - 1); j++) {         iters++;         if (arr[j] > arr[j + 1]) {           // move the bigger number (arr[j]) up:           temp = arr[j + 1];           arr[j + 1] = arr[j];           arr[j] = temp;           swaps++;         }       }     }     System.out.println("\nSwaps: " + swaps + "\nIters: " + iters);     return arr;   }   /**    * Based on a nicely written implementation from:     * {@link http://csalgorithm.wordpress.com/2010/03/13/optimized-bubble-sort/}    *     * @param arr    * @return    */   private static int[] bubbleSortOptimized(int[] arr) {     int lastSwapped = arr.length;     int i, temp;     int swaps = 0;     int iters = 0;     while (lastSwapped > 1) {       int newLastSwapped = 0;       for (i = 0; i < lastSwapped - 1; i++) {         iters++;         if (arr[i] > arr[i + 1]) {           temp = arr[i + 1];           arr[i + 1] = arr[i];           arr[i] = temp;           newLastSwapped = i + 1;           swaps++;         }       }       lastSwapped = newLastSwapped;     }     System.out.println("\nSwaps: " + swaps + "\nIters: " + iters);     return arr;   }   /**    * Based on pseudo code from:     * {@link http://www.algorithmist.com/index.php/Bubble_sort}    *     * @param arr    * @return    */   private static int[] bubbleSortOptimized2(int[] arr) {     int i, j, temp;     boolean swaped = false;     int swaps = 0;     int iters = 0;     for (i = 0; i < arr.length; i++) {       swaped = false;       for (j = 0; j < (arr.length - 1); j++) {         iters++;         if (arr[j] > arr[j + 1]) {           temp = arr[j + 1];           arr[j + 1] = arr[j];           arr[j] = temp;           swaped = true;           swaps++;         }       }       if (!swaped)         break;     }     System.out.println("\nSwaps: " + swaps + "\nIters: " + iters);     return arr;   }   /**    * Based on pseudo code from:     * {@link http://www.algorithmist.com/index.php/Bubble_sort}    *     * @param arr    * @return    */   private static int[] bubbleSortOptimized3(int[] arr) {     int i, j, temp;     boolean swaped = false;     int swaps = 0;     int iters = 0;     for (i = 0; i < arr.length; i++) {       swaped = false;       for (j = 0; j < (arr.length - i - 1); j++) {         iters++;         if (arr[j] > arr[j + 1]) {           temp = arr[j + 1];           arr[j + 1] = arr[j];           arr[j] = temp;           swaped = true;           swaps++;         }       }       if (!swaped)         break;     }     System.out.println("\nSwaps: " + swaps + "\nIters: " + iters);     return arr;   }      /**    * From:     * {@link http://stackoverflow.com/questions/8690732/    * bubble-sort-implementation-to-sort-arrays-how-effecient}    * @param arr    * @return    */   private static int[] bubbleSortOptimized4(int[] arr) {     boolean swapped = true;     int i = 0;     int j = 0;     int temp;     int swaps = 0;     int iters = 0;     while (swapped) {       swapped = false;       i++;       for (j= 0; j < arr.length - i; j++) {         iters++;         if (arr[j] > arr[j + 1]) {           temp = arr[j];           arr[j] = arr[j + 1];           arr[j + 1] = temp;           swapped = true;           swaps++;         }       }     }     System.out.println("\nSwaps: " + swaps + "\nIters: " + iters);     return arr;   } }

Final != Immutable

Just learned that in Java 1.6 (or anything after 1.3, from what I recall from the blog that I read), the final modifier on a primitive int array does not imply immutability (non-modifiable); found this when playing with a couple of sorting algorithms.  In the code below, if we want to use the same static array 'array' to be printed before sending it to various successive sorting methods, then we should send clones of it:

public class InsertionSort {   private static int array[] = { 5, 9, 7, 4, 1 };   public static void main(String args[]) {     System.out.print("Insertion Sort: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     int[] sorted = insertionSort(array.clone());     System.out.print("\nSorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }     System.out.print("\n\nBubble Sort: \nUnsorted: ");     for (int member : array) {       System.out.print(member + " ");     }     sorted = bubbleSort(array.clone());     System.out.print("\nSorted: ");     for (int member : sorted) {       System.out.print(member + " ");     }   }   private static int[] insertionSort(int[] arr) {     int i, j, newValue;     for (i = 1; i < arr.length; i++) {       newValue = arr[i];       j = i;       while (j > 0 && arr[j - 1] > newValue) {         arr[j] = arr[j - 1];         j--;       }       arr[j] = newValue;     }     return arr;   }   private static int[] bubbleSort(int[] arr) {     int i, j, temp;     for (i = 0; i < arr.length; i++) {       for (j = 0; j < (arr.length - 1); j++) {         if (arr[j] > arr[j + 1]) {           // move the bigger number (arr[j]) up:           temp = arr[j + 1];           arr[j + 1] = arr[j];           arr[j] = temp;         }       }     }     return arr;   } }

-->

Prep

The company I previously worked for downsized significantly recently, and I've found myself preparing for interviews as I did when I was looking for an internship back in early 2008.  To track this little journey publicly, I'll post what I find to be interesting and useful articles and books.

I have professional experience with Java.  So, other than just brushing up on its syntax, I've decided to learn more about other programming paradigms and languages to see where I could steer my career.  Here is what I've discovered so far (it may not be much or cutting edge, but I've got to start somewhere, so don't flame me)...

Functional programming appears to be taking off.  The dominant functional languages seem to be Haskell, Scala, and F#.  For Java, C#, and other OOP folks, Scala would be more familiar as it is also Object Oriented.

The C# language seems to be ahead of the current Java language (7) in many aspects, with concepts such as Delegates and Lambda Expressions.  I'm not mentioning LINQ there because there are many great JPA providers out there.  If these concepts provide an edge to developers and business priorities alike, then perhaps C# is worth pursuing.  I've had exposure to Java EE and Web Services in Java (with Jersey, Ext JS, and Spring), so the .NET equivalent offering Windows Communication Framework (WCF) would be something worth picking up. 

I don't think Java is going away anytime soon - OpenJDK is gaining lots of support.  Java 8 will be adding Lambda Expressions.    Also, trends seem to show that Java is still the most dominant language (1, 2).  In the second link, it's interesting to note the fall of book sales for many languages, and a steep increase for Objective C, JavaScript, and Java from 2009 onward, likely due to iOS development, and perhaps even a decline in demand from finance houses.