LINQ: from IEnumerable to concrete collections

I my recent posts introducing LINQ from a game developers point of view, I mentioned several times how the many LINQ methods returning sequences of the IEnumerable<T> type do not actually return an actual collection.

Instead they return a query that can be executed any number of time on the given input collection.

Of course, there comes a point at which we need to store the results of such queries as regular collections. Today we will talk about how LINQ supports this almost trivially.

Continue reading →

Sorting and Grouping – organizing data with LINQ

Last week I introduced LINQ from the perspective of a C# game developer completely unfamiliar with the framework. Today I would like to continue exploration of LINQ by focussing on a particular set of its functionality: methods to arrange and organize data.

In particular we will look into how we can sort and group our collections of items.

Continue reading →

LINQ – a game development focused introduction

I was recently asked for some pointers on how to get started with LINQ – and to maybe write a post about that. Using LINQ virtually every day I have to admit that it had not occurred to me that a C# programmer may not be familiar with it.

LINQ is a big topic, but this post is the first in a series to introduce the framework and its many uses – all from a game developer’s point of view.

Continue reading →

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 →

A discussion on matching string prefixes

Strings are an exceptionally flexible data type. They can be used to represent virtually any kind of data, or even behaviour – think of clear text script files.

With all this flexibility also come certain drawbacks however. Doing a lot of computations on or using strings can be very expensive – especially in languages like C#, where strings are immutable.

This is why especially in game development one has to find a balance between the use of strings, and more statically typed code. However, even if we optimise entirely for performance, there will always remain use cases for strings.

Today I want to look at one specific use case of strings: matching string prefixes.

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 →