Category Archives: General

Coursera/Stanford course: Algorithms: Design and Analysis , Part 1

General, , ,

screenshot_github_algorithmsAlthough I’ve been developing software for years, I noticed recently that I lacked the basic computer science knowledge that other people got at university, though it’s never been an issue outside of job interviews. I knew the basics of Big-O notation and how to use data structures but couldn’t describe exactly how various sort algorithms worked or how to analyze an algorithm’s performance from pseudo-code.

But this is all standard stuff now, so filling in the gaps in my knowledge seemed like a solvable problem. Over the last few weeks, I’ve worked through Coursera’s “Algorithms: Design and Analsis, Part 1” online course, provided by Stanford University. I was surprised to find myself enjoying it. It’s nice to get some insight into commonly used algorithms and data structures, and I guess it does help to inform choices made at a higher level, even if that’s only occasionally useful.

Mostly I enjoyed the programming exercises, writing implementations of Mergesort, Quicksort, Karger’s Minimum Cut Algorithm, Strongly Connected Components, Dijkstra’s Shortest-Path Algorithm, a 2-Sum Algorithm, and a Median Maintenance algorithm. Likewise, each week had a theoretical test, checking knowledge of stuff such as the Master Method, sorting algorithms, graph algorithms, heaps, (balanced) binary trees, hash tables, and bloom filters.

Hopefully I’ll keep it in all my head from now on, but that is always easier when you’ve written actual code that you can look back at. I used C++, but you can use any programming language, and nobody checks your code. Of course, I’m not allowed to publish my homework solutions.

I had already been slowly reading through Introduction to Algorithms, by Cormen, Leiserson, Rivest and Stein, which is hard going. It also has exercises, but I was far more motivated to complete the Coursera exercises, whose aim was always to get the correct specific numerical answer, so you knew when you had the code working properly. After I finished the course, I found it easy to then read the relevant chapters, which offer much more in-depth analysis than the Coursera course.

Although the participants are all still waiting for their certificates (presumably some skeumorphic image file), I’m sure that I’ve passed with 80-something percent. I’d have done better but I started the course after some homework deadlines had already passed. The final test also showed that I need to be more familiar with logarithm equivalences and geometric progressions. I do have Maths and Further-Maths A-Levels, but it’s been a long time.

Unfortunately, part 2 isn’t due to start again until some time in 2016. But I think I can do the course in the meantime, just without earning an official score.

Update: Here is my certificate for part 1:

murrayc-2015-09-24_coursera_stanford_algorithms_part1

Update: I did part 2 too.

gtkmm now uses C++11

General, , , ,

Switching to C++11

All the *mm projects now require C++11. Current versions of g++ require you to use the –std=c++11 option for this, but the next version will probably use C++11 by default. We might have done this sooner if it  had been clearer that g++ (and libstdc++) really really supported C++11 fully.

I had expected that switching to C++11 would require an ABI break, but that has not happened, so already-built applications will not be affected. But our API now requires C++11 so this is a minor API change that you will notice when rebuilding your application.

Some distros, such as Fedora, are breaking the libstdc++ ABI slightly and requiring a rebuild of all applications, but that would have happened even without the *mm projects moving to C++11. It looks like Ubuntu might be doing this too, so I am still considering taking advantage of a forced (not gtkmm’s fault) widespread ABI break to make some ABI-breaking changes in gtkmm.

C++11 with autotools

You can use C++11 in your autotools-based project by calling AX_CXX_COMPILE_STDCXX_11() in your configure.ac after copying that m4 macro into your source tree. For instance, I used AX_CXX_COMPILE_STDCXX_11() in glom. The *mm projects use the MM_AX_CXX_COMPILE_STDCXX_11() macro that we added to mm-common, to avoid copying the .m4 file into every project. You may use that in your application instead. For instance, we used MM_AX_CXX_COMPILE_STDCXX_11() in the gtkmm-documentation module.

C++11 features

So far, the use of C++11 in gtkmm doesn’t provide much benefit to application developers and you can already use C++11 in applications that use older versions of gtkmm. But it makes life nicer for the gtkmm developers themselves. I’m enjoying learning about the new C++11 features (particularly move constructors) and enjoying our discussions about how best to use them.

I’m reading and re-reading Scott Meyer’s Effective Modern C++ book.  C++11’s rvalue references alone require great care and understanding.

