The idea is to keep a slow traverser (the tortoise) and a fast traverser (the hare). If there are no cycles, eventually, the hare should hit the end of the list. However, if there are cycles, eventually the hare will see something that the tortoise has too which is enough for us to stop traversing.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

class Node(object):

    def __init__(self, data = None, next_node = None):
        self.data = data
        self.next = next_node


def traverser(head, step):
    at = head
    try:
        for i in range(1, step):
            at = at.next
    except AttributeError:
        raise StopIteration
    if at.next is None:
        raise StopIteration
    yield at.next


def has_cycle(head):
    tortoise = traverser(head, 1)
    hare = traverser(head, 2)
    seen_by_tortoise = set()
    while True:
        try:
            seen_by_tortoise.add(next(tortoise))
            hare_test = next(hare)
        except StopIteration:
            return False
        else:
            if hare_test in seen_by_tortoise:
                return True

The idea is to keep an inbox and outbox using stacks. Here is a simple implementation.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

class Queue(object):

    def __init__(self):
        self._inbox = Stack()
        self._outbox = Stack()

    def _refill(self):
        if not self._outbox:
            while self._inbox:
                self._outbox.push(self._inbox.pop())

    def peek(self):
        self._refill()
        try:
            return self._outbox.peek()
        except IndexError:
            raise EmptyQueueError()

    def pop(self):
        self._refill()
        try:
            retval = self._outbox.pop()
        except IndexError:
            raise EmptyQueueError()
        else:
            return retval

    def push(self, value):
        self._inbox.push(value)


class Stack():

    def __init__(self, iterable=None):
        self._data = [] if iterable is None else list(iterable)

    def __bool__(self):
        return bool(self._data)

    def peek(self):
        return self._data[-1]

    def pop(self):
        return self._data.pop()

    def push(self, value):
        self._data.append(value)


class EmptyQueueError(BaseException):
    pass

Datasets these days are getting larger and and so is hardware in keeping with Moore’s law. However, Moore’s law applies to population trends. For a given user, budget constraints create a situation where hardware resources increase as a step function. On the other hand, the growth function for datasizes can be approximated with a much smoother exponential. This keeps users typically chasing their own hyper-personal version of big data.

I recently started using lua and torch to learn about neural networks. I wanted to start simple and build a classifier for a kaggle competition. However, the data for this competition is too big for my machine with a measly 16 gigs of RAM. [This used to be a luxury only half a decade ago.]

So, after some digging around on github, I figured how to train with fairly large datasets with stock torch infrastructure and I’m gonna show you how and why it works.

One of the formats that I like to edit is markdown (yeah, yeah, I know about org-mode, shush!). Another thing that I like to do, when editing markdown, is to preview it in my browser as html. This can be done by exporting the markdown file to html each time the markdown buffer is written to. Now, I like this solution except when I don’t! To generalize the problem, one wants an action to be trigerred, perhaps for a major mode (or not), every time an event happens in a buffer. On the other hand, one also wants this behavior to be togglable at will. For example: convert all tabs to spaces, run a linter, compile a file etc every time an event occurs in the buffer.

The first sub-problem – of triggering the action – is solved easily using Emacs’ various hooks. The second problem is also easily solved using a little lisp. Here’s how.

Have you ever used a logistic regression? Would you like to be able to say you have used a neural network – perhaps in your next interview? Here’s your cheat code.

NB: NFL applies insomuch as you will have to know what we are talking about in this post. This is not a tutorial.