The Origin of Best Practices

Hacking

According to Richard Stallman, hackers have love of excellence and programming in common. The enjoy the creative challenging to overcome technical limitations and achieve things not thought possible before. People who are good at hacking are indispensable in todays technology-driven society. Hacking is a key skill, and we need people who are good at it. Without doubt, hacking is a useful skill in programming. Python is an excellent language to hack things in.

However, I don't think hacking is a great approach to programming in general. I give three reasons for that.

  • First hacking focuses on novel, difficult, or otherwise challenging problems.
  • Second, hacking has a strong connotation of excellence.Hackers are often considered an elite, a community that requires an unspoken skill level to belong to. But in programming ,there are many problems that do not need an expert to solve. Often, an average programmer is sufficient, where a hacker might become bored.
  • Third, not everybody wants to devote themselves to hacking. Many of us have other things to do than figuring out in all details how computers work; we have data to understand, websites to crate, a business to run, and families to take care of. In my option, programming is far too important to leave it to a small group of devoted experts.

Software engineering

Opposed to hacking, we find software engineering. Software engineering is concerned with a systematic approach to building software, usually in a corporate environment. Instead of focusing on the individual, software engineering is about controlling the entire process of building programs: its techniques cover finding out precisely what is to be built, designing a program with clearly defined opponents, verifying that the program actually works correctly and, finally, maintaining the program once it is being used.

The drawback of the software engineering approach is that it is too big for most Python projects.

Agile

The notion that software engineering is a rather heavy methodology is not new. When asking for an alternative, the answer you will often hear in 2017 is Agile. Agile is a philosophy dedicated to improving the software development process. Its core values are individuals and interactions, working software, customer collaboration, and responding to change. agile promotes rapid, evolutionary development of programs and working in short iterations.

Agile is a philosophy, not a set of tools. Agile tells us why we might want to program in a certain way (to crate working software quickly and have satisfied customers), but it does not tell us what to do when in front of a keyboard. Also, Agile frameworks are often difficult to implement in practice.

Software craftsmanship

Software craftsmanship acknowledges that a big portion of programming consists of simple task that need to be done. To do it well, we need to have the right tools, we need to have the right skills, and we need to apply both in practice. Programming being a craft like masonry, carpentry, or confectionery suggests that

  • Purpose matters. We are creating programs as a means to an end. Programming is not an art; we want to write programs that are used.
  • Planning matters.
  • Tools matter.
  • Skills matter.
  • Community matters.
  • Size does not matter.
  • Practice matters.

Introduction to Algorithms — Red-Black Tree

1. Properties of red-black trees

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can either RED or BLACK. By constraining the node colors on any simple path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.

Each node of the tree now contains the attributes color, key, left, right, and p. If a child or the parent of a node does not exist, the corresponding pointer attribute of the node contains the value NIL. We shall regard these NILs as being pointers to leaves (external nodes) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree.

A red-black tree is a binary tree that satisfies the following red-black properties:

  1. Every node is either red or black.
  2. The root is black.
  3. Every leaf (NIL) is black.
  4. If a node is red, then both its children are black.
  5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

Screen Shot 2017-05-05 at 8.27.10 P

As a matter of convenient in dealing with boundary conditions in red-black tree code, we use a single sentinel to represent NIL. For a red-black tree T, the sentinel T.nil is an object with the same attributes as an ordinary node in the tree.

  • Its color attribute is BLACK, and its other attributes — p, left, right, and key can take on arbitrary values.

As Figure (b) shows, all pointers to NIL are replaced by pointer to the sentinel T.nil.

We use the sentinel so that we can treat a NIL child of a node x as an ordinary node whose parent is x .

  • Although we instead could add a distinct sentinel node for each NIL in the tree, so that the parent of each NIL is well defined, that approach would waste space.
  • Instead, we use the one sentinel T.nil to represent all the NILs — all leaves and the root’s parent. The values of the attributes p, left, right, and key of the sentinel are immaterial, although we may set them during the course of a procedure for our convenience.