For now, we’ve just made these changes to the **mm projects:

  • Using auto to simplify the code.
    For instance,
    auto builder = Gtk::Builder::create();
  • Using range-based for-loops.
    For instance,
    for(const auto& row : model->children()) { … }
  • Using nullptr instead of 0 or (void*)0.
    For instance,
    Gtk::Widget* widget = nullptr;
  • Using the override keyword when we override a virtual method.
    For instance,
    bool on_draw(const Cairo::RefPtr<Cairo::Context>& cr) override;
  • Using noexcept instead of throw().
    For instance,
    virtual ~Exception() noexcept;
  • Using “= delete” instead of private unimplemented copy constructors and operator=().
  • Using C++11 lambdas, instead of sigc::slots, for small callback methods.
    See below.

libsigc++ with C+11

libsigc++ has also moved to C++11 and we are gradually trying to replace as much as possible of its internals with C++11. Although C++11 has std::function, there’s still no C++11 equivalent for libsigc++ signals and object tracking

You can use C++11 lambda functions with libsigc++. For instance, with glibmm/gtkmm signals:

button.signal_clicked().connect(
  [] () {
    std::cout << "clicked" << std::endl;
  }
);

And now you don’t need the awkard SIGC_FUNCTORS_DEDUCE_RESULT_TYPE_WITH_DECLTYPE macro if the signal/slot returns a value. For instance:

m_tree_model_filter->set_visible_func(
  [this] (const Gtk::TreeModel::const_iterator& iter) -> bool
  {
    auto row = *iter;
    return row[m_columns.m_col_show];
  }
);

With C++14 that should be even nicer:

m_tree_model_filter->set_visible_func(
  [this] (auto iter) -> decltype(auto)
  {
    auto row = *iter;
    return row[m_columns.m_col_show];
  }
);

These -> return type declarations are necessary in these examples just because of the unusual intermediate type returned by row[].

android-galaxyzoo: Fixing typical Android bugs

General, , ,

My Galaxy Zoo app for android has been on the Play store for several months now and seems to be generally well liked. So far it has around 800 users, increasing slowly and linearly, probably because it isn’t linked from the galaxyzoo.org website. But even the first hundred users were enough to show me several problems that I needed to fix. I’ve written about them here, with links to the commits that fixed them in my app, because other app developers will experience them too.

These were general Android development problems, not specific to android-galaxyzoo. I guess that this is the difference between someone who understands how the Android API should be used, and someone who has actually used it with real users. It shouldn’t be quite this difficult.

Work in the main thread (Strict Mode)

Your code should not perform long-running tasks, such as network or disk IO, in the main thread, because UIs should not be unresponsive. By enabling Strict Mode in your code, you can make this cause exceptions, turning a non-responsive app into a crashing app. It would be unwise to turn this on in your app’s release version.

However, some “power” users seem to have this on via the developer options. They probably experience instability in many apps. And Android 3.0 (Honeycomb) has some Strict Mode settings on by default. So you will get crash reports via the Google Play store if you ignore Strict Mode exceptions.

As I mentioned in my previous entry, AccountManager is documented as being safe for use on the Main UI Thread, but it’s not, so I needed to use the AccountManager via AsyncTask.

If you are using a ContentProvider, you should not try to store data in the ContentProvider in the main thread. I instead did that via AsyncTask.

Likewise, avoid calling BitmapFactory.decodeStream() in the main thread, though it’s easier to just use Picasso anyway.

Automatic cache deletion

Your app probably caches some data, such as images, in its cache directory, such as the getExternalCacheDir() directory (/storage/sdcard/Android/data/com.you.yourapp/cache). However, Android will delete those files whenever it needs the space, and it won’t explicitly tell your app that it’s happened. So you need to check that your cached files really exist, one by one. You can either check the files when you first try to use them (causing UI delay) or you can check in the background, maybe trying to re-download the files.

This confused my code completely and it was hard to identify the cause of the resulting bug because the cache deletion by the system was not triggered by any particular action in my app.

By the way, although the getExternalCacheDir() documentation says that you don’t need to request permission to use that (app’s own) directory since Android 4.4 (KitKat), that’s not true – you do need to request the permission on Android 5.0 (Lollipop).

IllegalStateException: Can not perform this action after onSaveInstanceState

There are things that you cannot do in between an activity’s state being saved and that activity being resumed. It’s hard to know when that is the case but if you get it wrong then your app will crash. Here’s a full explanation, though you’ll wish you didn’t have to bother with it.

For instance, you should delay any use of AlertDialog until the parent activity’s onResumeFragments, which I did like so.

