Since Timsort is not covered in class, this blog seems like the perfect place to write a few lines about the built-in sorting algorithm in Python. Timsort is a relatively new sorting algorithm, invented by Tim Peters for the Python programming language, and is arguably one of the best sorting algorithms invented so far.
The first thing to note about Timsort is that it is a hybrid sorting algorithm, utilizing both merge sort and insertion sort, and exploiting their respective strengths to achieve a worst case runtime of O(nlogn), which is best a modern sorting algorithm can achieve without the help of customized data structures or hash tables.
One of the central concepts of Timsort is the idea that any random list has a high probability of containing at least one sorted sublist, called 'run', which can be either non-descending or strictly descending. And then there is 'minrun', which is the minimum length of run required by the implementation of Timsort.
First, the algorithm searches for a run, if the run is shorter than the minrun, then items are removed from the remaining list and inserted into the correct position in the list. This process is repeated until all runs are obtained. After that, insertion sort, which is best for short lists, is used to sort the runs. When all of that is done, merge sort is used to merge (and sort) the runs and the remaining list.
Of course, the usage of merge sort and insertion sort in optimal conditions alone will not itself guarantee efficiency of the Timsort algorithm. The part that makes it fast depends on the size of the minrun and the management of the remaining list.
Wednesday, 26 March 2014
Wednesday, 19 March 2014
Week 10 SLOG
Regular Expressions (regexes) are found everywhere in computer interfaces, even if they seem to be obscured from the typical user. Our Csc148H1 assignment 2 is all about working with them, and since then, I have developed a deep respect for the people involved in the coding of regexes, because while the programming process seems to be easy at first glance, it is actually very complicated. There are always cases you have not considered and even when you do, you might get it wrong. For example, the star '*' case might seem very easy to code for at first, but it actually involves creating slices of the original string to be compared with the remaining regex.
When I mentioned that regexes are sometimes obscured, I'm talking about how search engines such as Google Search parses strings in the form 'r1 r2 r3' as r1.r2.r3. When you think about it, there is a lot going underneath the shiny interfaces that we encounter in our daily virtual lives.
When I mentioned that regexes are sometimes obscured, I'm talking about how search engines such as Google Search parses strings in the form 'r1 r2 r3' as r1.r2.r3. When you think about it, there is a lot going underneath the shiny interfaces that we encounter in our daily virtual lives.
Thursday, 13 March 2014
Week 9 SLOG
This week's class was primarily about the concept, implementation, and the performance advantage of the sorted binary tree data structure when it comes to searching. But while the worst case O(logn) runtime is impressive, there is actually another search method that eclipses the search power of the sorted binary tree - searching by means of a hash table.
First, a hash table is a array-like data structure that has a key and an associated value (similar to the dict type in Python). the nature of the value varies depends on the usage of the hash table. In the case of storage of raw data, the value is the memory address of the file/data. For the purpose of, say storing a list of numbers, the value *can* be the numbers themselves. So what are the keys? To obtain a key, a hash function is used to designate each value a unique number. So, when a user is searching for a particular number, the search engine only has to use the hash function to get a key, which can then be used to get the value directly from the table.
With hash tables, the worst case runtime is in the O(1) - constant time. Of course, the implementation is not easy and I would not be surprised if I only get to learn them in my third year.
First, a hash table is a array-like data structure that has a key and an associated value (similar to the dict type in Python). the nature of the value varies depends on the usage of the hash table. In the case of storage of raw data, the value is the memory address of the file/data. For the purpose of, say storing a list of numbers, the value *can* be the numbers themselves. So what are the keys? To obtain a key, a hash function is used to designate each value a unique number. So, when a user is searching for a particular number, the search engine only has to use the hash function to get a key, which can then be used to get the value directly from the table.
With hash tables, the worst case runtime is in the O(1) - constant time. Of course, the implementation is not easy and I would not be surprised if I only get to learn them in my third year.
Wednesday, 5 March 2014
Week 8 SLOG
During the reading week, I stumbled upon metaclasses while looking for some ideas/inspiration for the second assignment. What that began as a misunderstanding (as always) of the requirements of the first part of a2 (make public attributes read-only) became a really (valuable?) learning experience when I found out that not only are all classes in Python objects, they are instances of metaclasses, the most common being the metaclass type. type(), for the uninitiated actually has 2 functions.
The first, of course, is to return the data type (note that since Python does not have data types in the traditional sense, the term does not necessarily apply) of an object. To do that, only one argument, the object itself has to be passed to type().
What most Python users don't know is that type can alternately act as a class 'factory', accepting three arguments, and returning a class (which is actually an object itself). The first is a str with the desired name of the class to be returned, the second is a tuple of the classes to inherit from, and the third is a dict of the desired class attributes. Note that class attributes are the variables that can be accessed by calling <class name>.<variable name>, and the embedded methods in the class.
So what exactly do metaclasses do? Well, when used outside of class definitions, it just returns a class from the arguments passed. The interesting part is when a metaclass argument is passed to class defintions. To do so, Python users can either write a function (or class method - very complicated) which returns a class and then add the argument metaclass = <desired metaclass> to the class defintion. When the class is evaluated prior to code execution, the metaclass will override the __new__ method in the class (__new__ is the default metaclass, which returns a basic class object), thus modifying the class before instances of the new class can be created.
Of course, that is not all Python users can do with metaclasses. Should the metaclass be defined as a class itself, there are many other things that can be done. But as I said, doing that is extremely complicated (no kidding!) and I'm not necessarily confident enough to write it here yet.
The first, of course, is to return the data type (note that since Python does not have data types in the traditional sense, the term does not necessarily apply) of an object. To do that, only one argument, the object itself has to be passed to type().
What most Python users don't know is that type can alternately act as a class 'factory', accepting three arguments, and returning a class (which is actually an object itself). The first is a str with the desired name of the class to be returned, the second is a tuple of the classes to inherit from, and the third is a dict of the desired class attributes. Note that class attributes are the variables that can be accessed by calling <class name>.<variable name>, and the embedded methods in the class.
So what exactly do metaclasses do? Well, when used outside of class definitions, it just returns a class from the arguments passed. The interesting part is when a metaclass argument is passed to class defintions. To do so, Python users can either write a function (or class method - very complicated) which returns a class and then add the argument metaclass = <desired metaclass> to the class defintion. When the class is evaluated prior to code execution, the metaclass will override the __new__ method in the class (__new__ is the default metaclass, which returns a basic class object), thus modifying the class before instances of the new class can be created.
Of course, that is not all Python users can do with metaclasses. Should the metaclass be defined as a class itself, there are many other things that can be done. But as I said, doing that is extremely complicated (no kidding!) and I'm not necessarily confident enough to write it here yet.
Subscribe to:
Posts (Atom)