Forem: Mario Sangiorgio

Efficiently compute permutations

Mario Sangiorgio — Fri, 06 Apr 2018 00:00:00 +0000

Permutation : each of several possible ways in which a set or number of things can be ordered or arranged.

The problem

Given several items, it could be interesting to find all the possible ways we can arrange them. For instance, the string ABC has six permutations: ABC, ACB, BAC, BCA, CAB, CBA. Note that the number of permuration is the factorial of the number of items. This happens because we can pick any of the items as the first one, we have #items - 1 choices for the second and so on till we reach the last item with a single choice.

A recursive solution

We could compute all the permutations recursively, as shown in this Python function:

def permutations(items):
  if len(items) == 1:
    return [items]
  result = []
  # We keep only the distinct items to avoid returning duplicates
  for item in list(set(items)):
    others = items[:]
    others.remove(item)
    for permutation in permutations(others):
      # Note: if we want lexicographical order we should insert in front
      # assuming that items are sorted
      permutation.append(item)
      result.append(permutation)
  return result

We could execute this and get the results we expected:

>>> permutations([1,2,3])
[[3, 2, 1], [2, 3, 1], [3, 1, 2], [1, 3, 2], [2, 1, 3], [1, 2, 3]]
>>> permutations([1,2,1])
[[2, 1, 1], [1, 2, 1], [1, 1, 2]]

A better approach

This solution works, it is nice and simple but it isn’t very efficient: it requires us to create a lot of copies of the list of items so that we can pass them into the next recursive step. Another drawback is that this function computes (and keeps in memory) all the permutations, which it’s a waste if we only need a few of them.

We could look at this from another angle and ask ourselves if there is any way we could take a list of items and find out only the next permutation, whatever that means.

If we talk about the next permutation we kind of imply that there is an order between them. In principle the definition of permutations doesn’t imply any order, but we could always add a constraint ourselves and require some ordering. Using the lexicographical order is a good choice that allows us to generate the next permutation for a given list of items.

Going back to our initial example, we could start from ABC, reorganize the items to get ACB, do it another time to obtain BAC, and so on. This will allow us to compute all the permutations, but this time one of a time and without unnecessary copies of the list.

The first list in lexicographical order has all its items in non-decreasing order: forall i: items[i] <= items[i+1]. In our example, we have ABC and A < B and B < C. On the opposite, the last item has all its items in non-incresing order: forall i: items[i] >= items[i+1]. In our example, we have CBA and C > B and B > A.

Our algorithm needs to make us transition from these two extremes by rearranging the elements such that each permutation ‘increases’ the sequence by the minimal amount. The key observation is that we want to look for the longest suffix in non decreasing order (i.e. that is already the biggest possible). Let’s call it suffix. In order to make some progress we need to consider all the items in suffix and the one immediately before it, which we call pivot. If we start from 0125430 we could split the string in prefix = 01, pivot = 2, and suffix = 5430.

We’re looking for the minimal change so we shouldn’t touch prefix. If we do we’ll get a bigger change than the one we want. We can only move pivot and the items in suffix. We also must do that satisfying these two conditions to be able to advance to the next permutation in lexicographical order:

we need to replace pivot with the smallest value possible;
we must reshuffle the items such that the new suffix is minimal.

We can satisfy the first condition by replacing pivot with the smallest item in suffix greater than pivot itself. Taking a smaller value would mean going backwards, taking a bigger value would mean going too far. In our example we will get prefix = 01, pivot = 3 and suffix = 5420.

This is a step in the right direction, but we still have satisfy the second condition. We’ve got a maximal suffix, we can make it minimal by simply reversing it, which has the effect of turning the non-decreasing order to the non-increasing order we’re after. In our example we will get prefix = 01, pivot = 3 and suffix = 0245. We’re done, the next permutation is 0130245

The algorithm

The algorithm to implement this consists of the following steps:

find the largest k such that a[k] < a[k+1]. If we cannot find it, the item we’re looking at is already the last in lexicographical order. We could find the next item by just wrap around and generate the first permutation in lexicographical order.
Find the largest index l greater than k such that a[k] < a[l].
Swap a[k] and a[l].
Reverse the sequence from a[k + 1] up to and including the final element a[n].

In code this looks like:

def next_permutation(items):
  n = len(items)
  # Find pivot
  k = None
  for i in range(n-1):
    if(items[i] < items[i+1]):
      k = i
  if k is None:
    # items is maximal. We need to wrap around
    return None
  # Find new pivot
  for i in range(k, n):
    if(items[k] < items[i]):
      l = i
  # Swap pivot
  items[k], items[l] = items[l], items[k]
  # Reverse suffix
  for i in range(k+1, int((k+1+n)/2)):
    items[i], items[n-i] = items[n-i], items[i]
  return items