Likewise, you should not commit fragment transactions until after your activity has resumed. Again, its best to cause the commit of the fragment transaction in the parent activity’s onResumeFragments() because there’s nowhere suitable to do that in the fragment. The code could be much simpler if there was just somewhere safe in the Fragment to do this.

I believe that this problem hits every Android app developer who ever had more than a handful of users. It feels like a failure in the Android API design and the fixes feel like workarounds. If there was any clear way to structure app code to avoid this from the start then that would be mentioned early in the developer documentation.

Mutiple onLoadFinished() calls

If you use a ContentProvider (as I think you should) then you’ll use a Cursor Loader to get its data, overriding onCreateLoader() and onLoadFinished() and calling getLoaderManaged().restartLoader().

However, you will notice that your onLoadFinished() is often called more than once, sometimes with older data, confusing your app. This can be avoided by calling getLoaderManager.destroyLoader() in your onLoadFinished. For instance. I’m fairly sure this is an Android bug – at the least it is a poorly documented and unforgiving aspect of the API.

ConcurrentModificationException

I had at least one crash report with a ConcurrentModificationException, suggesting that two threads were changing the same data at the same time though I thought I had designed my code to avoid that and I thought I had made the class mostly immutable. So to avoid any chance of sharing data between threads I did some defensive copying (and here). I haven’t seen the crash since.

Toolbar’s Up button doesn’t act like the Back button

Android has a standard Back button that most users understand. It generally takes the user to the previous screen (activity), and that previous screen will look like it last looked for them.  But Android also has the concept of an Up button which few users understand.

The Up button is usually at the left of the app’s top toolbar (appbar) and it usually looks like a Back button. But it’s not a Back button. It takes the user to the parent level of the app instead of stepping back through all the previous screens that the user has traveled through since they were last at the top-level. Of course, most users don’t have any concept of the app having a hierarchy of screens in addition to a history of sibling screens. I predict that the Up button idea will be removed from Android one day.

At a second-level activity (something opened from the top-level), a user can justifiably expect the Back button and Up button to have the same effect – take me to the previous (top-level) screen/activity – even if the user knows about the Back/Up difference. However, by default the Up button will start a new parent activity instead of going back to the previous instance of that activity (as Back would). Users experience this as a loss of data – for instance this bug and this bug.

The fix for this depends on the situation:

Duplicated child fragments

My app uses child fragments (fragments in a fragment), which Android needs us to add in code rather than in the layout XML file. Strangely, I sometimes saw duplicate fragments thought it was hard to reproduce it reliably. The answer was to  always use FragmentTransaction.replace() instead of add().

 

Galaxy Zoo iPhone App: Developers welcome

General

Over the last couple of weeks I’ve made good progress on an IOS app for Galaxy Zoo, reimplementing what I’ve already done in the Galaxy Zoo Android app. The code is in github. This is my first time using Objective-C and developing for IOS, so I’m very open to helpful criticism.

Though it’s not screenshot ready, I think I’ve done the hard stuff, such as caching enough subjects from the server, uploading the classifications, removing old classifications, and dealing with cache files being deleted by the system. So I’m confident that I can get it finished fairly soon, give or take the usual bug fixing.

However, I’m going on vacation tomorrow for two weeks, so I filed github issues for the simple things that still need to be done. Maybe some other interested iPhone developers would like to contribute. It would be great to arrive back from vacation to a bunch of github merge requests.

Galaxy Zoo Android app: New Surveys

General, ,

The web-based Galaxy Zoo has switched to showing subjects from two new surveys, with new sets of questions for these surveys. So I’ve updated (see in github) the Android app too and the new version is now available in the play store. These new images are less clear, and the questions are a little harder to answer. Apparently some clearer images are on the way.

Unfortunately, though the data comes from the server, all of the decision trees, icons, help text, and example images need to be in the client – The web client and the Android app at the moment. I’ve written a small text document describing how to change the surveys used by the Galaxy Zoo Android app. It should be easier, but for now documented-and-awkward is better than not-documented-and-awkward.

Looking for Work

General,

I’ve really enjoyed the past year or so of “sabbatical”, learning new skills, doing some hobby projects, and spending more time with my kids, but it’s time to look for a proper job again. I suspect I’ll do some freelancing for a while until I find something suitable.

I’m hoping to find something still in the Linux and open source world, maybe moving into Android, and maybe with some management. I enjoyed running Openismus so I hope I can continue doing something similar: managing multiple small teams of highly skilled software developers who work with open source code and collaborative open source methods, while still doing some software development myself. I’d like to continue working with people with such high standards.

