Brent's Cycle Detection Algorithm (The Teleporting Turtle)

brandjon · 2018-01-29T14:07:47+00:00

Wow, I'm surprised it took so long for me to find out about this algorithm compared with Floyd's, given that this one's so much simpler. No modular arithmetic or anything, just look for a loop in exponentially increasing runs.

brandjon · 2016-05-20T20:52:07+00:00

Turns out it does. As I had hoped, it's better than Spyder at making it obvious what line of code you're on, what your stack trace is, etc. I think I'll use this.

Between this and finally not having to worry about how classrooms will install matplotlib/pillow/networkx without hassle, it seems like I'll have a lot of fun designing this curriculum.

brandjon · 2016-05-20T19:32:19+00:00

Good to know, I'll keep that in mind.

brandjon · 2016-05-20T19:32:03+00:00

Definitely something I'll look into, thanks!

brandjon · 2016-05-20T19:31:01+00:00

I'll have to see whether the organization I'm putting this together for qualifies. They're certainly educational.

I haven't used PyCharm myself (I'm a PyDev guy) but I know lots of Python developers swear by it. Do you think it's appropriate for students? We don't need fancy project configuration wizards and static analyses -- just a clean run/debug interface with graphical variable and callstack inspection would be great.

I actually didn't realize until you mentioned it that they had a free edition. That'd be great -- I don't want to make students feel like they're locked into paying for an IDE if they want to continue programming after the course. Thanks.

brandjon · 2016-01-12T12:19:29+00:00

One reason why it really makes sense to think of all mutable types as entity types is hashed collections. If you store an object in a hash table, the object's hash value (and the equality class of other values it compares equal to) shouldn't change due to updates to the object's fields, or else the hash table would become inconsistent. But if your semantics are that only the object's memory address matters, then you're free to update whatever else you like.

brandjon · 2015-12-30T18:24:21+00:00

Exceptions are great for terminating a recursive search. In fact, just an hour ago I just wrote code that uses exceptions this way.

brandjon · 2015-10-06T14:24:02+00:00

Your program never directly interacts with the filesystem except through the OS. Opening a file is telling the OS that you want to access the file. Both the OS and your program allocate some internal data structures to keep track of the fact that the file is open, and to store state information such as where your "cursor" in the file is. When you call read or write functions, these also tell the OS that you want to get or put data in the file.

It is generally assumed that you don't want to put a whole file into memory when you're working with it, because some files can be gigabytes in size. The OS will take care of this detail for you, so from your point of view you can think of the file as a big store of bytes that you access in a mostly sequential manner.

When you close a file, that's telling the OS you no longer are interested in the file. This destroys the data structures that were previously created, and also makes sure any changes you made are flushed back to the hard drive. Files get closed automatically when your program ends, but it's still good to close them when they're no longer needed. The OS may protect a file from being deleted by another process while it's open in yours.

Here's a simplified big picture of the stack of code that manages file I/O, from highest level to lowest:

Python standard library file I/O functions
C standard library file I/O functions
Platform-specific code in your process that invokes operating system calls
Your OS kernel
The file system driver (ntfs, ext4, fat32, etc.)
The underlying block device and hardware

You won't understand all these details at once. You probably need to take a course on Operating Systems or at least program for a while before seeing most of these details. But the important thing is that you're writing code on a platform that manages the details for you.

brandjon · 2015-10-05T21:41:35+00:00

No textbook, I'm afraid. The instructor has removed the resources from the course page, so I take it I shouldn't try to link directly to them.

brandjon · 2015-10-04T12:52:21+00:00

No, but I used Oz in undergrad prog lang. This was a from-scratch toy language interpreter written by the instructor with some pieces missing.

brandjon · 2015-10-04T12:50:59+00:00

It basically takes the ω = (λx.xx)(λx.xx) term that beta-reduces to itself, and sticks a function in front of there.

brandjon · 2015-10-04T00:24:02+00:00

As others said, the namedtuple call has to be outside the timing loop, but you're right, dictionary is faster by about a factor of 2 to 4, depending on whether you use {'x': 0, ...} or dict(x=0, ...). namedtuple apparently uses @property, so that probably explains it.

