When estimating a value, it is often easier to start with an upper and lower bound on that value. Once you have an upper and lower bound, you can pick a representative point estimate in that interval. The first and most obvious candidate is the (arithmetic) mean of the upper and lower bounds, but this is only valid if the upper and lower bounds are close together, or have the same order of magnitude. If the upper and lower bounds span multiple orders of magnitude, then it is better to use the geometric mean.
I was reading another blog post about reinforcement learning using Monte Carlo and tabulation methods that provided an example of the technique using Blackjack. I decided to implement my own method using Tic-Tac-Toe as an example. The basic idea is that you generate a random state of a game, and you generate a random action based on that state. Then you play the rest of the game through until the end and record the outcome. Then you should be able to store the state, action, and outcome as a key in a dictionary that refers to a count. Each time that state-action-outcome occurs again, you update the count by one. Over time, your dictionary will encode information about the relative strengths of different actions for a given state.
In this post, I’ll be (slowly) building a
UITableView application programmatically in a Playground. First we’ll add a simple UITableView, then we’ll add a UINavigationBar. In future edits, I’ll add some more views.
Summarizing the average performance of a set of things under different loads is a particularly tricky thing. The correct way to summarize performance is to use the geometric mean instead of the arithmetic mean. The tricky part is that the difference between the arithmetic and geometric mean is only significant under a certain condition, so the impact of using the arithmetic mean instead of the geometric may not be painfully obvious. Let’s start with an example.
Tonight I’m looking at some sorting algorithms in Python. First up are Bubble Sort and Selection sort, both with average and worst case runtime, and memory. Finally, I’ll look at an iterative and recursive implementation of Merge Sort.
This is a work in progress, there’s a lot of complex questions you can ask about graphs, but I though it was neat that you could produce an actual graphy looking thing in so few lines of code. This is a directed graph, and you use the graph object to first create nodes, and then define (unweighted) edges between them or to themselves. The
__repr__() method just lists the node data, whatever that is, with an ASCII arrow pointing to another node’s data.
Here is round two for linked lists, the doubly linked list. It’s not very much more complex than a singly linked list. Breaking things into cases using the
self.count attribute makes the code easier to read and reason about.
I’ve posted before about creating a tree in Python, but I like this implementation better. It uses a nested class to represent the nodes of the tree, and an interesting construction (line 11) that is a result of that nested class. Also, I do a simple pre-order traversal. I’ll flesh this guy out in later posts.