Friday, December 15, 2017

302: Redirect

I've got stuff scattered all over the place.  That's no way to build an internet presence!

When you're done reading all of this stuff, go to my official brain dumping ground.

https://reergymerej.blogspot.com

Wednesday, January 21, 2015

Binary Tree Fun

Let's parse this sucker without recursion.

(function () {
    'use strict';

    var Node = function (text, left, right) {
        this.text = text;
        this.left = left;
        this.right = right;
    };

    Node.prototype.print = function (vertical, direction) {
        var node = this;
        var queueOrStack = [this];
        direction = direction || 'right';

        do {
            node = queueOrStack[vertical ? 'pop' : 'shift']();

            if (node) {
                console.log(node.text);

                queueOrStack.push(node[direction === 'left' ? 'right' : 'left']);
                queueOrStack.push(node[direction]);
            }
        } while (queueOrStack.length);
    };

    var n0 = new Node(0);
    var n2 = new Node(2);
    var n1 = new Node(1, n0, n2);
    var n5 = new Node(5);
    var n4 = new Node(4, null, n5);
    var n6 = new Node(6, n4);
    var n3 = new Node(3, n1, n6);
    var n8 = new Node(8);
    var n10 = new Node(10);
    var n11 = new Node(11, n10);
    var n9 = new Node(9, n8, n11);
    var n14 = new Node(14);
    var n15 = new Node(15, n14);
    var n13 = new Node(13, null, n15);
    var n12 = new Node(12, n9, n13);
    var n7 = new Node(7, n3, n12);

    n7.print();
    // 7, 3, 12, 1, 6, 9, 13, 0, 2, 4, 8, 11, 15, 5, 10, 14

    n7.print(true);
    // 7, 12, 13, 15, 14, 9, 11, 10, 8, 3, 6, 4, 5, 1, 2, 0

    n7.print(true, 'left');
    // 7, 3, 1, 0, 2, 6, 4, 5, 12, 9, 8, 11, 10, 13, 15, 14

    n7.print(false, 'left');
    // 7, 12, 3, 13, 9, 6, 1, 15, 11, 8, 4, 2, 0, 14, 10, 5
}());

Thursday, January 15, 2015

Looping without Loops

I ran into an interesting JavaScript puzzle today.

Write a function that when passed an Array of integers will return the subset of evens without using loops (for...in, while, etc.) including builtin prototype methods that use loops.

There are two problems to solve here. The first is easy, but the second is tricky.

Identify Even Integers

This is pretty straight forward. A long time ago, I thought I invented this method. Turns out everyone's come to the same conclusion.

(x % 2 === 0) ? 'even' : 'odd';

This uses the modulo operator to figure out if there's anything left after dividing x by 2. If there is, it's odd.

Loop without Looping

The instinctual way to solve this problem is something like this.

var ints = [-3, -2, -1, 0, 1, 2, 3];

var getEvens = function (ints) {
  return ints.filter(function (x) {
    return x % 2 === 0;
  });
};

console.log(getEvens(ints)); // [ -2, 0, 2 ]

This uses the Array's filter method. It iterates through the Array and performs a callback. If the callback returns true, the item is included in the filtered Array.

If you look at the link, though, it's using a for loop. All the Array's iterator methods use loops; that's sort of the whole point of the Array data structure.

So, maybe we're thinking about this the wrong way. What is it we need to do? We need to run some code against every item in a collection.

Maybe we could do something like this.

var getEvens = function (ints) {
  var evens = [];

  if (ints[0] % 2 === 0) {
    evens.push(ints[0]);
  }

  if (ints[1] % 2 === 0) {
    evens.push(ints[1]);
  }

  ...

  return evens;
};

Technically, that would work as long as we copied that code enough times. It makes my teeth hurt to look at all that repetition, though. And what if the Array has 100,000 ints?

OK, scrap that.

How else can you get code to repeat without a loop? A function. That's the whole point of functions, right? They are reusable code.

var emergency = 0;

var getEvens = function (ints) {
  if (++emergency > ints.length) {
    throw new Error('whoah, too much recursion: ' + emergency);
  }

  return getEvens(ints);
};

There we go. We've got the code repeating and it's somewhat aware of the Array's length. We're on to something here.

Iterating with Recursion

Here's a better version with comments. Basically, we add an index parameter, combine it with a little tail recursion, and voilĂ ! We're iterating an Array without technically using a loop. I'd argue that this is still a loop, but it's not one of the loop control flow statements.

var getEvens = function (ints, i) {
  var evens = [];

  // We added an optional index param.
  i = i || 0;

  // This keeps us out of an infinite loop.
  if (i < ints.length) {

    // Test the current item, include if it passes.
    if (ints[i] % 2 === 0) {
      evens.push(ints[i]);
    }

    // Move to the next item, concatenate result with this item.
    return evens.concat(getEvens(ints, i + 1));
  }

  // We've iterated too far, so stop the recursion
  // by returning the empty Array.  The concat in
  // the calling function will make it magically disappear!
  return evens;
};

var ints = [-3, -2, -1, 0, 1, 2, 3];