And we can use it as follows:

>>> permutation = [1,2,3]
>>> while permutation != None:
... print(permutation)
... permutation = next_permutation(permutation)
...
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

Other approaches

This is not the only possible approach to generating permutations. There are in fact several other algorithms. I find Heap’s algorithm particulary interesting because it manages to generate the next permutation by swapping a single pair of elements.

Thanks to Project Nayuki for the post that inspired me to look into this algorithm.

The art of deleting code

Mario Sangiorgio — Tue, 26 Sep 2017 00:00:00 +0000

If you ask developers what their most productive days look like, you’ll surely get many mentions of the mythical days when they contributed negative lines of code to their projects.

People like to celebrate these days and they do it for good reasons: they likely eliminated some bugs, made the code simpler, cleaned up some technical debt. As a side effect their project compilation and runtime are now faster.

Where I work, we have a huge monolith that organically evolved and accumulated a huge amount of cruft. Last year we even spent some time reducing our technical debt. I spent that period almost exclusively getting rid of a huge amount of code and since then my coworkers use the expression going Wario when they are deleting some old code.

How do I know what to delete?

Deleting code is easy, knowing what to delete is definitely more challenging. The last thing I like to do is to reinstate something I removed because it turns out that something was actually still relying on it. We need some good ways to determine what code is dead with an high degree of confidence.

A very deep knowledge of the codebase is crucial and is what will allow you to obtain the best results but there are some tools that can be extremely helpful and show you what parts of your application aren’t useful anymore.

Know your codebase and you application

Knowing when and why some code was written for in the first place is invaluable and can give the best insights on whether you still need it or not.

As an example, think of code to read different version of a file format or older version of an HTTP API. In both cases, you cannot guarantee that this code has no uses just by looking at it. But you might know that all the files you care about have been moved to the new format or that all the clients are using the new version of the API. Congratulations, you’ve just identified good candidates for a nice clean up.

In a legacy codebase you’re likely to have many different ways of doing something. It might be a good idea to uniform your application to always use the latest approach. This will give you access to all the latest features and it will also allow you to retire the code related to the old approaches. Unfortunately, usually knowing how to migrate the new approach is not straightforward, otherwise someone else would have done it already. If that’s the case, you need to understand how the two approaches differ, what is really required by the use case that is still relying on old code and how you can replicate the functionality using the new code. It is usually possible, but it requires a lot of understanding and a fair amount of effort.

Static analysis

At work we mainly use C#, so we can leverage static analysis like the one performed by the compiler itself, by ReSharper and by ndepend to identify dead code. Cleaning it up is a good start, but it won’t get us too far: the most of the unused code that can be removed is code that is technically reachable.

For instance, all the code I mentioned in the previous examples would not be flagged by static analysis tools. For what they know, I might still have an old file around so they must produce conservative results. They assume that if there is a codepath that leads to the execution of a line of code it will eventually be reached.

That’s a perfectly valid approach: I would be very worried if these tools would give me unsound results.

Still, static analysis is very useful end extremely effective when, after I found what feature I can eliminate, I want to easily get rid of all its related code. But before we need to find the entry point to that feature using other means. Once that’s deleted all the rest will follow.

Dynamic analysis

If we cannot know what code is actually used just by analyzing it, can we get some more information if we instrument so that we can monitor how it’s actually used?

The answer is yes and there are several approaches that can lead you to achieve very good results, but you need to watch out for false positives. Dynamic analysis is not exhaustive so you need to make sure that you’ve waited long enough before you can declare a piece of code as dead.

Recording in a database all the command line arguments passed to your application will let you know what is actually in use. There is no point of support the functionality behind a command line switch if nobody ever uses it.

If you suspect that something is dead, you can use the tombstoning approach, which is a bit more invasive but it’s surely going to give you important information with a better level of detail.

Once you’ve collected data for a while you will know what is definitely used, what is likely to be unused and when something has been used for the last time. This is precious intelligence and it will be extremely helpful in identifying what you should try to delete next.

Conclusion

Deleting code is not always straightforward but with a good knowledge of the application you’re working on, and with the help of some tooling it is possible to achive very good results.

If you’ve read so far, I’d like to recommend you Greg Young’s The art of destroying software. It’s not going to teach you how to delete code, but it will give you some ideas on how to optimize for deletability the new code you’ll write so that deleting it, once you don’t need it anymore, will be as easy as possible.

Immutability Changes Everything - Pat Helland

