mhward07

Coding challenge: a sliding window map

Sep 5th, 2012
136
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.*;
  2.  
  3. public class SlidingWindowMap
  4. {
  5.     public final static int     s_MaxKeyCount = 500;
  6.  
  7.     public final static long    s_NumMSIn10Min
  8.                 = 10 /*min*/ * 60 /*sec/min*/ * 1000 /*ms/sec*/;
  9.  
  10.     public final static int     s_NumberOfRequestsIn10Min_OnePerSecond
  11.                 = 10 /*min*/ * 60 /*sec/min*/ * 2;  // 2 per second or every 500 ms
  12.  
  13.     public final static long    s_TimeBetweenRequestsInMs = 500;
  14.    
  15.     // Input data members
  16.     private Set<String>         m_Keys;
  17.     private Iterator<String>    m_KeysIterator;
  18.     private int             m_MaxCount;
  19.     private long            m_PeriodMs;
  20.     private KeyStyle        m_KeyStyle;
  21.  
  22.     // Throttled data members
  23.     private long            m_LastTime;
  24.    
  25.     // Non-throttled data members
  26.     private int         m_CurrentCount;
  27.    
  28.     enum KeyStyle
  29.     {
  30.         NoThrotle,
  31.         Throtle
  32.     }
  33.  
  34.     public static void main(String[] args)
  35.     throws Exception
  36.     {
  37.         KeyStyle ks = KeyStyle.Throtle;
  38.        
  39.         if(args.length == 1)
  40.         {
  41.             String keyStyle = args[0];
  42.             if(keyStyle.equalsIgnoreCase("-throttled"))
  43.             {
  44.                 ks = KeyStyle.Throtle;
  45.             }
  46.             else if(keyStyle.equalsIgnoreCase("-nonthrottled"))
  47.             {
  48.                 ks = KeyStyle.NoThrotle;
  49.             }
  50.         }
  51.        
  52.         Set<String> keys = generateKeys();
  53.        
  54.         SlidingWindowMap m = null;
  55.         m = new SlidingWindowMap(keys, 500, s_NumMSIn10Min, ks);
  56.        
  57.         long start = System.currentTimeMillis();
  58.        
  59.         boolean firstNullAchieved = false;
  60.         // Rate is greater than 500 in 10 min. ==> 2 per second. Null's should occur           
  61.         for(int i=0; i<s_NumberOfRequestsIn10Min_OnePerSecond; i++)
  62.         {
  63.             String key = m.getNextKey();
  64.             System.out.println(key);
  65.            
  66.             if(key == null && firstNullAchieved == false)
  67.             {
  68.                 long firstNull = System.currentTimeMillis();
  69.                 long whenFirstNullAchieved = firstNull - start;
  70.                 System.out.println("Time Of First Null = "+whenFirstNullAchieved);
  71.                 firstNullAchieved = true;
  72.             }
  73.            
  74.             Thread.sleep(s_TimeBetweenRequestsInMs);
  75.         }
  76.  
  77.         long stop = System.currentTimeMillis();
  78.  
  79.         long total = stop - start;
  80.  
  81.         System.out.println("Total Time = "+total);
  82.     }
  83.    
  84.     private static Set<String> generateKeys()
  85.     {
  86.         Set<String> keys = new HashSet<String>();
  87.         for(int i=0; i<s_MaxKeyCount; i++)
  88.         {
  89.             keys.add("Key"+i);
  90.         }
  91.         return keys;
  92.     }
  93.  
  94.     public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs)
  95.     {
  96.         this.m_Keys         = keys;
  97.         this.m_KeysIterator = keys.iterator();
  98.         this.m_MaxCount     = maxCount;
  99.         this.m_PeriodMs     = periodMs;
  100.     }
  101.    
  102.     public SlidingWindowMap(Set<String> keys, int maxCount, long periodMs, KeyStyle keyStyle)
  103.     {
  104.         this(keys, maxCount, periodMs);
  105.        
  106.         this.m_KeyStyle = keyStyle;
  107.     }
  108.  
  109.     /**
  110.      * @return a key that has been used less than 'maxCount' times during the
  111.      * past 'periodMs' milliseconds or null if no such key exists.
  112.      */
  113.     public String getNextKey()
  114.     {
  115.         String key = null;
  116.         if(this.m_KeyStyle == KeyStyle.NoThrotle)
  117.         {
  118.             key = getNonThrottledNextKey();
  119.         }
  120.         else if(this.m_KeyStyle == KeyStyle.Throtle)
  121.         {
  122.             key = getThrottledNextKey();
  123.         }
  124.         return key;
  125.     }
  126.  
  127.     /**
  128.      * To allow some keys to be accessible through the entire 10 min period.  
  129.          * Return a null for any additional requests over the rate of 0.8333 requests per second.  
  130.          * Every 1.2 seconds a valid key can be provided.
  131.      */
  132.     private String getThrottledNextKey()
  133.     {
  134.         String key = null;
  135.  
  136.         long currentTime = System.currentTimeMillis();
  137.         if(currentTime - this.m_LastTime >= 1200)
  138.         {
  139.             if(this.m_KeysIterator.hasNext())
  140.             {
  141.                 key = this.m_KeysIterator.next();
  142.                 this.m_LastTime = currentTime;
  143.             }
  144.         }
  145.  
  146.         return key;
  147.     }
  148.  
  149.     /**
  150.      * First come first serve, all keys may be used up in the first few minutes, leaving a range of
  151.      * time at the end of the period that no keys are returned to any requests.
  152.      */
  153.     private String getNonThrottledNextKey()
  154.     {
  155.         String key = null;
  156.         if(this.m_CurrentCount != this.m_MaxCount)
  157.         {
  158.             if(this.m_KeysIterator.hasNext())
  159.             {
  160.                 key = this.m_KeysIterator.next();
  161.             }
  162.         }
  163.         return key;
  164.     }
  165. }
RAW Paste Data