Screen Shot 2017-05-05 at 8.28.39 P

We generally confine our interest to the internal nodes of a red-black tree, since they hold the key values. In the remainder of this article, we omit the leaves when we draw red-black trees, as shown in (c).

Screen Shot 2017-05-05 at 8.30.02 P

We call the number of black nodes on any simple path from, but not including, a node x down to a leaf the black-height of the node, denoted bh(x). By property 5, the notion of black-height is well defined, since all descending simple paths from the node have the same number of black nodes. We define the black-height of a red-black tree to be the black-height of its root.

The following lemma shows why red-black tree make good search trees.

Lemma 1

A red-black tree with n internal nodes has height at most 2 \lg(n+1) .

proof:

As an immediate consequence of this lemma, we can implement the dynamic-set operations in O(\lg n) time on red-black trees, since each can run in O(h) time on a binary search tree of height h and any red-black tree on n nodes is a binary search tree with height O(\lg n) . Although the algorithms TREE-INSERT and TREE-DELETE in Binary Search Tree run in O(\lg(n)) time when given a red-black tree as input, they do not directly support the dynamic-set operations INSERT and DELETE, since they do not guarantee that the modified binary search tree will be a red-black tree.


2. Rotations

The search-tree operations TREE-INSERT and TREE-DELETE, when run on a red-black tree with n keys, take O(\lg n) time. Because they modify the tree, the result may violate the red-black properties enumerated in Section 1. To restore these properties, we must change the colors of some the nodes in the tree and also change the pointer structure.

We change the pointer structure through rotation, which is a local operation in a search tree that preserves the binary-search-tree property. Figure 2 shows the two kinds of rotations: left rotations and right rotations.

  • When we do a left rotation on a node x , we assume that its right child y is not T.nil ; x may be any node in the tree whose right child is not T.nil .
    • The left rotation “pivots” around the link from x to y . It makes y the new root of the subtree, with x as y ‘s left child and y ‘s left child as x ‘s right child.

The pseudocode for LEFT-ROTATE assumes that x.right \neq T.nil and that the root’s parent is T.nil .

fig_13-2

LEFT-ROTATE(T, x)
  

Figure 3 shows an example of how LEFT-ROTATE modifies a binary search tree. The code for RIGHT-ROTATE is symmetirc. Both LEFT-ROTATE and RIGHT-ROTATE run in O(1) time. Only pointers are changed by a rotation; all other attributes in a node remain the same.

fig_13-3

3. Insertion

We can insert a node into an n -node red-black tree in O(\lg(n)) time. To do so, we use a slightly modified version of the TREE-INSERT procedure to insert node z into the tree T as if it were an ordinary binary search tree, then we color z red. To guarantee that the red-black properties are preserved, we then call an auxiliary procedure RB-INSERT-FIXUP to recolor node and perform rotations. The call RB-INSERT(T, z) inserts node z , whose keys is assumed to have already been filled in, into the red-black tree T .

RB-INSERT(T, z)
  

The procedures TREE-INSERT and RB-INSERT differ in four ways.

  • First, all instance of NIL in TREE-INSERT are replaced by T.nil.
  • Second, we set z.left and z.right to T.nil in lines 14-15 of RB-INSERT, in order to maintain the proper tree structure.
  • Third, we color z red.
  • Fourth, because coloring z red may cause a violation of one of the red-black properties, we call RB-INSERT-FIXUP(T, z) of RB-INSERT to restore the red-black properties.