I don’t expect this to be easy because:

  • I want to stay in Munich.
  • I’d really like part time or flexible (start early, leave early) hours so I can spend some of the afternoon with my kids.
  • Running Openismus gave me project management experience, but I’m not sure it’s given me enough to call myself a manager rather than a programmer, and I don’t want to stop being a programmer.
  • GTK+ (and gtkmm) experience is apparently no longer such a popular niche. Qt still is but I’m less enthusiastic about it.
  • C++ is still broadly popular, but I’d like to stay away from MS Windows development.
  • I’ve really enjoyed doing Java Android development recently, but I hesitate to call myself an expert Java developer, compared to my C++ skills. Then again, if most Java developers are as bad as most C++ developers, then I must be better than most.
  • Although I’m learning some Algorithm analysis theory at the moment for fun, it doesn’t greatly interest me and I’ve never needed it over the last 20 years. But it seems to have become a popular interview filter.
  • I’m still not a Kernel developer and I still don’t really want to be. I like creating libraries, tools, and user experiences.

Here’s my CV if you think I can be useful.

Processing for Kids

General, ,

Liam (7) has been playing a little recently with Processing, mostly drawing shapes and moving them around. The Hello Processing interactive video tutorial is an excellent introduction, for kids too. Thanks to Jon Nordby for suggesting Processing.

Liam is gradually working through the Getting Started with Processing book, typing in example code and changing it as the book suggests. Previously he has used Scratch and he’s started using the Lego Mindstorms programming environment, which is surprisingly visually complicated. But Processing is a nice introduction to real text-based programming, where you must type everything perfectly correctly or the computer will complain with incomprehensible error messages.

So far this seems to be the closest modern-day equivalent to my childhood experiences of sitting down with a Sinclair ZX81, Spectrum, or BBC Micro and trying things out from a book on BASIC. The expectations are low so you can easily feel that you’ve achieved something significant.

IMG_20141219_124554

The Processing IDE is a very simple and obvious UI and a Processing hello-world can be just one line, without any platform initialization, without specifying anything about exactly where your output should appear:

line(15, 25, 70, 90);

By default there’s just one screen that you draw on, and all functions and types appear to be in a global namespace. So you can start making things happen without the distraction of boilerplate code and without figuring out where in that mess to put your own code. You don’t need to learn about objects, inheritance, or encapsulation, though of course you should later.

Writing an iPhone or Android app might seem more interesting to modern kids, but they’d have to wade through so much kibble just to get started, while always noticing how far they are from achieving anything like the existing apps they see.

Processing is actually Java. When you write code, that code then seems to be the contents of a method in a (derived?) PApplet class, though you don’t see that other than in some compiler error messages. The functions such as size(), stroke(), point(), ellipse(), color(), strokeWeight(), etc, are actually member methods of this class. You don’t need to import any Java classes to use this API.

Java is fairly forgiving, particularly for the simple examples that people will start with. And it  offers a nice route into object orientated programming without the lower-level pain of C or C++.

Instead of just writing a bunch of code to run and then stop, you can instead define (override) setup() and draw() functions that do what you’d expect. The draw() method can make use of member variables such as mouseX and mouseY (these are not parameters of draw()). Likewise, you can implement keyPressed() and make use of keyCode. So you get a simple introduction to making a program interactive by doing event-driven programming.

Processing is not perfect, and I think you’d feel the lack of a real API and IDE as soon as your project became more serious, but it’s a great introduction to real programming.

PrefixSuffix revived

General, , , ,

In 2002 I released a little GNOME app to rename files by changing the start or end of the filename, using gtkmm and gnome-vfs(mm). It worked well enough and was even packaged for distros for a while before the dependencies became too awkward.

I’ve never heard of a single person using it, but I still need the app now and then so I just updated it and put it in github, changing it from gtkmm 2.4 to gtkmm 3, removing the bakery dependency, and changing from gnome-vfs to GIO. I also removed most signs of my 2002 code style.

It seems to work, but it really needs a set of test cases.

I’m sure that the performance could be vastly improved but I’m not greatly interested in that so far. Patches are welcome. In particular, I haven’t found an equivalent for the gnome_vfs_xfer_uri_list() function for renaming several files at once and I guess that repeated sequential calls to g_file_set_display_name_async() are probably not ideal.

screenshot_prefixsuffix