Resort to sort

So the past few days I've been playing around with some simple algorithms. I'm not 'professionally' trained, and most of my experience has been with what I've seen in code or have implemented myself. Does that make me less of a developer for not being classically trained? Maybe, maybe not.

In particular I've been playing around with some of the sorting algorithms. Stuff like Bubble sort, Selection sort, Insertion sort, and of course Quicksort.

My first task as been to study the algorithm and look at whatever pseudo-code or explanation is presented for the algorithm. Study and understand it. Then is to walk away from any computer or anything, take a little break. After a short time I then pull out a pen and paper and write down a Dart version of the code. I write it out in front of me without referring to APIs, or without referencing the material.

I later then enter that code (or re-write it) into the Dart editor in a simple test file I have. I run it, fix my bugs, and run it again. My test file contains all of the various sorts as I learn them, it then prints out the sorted list and the time it took to complete (using a Stopwatch). I also have a function to create a list of X size filed with values from Random.nextInt.

Being able to easily create a random list of a determined size is nice, as it allows me to easily increment the list size as I choose and see the differences in performance. For instance it took a list of almost 5000 items for Quicksort with the two isolates to be faster than the main-thread version of Quicksort. (See Edit note below)

Many of the algorithms I've implemented are without performance improvements and are far from the most efficient versions available. One thing I've noticed though is List.sort((a, b) => a - b); has generally been one of the best performing algorithms, in lists of up to 10,000 items.

However as I mentioned none of the algorithms has been tuned for best performance or memory usage and are just the 'simple' versions of the algorithms just for my own learning purposes and less for actual performance comparisons. The performance comparisons are more of a visual reference to the Big O Notation for myself.

[Edit:]So I was wrong. I had poorly implemented my Quicksort with Isolates. Very poorly. It was a hodgepodge of Futures and a custom callback. I went through and cleaned it up and changed it so it returned a Future instead of calling a callback. Once I did that I saw an over 10x speed increase in the Quicksort with Isolates version and it and was about the same speed as the Main-threaded Quicksort for lists below 500 items. And faster for lists greater than 500 items. This has more to do with my unfamiliarity with Isolates than with the algorithms themselves.[/Edit]

For those who may be interested, you can the current version of the file here: https://github.com/butlermatt/sorting_dart. As time goes by, I will be adding more algorithms (with comments) as I learn them myself. Again please recall these are not optimized in any way and are only presented as-is, as proof of concept.
In time I may add some optimized versions of algorithms myself as I progress. Keep in mind however this is primarily a learning project and not designed for use. They may be (and are) buggy.

Serving Sockets... The Salad

I haven't had the opportunity to do much with Dart lately, due to scheduling. However this afternoon I had a little chance to write some more. I decided that I wanted to modify the EchoServer to maintain the connection and close the connection only when receiving a specific command. I also wanted to add a command to shutdown the server itself completely. In order to properly accommodate this, I needed to refactor the server code a little. I wrapped the ServerSocket in a manager class:

#import('dart:io');

class ServerManager {
  ServerSocket _listenServer;
  
  ServerManager() {
    _listenServer = new ServerSocket("127.0.0.1", 5700, 0);
    
    _listenServer.connectionHandler = this._handleConn;
  }

  void _handleConn(Socket conn) {
    StringInputStream clientIn = new StringInputStream(conn.inputStream);
    
    clientIn.lineHandler = () {
      String input = clientIn.readLine();
      print("Received: $input");
      if(input.toLowerCase() == 'stop') {
        String cls = "** Stopping Server. Closing connection **\n";
        conn.writeList(cls.charCodes(), 0, cls.length);
        conn.close();
        _listenServer.close();
        print("** Stopping Server! **");
      } else if(input.toLowerCase() == 'exit') {
        String cls = "** Closing connection to client **\n";
        conn.writeList(cls.charCodes(), 0, cls.length);
        conn.close();
        print("** Closing connection to client. **");
      } else {
        String output = "${input.toUpperCase()}\n";
        conn.writeList(output.charCodes(), 0, output.length);
        print("Sent: $output");
      }
    };
    
  }
}

void main() {
  ServerManager sMan = new ServerManager();
 
}

So as you can see I made a few changes from my original EchoServer. As mentioned above I wrapped the server in a manager class, this enables me to easily close the server socket without using a global variable. In addition I added a couple clauses to check for the 'stop' or 'exit' commands which will stop the server or just close the client connection respectively. And finally I stopped pulling the output stream of the sockets directly, and instead use the writeList methods directly on the socket itself. I wasn't gaining any real benefit by creating an additional variable for the socket's OutputStream, so I just dropped it altogether.

Now as is, the above will run and accept connections and echo any new lines until the stop or exit commands are received. If the exit command is received, then the server will close the connection to that socket. If stop is received it will close the connection to that socket and then tell the server to close. However because of the event driven nature of the server, the Sockets and ServerSockets are not blocking. That is, even without adding any additional threads (Isolates), we can accept connections from multiple sources. If you open up multiple telnet connections to the host, you can see how you can send data and receive responses on each connection independent of the other.