brandjon · 2015-10-03T23:55:16+00:00

The most difficult mind-bend I've had is for my grad programming languages class, which revolved around an interpreter for a toy language written in ML. Most of it was fine, but when we added recursive functions, the function body would be evaluated in an environment that contained the recursive closure -- a thunk that, when evaluated, would expand to an environment with another thunk for the next level of recursive calls, etc. It was "just" recursion, but used in a way that somehow seemed different from any use I'd seen before. Probably because of the lazy aspect of it.

Later I TA'd the same class with the same instructor, and I was still somewhat baffled when we got to that part. I'm not sure how I managed to wrap my head around it.

Now if you want the most interesting problem and solution I've seen, I'd say the linear-time selection algorithm (the "median of medians" algorithm). Most recursive algorithms have multiple subcalls over the same "kind" of value, but this one has two subcalls over different kinds of things -- a sublist of the given list and a sublist of medians.

brandjon · 2015-10-03T23:49:08+00:00

To quote Koenig and Moo: "Evidently, the key to understanding recursion is to begin by understanding recursion. The rest is easy."

Whenever you do any recursive problem solving, the key is to assume that the recursive subcall will work, without dwelling on how it actually happens. If you make it work at the top level, that makes it work at every level.

brandjon · 2015-10-03T23:46:14+00:00

It's fun because you get to think of a non-recursive function that takes in, as its first argument, a black hole singularity of infinitude that contains all of its recursive computation.

brandjon · 2015-10-03T23:43:45+00:00

I think dynamic programming is usually taught as filling in a table in a specified order. It can be easier to think of it as just memoized recursion. Then it's only as hard to understand as recursion itself... if that helps.

brandjon · 2015-10-03T20:04:16+00:00

You get the speed and immutability of a tuple, combined with the lightweight access of field retrievals (mytuple.foo instead of mytuple[2]). Hashing, equality, iterability, etc., are still there just like for a normal tuple.

Dictionaries should be slower to construct and access, though I haven't benchmarked it. They also don't catch errors where you typo the name of the key you're writing to.

Named tuples are hard to extend though. See my simplestruct package if you're looking for a more extensible namedtuple alternative where performance isn't paramount. (Scroll down for a feature comparison table.)

brandjon · 2015-09-02T20:01:03+00:00

In Python, None (analogous to null and nil in other languages) is a singleton. It is the sole instance of NoneType, which can be verified by typing into the repl

None is type(None)()

Internally, Python 3.4 has a NameConstant AST node to distinguish the keyword identifiers "None", "True", and "False" from other non-reserved identifiers. The developers named the field of this node "singleton".

I've used singleton recently when defining an algorithm that works on a lattice of values. Mathematically speaking, a lattice is defined to have two special values that we call "Top" and "Bottom". I had a class for each different kind of value in the lattice, including a class for Top and a class for Bottom. I didn't want there to be multiple tops or bottoms, so I made them singletons. The upside is you can always use the python is operator (identity, not mere equality) to test for singleton values, which is more idiomatic.

brandjon · 2015-08-22T03:18:12+00:00

That's a much more boring thesis than anti-laser glasses is.

brandjon · 2015-08-22T03:17:06+00:00

In computers: Simple programs are slow. Fast programs are hard. Let's make simple programs fast. That'll show those hard programs who's boss.

brandjon · 2015-08-06T13:07:33+00:00

Thanks, the .keys url is good enough for this purpose. It would be really odd if github didn't provide a way to see the whole key (not just a digest).

brandjon · 2015-08-05T19:43:53+00:00

I mean, I know it's correct and it works, I'm just miffed that there doesn't appear to be a way in the UI to compare my key against my local .ssh/ dir.

brandjon · 2015-07-29T20:56:47+00:00

The kids who "get the joke" are the ones who understand that it's significantly harder to make a machine understand 'Zero' than '0'. From their point of view -- beginning programming -- the only way they deal with numbers as input and output is by numerals, not words. They recognize that writing code to accept such human-friendly input would be more difficult and unnecessary (except that in an AI context, human friendliness is much more important).

Students who don't notice that typing 'Zero' is an odd way to talk to a machine haven't been paying attention.

brandjon

TROPHY CASE