console.log(getEvens(ints));
// [ -2, 0, 2 ]

Performance

So, this achieves the objective spelled out by the problem. How does it perform, though?

Using the ints -5000 through 5000 in an Array, I tested this method and the filter version each 100 times. Here are the results.

Recursion Version
8388ms

Filter Version
148ms

Obviously, you want to use the filter version. Maybe we could refactor the recursion version to not use all those concats and speed it up, but it's not worth the effort. The first time I tested this I used an Array of 100,000 ints and - surprise! - the max callstack size was exceeded.

Friday, January 9, 2015

MEAN.io is Getting Pretty Cool

It's been a while since I check on the latest MEAN.io stuff.  When I first started learning the MEAN stack I used it to help me get my bearings, even contributed a little to the project.  There's a lot of non-MEAN stuff, though, that was distracting me from what I was trying to learn.  It's loaded down with lots of packages.  They're all very cool, but distracting nonetheless.

I just checked it out again, and the project has come a long way.  They've got an npm package with scaffolding generation and a package system that allows you to publish custom bits of MEAN.io code.  It's pretty cool.

Thursday, January 8, 2015

Rebrand THIS!

I haven't posted a blog here in a little while. It's not because I've been on hiatus, just that my interests don't always fit in the MEAN category. Here are some examples of what I've been up to since my last post:

I wanted to share what I've learned about all of these, but none of them fit into the MEAN stack. The options I see before me are:

  1. Create a new blogger site for each category
  2. Change "MEAN" to "CD1003CmpVSSGSHdG" (and keep appending for each new category)
  3. Write whatever I feel like and tag the posts

After much consideration and given the fact that I have like 2 unique visitors to the site (me from home and me from work), I'm going to opt for option 3.

Henceforth, this blog will contain whatever the heck I feel like. Hooray!

Wednesday, October 1, 2014

MongoDB Aggregation

Aggregation

Basic read operations are fine, but what about looking at the documents and computing results? To do that, we'll need to use aggregations.

First off, let's seed our database with some data we can aggregate.

var i = 40;
var names = 'George|Samuel|Thomas|Benjamin|John'.split('|');
var colors = 'Red|Orange|Yellow|Blue|Green|Indigo|Violet'.split('|');

while (i--) {
    db.people.insert({
        name: names[i % names.length],
        number: i,
        color: colors[i % colors.length],
        rand: Math.random()
    });
}

Whet Your Whistle

The aggregation docs are pretty deep, especially when you're just looking for a simple answer. So, to keep up the motivation, here's a quick taste of grouping.

db.people.aggregate([
    {
        $group: {
            _id: '$color',
            count: {
                $sum: 1
            }
        }     
    }
]);
{
    "result" : [
        {
            "_id" : "Red",
            "count" : 6
        },
        {
            "_id" : "Indigo",
            "count" : 5
        },
        {
            "_id" : "Violet",
            "count" : 5
        },
        {
            "_id" : "Orange",
            "count" : 6
        },
        {
            "_id" : "Yellow",
            "count" : 6
        },
        {
            "_id" : "Blue",
            "count" : 6
        },
        {
            "_id" : "Green",
            "count" : 6
        }
    ],
    "ok" : 1
}

Whoa, Nellie!

Aggregation can be confusing when you first run into it, which usually happens when trying to figure out how to do grouping. That's why I've shown $group above, but it's is actually one of the trickier aggregation stages.

I suggest slowing down and learning how aggregation works at a high level to allow the concepts to sink in. Once you get that, the specifics are easily demystified by referring to the docs.

How Does Aggregation Work?

Simply put, aggregation takes a collection of documents and turns them into a new collection of documents. Each of these transformations is referred to as an aggregation stage. How each aggregation stage works varies, but you can figure them out easily once you understand what you're looking at.

Aggregation works by passing a collection through a series of stages, each changing the collection and passing it off to the next stage. This is the aggregation pipeline.

An Example

db.people.aggregate([
    // Change the documents in people by sorting.
    { $sort: { name: -1 } },

    // Change the sorted documents from the previous stage
    // by limiting them to the first 3.
    { $limit: 3 },

    // Change which fields are present in the
    // 3 sorted documents.
    { $project: { _id: 0, name: 1, color: 1 } }
]);

{
    "result" : [
        {
            "name" : "Thomas",
            "color" : "Violet"
        },
        {
            "name" : "Thomas",
            "color" : "Green"
        },
        {
            "name" : "Thomas",
            "color" : "Yellow"
        }
    ],
    "ok" : 1
}

What is the Result?

This makes sense, but what is this new object structure? It's not a collection like we saw in the CRUD post. According to TFM, it is a cursor.

Remember, in mongo, the shell interface, cursors are printed out automatically when you don't assign the operation to a variable.

So, it says it's a cursor, and it has the documents in result, but there's definitely something different. Let's compare the keys in the two different cursor types.

var findCursor = db.people.find();
var aggregateCursor = db.people.aggregate([{ $limit: 10 }]);

Object.keys(findCursor).sort();