RB-INSERT-FIXUP(T, z)
  while z.p.color == RED
    if z.p == z.p.p.left
        y = z.p.p.right
        if y.color == RED
            z.p.color = BLACK           // case 1
            y.color = BLACK             // case 1
            z.p.p.color = RED           // case 1
            z = z.p.p                   // case 1
        else if z == z.p.right
                  z = z.p               // case 2
                  LEFT-ROTATE(T, z)     // case 2
        else
            z.p.color = BLACK           // case 3
            z.p.p.color = RED           // case 3
            RIGTH-ROTATE(T, z.p.p)      // case 3
    else (same as then clause with "right" and "left" exchanged)
  T.root.color = BLACK            

To understand how RB-INSERT-FIXUP works, we shall our examination of the code in three major steps.

  • First, we shall determine what violations of the red-black properties are introduced in RB-INSERT when node z is inserted and colored red.
  • Second, we shall examine the overall goal of the while loop in line 1-15.
  • Finally, we shall explore each of the three cases within the while loop’s body and see how they accomplish the goal.

Figure 4 shows how RB-INSERT-FIXUP operates on a sample red-black tree.

fig_13-4


4. Deletion

RB-DELETE-FIXUP(T, x)

Introduction-to-algorithms — dynamic programmimng

Dynamic programming typically applies to optimization problems in which we make a set of choices in order to arrive at an optimal solution. As we make each choice, subproblems of the same form often arise. Dynamic programming is effective when a given subproblem may arise form more than one partial set of choices.

  • The key technique is to store the solution to each such subproblem in case it should reappear.

Divide-and-conquer algorithms portion the problem into disjoint subproblems, solve the subproblems recursively, and then combine their solutions to solve the original problem — that is, when subproblems share subsubproblems.

  • In this context, a divide-and-conquer algorithm does more work than necessary, repeatedly, solving the common subsubproblems.

A dynamic-programming algorithm solves each subsubproblem just once and then saves its answer in a table, thereby avoiding the work of recomputing the answer every time it solves each subsubproblem.

We typically apply dynamic programming to optimization problems. Such problems can have many possible solutions. Each solution has a value, and we wish to find a solution with the optimal (minimum or maximum) value. We call such a solution an optimal solution to the problem, as opposed to the optimal solution, since there may be several solutions that achieve the optimal value.

When developing a dynamic-programming algorithm, we follow a sequence of four steps:

  1. Characterize the structure of an optimal solution.
  2. Recursively define the value of an optimal solution.
  3. Compute the value of an optimal solution, typically in a bottom-up fashion.
  4. Construct an optimal solution from computed information.

Step 1-3 from the basis of a dynamic-programming solution to a problem.

  • If we need only the value of an optimal solution, and not the solution itself, the we can omit step 4.
  • When we do perform step 4, we sometimes maintain additional information during step 3 so that we can easily construct an optimal solution.

Read More »

Performance of Python Data Structures

It is important for you to understand the efficiency of these Python data structures because they are the building blocks we will use as we implement other data structure in the remainder of the book.

Lists

The designers of Python had many choices to make when they implemented the list data structure. Each of these choices could have an impact of how fast on how fast list operations perform. To help them make the right choices they looked at the ways that people would most commonly use the list data structure and they optimized their implementation of a list so that the most common operations were very fast. Of course they also tried to make the less common operations fast, but when a tradeoff and to be made the performance of a less common operation was often sacrificed in favor of the more common operation.

Two common operations are indexing and assigning to an index position. Bothe of these operations take the same amount of time no matter how large the list becomes. When an operation like this is independent of the size of the list they are O(1) .

Read More »

Mathematics for 3D Game Programming and Computer Graphics – Vectors

Vectors are of fundamental importance in any 3D game engine. They are used to represent points in space, such as the locations of objects in a game or the vertices of a triangle mesh. They are also used to represent spatial directions, such as the orientation of the camera or the surface normals of a triangle mesh. Understanding how to manipulate vectors is an essential skill of the successful 3D programmer.

Throughout this book, we encounter vectors of various types, usually representing two-dimensional, three-dimensional, or four-dimensional quantities. For now, we make no distinction between vectors representing options and vectors representing directions, nor do we concern ourselves with how vectors are transformed from one coordinate system to another.

