Tag: algorithm

  • Data retrieval service with exponential backoff

    Here we will create Data retrieval service with exponential backoff that we covered in the previous post.

    Implementation

    
    package com.rms.blueprint.data;
    
    import java.util.Date;
    import java.util.Objects;
    import java.util.concurrent.TimeUnit;
    import java.util.function.Function;
    import java.util.function.ObjLongConsumer;
    import java.util.function.Supplier;
    
    import org.slf4j.Logger;
    import org.slf4j.LoggerFactory;
    
    public class DataRetrievalWithBackoff implements Runnable
    {
        public final Logger LOGGER = LoggerFactory.getLogger(DataRetrievalWithBackoff.class);
    
        private final Supplier pendingSupplier;
    
        private final ObjLongConsumer readyConsumer;
    
        private final Function capacitySupplier;
    
        private final long minLoadDurationInSeconds;
    
        private final long capacity;
    
        private final long maxBackoffDelayInSeconds;
    
        /**
         * @param config
         *            Configuration properties
         * @param pendingSupplier
         *            Supplier that tells us how many items is being processed at
         *            this time
         * @param readyConsumer
         *            Consumer that will be called when data is ready to load
         * @param capacitySupplier
         *            Function to calculate current capacity
         */
        private DataRetrievalWithBackoff(final long capacity, final long minLoadDurationInSeconds,
                final long maxBackoffDelayInSeconds, final Supplier pendingSupplier,
                final ObjLongConsumer readyConsumer, final Function capacitySupplier)
        {
            Objects.requireNonNull(pendingSupplier);
            Objects.requireNonNull(readyConsumer);
            Objects.requireNonNull(capacitySupplier);
    
            this.capacity = capacity;
            this.minLoadDurationInSeconds = minLoadDurationInSeconds;
            this.maxBackoffDelayInSeconds = maxBackoffDelayInSeconds;
    
            this.pendingSupplier = pendingSupplier;
            this.readyConsumer = readyConsumer;
            this.capacitySupplier = capacitySupplier;
    
            LOGGER.info(String.format("capacity ", capacity));
            LOGGER.info(String.format("minLoadDurationInSeconds ", minLoadDurationInSeconds));
            LOGGER.info(String.format("maxBackoffDelayInSeconds ", maxBackoffDelayInSeconds));
    
        }
    
        @Override
        public void run()
        {
            LOGGER.info("Running Data Retrieval");
    
            long lastLoadedTime = 0l;
            int attempt = 0;
    
            while (true)
            {
                if (Thread.currentThread().isInterrupted())
                {
                    LOGGER.trace("Interrupted stopping [while]");
                    break;
                }
    
                final long delta = TimeUnit.MILLISECONDS.toSeconds(System.currentTimeMillis() - lastLoadedTime);
                final long pending = pendingSupplier.get();
    
                final long backoffTime = DataUtil.backoff(attempt,
                                                          maxBackoffDelayInSeconds,
                                                          minLoadDurationInSeconds / 2.0);
    
                LOGGER.trace("Loading : lastLoaded : {} > {}  delta(s) {} pending : {} backoffTime  = {}",
                             new Object[] { lastLoadedTime, new Date(lastLoadedTime), delta, pending, backoffTime });
    
                if (delta >= minLoadDurationInSeconds && pending <= capacitySupplier.apply(capacity))
                {
                    LOGGER.info("Loading : lastLoaded :  {} >  {}  delta(s) {} pending : {}",
                                new Object[] { lastLoadedTime, new Date(lastLoadedTime), delta, pending });
    
                    // let the consumer know that we are ready
                    readyConsumer.accept(backoffTime, attempt);
    
                    if (pending == 0)
                        ++attempt;
                    else
                        attempt = 0;
    
                    lastLoadedTime = System.currentTimeMillis();
                }
                else
                {
                    ++attempt;
                }
    
                try
                {
    
                    Thread.sleep(TimeUnit.SECONDS.toMillis(backoffTime));
                }
                catch (final InterruptedException e)
                {
                    LOGGER.trace("Interrupted stopping  [sleep]");
                    Thread.currentThread().interrupt();
                    break;
                }
            }
        }
    
        public static class Builder
        {
            private final Function DEFAULT_CAPACITY_SUPPLIER = (capacity) -> capacity / 2;
    
            private long minLoadDurationInSeconds = 60;
    
            private long capacity = 100;
    
            private long maxBackoffDelayInSeconds = 120;
    
            private Supplier pendingSupplier;
    
            private ObjLongConsumer readyConsumer;
    
            private Function capacitySupplier;
    
            public Builder capacity(final long capacity)
            {
                this.capacity = capacity;
                return this;
            }
    
            public Builder maxBackoffDelay(final long duration, final TimeUnit unit)
            {
                Objects.requireNonNull(unit);
                this.maxBackoffDelayInSeconds = unit.toSeconds(duration);
                return this;
            }
    
            public Builder minLoadDuration(final long duration, final TimeUnit unit)
            {
                Objects.requireNonNull(unit);
                this.minLoadDurationInSeconds = unit.toSeconds(duration);
                return this;
            }
    
            public Builder readyConsumer(final ObjLongConsumer readyConsumer)
            {
                Objects.requireNonNull(readyConsumer);
                this.readyConsumer = readyConsumer;
                return this;
            }
    
            public Builder capacitySupplier(final Function capacitySupplier)
            {
                Objects.requireNonNull(capacitySupplier);
                this.capacitySupplier = capacitySupplier;
                return this;
            }
    
            public Builder pendingSupplier(final Supplier pendingSupplier)
            {
                Objects.requireNonNull(capacitySupplier);
                this.pendingSupplier = pendingSupplier;
                return this;
            }
    
            public DataRetrievalWithBackoff build()
            {
                // check invariant
                Objects.requireNonNull(pendingSupplier, "Pening items supplier not provided");
                Objects.requireNonNull(readyConsumer, "Ready Consumer not provided");
    
                if (capacitySupplier == null)
                    capacitySupplier = DEFAULT_CAPACITY_SUPPLIER;
    
                return new DataRetrievalWithBackoff(capacity,
                                                    minLoadDurationInSeconds,
                                                    maxBackoffDelayInSeconds,
                                                    pendingSupplier,
                                                    readyConsumer,
                                                    capacitySupplier == null ? DEFAULT_CAPACITY_SUPPLIER
                                                        : capacitySupplier);
            }
        }
    }
    
    
    

    Usage

    
       //@formatter:off
                final DataRetrievalWithBackoff service = new DataRetrievalWithBackoff.Builder()
                        .capacity(1000)
                        .maxBackoffDelay(100, TimeUnit.SECONDS)
                        .minLoadDuration(10, TimeUnit.SECONDS)
                        .pendingSupplier(() -> getNumberOfPendingItemsToProcess())
                        .readyConsumer((time, attempt) -> fire(new DataLoadEvent()))
                    .build(); 
               //@formatter:on
    
  • Calculating partial Hausdorff Distance

    
    struct Point
    {
    	Point(int_t _x, int_t _y) : x(_x), y (_y)
    	{
    
    	}
    
    	int_t x;
    	int_t y;
    };
    
    
    typedef std::list points_t;
    
    double euclideanDistance(const Point& lhs,const Point& rhs)
    {
    	 double p1 = std::pow((float)(rhs.x - lhs.x), 2);
    	 double p2 =  std::pow((float)(rhs.y - lhs.y), 2);
    	 double vd =  std::sqrt(p1 + p2);
    
    	 return vd;
    }
    
    
    double hausdorffPHD(points_t seta, points_t setb)
    {
        double maxDistance = 0;
    
        points_t::iterator afront = seta.begin();
        points_t::iterator aback  = seta.end();
    
        std::vector ranking;
    
        for(int_t i=0; afront != aback ; ++afront, ++i)
        {
        	Point* a = *afront;
            double minDistance = std::numeric_limits::max();
    
            points_t::iterator bfront = setb.begin();
            points_t::iterator bback  = setb.end();
    
        	for(; bfront != bback ; ++bfront)
    	    {
        		Point* b = *bfront;
        		double ed = euclideanDistance(*a, *b);
    
                if (ed < minDistance)
                    minDistance = ed;
    	    }
    
        	ranking.push_back(minDistance);
        }
    
        std::sort(ranking.begin(), ranking.end());
    
        double fraction = .7;
        int k = (int) (seta.size() * fraction);
        return ranking[k];
    }
    
    
    double hausdorff(points_t seta, points_t setb)
    {
        double habPHD = hausdorffPHD( seta, setb);
        double hbaPHD = hausdorffPHD( setb, seta);
        double distancePHD = std::max(habPHD, hbaPHD);
        printf("hd = %0.4f\t %0.4f\t %0.4f\t \n", distancePHD, habPHD, hbaPHD);
        return distancePHD;
    }
    
    
    int_t main(int_t argc, char_t** args)
    {
    
    	points_t seta;
    	points_t setb;
    
    	seta.push_back(new Point(1,2));
    	seta.push_back(new Point(2, 4));
    
    	setb.push_back(new Point(2, 4));
    	setb.push_back(new Point(3, 4));
    
    	double val = hausdorff(seta, setb);
    }
    
  • HashTable implemented using quadratic probing for collision resolution

    Using quadratic probing for collision resolution

    #define ERROR_TABLE_FULL       -1
    #define ERROR_RECORD_NOT_FOUND -1
    #define ERROR_DUPLICATE_RECORD -1
    
    class HashTable{
    public:
    	HashTable(int table_size);
    	int insert(const string &record);
    	int retrieve(const string &record);
    private:
    	int hash(const string &record);
    	int hash_size;
    	int record_count;
    	string* table;
    };
    
    /**
     * Constructor accepting table_size
     */
    HashTable::HashTable(int table_size){
    	hash_size = table_size;
    	table = new string[hash_size];
    	record_count = 0;
    }
    /**
     * Hash function calculated using
     * product p of all the characters of the key
     * and then returns the index where index=s%hash_size
     */
    int HashTable::hash(const string &key) {
    	int value = 1;
    	for (int position = 0; position < max_key_length; position++){
    		if(key[position] == 0){
    			break;
    		}
    		value *= key[position];
    	}
    	value %= hash_size;
    	if (value < 0){
    		value += hash_size;
    	}
    	return value;
    }
    /**
     * Insert new record
     * Collision function uses h+i^2
     *
     */
    int HashTable::insert(const string &record){
    	if(record_count == hash_size){
    		return ERROR_TABLE_FULL;
    	}
    
    	int hash_key = hash(record);
    	int increment = 1;
    
    	int probe_counter=0;
    	int hash_mid=(hash_size+1)/2;
    
    	while(1){
    		//Check for overflow
    		if(probe_counter > hash_mid){
    			return ERROR_RECORD_NOT_FOUND;
    		}
    		string tmp = table[hash_key];
    		//Empty slot
    		if(tmp.empty()){
    			break;
    		}//Position already taken, duplicate keys are not allowed
    		else if(tmp.compare(record) == 0) {
    			return ERROR_DUPLICATE_RECORD;
    		}
    		else{
    			//Handles collision using h+i^2
    			hash_key = (hash_key+increment) % hash_size;
    			increment+=2;
    			probe_counter++;
    		}
    	}
    	table[hash_key] = record;
    	record_count++;
    	return hash_key;
    
    }
    /**
     * Retrieve record index
     */
    int HashTable::retrieve(const string &record){
    	int hash_key = hash(record);
    	int increment = 1;
    
    	int probe_counter=0;
    	int hash_mid=(hash_size+1)/2;
    
    	while(1){
    		//Overflow encountered if the probe is bigger than hash_size/2
    		if(probe_counter > hash_mid){
    			return ERROR_RECORD_NOT_FOUND;
    		}
    		string tmp = table[hash_key];
    		//Record empty for the key
    		if(tmp.empty()) {
    			break;
    		}
    		else if(tmp.compare(record) == 0){
    			return hash_key;
    		}
    		else{
    			hash_key = (hash_key+increment) % hash_size;
    			increment+=2;
    			probe_counter++;
    		}
    	}
    	return ERROR_RECORD_NOT_FOUND;
    }
    
  • Level order traversal – Breadth-first

    Here is implementation of level order traversal of a binary tree.

    Level order traversal is nothing more than traversing each level at a time

               10              Lev 1
              /   \
            9     15          Lev  2
          /      /   \ 
        7      12    17      Lev 3
    

    Output

    10 9 15 7 12 17
    

    AVL Tree example

    ++++++++++++++++++++++
    69:  29  77 
    29:  15  48 
    15:  5  23 
    5:  3  11 
    11:  -  14 
    23:  16  26 
    16:  -  18 
    48:  33  64 
    33:  32  46 
    64:  50  68 
    77:  72  84 
    72:  71  76 
    84:  80  89 
    80:  79  82 
    89:  87  93 
    ++++++++++++++++++++++
    
    The level order result is:
    ++++++++++++++++++++++
    69 29 77 15 48 72 84 5 23 33 64 71 76 80 89 3 11 16 26 32 46 50 68 79 82 87 93 14 18 
    ++++++++++++++++++++++
    

    Implementation

    /**
     * Implementation of Level order traversal
     * Prints nodes at each level left to right
     */
    template 
    void AVL_tree::level_order() {
    	cout << "++++++++++++++++++++++" << endl;
    	if(this->root == NULL){
    		cout << "EMPTY TREE" << endl;
    	}else{
    		cout << endl;
    		queue*> nodeQueu;
    		nodeQueu.push(this->root);
    		while(!nodeQueu.empty()){
    			Binary_node* entry=nodeQueu.front();
    			cout<data<<" ";
    			if(entry->left != NULL){
    				nodeQueu.push(entry->left);
    			}
    			if(entry->right != NULL){
    				nodeQueu.push(entry->right);
    			}
    			nodeQueu.pop();
    		}
    	}
    	cout << "\n++++++++++++++++++++++" << endl;
    }
    

    Complexity

    Running time complexity of this algorithm is O(n) since every node will have to be explored