Using arrays to speed up static tree traversal

Over the last two weeks I wrote about how to construct and query a string prefix-trie. We used the data structure to quickly find all strings with a given prefix, and to find the longest common prefix in that list.

Today we will take a look at how we can use arrays to improve performance even further. We will also take a closer look at the run-time of our algorithms from last week’s posts and show how our new approach is significantly better.

While we are looking at the example of a prefix-trie, the same method can be applied to any static tree.

Continue reading →

Matching string prefixes using a prefix-trie 2

After discussion the general problem of matching string prefixes two weeks ago, we starting on the implementation of a prefix-trie to solve the problem efficiently last week.

Our implementation so far is able to quickly construct a prefix-trie from a list of strings. What is still missing is any kind of functionality to query the data structure for information.

Today we will take a look at how to use this data structure to enumerate all strings with a given prefix, and how to obtain the longest common prefix in that list.

Continue reading →

Matching string prefixes using a prefix-trie

Last week we discussed the problem of matching string prefixes and designed algorithms on the basis of a sorted list of strings.

Our solutions had good runtimes given the constraint, however we can do much better by using a specialised data structure instead.

The data structure in question is a trie, also called radix tree or prefix tree.

Today we will look at how to construct exactly that.

Continue reading →

LINQ Extensions 3: Batch into sub-sequences

After last weeks post on extracting elements out of a list by minimum or maximum keys Ody Mbegbu mentioned on Google+ how he feels that something LINQ is missing is the functionality to batch, page, or divide a sequence into sub-sequences of a given size.

That is what we are going to look at today!

Continue reading →

LINQ Extensions 2: Minimum/Maximum by key

Last week we talked about LINQ, its usefulness, and how to write our own methods to make it even more powerful. Today, I want to look at another couple of methods that I have found handy in a number of different situations. We will look at how to extract the maximum or minimum element of a list by a given key or selector.

Continue reading →

DIY: Useful LINQ Extensions

LINQ (Language Integrated Query) is one of the most powerful features of modern .NET. Powered by generics, lambda expressions, method chaining, extension methods, and deferred execution it allows to write extremely concise code when dealing with collections.

In this post we will look some useful LINQ extensions I have written over the years to make my work with LINQ even easier and quicker, and help me simplify my code.

Continue reading →

Converting between Structs and Byte Arrays

In object-oriented code bases, we tend to express most of not all of our data in highly semantic and contextual ways – that is, we use classes that contain both data and behaviour, and often even more information through inheritance, attributes, and more.

However, sometimes we need to extract the data contained in these types – for example for sending network messages, or saving to disk. In this post we will look into converting between structs and byte arrays, to make exactly this possible.

We will compare different ways of doing so, and analyse them for performance and easy of use.

Continue reading →

Snake: Smooth and accurate following behaviour

Following another object is one of the most basic movement behaviours an item can exhibit – both in the real world, and in games.

There are many different ways in which objects can follow each other, and depending on the circumstances, different kinds of movement may be appropriate.

Today we will look at one particular kind: A number of objects following another in a trail at regular distances. The movement found in games like Snake.

However – unlike the original Snake and many of its spin-offs – we will neither constrain ourselves to a grid, or to fixed time steps.

Instead we want our solution to follow arbitrary paths with arbitrary accuracy.

Continue reading →

Automating object pooling using IDisposable and finalizers

Last week we looked into the concept of object pooling, and how it can be used to increase performance by reusing objects that are expensive to create.

We also implemented a generic static class to make using object pools as simple as possible. Today I want to expand on the topic by showing how we can go even further and completely automate the pooling.

Continue reading →