Vector Properties

The Dot Product

The dot product of two vectors, also known as the scalar product or inner product, is one of the most heavily used operations in 3D graphics because it supplies a measure of the difference between the directions in which the two vectors point.

\mathbf{P} \cdot \mathbf{Q} = \sum_{i=1}^{m} P_i Q_i.

This definition states that the dot product of two vectors is given by the sum of the products of each component. In three dimensions, we have

\mathbf{P} \cdot \mathbf{Q} = P_x Q_x + P_y Q_y + P_z Q_z.

The dot product P \cdot Q may also be expressed as the matrix product:

\mathbf{P}^T \mathbf{Q} = \begin{bmatrix}P_1 & P_2 & \cdots & P_n\end{bmatrix} \begin{bmatrix} Q_1 \\ Q_2 \\ \vdots \\ Q_n \end{bmatrix},

Now for an important theorem that reveals the ubiquitous utility of the dot product.

Given two n -dimensional vectors \mathbf{P} and \mathbf{Q} , the dot product \mathbf{P} \cdot \mathbf{Q} satisfies the equation

\mathbf{P} \cdot \mathbf{Q} = \lVert P \rVert \lVert Q \rVert \cos \alpha

where \alpha is the planar angle between the lines connecting the origin to the points represented by \mathbf{P} and \mathbf{Q} .

The Cross Product

The cross product of two three-dimensional vectors, also known as the vector product, returns a new vector that is perpendicular to both of the vectors being multiplied together. This property has many uses in computer graphics, one of which is a method for calculating a surface normal at a particular point given two distinct tangent vectors.

The cross product of two 3D vectors P and Q , written as P \times Q , is a vector quantity given by the formula:

P \times Q = < P_yQ_z - P_zQ_y, P_zQ_x - P_xQ_z, P_xQ_y - P_yQ_x >

A commonly used tool for remembering this formula is to calculate cross products by evaluating the pseudodeterminant

P \times Q = \begin{vmatrix} i & j & k \\ P_x & P_y & P_z \\ Q_x & Q_y & Q_z \end{vmatrix}

Theorem 2.8

\lVert P \times Q \rVert = \lVert P \rVert \lVert Q \rVert \sin \alpha

where \alpha is the planar angle between the lines connecting the origin to the points represented by P and Q .

We know that any nonzero result of the cross product must be perpendicular to the two vectors being multiplied together, but there are two possible directions that satisfy this requirement. It turns out that the cross product follows a pattern called the right hand rule.

Mathematics for 3D Game Programming and Computer Graphics – The render pipeline

This chapter provides a preliminary review of the rendering pipeline. It covers general functions, such as vertex transformation and primitive rasterization, which are performed by modern 3D graphics hardware. Readers who are familiar with these concepts may safely skip ahead. We intentionally avoid mathematical discussions in this chapter and instead provide pointers to other parts of the book where each particular portion of the rendering pipeline is examined in greater detail.

Graphics Processors

A typical scene that is to be rendered as 3D graphics is composed of many separate objects. The geometrical forms of these objects are each represented by a set of vertices and a particular type of graphics primitive that indicates how the vertices are connected to produce a shape. Figure 1.1 illustrates the ten types of graphics primitive defined by the OpenGL library. Graphics hardware is capable of rendering a set of individual points, a series of line segments, or a group of filled polygons. Most of the time, the surface of a 3D model is represented by a list of triangles, each of which references three points in a list of vertices.

f0002-01

Read More »

Getting MEAN – Designing a MEAN stack architecture

A common MEAN stack architecture

A common way to architect a MEAN stack application is to have a representational state transfer (REST) API feeding a single-page application (SPA). The API is typically built with MongoDB, Express, and Node.js, with the SPA being built in Angular. The approach is particularly popular with those who come to the MEAN stack from an Angular background and are looking for a stack that gives a fast, responsive API. Figure 2.1 illustrates the basic setup and data flow.

