Recent Updates Toggle Comment Threads | Keyboard Shortcuts

  • maravindblog 6:29 am on July 7, 2018 Permalink | Reply
    Tags: ES8,   

    Yes! It’s that time of the year: ES2018 

    ECMAScript 2018 features proposals are finalized! Here is the rundown of top features with practical use-cases and syntax.

    Overview

    1. Major new features:
      • Rest/Spread Properties
      • Asynchronous Iteration
    2. New features:
      • Promise.prototype.finally()
      • Template Literal Revision
    3. New regular expression features:
      • RegExp named capture groups
      • RegExp Lookbehind Assertions
      • RegExp Unicode Property Escapes

    Object Rest/Spread

    ECMAScript 6 introduced rest elements for array destructuring assignment and spread elements for array literals.

    This proposal introduces analogous rest properties for object destructuring assignment and spread properties for object literals. If you were using TypeScript or transpilers like babel. You might have already used this.

    First things first, a basic example

    Rest Properties

    Rest properties collect the remaining own enumerable property keys that are not already picked off by the destructuring pattern; here x, y are destructured but the rest (literally) are copied on to new object z.

    let { x, y, ...z } = { x: 1, y: 2, a: 3, b: 4 };
    x; // 1
    y; // 2
    z; // { a: 3, b: 4 }

    Spread Properties

    Spread copies own enumerable properties from a provided object onto the newly created object.

    let n = { x, y, ...z };
    n; // { x: 1, y: 2, a: 3, b: 4 }

    An intuitive use-case for the object spread operator

    Filling in defaults for user data

    const DEFAULTS = {foo: 'a', bar: 'b'};
    const userData = {foo: 1};
    
    const data = {...DEFAULTS, ...userData}; // final, {foo: 1, bar: 'b'}
    const _data = Object.assign({}, DEFAULTS, userData); // gives same result

    note order matters even if property keys don’t clash.

    Object spread property is similar to Object.assign() in many ways. Yet, both behave differently in multiple scenarios. The differences would be a different topic on its own.

    Here is a GOTCHA
    This only iterates over own properties, the spread operator does not copy the prototype.


    Asynchronous Iteration

    ECMAScript 6 introduced synchronous iteration. which is very similar to the iterator concept of other languages like Java.

    here is a quick recap, Would recommend refreshing your understanding on iterator as the syntax and philosophy is carried forward to async iterator as well.

    const iterable = ['a', 'b'];
    const iterator = iterable[Symbol.iterator]();
    iterator.next()
      // { value: 'a', done: false }
    iterator.next()
      // { value: 'b', done: false }
    iterator.next()
      // { value: undefined, done: true }

    But what about data that is delivered asynchronously? For example, lines of text, read asynchronously from a file or an HTTP connection.

    First things first, A basic example

    const asyncIterable = createAsyncIterable( [ 'a', 'b' ] ); [1]
    const asyncIterator = asyncIterable[Symbol.asyncIterator](); [2]
    
    asyncIterator.next() [3]
    .then(iterResult1 => { [4]
       console.log(iterResult1);
       // { value: 'a', done: false }
       return asyncIterator.next(); [5]
    
    })
    
    .then(iterResult2 => {
       console.log(iterResult2);
       // { value: 'b', done: false }
       return asyncIterator.next();
    })
    
    .then(iterResult3 => {
       console.log(iterResult3);
       // { value: undefined, done: true } [6]
    });

    Okay, I know it’s a mouthful. Let’s iterate over the code line-by-line.

    [1] We are converting its synchronously iterable parameter into an async iterable. This is for demonstration.

    [2] Async iterables are marked via Symbol.asyncIteratorWhereas, sync iterables are marked as Symbol.iterator.

    [3] Method next() of an async iterator returns Promises for IteratorResults (vs. IteratorResults directly).

    [4] Capturing the result of first iterator promise.

    [5] Returning the next element of the iterator to continue the promise chain.

    [6] Iterator end object which value as undefined and done as true is returned. There is no difference here with respect to synchronous iteration.

    But the syntax seems quite messy and verbose isn’t it? you can process the results of the Promises via await and the code becomes simpler.

    async functionf() {
    
     const asyncIterable = createAsyncIterable( [ 'a', 'b' ] );
     const asyncIterator = asyncIterable[Symbol.asyncIterator]();
    
     console.log(await asyncIterator.next());
      // { value: 'a', done: false }
    
     console.log(await asyncIterator.next());
      // { value: 'b', done: false }
    
     console.log(await asyncIterator.next());
      // { value: undefined, done: true }
    }

    for-await-of

    The proposal also specifies an asynchronous version of for-of loop

    async functionf() {
    
      for await(const x of createAsyncIterable( [ 'a', 'b' ] )) {
        console.log(x);
      }
    
    }
    
    // Output:
    // a
    // b

    An intuitive use-case for Async Iterator

    Here is an example (follow the link) that creates an iterator that returns random numbers, but those random numbers come from a web service.


    Promise.prototype.finally

    .finally() works as follows:

    promise
       .then(result => {···})
       .catch(error => {···})
       .finally(() => {···});

    finally’s callback is always executed

    An intuitive use-case for ‘finally’

    The most common use case is similar to the most common use case of the synchronous finally clause: cleaning up after you are done with a resource. That should always happen, regardless of whether everything went smoothly or there was an error.

    let connection;
    db.open()
    .then(conn => {
    connection = conn;
    return connection.select({ name: ‘Jane’ });
    })
    .then(result => {
    // Process result
    // Use `connection` to make more queries
    })
    ···
    .catch(error => {
    // handle errors
    })
    .finally(() => {
    connection.close();
    });


    RegExp

    Named Capture Groups

    Before we get to named capture groups, let’s take a look at numbered capture groups; to introduce the idea of capture groups.

    Numbered capture groups enable you to take apart a string with a regular expression.

    const RE_DATE = /([0-9]{4})([0-9]{2})([0-9]{2})/;
    const matchObj = RE_DATE.exec(‘2018-07-07’);
    const year = matchObj[1];         // 2018
    const month = matchObj[2];     // 07
    const day = matchObj[3];          // 07

    Now, the same example with named capture groups

    const RE_DATE = /(?<year>[0-9]{4})-(?<month>[0-9]{2})-(?<day>[0-9]{2})/;

    const matchObj = RE_DATE.exec(‘2018-07-07’);
    const year = matchObj.groups.year;                   // 2018
    const month = matchObj.groups.month;           // 07
    const day = matchObj.groups.day;                      // 07

    The name must be a legal JavaScript identifier (think variable name or property name).

    RegExp look-behind assertions

    Look-behind assertions work like lookahead assertions but in the opposite direction.

    Positive look-behind assertions

    const RE_DOLLAR_PREFIX = /(?<=\$)foo/g;
    ‘$foo %foo foo’.replace(RE_DOLLAR_PREFIX, ‘bar’);
    // ‘$bar %foo foo’

    As you can see, 'foo' is only replaced if it is preceded by a dollar sign. You can also see that the dollar sign is not part of the total match, because the latter is completely replaced by 'bar'.

    Negative look-behind assertions

    const RE_NO_DOLLAR_PREFIX = /(?<!\$)foo/g;
    ‘$foo %foo foo’.replace(RE_NO_DOLLAR_PREFIX, ‘bar’);
    // ‘$foo %bar bar’

    RegExp Unicode property escapes

    JavaScript lets you match characters by mentioning the “names” of sets of characters. For example, \s stands for “whitespace”:

    > /^\s+$/u.test('\t \n\r')
    true

    This lets you additionally match characters by mentioning their Unicode character properties inside the curly braces of \p{}.

    One of the benefits of property escapes is that they make regular expressions more self-descriptive.

    An intuitive use-cases

    Matching whitespace:

    > /^\p{White_Space}+$/u.test('\t \n\r')
    true

    Matching letters:

    > /^\p{Letter}+$/u.test('πüé')
    true

    Matching Greek letters:

    > /^\p{Script=Greek}+$/u.test('μετά')
    true

    And, Done!

    This is a brief explanation of the new ECMAScript 2018 release feature. In-depth discussion and compatibility will be discussed in further coming posts.

    If you are truly interested in getting daily feed on developer stuff like this but in small byte size. Subscribe to ALBTY. Real-life use cases, tips, and tricks are posted daily. See you there!

    Advertisements
     
  • maravindblog 2:18 pm on May 28, 2018 Permalink | Reply
    Tags: , , props, , state   

    Componetizing Everything – Finalizing The State 

    In the last post, we have considered a non-react app and started to break it up into many logical components. In the process, We have also learnt that these components would need certain information in form of props to operate as expected.

    caseStudyComposingComponents-3

    This was the final component composition for our app. GameComponent is the wrapper/container component which contains all the event handlers. So, It makes sense to handle all the information from this component itself. There is no need of any extra state apart from the state in GameComponent.

    We are just working out with the GameComponent which obviously can be a part of a bigger application.

    A “State” is just a javascript object which dictates the state of the component. We can have as many states as we want but always need to be very careful while designing the state. Because a state acts as the single source of the truth for the component as well as the children if the properties of the.

    State properties are passed as props to child components.

    Now, Let’s consider few possible versions for the state

    version 1 

    carbon.png

    Good

    • No redundant information
    • compact and exactly matches current game requirement

    bad

    1. Hard coded players; Not scalable
    2. No history of the previous session scores.
    3. activePlayer values true/false is not intuitive.

    version 2: Building upon the points above

    carbon (2).png

     

    Now the state is scalable as any number of players can be added into the array

    good

    1. Scalable.
    2. Intuitive activePlayer property.
    3. History of previous gained scores of players.

    bad

    1. Not compact enough.
    2. Redundant totalScore; as totalScore can always be calculated from the session scores.

    version 3: Final best possible state ( opinionated of course )

    carbon (3).png

    After analyzing the above states, I believe this is the one of the best possible state for this app.

    good

    1. Compact, Scalable.
    2. No redundant information.
    3. totalScore can be calculated from the sessionScores; where the last index of the sessionScores is the latest current session scores.
    4. lastDiceRoll is used for displaying the dice image.
    5. activePlayer contains the currently active player id.
    6. As each player is an object now, we can add other information such as the player name for a better game experience.

    bad

    1. Are there any? let me know… 😛

    Conclusion

    In the previous post, we have broken down the non-react app into various intuitive components and also information they need. In this post, we have analyzed various versions for the state that resides in the GameComponent (which passes down the information from the state as props to other components). 

    Hope you like this post.

     
  • maravindblog 3:40 am on May 28, 2018 Permalink | Reply
    Tags: , ,   

    Componetizing Everything! 

    No doubt, React is one of the most popular and successful libraries to create awesome, responsive web apps. One of the main reason for its success is the concept of “Components”. in fact, You literally write everything as components in react.

    In this post, let us discuss how can we convert a non-React app to React app by componentizing and state management (project referenced below).

    Everything about the philophies behind how the state properties should be choosed is discussed in this post.

    caseStudyComposingComponents-pre.png

    This is basically a dice game. If you are interested to learn more about the rules of the game you can check out the project ReadMe. But for us, Just the UI is sufficient, after all, react is UI framework.

    React is all about creating reusable isolated components which makes them easily shareable, testable. it’s almost time to unlearn stuff like the model, view, controller (MVC), 2-way binding, template views.

    Now, What do I mean by componentizing?  It’s the way you split your web app into various reusable components.

    Characteristics of component: Composable, Reusable, Testable, Shareable, Detachable

    Checking For Possible Component Candidates:

    The game has a fairly simple layout. The 2 players, 1 game controller, dice. But we also need a component which can hold all these components. Let’s call it is as GameComponent.

    GameComponent

    This component is only responsible for HTML layout and state management. These type of components are also called as Container components. Before we discuss which are possible properties for the state. We need to zero on what properties are used by children components.

    Player Component

    Though there are 2 players (player 1, player 2) almost all the UI is same except the player name and the score. So, We can create one player component and pass in the required props (props are the way you pass data to child component). 

    The props necessary for Player component are

    1. Player Name
    2. Player Total score
    3. Player Current Session Score

    CurrentSession Component

    But we can go little further and create another component just to show the player’s current session. Because dividing into components allows us to work in isolation and deal with them separately without affecting other components.
    caseStudyComposingComponents-1.png

    motivation? contains more styling and possibly can be changed in future as well. Props to this component are player current session score.

    This is a visual representation of the components and props we created till now,

    carbon.png

    Actions Component

    Now we need a component for holding all the game controls like roll dice, hold etc. caseStudyComposingComponents-2.png

    Even this component can be further split into 2 components.

    1. Dice Component: Just shows an image for corresponding die count.
      • props: dice roll number
    2. Controller Component Holds button new game, roll dice, hold. These buttons have event handlers in our parent component GameComponent. 

    Dice component is a classic example of presentational component because it literally presents the image on change of props.

    The controller component is an example of a controlled component. As all the handling of the on click events on the buttons is done in parent component.

    This is the visual representation of the interaction between GameComponent and ActionsComponent.

    carbon2.png

    Here is the final composition of components:

    caseStudyComposingComponents-3.png

    In this post, we have taken a non-react app and started converting to react app. We finalized on the components

    1. GameComponent
    2. PlayerComponent
    3. CurrentSessionComponent
    4. ActionsComponent
    5. ControllerComponent
    6. DiceComponent

    We have also understood what information should be passed to these components in form of props. In the next post, we will figure out what properties we can and should consider in the state.

    next up, Finalyzing The State

    I hope you liked this post and special thanks to Akasy Hegde.

     

     
  • maravindblog 2:38 am on July 5, 2018 Permalink | Reply
    Tags: http http-headers albty   

    HTTP Headers | Last-Modified / If-Modified-Since | Usage

    Last-Modified / If-Modified-Since is explained neatly in this illustration

     
  • maravindblog 4:06 pm on April 24, 2018 Permalink | Reply  

    How Did I Decide To Learn React? 

    For starters, React is a library to create UI for a website. This technology is developed by Facebook. It is in fact very widely used in all Facebook products.

    Fun Fact: React is used more in Facebook than Angular in Google.

    So, why we are talking about React now? As it’s been for quite a long time now, almost 5 years ago (March 2013). To give a perspective with angular release timeline. angularJs (almost deprecated now) is released on October 20, 2010, and Angular 2 (a completely rewrite of angularJs) on September 14, 2016. So React was released after angularjs which by then was more stable and established. But angularJs being a framework had many goodies out of the box like router, animations etc. And in fact, bigger applications started facing performance issues using angularJs (maybe that’s why you should not develop a framework in 10days).

    Okay, Those dates are only for some history. I was nowhere near web development in 2010. I have started working on angular 2 and angularJs in 2016.

    I already knew about react then and wanted to check it as well. But there were no good tutorials and react documentation was not great. So, Since then even though many developers liked and started developing on react, I have resisted.

    But in late 2017, I wanted to give react a second chance, which by the way, got many updates and became much more stable and established. There were many tutorials as well online (mainly youtube), but were certainly not of high quality.

    At that time, I have observed 3 main issues

    1. License
    2. HTML in javascript (this is what I assumed then, I’ll clarify in a moment)
    3. Redux, for state management

    First, License, Facebook had a very lame non-open source license(BSD), which technically made all applications developed in react controlled by Facebook’s policies (which by no means are great). But due to a lot of resistance and friction among developer community the license is now revoked to MIT.

    Second, If anyone says that react is awkward as it allows you to write HTML in javascript, Just stop them right away and say that

    ” buddy, you are wrong, let me explain “

    comp

    Consider this react code, ButtonCounter is a component. why? because it is extending React.Component. If you are not aware of classes in JS (introduced in ES6 version).It is just a “syntactical sugar” over existing prototypes.  The keyword is “syntactical sugar”, This means that though the behavior is same, There is only change in the way you write that particular construct. This feature is specifically added keeping developers in mind. To make our lives easier.

    Here is how a class can be implemented in ES5.  on left ES6 class and on right es5 implementation of same.

    camp

    nice, But wait! Did we go off topic? No! not at all. Like class is just a “syntactical sugar” over prototype, The HTML-like (or more correctly XML-like) syntax is just a “syntactical sugar” over react’s way of creating an element. This syntax is enabled by JSX. Which has to be converted back to javascript before running your code on the website. How JSX code converts to javascript, you may ask! Here it is!

    camp

    This understanding immediately made me wiser and also is more clear on how it works under the hood.

    Third, Redux

    One of the reasons I did not show much of interest in react because anytime I start a tutorial (I generally prefer a video series in initial phases than documentation. Hence for me it is more important to find a great video series and well-opinionated host), They included Redux in the series which suggested react alone cannot do much  (which is a wrong assumption).

    Redux is state management library which in itself another library and has a learning curve. But that was one concept I did not focus on. But lately, I have started working on NGRX (which is greatly inspired by redux). As now I have understood the concepts of state management. I believe I will not be overwhelming anymore.

    Now, With a clear understanding and at most zero bias towards any framework or library, I have started learning/developing on react.

    Tip: Before judging make sure you have enough knowledge.

    After this long article, if you are still feeling why you may consider learning react now.  I have a couple of points for you.

    1. In 2016, Most famous JS library JQuery (yup!). But let’s understand why? why because of its compact size. JQuery can only manipulate DOM and nothing more. Which has many use cases, For example, If your whole application is one page and you just want to show top 100 movies. You wouldn’t consider angular because the angular framework itself will be more than your code!
      By 2017, React has overtaken JQuery. Because it offers same compactness and better features overall.
    2. Availability to customize and build an application. What do I mean by it? For example, Angular router comes out of the box when you install angular. But definitely, angular router is not perfect and there may be cases you want to use a 3rd party router. Even you absolutely can do that! it just does not make sense! But with react there is a separation of concerns and gives chance to the developer to make the choice.

    This article is highly opinionated. Even though if you differ with any point, I’m always open to a healthy discussion.


    Find more about me

    My youtube channel

     

     
  • maravindblog 5:51 pm on February 28, 2018 Permalink | Reply
    Tags: developer, , , optimization, V8   

    Javascript Optimization Choices: Part 1 

    I came across a very interesting talk where the presenter talks about the internal workings of Chrome’s javascript engine i.e V8.

    Here are points from the video which seemed very practical and useful. This talk basically concentrated on arrays.

    1. There are 2 types of  “elements kinds” holey or packed element arrays. If you are creating an array like.

    const a = new array(5) // makes ‘a’ a holey array kind

    This is bad because V8 should check many other conditions and in worst case need to check whole prototype chain before returning ‘undefined’.

    2. Never create an array like this

    const a = new array(5)

    Until and unless you are creating a huge array and want to save time on array creation.

    3. Rather consider this approach.

    const a = []

    a.push(1)

    a.push(2)

    4. for loop, foreach, for of all have equal performance.

    const a = [1, 2, 3];

    for (let i = 0; i < a.length; i++) {
    const item = a[i];
    console.log(item);
    }

    a.foreach(item => {
    console.log(item);
    });

    for (item of a) {
    console.log(item);
    }

    5. Prefer arrays over array-like objects, if you have array-like objects consider converting into an actual array and perform operations. There are many array optimizations which are lost when we use array-like objects.

    Array-like objects look like arrays. They have various numbered elements and a length property.

    function hybridToArray(nodes) {
    try {
    // works in every browser except IE
    var arr = Array.prototype.slice.call(nodes);
    return arr;
    } catch (err) {
    // slower, but works in IE
    var arr = [],
    length = nodes.length;
    for (var i = 0; i < length; i++) {
    arr.push(nodes[i]);
    }
    return arr;
    }
    }

    6. From ES6, we can use argument deconstruction to accept the arguments to methods. Previous before ES6, we can check the arguments passed to a function at run-time using ‘arguments’objects. But using […args] syntax for accepting the arguments for a method is much more efficient.

    // ES6

    function someFunc(…args) {
    console.log(args.length, args);
    }

    Here is the link to the talk, https://youtu.be/EhpmNyR2Za0

    Hope you have enjoyed this, If you have any interesting and useful performance-related optimization coding suggestions please free to comment on the post.

     
  • maravindblog 6:37 am on December 30, 2017 Permalink | Reply
    Tags: 2017, 2018, journey   

    My Journey: 2017 

    2017 has been a great year. A lot good has happened and definitely, this year is certainly start to many things and also end to some beautiful things too. This post is just a run down through all my ups-downs in this year and kind of like a report card.

    The main difference between this year and any other previous years was that this year I had a resolution i.e create a digital presence. The medium I have chosen was Youtube (and Blogs). I still remember the enthusiasm with which I have created the first video. I’m happy with my progress till now. I have around 100 subscribers and 24 videos. I’m happy because I’ve produced videos only in 7months. If you are like what about the other 5months? Ans. There had been few awesome trips (work/personal) and a lot of procrastination.

    I’ve released my first video on Jan 8, 2017. Since then as I already mentioned I have produced 24videos. I have learned a lot in the course. Honestly, The path was not pleasant. Many times my PC crashed, recorded videos in scorching 40c deg summer heat (as fan sound is disturbing), multiple double works. nevertheless, I consider all these as learning.

    Meanwhile, I was doing my internship at Accolite Inc. and also my UG final semester. I finished my internship as well as the UG final semester almost about the same time. First, The UG is very dear to me. 4years in the same college forced me (just kidding.) to be friends with 6 amazing people. And apparently the long conversations and silly jokes in college cafeteria came to an end. I embrace that fact and shall cherish those moments for life.

    I couldn’t spend much time in college in my final semester as I was doing my internship. The internship was a great start to my professional career. Accolite is a great place to work and some of the amazing and interesting people work there. Luckily, I got
    good opportunities to develop a product and in fact, I developed a whole new feature for it. And at that point of time that was big deal for me and matter of pride. To the end of the internship, I was moved to another project which introduced me to Angularjs and web development. I always wanted to be full stack web developer. Matter of fact, by then I was learning Angular2 on my own. 30th June was the last day of the internship.

    By this time I got my results for my UG. I’ve graduated with flying colours and secured 80% (personally, a huge achievement for me).

    3rd July was my first day of full-time professional career. But this time en-route Delhi because it was the time for AU (Accolite University). AU is an intensive workshop style training program for AUers. There are a plethora of memories but I want to mention few highlights. Every AUer is put into groups and given projects. Fortunately or unfortunately we got one of the biggest problem statement. TL’DR we have successfully completed the project and stand top 2 on the leaderboard. This was a great experience for me I learnt a lot about myself and people around me. I understood my strengths and weaknesses. Besides the work, there has lot happened personally also. Met lot of great and fun loving people. Travelled to Agra and Lansdowne, 2 great places. Certainly, ended AU with a bang! That was the first time I stayed so long away from home. but when I was leaving Delhi it was equally hard to leave as much I wanted to go home.

    After AU I’m officially a working professional (wow! sounds very mature). But funnily I had no work just after the AU (at least it left like that after so much intense work). I read a lot of books at this time. Even if I want to I cannot remember what productive things I have done in those days but I do not regret as I learnt a lot about people and how to deal with them(better way).

    I went to Kerala with family in November. Kerala is a true “God’s Own Place”. Such mesmerising beauty of nature definitely baffles everyone. Then another vacation to Mumbai with my college buddies. Mumbai is a great place and this was the first time ever I went on a trip without adult supervision. There is a lot I need to learn to become more mature. There are few(just a few!) things I’m certainly not good at, Need to work on them next year.

    So, Where we are in the timeline of my journey? Ans. December.

    In December, I was mentally laying out plans for next year. I’m sure things will not turn out the way we have imagined. But I believe we can exercise our brain to imagine better every time. As I initially mentioned 2017 is start to many good things. I plan to end them really well the next year and keep making better quality videos and gain more expertise.

    So, 2017 is ending! I’m sure I might have missed many details here. But on whole, I have covered as many highlights of the year as possible.

    My new year resolutions,
    1. Read more books (read 8 books in total in 2017)
    2. Stick to one technology and gain expertise.
    3. Grow as a better human being.
    4. Obviously, produce better quality videos and have >1000 subscribers by 2018 end.

     
  • maravindblog 1:33 am on May 15, 2017 Permalink | Reply  

    Am; YourMove: How a 280 year old algorithm is used in a year old application? | tech talk 

    he the post will be updated soon…

    This post is a complete description about the video post on 15th May, 17 in AM; YourMove .

    If you are a computer science student or if you have ever have looked various algorithms. Devising an algorithm can be really hard, but a well-optimized algorithm can always be appreciated. Classic algorithms never go out of fashion in fact In computer science most oof the systems are still working fine under those algorithms it self. Algorithms are answers or solutions to real world problem stated in the most interesting problem statement. I personally get excited when I see a great algorithm and always want to share the same knowledge and excitement.

    But, Nowadays due boom of application development algorithm engineering is not really focused topic by engineering students. But we never know when a oldie-but-goodie algorithm might come in handy. This post focuses on a Google’s application Google Trips, Which used a 280-year-old algorithm!

    If you do not know what is Google Trips where we can plan our vacation. One of the features, we can pre-plan which places we are interested in visiting and google creates a optimal route with minimum travel time. Google also takes care of your interests, timings and other important parameters. This is termed as ” itineraries”. 

    The problem statement of the application is very similar to that of travelling salesmen problem. It states that,

    Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

    But Travelling salesmen problem belongs to the class of NP-hard. NP-hard problems are those problems which cannot be solved in deterministic time. That means they cannot be solved in polynomial time. so, a TSP cannot be implemented and if so we cannot expect a great user experience! Which is, in fact, a real deal for a company like Google.

    But TSP problem can be solved by making some assumptions and approximations. The rest of the post talks about how the problem of creating itineraries is solved by using the discoveries of some great scientists.

    In 1736, Leonhard Euler,  studied the following question: is it possible to walk through the city crossing each bridge exactly once?

    —-add pic

    As it turns out, for the city of Königsberg, the answer is no

    Euler noticed that if all the nodes in the graph have an even number of edges (such graphs are called “Eulerian” in his honour) then, and only then, a cycle can be found that visits every edge exactly once. Keep this in mind, as we’ll rely on this fact later!

    One of the approximation algorithms for TSP is an algorithm by Christofides. The assumption is the distances form a metric space (they are symmetric and obey the triangle inequality). It is an approximation algorithm that guarantees that its solutions will be within a factor of 3/2 of the optimal solution length.

    This is an important part of the solution and builds on Euler’s paper.  here is a quick four-step rundown of how it works here:

    1. We start with all our destinations separate and repeatedly connect together the closest two that aren’t yet connected. This doesn’t yet give us an itinerary, but it does connect all the destinations via a minimum spanning tree of the graph.
    2. We take all the destinations that have an odd number of connections in this tree (Euler proved there must be an even number of these), and carefully pair them up.
    3. Because all the destinations now have an even number of edges, we’ve created a Eulerian graph, so we create a route that crosses each edge exactly once.
    4. We now have a great route, but it might visit some places more than once. No problem, we find any double visits and simply bypass them, going directly from the predecessor to the successor.

    This is how a couple of algorithms and their discoveries are cleverly used to get a solution for their problem statement. I hope this post inspires you and motivates you to start looking into algorithms in a different perspective to solve real world problems.

    And I’ll see you in the next one.

    Sources: https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html

     

     

     
    .

     
  • maravindblog 5:33 am on May 2, 2017 Permalink | Reply  

    Am; YourMove: Visualize Sorting a Stack ! 

    This blog summarization of the video from a YouTube channel AM; YourMove. This is the link to the video.

    In this video, the presenter discussed how to sort a stack by just using basic stack operations like push, pop or peek etc. Other constraints on the problem are we can only use data structure stack. But it gives us the flexibility that we can use more than one stack (if we need).

    It is one of the simple interview questions out there but the presenter made it more interesting by using a visualizing tool called processing IDE to show the viewers how the elements in the stack are pushed and popped. The video is attached at end of the post.

    The presenter informs that the algorithm’s complexity is O(n2) which by no means sounds optimal but under these circumstances this best we can get. The algorithm is discussed below.

    We need 2 stacks. The idea is to pull an item from the original stack and push it on the other stack. If pushing this item would violate the sort order of the new stack, we need to remove enough items from it so that it’s possible to push the new item. Since the items we removed are on the original stack, we’re back where we started.

    code

    Link to the visualization sample video (CLICK HERE) . You can check out the code HERE.

    This was one of the interesting topics yet on AM; YourMove. Check out the channel here SUBSCRIBE NOW!

     
  • maravindblog 5:22 pm on April 18, 2017 Permalink | Reply  

    Am; YourMove : What is Load Balancer and Consistent Hashing #2 

    This is cont. Am; YourMove : What is Load Balancer and Consistent Hashing #1

    In last post, we were introduced to concepts like hashing. In this post, we will learn in detail why “just” hashing will not work and why there is a need for an algorithm like consistent hashing. In specific, we will try to know more about the algorithm that is developed by google.

    We now know that we have load balance the requests across multiple data centers. Consider an example for why classic hashing technique is not sufficient. If you have a collection of n cache machines then a common way of load balancing across them is to put object o in cache machine number hash(o) mod n. This works well until you add or remove cache machines (for whatever reason), for then n changes and every object is hashed to a new location.

    This is why consistent hashing comes into the picture. It is interesting to note that it is only the client that needs to implement the consistent hashing algorithm – the memcached server is unchanged. Other systems that employ consistent hashing include Chord, which is a distributed hash table implementation, and Amazon’s Dynamo, which is a key-value store (not available outside Amazon).

    The algorithm which we will be discussing in the post is called as  “consistent hashing with bounded loads”. The main aim for the algorithm is to achieve both uniformity and consistency in the resulting allocations.

    We can think about the servers as bins and clients as balls.

     

    The uniformity objective encourages all bins to have a load roughly equal to the average density (the number of balls divided by the number of bins). For some parameter ε, we set the capacity of each bin to either floor or ceiling of the average load times (1+ε). This extra capacity allows us to design an allocation algorithm that meets the consistency objective in addition to the uniformity property.

    Imagine a given range of numbers overlaid on a circle. We apply a hash function to balls and a separate hash function to bins to obtain numbers in that range that correspond to positions on that circle. We then start allocating balls in a specific order independent of their hash values (let’s say based on their ID). Then each ball is moved clockwise and is assigned to the first bin with spare capacity.

    Consider the example above where 6 balls and 3 bins are assigned using two separate hash functions to random locations on the circle. For the sake of this instance, assume the capacity of each bin is set to 2. We start allocating balls in the increasing order of their ID values. Ball number 1 moves clockwise and goes to bin C. Ball number 2 goes to A. Balls 3 and 4 go to bin B. Ball number 5 goes to bin C. Then ball number 6 moves clockwise and hits bin B first. However, bin B has capacity 2 and already contains balls 3 and 4. So ball 6 keeps moving to reach bin C but that bin is also full. Finally, ball 6 ends up in bin A that has a spare slot for it.

     

    Capture

     

    Upon any update in the system (ball or bin insertion/deletion), the allocation is recomputed to keep the uniformity objective. The art of the analysis is to show that a small update (a few number of insertions and deletions) results in minor changes in the state of the allocation and therefore the consistency objective is met. In the paper, its also show that every ball removal or insertion in the system results in O(1/ε2) movements of other balls.

    This algorithm is just not theoretical! This is in fact implemented in one of the famous companies. Andrew Rodland from Vimeo had found the paper and used it for their load balancing project at Vimeo. The results were dramatic: applying these algorithmic ideas helped them decrease the cache bandwidth by a factor of almost 8, eliminating a scaling bottleneck. He recently summarized this story in a blog post detailing his use case.

    Check out simple implementation of simple consistent hashing algorithm check –link

    The algorithm is open-source, allowing anyone to use this algorithm. To get more insights like improvement statistics, performance analysis etc is found in the paper published. paper

    This was one of the interesting topics yet on AM; YourMove. Check out the channel here SUBSCRIBE NOW!

    And, I’ll see you in the next one !

     
c
Compose new post
j
Next post/Next comment
k
Previous post/Previous comment
r
Reply
e
Edit
o
Show/Hide comments
t
Go to top
l
Go to login
h
Show/Hide help
shift + esc
Cancel