But this also leaves us with a small issue. If we tell the server to stop from one telnet session while the other is still active.. the server will accept the stop command, and it will schedule the ServerSocket to be stopped, but not until the other socket has been closed. Try it out and you will see that the connection in which we issue the stop command is disconnected, and the console will indicate that the server is stopping. But the other telnet session will remain active until we issue an exit or stop command. Only once the 2nd session is closed will the server stop. And if for some reason the other session does not terminate properly (for instance connection drops or the telnet application is closed before issuing an exit/stop command) then the server will hang, not accepting new connections but not terminating either (assuming eventually the socket will time out but potentially not since I do not have those error handlers in place either).

This may be the desired situation with some servers to shut them down gracefully for instance, however in our EchoServer we want it to shut down immediately if it receives the stop command. So we'll need to keep a list of active connections and iterate through them and close each one, then stop the server. So I ended up with the following:

#import('dart:io');

class ServerManager {
  ServerSocket _listenServer;
  List _socketList;
  
  ServerManager() {
    _socketList = new List();
    _listenServer = new ServerSocket("127.0.0.1", 5700, 0);
    
    _listenServer.connectionHandler = this._handleConn;
  }
  
  void sendStops() {
    List cls = "** Server received stop request. Closing connection to client **\n".charCodes();
    
    while(!_socketList.isEmpty()) {
      Socket conn = _socketList.removeLast();
      conn.writeList(cls, 0, cls.length);
      conn.close();
    }
  }
  
  void _handleConn(Socket conn) {
    _socketList.add(conn);
    StringInputStream clientIn = new StringInputStream(conn.inputStream);
    
    clientIn.lineHandler = () {
      String input = clientIn.readLine();
      print("Received: $input");
      
      if(input.toLowerCase() == 'stop') {
        sendStops();
        _listenServer.close();
        print("** Stopping Server! **");
      } else if(input.toLowerCase() == 'exit') {
        String cls = "** Closing connection to client **\n";
        conn.writeList(cls.charCodes(), 0, cls.length);
        int sockInd = _socketList.indexOf(conn);
        _socketList.removeRange(sockInd, 1);
        conn.close();
        print("** Closing connection to client: $sockInd **");
      } else {
        String output = "${input.toUpperCase()}\n";
        conn.writeList(output.charCodes(), 0, output.length);
        print("Sent: $output");
      }
    };
    
  }
}

void main() {
  ServerManager sMan = new ServerManager();
 
}

As you can see I also added a method sendStops just to iterate through all the sockets, popping them out of list and sending them the stop notice and disconnecting them. I made this separate from the actual stopping of the server in case it should ever be required for any other reason as well. Initially I tried using a Set to hold just unique connections, and provide easier way of removing elements however I found out that there's an issue with Set's in that any values stored in a set must implement Hashable. This wasn't added in the API documentation and it was only after a little digging through the DartBug page and Newsgroup that I found this is 'expected' behaviour. As such, I had to use the list. For a specific 'exit' command I have to get the index of the value and remove it from the list with removeRange with a size of 1 element. I also setup the broadcast message directly to a List of Int's immediately just to avoid having to convert it multiple times as I iterate through the connections. While still missing any error handling, etc. I'm rather pleased with how the server is progressing and in some ways it conjures up images of the old school MUD's. Maybe a project to play with?

A List of List stuff

So I continued on reading Seth Ladd's blog post on Lists and Arrays in Dart. One thing I didn't see mentioned that I think should be said, is that Lists are not type dependent. For people familiar with current dynamic languages such as Python, Ruby, and JavaScript that's not a big deal. But for those coming from Java, C, and other similar languages it is important to note that a List doesn't need to be all the same type. For instance the following is entirely valid:

List list = [1, "two", 3.48283008, [4, 4, "four", 4]];

So a List can contact mixed variable types, numbers, strings, even more Lists. However for those familiar with Javascript and other such dynamic languages who are used to associative arrays, its important to know that Lists are not that. As such you cannot assign a value to an index that does not yet exist.

List list = new List();
list[0] = "zero";
list[1] = 1;

IndexOutOfRangeException: 0

However, for extendable arrays, you can call set on length and increase the value. So you can grow, or shrink with more than just the add or addAll methods. For instance the following is valid:

List list = new List();
list.length = list.length + 2; // Now have two null values in the list.
list[0] = "zero";
list[1] = 1;
list.length = list.length - 1; // This removes the last value from the list.