fig_2-1

What is a REST API?

REST stands for REpresentational State Transfer, which is an architectural style rather than a strict protocol. REST is stateless – it has no idea of any current user state or history.

API is an abbreviation for application program interface, which enables applications to take to each other.

So a REST API is a stateless interface to your application. In the case of the MEAN stack, the REST API is used to create a stateless interface to your database, enabling a way for other applications to work with the data.

Figure 2.1 is a great setup, ideal if you have or intend to build an SPA as your user-facing side.

  • Angular is designed with a focus on building SPAs, pulling in data from a REST API, as well as pushing it back.
  • MongoDB, Express, and Node.js are also extremely capable when it comes to building an API, using JSON all the way through the stack, including the database itself.

This is where many people start with the MEAN stack, looking for an answer to the question, "I've built an application in Angular; now where do I get the data?"

Read More »

Getting MEAN – Introducing full-stack development

The MEAN stack is a pure JavaScript stack comprised of four main technologies, with a cast of supporting technologies:

  • MongoDB — the database
  • Express — the web framework
  • Angular — the front-end framework
  • Node.js — the web server

Why the MEAN stack specifically?

The MEAN stack pulls together some of the "best-of-breed" modern web technologies into a very powerful and flexible stack. One of the great things about the MEAN stack is that it not only uses JavaScript in the browser, it uses JavaScript throughout. Using the MEAN stack, you can code both the front end and back end in the same language.

The principle technology allowing the this to happen is Node.js, bringing JavaScript to the back end.

Read More »

TypeScript as a language for Angular applications

The reason is that developing in JavaScript isn’t overly productive. Say a function expects a string value as an argument, but the developer mistakenly invokes it by passing a numeric value. With JavaScript, this error can be caught only at run- time. Java or C# compilers won’t even compile code that has mismatching types, but JavaScript is forgiving because it’s a dynamically typed language.

On larger projects, good IDE context-sensitive help and support for refactoring are important. Renaming all occurrences of a variable of function name in spatially typed languages is done by IDEs in a split second, even in projects that have thousands oaf lines of code; but this isn’t the case in JavaScript, which doesn’t support types. IDEs can help with refactoring much better when the types of the variables are known.

To be more productive, you may consider developing in a statically typed language and then convert the code to Javascript for deployment. Currently there are dozens of languages that compile to JavaScript. The most popular are TypeScript, CoffeeScript, and Dart.

Why not use the Dart language?

  • Interoperability with third-party Javascript libraries isn’t that great.
  • Development in Dart can be done only in a specialized version of the Chrome browser (Dartium) that comes with the Dart VM.
  • The generated JavaScript isn’t easily readable by a human.
  • The community of Dart developers is rather small.

Read More »

JavaScript definite guide – Arrays

An array is an ordered collection of values. Each value is called an element, and each element has a numeric position in the array, known as its index.

  • JavaScript arrays are untyped: an array element may be of any type, and different elements of the same array may be of different types. Array elements may even by objects o other arrays, which allows you to create complex data structures, such as arrays of objects and arrays of arrays.
  • JavaScript arrays are zero-based and use 32-bit indexes: the index of the first element is 0, and the highest possible index is 4294967294 (2^32−2 ), for a maximum as needed and there is no need to declare a fixed size for the array when you create it or to reallocate it when the size changes.
  • JavaScript arrays may be sparse: the elements need not have contiguous indexes and there may be gaps.
  • Every JavaScript array has a length property.
    • For non sparse arrays, this property specifies the number of elements in the array.
    • For sparse arrays, length is larger than the index of all elements.

JavaScript arrays are specialized form of JavaScript object, and array indexes are really little more than property names that happen to be integers. Implementations typically optimize arrays so that access to numerically indexed array elements is generally significantly faster than access to regular object properties.


Inner link