Mario Sangiorgio — Wed, 30 Aug 2017 23:37:52 +0000

Inspired by Adrian Colyer's the morning paper series, Fabian Giesen's papers I like posts and the Papers we love talks I decided to start writing posts about interesting papers I read.

Pat Helland's Immutability Changes Everything describes why we need immutability and how adopting it now that storage and computational power make it affordable.

The key concept around immutability is append only computing: observed facts are recorded and kept forever while the results that can derived from their analysis are computed on demand.

Is this new?

It's interesting the this isn't a completely new concept.
A well known example is accounting, which is entirely based on an append only record of transaction.

Accountants don't use erasers or they go to jail.

Pre-telephone "distributed systems" are another historical example.
Messages used to be logged in forms consisting in append only section so that all the participants always had access to the full message history.

DataSets and Big Data

The paper define DataSets as a fixed and (semantically) immutable collection of data with a unique identifier.
Immutability is especially important when dealing with Big Data.
If the amount of that that needs to be processed requires distribution, the only sane way to deal with it is to guarantee that it won't change.
This enable idempotent functional calculations, which can be distributed and that can adopt a let it fail approach: if something fails it's ok, it will be restarted.

It's important to note that the requirement is for immutability to be semantic: as long as we don't change the content, we can choose to physically arrange the data the way we want.
This allows us to organize the data in the most efficient way for the task and we can also have multiple different representation of the same DataSet.

Normalization is very important in a database designed for update.
The only reason to normalize immutable DataSets may be to reduce the storage necessity for them.

Immutability and evolving data

Sometimes we want to keep track of the evolution of some data.
We can do that in an immutable way, but we need to keep track of all the changes.
One way to do that is to keep track of version history.
This can be done in a strongly consistent way (linear version history) in an eventual consistent way (directed acyclic graph of version history, like what you usually work with in Git).

Versioning techniques have also been adopted to improve the performance of database systems.
With multi-version concurrency control updates don't overwrite existing data.
Instead, they create a new, isolated, version.
This technique has been adopted to allow concurrent access to a database by different transaction while protecting them from observing inconsistent data.
A log-structured merge-tree records changes by appending them to a log.
This allows for very efficient insertions but would required to keep the whole history around forever and it would cause read performance to be poor.
To get around this, periodically the log gets compacted removing duplicates and reorganizing the data for more efficient reads.

Immutability in file-systems

Immutable data has been widely employed to file-systems too.
Log-structured file-system treats the disk as a circular log.
This gives very good write performance (especially on magnetic disks) and it offers features like snapshotting and easy recovery from crashes.
Of course, this is not free: as the disk becomes full there is the need to reclaim the blocks that don't contain useful information anymore to make space for new data.

Distributed file-systems like GFS and HDFS exploit immutability to achieve high availability.
Files are composed of immutable blocks and they have a single writer.
With this design, block-level replication is possible without the need of worry about update anomalies.

Immutability in distributed systems

Immutability provides benefit even when working with a distributed datastore using consistent hashing.
If data is mutable we need to settle for eventual consistency while rebalancing.
With immutable data we don't need to worry about stale versions present in different nodes.
If a node has some information, that's the only value it will ever assume.

Hardware design

SSD wear leveling algorithms treat blocks as immutable and use copy-on-write to spread more evenly the writes across the whole unit.
Hard disks embrace immutability with an approach similar to log-structured file-systems improve performance and be able to operate at higher density.

The dark sides

Immutability is very useful but it isn't a silver bullet.
Embracing it requires us to do some trade-offs.
Denormalization increases the amount of storage required.
Copy-on-write increases disk activity, in a phenomenon called write amplification.
It's important to keep this in mind when designing a system.

This post originally appeared on my personal blog

My use-case for Go

Mario Sangiorgio — Sun, 27 Aug 2017 16:33:21 +0000

After using a few very good applications written in Go (Syncthing, Docker and Hugo are some examples) I wanted to get to learn a bit more about the language.

I'm very interested in programming languages theory and how it could give developers the tools they need to write software in the best possible way and with as many guarantees as possible on the correctness of the resulting applications.