Something important to note however, currently the API does not specifically state that changing the length to a value lower than the current will always have this effect. Currently there is no guarantee that the values will be removed from the end of the List, or even that they will be removed at all. I can see a situation where, if the values at the end are not null, then they may not reduce the size of the List. That or when setting list size, the new value must be greater than or equal to current size. As the libraries are improved and change (and there will be change don't doubt that for a second), we'll get a better idea of what to expect.

There are a number of List methods which can be extremely useful, that require a function be passed to them as an argument. You can create these functions inline or pass the name of another function. I'll cover more on passing functions in another post. Some of these methods are: filter, some, every, sort. Some and Every return true or false values. every returns true if every value in a list meets the criteria defined by the function passed as an argument. some returns true if at least one of the values meets the criteria.

bool isNum(var e) => e is num;

main() {
  var list = [1, 2, "three"];
  print( list.every(isNum) );
  print( list.some(isNum) );
}

Gives the result:

false
true

Something to note is that the some, every and filter methods are defined as part of the Collection interface not specifically in List.

Something to make note of is that filter will return a new list of items that return true from the passed function, whereas the sort method will modify the existing list rather than return a new one. Take the following code as an example of how to use each.

main() {
  var list = [4, 3, 6, 1, 2, 5];
  list.sort(compare(a,b) {
    if (a == b) {
      return 0;
    } else if (a > b) {
      return 1;
    } else {
      return -1;
    }
  });
  // List is now [1, 2, 3, 4, 5, 6]

  var evens = list.filter(f(e) => e % 2 == 0);
  // list is still [1, 2, 3, 4, 5, 6]
  // evens is [2, 4, 6]
}

In the above code the list.sort method modifies the List we're working with, whereas the list.filter method returns a new List and does not make any changes to the existing list. One thing I'm not currently sure of is why the difference. Is it that sort is not removing or modifying the elements of the list where as filter does? To me anything that modifies the existing List, even if it's changing the ordering of the elements, should return a new List, which I can then assign back to the same variable if I so choose. As it stands now, I have to make a copy of the list prior to the sort if I want to keep the original ordering.

Another item to note, based on my limited trials, when iterating over the values of a List, elements are passed as value not reference. Thus if you make any changes to the value, they will not persist outside of the scope of the function. Here's an example of what I mean:

main() {
  var list = [1, 2, 3];
  for(var x in list) {
    x = x*2;
  }
  // List is still [1, 2, 3]
  
  list.forEach(f(x) { x = x*2; });
  // List is still [1, 2, 3]
}

In the first case, using the for loop I can understand that the elements are passed as values and that it does not modify the original list. However in the second case, using the forEach method, you would expect that any changes to the value there would be reflected in the list after the fact.

In any case. I highly recommend reading through the API references for List and for Collection to get an idea as to what other capabilities they hold.

A List of Errors.

Before I get started on this post on Lists (actually, I already started it yesterday but didn't complete it yet ;), I did want to share the information that Seth Ladd recently shared regarding the Dart issue tracker. Sometimes it can be hard to locate or you just can't recall the location to access the tracker. Well never fear! There is a new redirect URL available to use.

dartbug.com

Redirects to the main issue list.

dartbug.com/new

Redirects to the new issue template.

dartbug.com/1199

Redirects to a specific issue number (in this case 1199, the one I submitted and mentioned in my last blog post).

So I'm continuing with Seth Ladd's series on Dart. Today I'm looking at Lists and Arrays. One particular quote from the post particularly grabbed my attention and interest:

Fun fact: As of 2011-12-22, the word "array" does not appear in the Dart spec.'

This interested me as virtually all languages have arrays and refer to them as such. But sure enough a quick search through the current language spec reveals no results for 'array'. Now, as stated in Seth's blog, Dart arrays are Lists. I found it an interesting point none the less.

Interestingly enough however, the VM does output an error which refers to arrays. But when compiled to Javascript (via frog or dartc) the errors properly reflects 'lists'. First I'll demonstrate the code and error then I'll actually provide some additional comments regarding the code.

main() {
  var list = new List(3); // Create an immutable, or 'non-extendable' list
  list.add(4); // Now try to change it (extend it).
}

This results in the following error:

Unhandled exception:
UnsupportedOperationException: Cannot add to a non-extendable array

But when executed on the dartboard we get the following error:

UnsupportedOperationException: Cannot add to a non-extendable list

It surprises me a little that the VM does specifically reference array whereas the code compiled to Javascript, which does have arrays, correctly references a list. There already exists a couple of bug reports. One which I'll only briefly mention, indicates that the word 'array' should be removed from all internal libraries. The second, which I added a comment to regarding the VM specifically is: Issue 1028. This issue aims to be more encompassing removing references from the Libraries as all references which may become visible.

So you may be wondering why it is that List provides an add method if it just generates an error. Well that's because there are two types of lists. A 'non-extendable' list which is created by passing a size to the constructor, or you can create a list without the optional argument to the constructor which creates an empty list you can extend by adding (or removing) values from. An extendable list can also be created from a list literally such as:

var list = [1, 2, 3];

Note however, that unlike some other languages (such as Ruby), you can not call a method on the List literal. Thus the following is not valid code:

var list = [1, 2, 3].add(4);

You'll receive a warning indicating "expression does not yield a value". But it will compile and run (at least until you try to call a List method on list such as length which will generate a runtime error.

However there is a bug in the add method which I have just discovered. The API for List.add indicates that the return type is 'void' (or no return value). This works as expected in the dartboard (javascript). However in the Dart VM, list.add(value) returns the new size of the list. I have submitted a bug report for it here: Issue 1213.