[
    "_batchSize",
    "_collection",
    "_cursor",
    "_db",
    "_fields",
    "_limit",
    "_mongo",
    "_ns",
    "_numReturned",
    "_options",
    "_query",
    "_skip",
    "_special"
]

Object.keys(aggregateCursor).sort();

[ "ok", "result" ]

Now, those don't appear to be the same, but cursors warrant their own post.

Tips for Working Through Aggregation

In my first draft, I got right into explaining each of the rabbit holes in the aggregation stages. That's dumb. Instead, I would like to teach you to fish.

Plan it Out

Figure out what it is you want to do, like this.

db.people.aggregate([
    // group by color

    // sort by count of color

    // pick the top 2

    // remove all the fields except the color
]);

Pick the Stages

There are only 10 aggregation stages. Read the descriptions to see which one(s) you want to you use.

db.people.aggregate([
    // group by color
    { $group: {} },

    // sort by count of color
    { $sort: {} },

    // pick the top 2
    { $limit: {} },

    // remove all the fields except the color
    { $project: {} }
]);

Set the Stages Up

Now that you know what stages you'll use, go through them one-by-one and read the docs. With our cheatsheet, you can keep your eyes on the prize. It's less likely to you'll be overwhelmed or distracted by all the new concepts and terminology that come along with aggregation.

Right at the top of each stage's docs, it shows the structure we need to use. Additionally, they include lots of detail and several examples. Just fight the temptation to get distracted.

If you can, you should end up with something like this.

db.people.aggregate([
    // group by color
    {
        $group: {
            _id: '$color',
            count: {
                $sum: 1
            }
        }
    },

    // sort by count of color
    { $sort: { count: -1 } },

    // pick the top 2
    { $limit: 2 },

    // remove all the fields except the color
    {
        $project: {
            _id: 0,
            color: '$_id'
        }
    }
]);

{
    "result" : [
        {
            "color" : "Orange"
        },
        {
            "color" : "Red"
        }
    ],
    "ok" : 1
}

References

Friday, September 26, 2014

MongoDB CRUD: Part II

Welcome to part two of our excellent adventure. Before we resume, let's seed our database with some more documents to play with.

var max = 33;
while (max--) {
    db.stomach.insert({
        name: 'Oreo',
        part: max % 3 === 0 ? 'white' : 'black'
    });
}

Update

Now that we've got a bunch of Oreos in our stomach collection, I don't think the Sweetwater we added in Part I was such a good idea. Let's change it.

  1. Find the documents we want to update. We'll do that with another query.
  2. Specify the new values. That's done with the update parameter.
db.stomach.update(
    // query
    { beer: 'Sweetwater' },

    // update parameter
    {
        $set: {
            beer: 'root'
        }
    }
);

We changed the document's beer value from 'Sweetwater' to 'root'. This did not affect the other fields in the document, as you can see.

db.stomach.find({
    beer: {
        $exists: true
    }
}).pretty();

{
    "_id" : ObjectId("5424a5ba28f262081e997a7f"),
    "beer" : "root",
    "count" : 2
}

What if we want to completely replace the fields in the document, though? Who wants rootbeer with cookies? Let's make it more complimentary to the other documents in the collection.

db.stomach.update(
    // query
    {
        beer: {
            $exists: true
        }
    },

    // update parameter
    {
        drink: 'milk',
        type: 'skim',
        ounces: 8
    }
);

By specifying a plain object as the update parameter instead of update operators, we've completely changed the document.

> db.stomach.find({ drink: 'milk' }).pretty();
{
    "_id" : ObjectId("5424a5ba28f262081e997a7f"),
    "drink" : "milk",
    "type" : "skim",
    "ounces" : 8
}

Note that the _id does not change when using update, even when replacing the document.

Now, let's change all those old-fashioned Oreos to one of the new flavors.

db.stomach.update(
    // query
    {
        name: 'Oreo',
        part: 'white'
    },

    // update parameter
    {
        $set: {
            part: 'berry'
        }
    }
);

Let's see the results.

> db.stomach.find({ name: 'Oreo', part: 'berry' }).pretty();
{
    "_id" : ObjectId("542603ba21330a1f47f4bd68"),
    "name" : "Oreo",
    "part" : "berry"
}

Only one of the documents was updated. This brings us to the 3rd parameter of update, the options. The options are described in the documentation, one of which is multi.

db.stomach.update(
    // query
    {
        name: 'Oreo',
        part: 'white'
    },

    // update parameter
    {
        $set: {
            part: 'berry'
        }
    },

    // options
    {
        multi: true
    }
);
> db.stomach.find({ name: 'Oreo', part: 'berry' }).count();
11

By default, update only modifies a single document. With multi, we can make it update all the documents matched by our query.

Delete

Now we've got a stomach collection full of berry cookies and milk, the anchovy pizza isn't really sitting well. Let's barf it up.

db.stomach.remove({
    anchovies: {
        $exists: true
    } 
});

That should seem pretty intuitive by now.

References


Check out the accompanying Github repo to these posts about MongoDB/Mongoose.