To get an idea of where programming languages theory is headed have a look at the post Graydon Hoare (the creator of Rust and now one of Swift's developers) published discussing possible new research directions for programming languages.

I obviously wasn't expecting Go to address any of these issues but I find it very interesting that its designers deliberately ignored lots of what I would consider basics features in the name of simplicity.
The lack of generics is often mentioned in discussions regarding Go.
I would have liked Go to have algebraic data types and immutability by default. I would gladly give nil away to get these features.

On the positive side, Go has good libraries, good tooling, a common style and a syntax that is extremely easy to pick up. It's fast enough and it has good support for concurrency via goroutines. It also produces executables that are very easy to deploy anywhere.

Given this description, it seems to me that Go is an evolution of C and Python and I decided to give it a try rewriting a project originally written in Python I am working on.

That project is very simple, small and self contained. It interacts with Twitter (a good library is a huge plus), and it analyzes my interactions with the people I follow.
The goal is to find out if I'm following people I am not interacting with much.
I somehow ended up following too many people and I needed to find a way to bring my following to a more manageable number.

That is admittedly something too simple to draw conclusions, but I think it was still good enough to get a feeling of the language and I had a good impression.
Picking up the language has been very easy, the library I used is good. With respect to Python I have a type system, albeit limited, and I get an executable I can easily deploy with no additional dependencies.

Given this experience I believe I'll consider Go again for projects of a similar size and scope or for simple command line applications.
For that use case, I believe it's a much better fit than Python while it's simplicity could make me be more productive than if I were using other languages.

Originally posted on mariosangiorgio.github.io

Designing Data-Intensive Applications

Mario Sangiorgio — Thu, 09 Mar 2017 00:00:00 +0000

I recently read Designing Data-Intensive Applications by Martin Kleppmann and I really appreciated it. I especially liked that the book covers a wide range of topics and I think it’s a very good introduction to the subject. I had a prior exposure to most of the covered topics in some university classes, but the book has been a useful refresher and it surely taught me several new things.

The book starts with details on data modeling and querying with a comparison of the different models and explaining what kind of tasks they’re suitable for. Going throught that chapter will help you decide when it makes sense for you to use a relational database management system or when a NoSQL database is a better choice, just to name two of the most common paradigms. However, I enjoyed that the book doesn’t stop there: it covers a good variety of approaches and it also puts them in their historical context.

Once you know how to model your data and your queries, it’s time to dive deeper in the implementation of a data storage system. The book covers with enough details different implementation techniques and the data structure commonly used so you’ll know what properties to expect from a system implemented in a certain way.

The central part of the book shows how to make a data intensive system with certain properties. Here you’ll discover how speading the load over multiple machines is going to let you scale. And you’ll also learn again that distributed systems are hard. The book focuses on replication and partitioning, transactions (both on a single system and distributed). Finally, the central part of the book ends with a chapter about consistency and consensus.

Once you got so far into the book you’ll have a clearer idea of how storage systems work and you’ll hopefully be able to pick the one that fits with the problem you want to solve. In the final part, the book discusses common patterns to implement applications on top of a storage systems. Depending on the nature of your data you might want to do batch or stream processing. Either way, the book discusses the most common approaches.

I’d really recommend this book. I think it hits the sweet spot between giving a comphrehensive overview and giving enough details and reference to be actually useful. You won’t learn all the implementation details of a particular system, but you’ll learn enough of how a huge variety of systems work so you’ll find yourself in a good position when you’ll have to choose how to implement your data intensive application.

This post was originally published on mariosangiorgio.github.io

Do you realy need a dependency injection container?

Mario Sangiorgio — Sun, 08 May 2016 00:00:00 +0000

I think dependency injection is a very effective technique to write more modular and generally better structured programs. It vastly improves the design of an application encouraging decoupled and highly testable components.

What I like less is that often programmers who dependency injection also use a container. They use it to wire all the components up using some sort of magic, usually through reflection.

Magic always comes with a price

The use of magic is exactly the reason why I don’t like containers. They save you from writing some boilerplate code, which is never the hardest thing you’ll write in an application with a decent architecture, and doing so they’ll make you pay the price of losing several extremely useful features.

Here are some, just to name a few:

would you like the compiler to show you an error when you miss something? Sorry, this is not going to happen. The container moved wiring your application up at runtime. You’ll get an exception instead.
do you like when your IDE helps you finding where constructors are used? I do, but the price for not writing some code is that the IDE cannot help me with that. The code is not used anywhere as far as it can tell.

Mark Seeman shows clearly the trade offs between not using a container at all, using it with explicit registrations and using it by convention. The first case is simple and valuable. The second is quite sophisticated and pointless. He claims that the third is sophisticated but valuable.

When you use a container in the good way, you get something that is low maintenance at the price of using a technique that is hard to learn and weakly typed. That’s definitely not for me, and that’s the reason why I agree with yegor256 when he says that DI-containers are code polluters. I think that there is something wrong with your application if you really need to use a container to save you from the burden of putting all the components of your application together. You probably should have a look at how your application is structured rather than hiding the issues under the carpet and pretending that the problem is not there.

This post was originally published on mariosangiorgio.github.io