In a recent post, I had this sequence of characters (which I’m expressing this way to avoid repeating the problem): <single-quote><backslash><numeral zero><single-quote>. That’s the NULL character, if you didn’t know.
It broke my feed. I’m not sure if it was IE or WordPress, but either way is bad so I replaced the offending sequence with a comment the feed was fixed.
This is part three of my series on fast searching and filtering of text using C#.
The previous article developed an indexing method using a hash table. This article develops a method using a trie structure. If you don’t know tries, I highly encourage to go read about them before continuing.
This filtering method is much more complex than previous versions, but we’ll take it one step at a time.
Our data structure is more complex than a hash table, and definitely more involved than a simple list. We start with a data structure called a trie that contains a list of results, and links to the next nodes, indexed by letter. The key represented by a trie is determined by the path to that trie from the root. The root represents all keys and values (or none, depending on how you look at it). The trie is built up as we index items, beginning with an empty root. An illustration would be helpful about now:
This diagram shows the top portion of an example trie structure. The root node has no results (since there are no values in the path to that node). The _next variable indexes the next links in the chain. Here, there is only one link–to ‘h’. The node with the value “h” has two further links–to ‘e’ and ‘a’.
So far, so good. However, in our implementation, we limit the depth of this tree to three so the results will potentially contain many entries. For example, if we followed the ‘l’ link in the “he” node, we would get to a node with the value “hel”. If we then indexed the word “hello”, the same node would then contain “hel” and “hello” because we’ve stopped the tree growth here. You can experiment with different values, but I found limited value beyond 3.
To add a new item, we need to get substrings of the key, like usual, but unlike before, we don’t need to retrieve all substrings, just the longest substrings that aren’t the initial portions of a substring already found. Clear?
No? Here’s an example:
With the previous indexer (using the hash table), the substrings of “hello” would be:
h, he, hel, e, el, ell, l, ll, llo, lo, o
Now, think about our trie structure. Is there any reason to consider ‘h’ if we’re going to consider ‘he’ anyway? Why not just store our value under the results for “he”, and then if we filter on ‘h’ , just return the unified results of the ‘h’ node and every subnode under it. We’ve just cut our memory requirements substantially.
For a trie, we only need substrings of our tree height (or shorter if a longer one doesn’t exist–i.e., at the end of keys). If our maximum keylength/tree-height is 3, then the substrings required for “hello” are now just:
hel, ell, llo, lo, o
Nice.
Once we have these substrings, we can generate the trie, inserting our value (and full key) into the results of the bottom-most trie node we can reach, creating new trie nodes as necessary.
To find all values pertaining to a filter text, we start with the root node, and look up the filter text character by character, traversing the trie. If we run out of nodes, then there are no results. IF we run out of characters the results will include all the results in the current node as well as the results in subnodes.*
(*FYI: if we stored all the results in all applicable nodes, i.e., if we stored the value “Hello” in the nodes “hel”, “he” and “h”, we could speedup searches, BUT we’d use a lot more memory…and it would be exactly equivalent to the hash table implementation–we wouldn’t gain anything.)
With that overview out of the way, let’s cover the basic data structures we’ll need to pull this off.
The first is something we’re familiar with, the IndexStruct–which is actually a class like in the previous article:
1: private class IndexStruct
2: {
3: public UInt32 sortOrder;
4: public string key;
5: public T val;
6:
7: public IndexStruct(string key, T val, UInt32 sortOrder)
8: {
9: this.key = key;
10: this.val = val;
11: this.sortOrder = sortOrder;
12: }
13: };
This time, the sort order will be important as we’ll see below.
The next data structure we need is a trie. Technically, a trie is the whole tree, but since you can define a tree as a node with subtrees, it works to define a node too.
Here are the fields and properties we’ll need for the Trie class:
1: private class Trie
2: {
3: private char _val;
4: private Dictionary<char, Trie> _next = new Dictionary<char, Trie>();
5: private IList<IndexStruct> _results;
6:
7: #region Properties
8: public char Value
9: {
10: get
11: {
12: return _val;
13: }
14: set
15: {
16: _val = value;
17: }
18: }
19:
20: public IList<IndexStruct> Results
21: {
22: get
23: {
24: return _results;
25: }
26: }
27:
28: public Dictionary<char, Trie> Next
29: {
30: get
31: {
32: return _next;
33: }
34: }
35:
36: #endregion
37:
38: //...methods to follow...
39: }
The _val fields simply refers to the character this trie represents, though we don’t actually need it. I included it just for completeness. The _next dictionary associates the next character with another Trie object. The _results list stores all items that need to be stored in the current Trie object. The properties just wrap the fields.
The constructor is simple:
1: public Trie(char val)
2: {
3: _val = val;
4: }
We need a function to add a result to the trie’s list of results:
1: public void AddValue(IndexStruct indexStruct)
2: {
3: if (_results == null)
4: {
5: _results = new List<IndexStruct>();
6: }
7: _results.Add(indexStruct);
8: }
Notice, that the node only adds results to itself–it doesn’t try to figure out if a result belongs in itself or a sub-node in _next. To do that would require that each node have knowledge about keys as well as its place in the entire tree. This logic is better kept at a higher level.
We also need to associate a new trie node with a character:
1: public void AddNextTrie(char c, Trie nextTrie)
2: {
3: this.Next[c] = nextTrie;
4: }
OK, now we need to get into something more complex. We need a function to return all the results in the current trie, plus all the results in subnodes. Also, they should all be sorted. We could just return a huge list and sort them at the highest level with something like quicksort, but I have some additional knowledge about the data. I know that it’s being added in sorted order (since that’s how I define it. If it weren’t, we could presort each node anyway once indexing was done.) So let’s assume that each node’s results are already sorted. If that’s the case, we have an ideal setup for a merge sort!
Now, it’s entirely possible that just doing quicksort at the end would be faster, but in my tests at least, the merging seemed a little faster, especially since the results were mostly sorted, which is quicksort’s worst-case scenario.
So let’s define a helper function that takes two lists of IndexStruct and returns a single merged list:
1: private IList<IndexStruct> Merge(IList<IndexStruct> a, IList<IndexStruct> b)
2: {
3: if (a == null || a.Count == 0)
4: {
5: return b;
6: }
7: if (b == null || b.Count == 0)
8: {
9: return a;
10: }
11: int iA = 0, iB = 0;
12: List<IndexStruct> results = new List<IndexStruct>(a.Count + b.Count);
13: while (iA < a.Count || iB < b.Count)
14: {
15: if (iA < a.Count &&
16: (iB == b.Count || a[iA].sortOrder < b[iB].sortOrder))
17: {
18: results.Add(a[iA]);
19: iA++;
20: }
21: else if (iA<a.Count && iB<b.Count &&
22: a[iA].sortOrder == b[iB].sortOrder)
23: {
24: //if they're equal, make sure we skip the other
25: //one so we don't add it later
26: results.Add(a[iA]);
27: iA++;
28: iB++;
29: }
30: else
31: {
32: results.Add(b[iB]);
33: iB++;
34: }
35: }
36: return results;
37: }
This function interweaves the two arrays into a single array by always grabbing the smallest item from the next positions in the two lists. Look at lines 21-28. This is critical. We need to be on the lookout for identical sortorders, which indicate the same values. We don’t want to include those twice. This situation comes up when our value is “hi-ho” and we filter on “h”–results for both “hi” and “ho” will appear, and we don’t need both.
OK, so we we have a generic merge function. Now let’s make it work on the Trie:
1: public IList<IndexStruct> GetCombinedResults()
2: {
3: Queue<IList<IndexStruct>> queue = new Queue<IList<IndexStruct>>();
4: //first enqueue items in this node
5: if (_results != null && _results.Count > 0)
6: {
7: queue.Enqueue(_results);
8: }
9:
10: //get items from sub-nodes
11: foreach (Trie t in _next.Values)
12: {
13: IList<IndexStruct> r = t.GetCombinedResults();
14: queue.Enqueue(r);
15: }
16:
17: //merge all items together
18: while (queue.Count > 1)
19: {
20: IList<IndexStruct> a = queue.Dequeue();
21: IList<IndexStruct> b = queue.Dequeue();
22: queue.Enqueue(Merge(a, b));
23: }
24: return queue.Dequeue();
25: }
We maintain the list of items to merge together with a queue. We first enqueue the items in this node, then we call GetCombinedResults() for all subnodes, and enqueue those results. Finally, we merge the queued lists together, enqueueing the result, until a single list is formed.
Phew! OK, now let’s look at the rest of the indexer.
RemoveUnneededCharacters is the same as before:
1: private string RemoveUnneededCharacters(string original)
2: {
3: char[] array = new char[original.Length];
4: int destIndex = 0;
5: for (int i = 0; i < original.Length; i++)
6: {
7: char c = original[i];
8: if (char.IsLetterOrDigit(c))
9: {
10: array[destIndex] = c;
11: destIndex++;
12: }
13: }
14: return new string(array, 0, destIndex);
15: }
We talked about our new version of GetSubStrings() above, and here it is:
1: private List<string> GetSubStrings(string key)
2: {
3: List<string> results = new List<string>();
4: //we only need to return substrings that
5: //themselves don't begin other substrings
6: //easy to do--return first _maxKeyLength characters
7: //or whatever's left, if shorter
8: for (int start = 0; start < key.Length; start++)
9: {
10: int len = Math.Min(_maxKeyLength, key.Length - start);
11: string sub = key.Substring(start, len);
12: //remove this if() to speed up index creation
13: //at the cost of slightly longer lookup time
14: if (key.IndexOf(sub) == start)
15: {
16: results.Add(sub);
17: }
18: }
19: return results;
20: }
As you can see, it’s mostly comments. Before we add our substring we make sure it’s the first occurence in the string of that particular sequence of characters (“don’t begin other substrings”). This prevents us from indexing “he” twice in the word “hehe”.
Now, to the real stuff! Actually, most of our work is done for us. So let’s declare our indexer:
1: class TrieIndexer<T> : IIndexer<T>
2: {
3: private Trie _rootTrie = new Trie(/*null char goes here--HTML doesn't like it/*);
4: private int _maxKeyLength = 3;
5:
6: public TrieIndexer(int maxKeyLength)
7: {
8: _maxKeyLength = maxKeyLength;
9: }
10: //..methods to follow...
11: }
We have our root trie node with a null character, and the constructor takes the maximum key length (which corresponds directly to the height of trie).
1: public void AddItem(string key, T value, UInt32 sortOrder)
2: {
3: string toAdd = key.ToLower();
4:
5: toAdd = RemoveUnneededCharacters(toAdd);
6:
7: IndexStruct indexStruct = new IndexStruct(toAdd, value, sortOrder);
8:
9: List<string> subStrings = GetSubStrings(toAdd);
10:
11: foreach (string ss in subStrings)
12: {
13: Trie currentTrie = _rootTrie;
14: for (int i = 0; i < ss.Length; i++)
15: {
16: char c = ss[i];
17: Trie nextTrie = null;
18: if (!currentTrie.Next.TryGetValue(c, out nextTrie))
19: {
20: nextTrie = new Trie(c);
21: currentTrie.AddNextTrie(c, nextTrie);
22: }
23: currentTrie = nextTrie;
24: }
25: currentTrie.AddValue(indexStruct);
26: }
27: }
Lines 3-10 are the typical preprocessing of the key, and creating a structure for it and the value to live. The fun stuff happens in 12-30. With each substring, we begin at the root, and try to branch out node-by-node, character-by-character to find the bottom-most trie in which to place our indexed value. If the next one doesn’t exist, we create it. Once we get to the bottom of the tree for this subkey we add our value to the structure.
Now let’s turn our attention to the filtering part. It’s almost like adding new values:
1: public IList<T> Lookup(string filterText)
2: {
3: Trie currentTrie = _rootTrie;
4:
5: int maxTrieLength = Math.Min(filterText.Length, _maxKeyLength);
6: for (int i = 0; i < maxTrieLength; i++)
7: {
8: Trie nextTrie = null;
9: if (currentTrie.Next.TryGetValue(filterText[i], out nextTrie))
10: {
11: currentTrie = nextTrie;
12: }
13: else
14: {
15: //no results
16: return new List<T>();
17: }
18: }
19: Debug.Assert(currentTrie != null);
20:
21: return GetResults(filterText, currentTrie);
22: }
We set our current node to the root. We then figure out the length of the path we need to traverse. If our filter text is longer than our maximum key length, we only want to go as far as the key length (and vice versa).
We do the same type of lookups as in AddItem, but this time if the next node isn’t present, we just return an empty list–there were no results for that filter text.
Once we find the target node, we call another function to actually compile the results for us:
1: private IList<T> GetResults(string filterText, Trie trie)
2: {
3: List<T> results = new List<T>();
4:
5: IList<IndexStruct> preResults = trie.GetCombinedResults();
6: if (preResults.Count <= 0)
7: {
8: return results;
9: }
10: results.Capacity = preResults.Count;
11: uint prevSortOrder = 0;
12: foreach (IndexStruct item in preResults)
13: {
14: Debug.Assert(item.sortOrder > prevSortOrder);
15: prevSortOrder = item.sortOrder;
16:
17: if (filterText.Length <= _maxKeyLength ||
18: item.key.IndexOf(filterText,
19: StringComparison.InvariantCultureIgnoreCase) >= 0)
20: {
21: results.Add(item.val);
22: }
23: }
24: return results;
25: }
In line 5, we call GetCombinedResults() and store it in the variable preResults. Why preResults? Why aren’t they final? For one, they are the entire IndexStruct object, and we still need to extract the values. Secondly, it’s possible the user entered a longer filter text than we indexed, so we still have to do a linear walk of the list and do string searches to make sure the preResult is really valid. Thankfully, we can avoid this if the filterText is short.
And now…we’re done! This one was a beast! There are still some optimizations to be found in here, but it’s pretty good. OK, so what about performance of this thing?
Let’s run it on lesmis.txt first:
OK, for raw speed it’s actually slower than naive–overall. But look closer. Nearly ALL the time penalty is coming from the lookup of “h”. The next results are over ten times faster than naive. Now, let’s compare to the substring method. The trie method is overall slower still, and the search times are comparable (except for the initial search). But, look at memory usage: the trie method uses less than HALF what the substring method used. Also, the index creation time is 4 times faster. Mixed bag, but impressive none-the-less.
Now let’s run it on huge.txt:
Ouch, over a second–but again, it’s all because of that initial search for “h”. All the other times are about the same. Comparing to the substring method, it uses almost a third of the memory, and takes a third of the time to create the index.
So what can we say about this method?
Pros:
Cons:
(Note: in the course of writing this article, I changed my implementation to no longer need the Finish() function, which was part of the IIndexer<T> interface. I know I promised we’d use it, but I don’t need it!)
So where do we go from here? I have some notes about implementing this paired with a ListView control. Stay tuned for part 4!
This is part two of my series on fast searching/filtering of text using C#.
In the previous article, we developed the filtering interface, built up a testing framework and implemented a naive indexer. For many purposes, that indexer performs more than adequately. Still, there are other possible implementations that might work better (or not…let’s wait and see).
In this installment, let’s develop something based on hash tables. With O(1) look-up time, they could be the ticket to blazing fast lookups.
We reuse the same internal structure as the NaiveIndexer, except I’ve changed it to a class. It needs to be reused many, many times for the same value so it’s much more efficient to share the object around instead of make copies:
1: private class IndexStruct
2: {
3: public string key;
4: public T val;
5:
6: public IndexStruct(string key, T val)
7: {
8: this.key = key;
9: this.val = val;
10: }
11: };
The fields are thus:
1: private int _maxKeyLength = 999;
2: private Dictionary<int, List<IndexStruct>> _hashes;
Notice again that we still don’t have to keep track of sort order in the IndexStruct. This is because down at the bottom of the data structure, all the data is still stored in List<> objects. I’m still breaking the law of abstraction by associating sort order to the order in which I add items, but…hey, it’s just an example.
Let’s take a look at the constructor and figure out what the maximum key length is for, and a few other issues we have to handle:
1: public SubStringIndexer(int numItems, int maxKeyLength)
2: {
3: _maxKeyLength = maxKeyLength;
4: _hashes = new Dictionary<int, List<IndexStruct>>(numItems);
5: }
As you can see, the constructor takes two arguments.
The number of items is used to initialize the Dictionary<> ( a hash table class) to the number of items we can expect. If you know you’re hash table theory, you know that the size of a hash table should ideally be a prime number much larger than the number of items you want to insert. I have not bothered to do that here and experimentation did not show a significant benefit. Also, the hash table will automatically expand itself anyway for a certain load factor.
The maxKeyLength parameter is crucial. Since this indexer works by calculating substrings, it’s important to specify just how big those substrings can be. There’s a tradeoff here. The longer the maximum, the more substrings can be precalculated, and the faster the searches will be. However, you pay an enormous price in memory usage. We’ll see that price below when we run this example. I’ve chosen 3 as a fairly good balance between speed and space.
Before we override our interface methods, let’s define some helper functions we’ll need. The first is something we’re familiar with:
1: private string RemoveUnneededCharacters(string original)
2: {
3: char[] array = new char[original.Length];
4: int destIndex = 0;
5: for (int i = 0; i < original.Length; i++)
6: {
7: char c = original[i];
8: if (char.IsLetterOrDigit(c))
9: {
10: array[destIndex] = c;
11: destIndex++;
12: }
13: }
14: return new string(array, 0, destIndex);
15: }
Just as with the naive indexer (in fact, with all the indexers), we need to strip out unimportant characters.
One of the most important functions we’ll need is something to generate substrings given a key.
1: private List<string> GetSubStrings(string key)
2: {
3: List<string> results = new List<string>();
4:
5: for (int start = 0; start < key.Length; start++)
6: {
7: /*get maximum length of substring based on current
8: * character position (constrain it to within the string
9: * and less than or equal to the maximum key length specified
10: * */
11: int lastLength = Math.Min(key.Length - start, _maxKeyLength);
12:
13: /* Get each substring from length 1 to lastLength
14: */
15: for (int length = 1; length <= lastLength; length++)
16: {
17: string sub = key.Substring(start, length);
18: if (!results.Contains(sub))
19: {
20: results.Add(sub);
21: }
22: }
23: }
24: return results;
25: }
GetSubStrings returns a list of all substrings of length 1 to _maxKeyLength. If you think about it, you can see why limiting this number to a small number is a good idea. If you have thousands of different keys, each of a fairly sizable length, you will generate thousands and thousands of unique substrings, not to mention how long it will take (a very long time).
Now let’s look at how this indexer works.
Here’s the way it works. Each substring of a key is converted to a hash number, which is the index into the hash table. The hash of the substring is used instead of the substring itself to avoid storing the substrings in the hash table’s list of keys–just for memory reasons.
The value of each slot in the table is a list of items. Lookup works by first narrowing down the list by doing a hash lookup on the filter text, then doing a linear search through all the items returned from the hash table. We’ll see the details below.
1: public void AddItem(string key, T value, UInt32 sortOrder)
2: {
3: string toAdd = key.ToLower();
4:
5: toAdd = RemoveUnneededCharacters(toAdd);
6:
7: List<string> subStrings = GetSubStrings(toAdd);
8: IndexStruct indexStruct = new IndexStruct(toAdd, value);
9: foreach (string str in subStrings)
10: {
11: List<IndexStruct> items = null;
12: int hash = str.GetHashCode();
13:
14: bool alreadyExists = _hashes.TryGetValue(hash, out items);
15: if (!alreadyExists)
16: {
17: items = new List<IndexStruct>();
18: _hashes[hash] = items;
19: }
20: items.Add(indexStruct);
21: }
22: }
After normalizing the key (lower-case, alphanumeric), we get the valid substrings. For each of those, we calculate it’s hash and try to look it up in our hash table. If it doesn’t exist, we create a new list for that substring. Then we add the new entry to that list.
Lookup is a little more complicated, but still straightforward enough.
1: public IList<T> Lookup(string subKey)
2: {
3: string toLookup = subKey.ToLower();
4: List<IndexStruct> items = null;
5: List<T> results = new List<T>();
6: int hash = 0;
7:
8: if (subKey.Length > _maxKeyLength)
9: {
10: /*
11: * If the substring is too long, get the longest substring
12: * we've indexed and use that for the initial search
13: */
14: toLookup = toLookup.Substring(0, _maxKeyLength);
15: hash = toLookup.GetHashCode();
16: }
17: else
18: {
19: hash = toLookup.GetHashCode();
20: }
21:
22: bool found = _hashes.TryGetValue(hash, out items);
23: if (found)
24: {
25: results.Capacity = items.Count;
26: foreach (IndexStruct s in items)
27: {
28: /*
29: * Have to check each item in this bucket's list
30: * because the substring might be longer than the indexed
31: * keys
32: */
33: if (s.key.IndexOf(subKey, StringComparison.InvariantCultureIgnoreCase) >= 0)
34: {
35: results.Add(s.val);
36: }
37: }
38: }
39:
40: return results;
41: }
We first convert the subKey parameter (what we’re searching on) to lower case to normalize it. If that text is longer than the maximum subkey we’ve indexed, we trim it down to match the maximum size. Then we calculate the hash code and see if it’s in our list. If it isn’t found, there are no results and we return the empty list.
If a list was returned, we still have to go search through the entire list and do string searches to make sure our entire subkey is present in the key before adding it to the result set.
(If we needed to be concerned about sort order, we would do another post-processing step and sort the results list by sortorder.)
So let’s see how this works in practice by running it against the same lesmis.txt file.
It’s nearly 3 times faster! But at what cost? It now takes about 8 seconds to create the index in the first place, and it uses 31 MB of memory. Ouch!
But I wonder….what if I run this against truly huge data sets…
I create a million-line file out of various books available at the Gutenberg project. First, let’s run the naive indexer:
Now the naive way is taking over a second to do the search. What about our new substring indexer?
It takes nearly a minute to create the index, but lookups are now almost 5 times faster than the naive version–it definitely scales better. Well, except for that 270 MB index size!
So, this is an improvement in some ways, but it has some big costs (index creation time, index size). Next time, I’ll show yet another way that has some advantages.
Even though I recently wrote about just using naive algorithms when they’re sufficient, it helps to know about other options and their characteristics. With that mind, I’m beginning a little series (4 parts planned–I’ll update this list as I go along) in C# documenting how I developed a few different approaches to doing fast (instant) filtering of large lists.
The article index:
I recently changed some internal apps at work do use filtering instead of column sorting of large listviews. It took a few days for the users to get used to it, but I’ve gotten comments back that it is amazingly better. The reason is that you are hiding all sorts of data you don’t need to look at. This is better in many cases than sorting, especially if you’re sorting 10,000 items. It’s also fairly intuitive for users to use.
Our indexer must have certain capabilities, so says me:
The first thing we need to do is define a common interface that all our indexers will implement. This will make it very easy to swap them out when comparing different implementations.
Before showing the code, let’s discuss exactly what the indexer needs to do. Basically, the indexer has to accomplish two tasks:
We’ll assume that all keys will be strings because the point here is to do search, and search require strings. The actual values stored in the index, however, can be anything, so let’s make sure the interface supports generics.
Another potential problem is sort order. The internal index representation may not respect the order (for example, if a hash table were used, items are definitely not maintained in a sorted order). Our interface should provide a way to handle this.
It’s also possible that an indexer may want to know when indexing is finished so it can clean up any temporary data it may have created. Our first example will not use this, but we’ll put it in the interface now anyway.
So without further ado, here is our interface in all her glory:
1: interface IIndexer<T>
2: {
3: void AddItem(string key, T value, UInt32 sortOrder);
4:
5: IList<T> Lookup(string subKey);
6:
7: void FinishIndex();
8: }
Just three tiny functions. That’s all we need to get started.
With our interface designed we can quickly build a simple indexer. The algorithm for this one is brain-dead simple:
I did say this was naive.
Let’s start our implementation by deriving a new class from IIndexer<T>:
1: class NaiveIndexer<T> : IIndexer<T>
2: {
3:
4: }
No constructor is needed so let’s jump into the data structures required. For one, we need to store the key and value we’re adding, so let’s make a private structure to hold those together as well as a member variable list of structures to hold our data.
1: private struct ItemStruct
2: {
3: public string _key;
4: public T _value;
5: //public ushort _sortOrder;
6: };
7:
8: List<ItemStruct> _items = new List<ItemStruct>();
I include the sort order merely to show where it could go. I’ve left it commented it out in my implementation because I’m adding things in sorted order and the List<T> will keep things sorted for me. This is probably breaking the abstraction, but it’s easy enough for you to add it back in if you want. (Like I said, I wanted this to be as easy and light-weight as possible, so a leaky abstraction is acceptable in this case).
With these data structures, adding a new item is a piece of cake. We just create a new instance of the structure, set the fields, and add it to _items.
1: public void AddItem(string key, T value, UInt32 sortOrder)
2: {
3: string realKey = RemoveUnneededCharacters(key);
4: ItemStruct itemStruct = new ItemStruct();
5: itemStruct._key = realKey;
6: itemStruct._value = value;
7: //itemStruct._sortOrder = sortOrder;
8: //could insert into place of sortOrder, after a grow, if desired
9: _items.Add(itemStruct);
10: }
Woah, hold on! RemoveUnneededCharacters? Well, in my application I only wanted to index alphanumeric characters. This function strips all others from a string and returns the “real” key to use. Of course, during lookups, you’ll have to be similarly careful to sanitize the input to prevent searching on stripped characters.
1: private string RemoveUnneededCharacters(string original)
2: {
3: char[] array = new char[original.Length];
4: int destIndex = 0;
5: for (int i = 0; i < original.Length; i++)
6: {
7: char c = original[i];
8: if (char.IsLetterOrDigit(c))
9: {
10: array[destIndex] = c;
11: destIndex++;
12: }
13: }
14: return new string(array, 0, destIndex);
15: }
I think that’s a fairly efficient way of stripping characters that doesn’t rely on creating temporary strings, but if you have a better way, I’d love to see it.
Doing searches is similarly straightforward. We loop through each ItemResult in _items and see if our subkey is in the key. If it is, add it to a result list. After all are searched, return the result list.
1: public IList<T> Lookup(string subKey)
2: {
3: List<T> results = new List<T>();
4: foreach (ItemStruct itemStruct in _items)
5: {
6: if (itemStruct._key.IndexOf(subKey,
7: StringComparison.InvariantCultureIgnoreCase)>=0)
8: {
9: results.Add(itemStruct._value);
10: }
11: }
12: //Sort on results[i]._sortOrder, if desired
13: return results;
14: }
And that’s it! We now have a fully-functioning naive indexer. Now, let’s see how can test it and set the foundation for comparison of all the indexers we’re build.
I’m not going to include all of the code for the test harness here–you can find it in the sample code download. A simple description of it will suffice.
The test harness will take as input a filename, the number of items to index, what to search for (or filter on), and the indexing method. This will allow us to easily add other indexing methods as we develop them. Of course, being a simple test harness, there is no error-handling.
The items to be indexed will be lines from a text file. I’ve supplied the text of Les Misérables by Victor Hugo from Project Gutenburg, but you can use any text file you want (the larger the better). Les Misérables has about 70,000 lines. This is actually fairly small-medium.
Since, the reason for creating these indexers arose out of search-as-you-type functionality in one of my apps, the harness does progressive lookups on successive substrings of the key you type. I.e., if you do a search on “valjean”, it will first search “v”, then “va”, then “val”, etc.
Here is a screenshot of a sample run (click to enlarge):
I mentioned above that the need for this arose from doing filter-as-you-type functionality in one of my applications. This realization can lead to a major optimization, which I have not implemented in this example. If you’re doing successive searches, first searching for “v”, then “va”, then “val”, etc. You can cache the search filter and results of the previous query, and then on the next search instead of looking through the entire _items list, you can just look through the cached results instead. First, you just check to make sure that the previous filter is a substring of the current filter.
Next time, I’ll develop another indexing method that has some additional advantages and disadvantages. Using the test hardness, we can compare the different algorithms under different conditions. Stay tuned.
(I’m out of town this weekend, so comments will be approved after I return home)
Need to interact with some hardware via serial port? I’m having to do some serial port communications in a project at work, and it is officially Not Fun. There was some original code that was doing only reads from the port, and I needed to some significant functionality that would not be possible with the existing code. So rather than writing a ton of code from scratch (well, other than what I will have to do anyway), I tried to find some open-source, commercial-friendly serial port libraries on the Internet.
The only one I could find that seemed to be perfectly suited to the task at hand was Serial Library for C++ by Ramon de Klein. It has a number of classes for various ways of accessing the serial port and handling events, interacting with Windows. It also supports MFC.
The license is LGPL, which makes it’s ok for me to use in the project. As Ramon’s article notes, doing serial port communications from scratch is hard. So reuse what is out there.
If you’re in .Net, you already have some nice classes in the form of System.IO.Ports.SerialPort, which was added in 2.0.
In my previous post, I showed some code that we “fixed” and it caused problems–it actually broke the algorithm.
The bug was in relying on some compiler behavior and the usage of the stack.
Here’s the original (pre-“fix”) code again for reference:
for(i = 0; i < overlaySize.cx; i++) { long i1 = (long)((double)i / numXTimes); double xPercent = (double)i / numXTimes - i1; // get the indeces into the data array long lIndex1 = i1 + (j1 * m_DataSize.cx); long lIndex2 = lIndex1 + m_DataSize.cx; double yVal1, yVal2; if(i1 != oldi1) { yVal1 = m_DataArray[lIndex1] + //etc...
yVal2 = m_DataArray[lIndex1 + 1] + //etc...
oldi1 = i1; } // figure out the value double theVal = yVal1 + (yVal2 - yVal1) * xPercent;
}
The answer lies in the realization that yVal1 and yVal2 need to retain their values through each iteration of the loop. It always worked before because the compiler ensured that each time those variables are used, even if they’re not initialized after declaration, they reference the same place in the stack on each loop iteration. By setting them to 0.0 each time, we’re breaking the reuse functionality. Finding this, we realized that is horrible! At the very least, it’s brittle, prone to break if anything went into the loop which altered the stack differently on different iterations.
Thankfully, it was easy to fix. Just move the declarations and initialize them outside the loop.
double yVal1 = 0.0, yVal2 = 0.0;
for(i = 0; i < overlaySize.cx; i++) { long i1 = (long)((double)i / numXTimes); double xPercent = (double)i / numXTimes - i1; // get the indeces into the data array long lIndex1 = i1 + (j1 * m_DataSize.cx); long lIndex2 = lIndex1 + m_DataSize.cx; if(i1 != oldi1) { yVal1 = m_DataArray[lIndex1] + //etc...
yVal2 = m_DataArray[lIndex1 + 1] + //etc...
oldi1 = i1;
}
// figure out the value
double theVal = yVal1 + (yVal2 - yVal1) * xPercent;
}
I don’t know who wrote the brain-dead code in the first place, but…wow.
Anyway, lessons learned?
We’ve been working on our next version of our flagship product at work and, as part of that, we upgraded to Visual C++ 8 (2005) and turned on the most strict compiler settings, warning level 4, more debug runtime checks–basically trying to make everything very strict.
As part of that process, we had to go through the code and fix hundreds (thousands?) of warnings that just became errors.
One area was the following:
for(i = 0; i < overlaySize.cx; i++) { long i1 = (long)((double)i / numXTimes); double xPercent = (double)i / numXTimes - i1; // get the indeces into the data array long lIndex1 = i1 + (j1 * m_DataSize.cx); long lIndex2 = lIndex1 + m_DataSize.cx; double yVal1, yVal2; if(i1 != oldi1) { yVal1 = m_DataArray[lIndex1] + //etc...
yVal2 = m_DataArray[lIndex1 + 1] + //etc...
oldi1 = i1;
}
// figure out the value
double theVal = yVal1 + (yVal2 - yVal1) * xPercent;
}
I’ve of course cut out a number of lines from this loop that weren’t relevant to the point.
The compiler flagged yVal1 and yVal2 as being potentially unitialized before they were used. It’s because they’re initialized inside an if statement.
So to remedy this, I initialized them to 0.0:
double yVal1=0.0, yVal2=0.0;
if(i1 != oldi1) {//etc.
I go on to fix other warnings-become-errors, and we finally create our first build with VC8 a week or two later. Then, we start having problems in one area of the program. A data file is working on looks horrible, and it’s taking 45 minutes to do the calculations instead of 2-3 seconds. What’s going on? It took a while to find it, but find it I did…
There is a serious bug in the code above, which my initializing the variables hid. The answer next time!
After you’ve looked at Visual Studio all day for a few days in a row, the brightness of the white background can really start to bother you, especially as LCD monitors get brighter and brighter. That’s why I’ve become a big fan of Dave Reed’s Dark Side theme for Visual Studio 2005. It took me a few hours to get used to it, but now I’m hooked.
The only thing I changed was the font. I really like Consolas, size 13. Courier New is Courier-Old-and-No-Longer-Used.
At work, I still have to use VS2003 for a project, and keeping it in the older, white background really helps me distinguish which environment I’m in.
In developing an important component (which I will discuss soon) for my current personal project, there were a number of different algorithms which I could use to attack the problem. I wasn’t sure which one would be better so I decided to implement each of them and measure their time/memory usage. I have a series of articles planned on those, but first I need to mention how I did the measurement.
For the timing, I simply wrapped the API functions for QueryPerformanceCounter and QueryPerformanceFrequency into a C# class. There are plenty of examples out there on the net to do this.
The memory usage is even simpler. The function you need is GC.GetTotalMemory(bool forceFullCollection). This function returns the amount of memory allocated. The little program below demonstrates how to use it.
using System; namespace MemUsageTest { class Program { static void Main(string[] args) { long memStart = GC.GetTotalMemory(true); Int32[] myInt = new Int32[4]; long memEnd = GC.GetTotalMemory(true); long diff = memEnd - memStart; Console.WriteLine("{0:N0} bytes used", diff); } } }
The output on my 32-bit system is “40 bytes used”–16 bytes for integers and 24 bytes of array overhead.
Passing true to GetTotalMemory is important–it gives the garbage collector an opportunity to reclaim all unused memory. There is a caveat, though. If you read the documentation, you’ll notice it says it attempts to discover the amount of bytes in use, and that setting forceFullCollection only gives it an opportunity and waiting a bit before returning. It does NOT guarantee that all unused memory is reclaimed.
As far as my work goes, I’ve noticed that it does a pretty reliable and consistent job.
In my current project, I’m using a custom ListView-like control to give my WinForms app a very rich interactive experience. This control does not implement mouse wheel scrolling like the Microsoft ListView implementation does so it was up to me to add it. You can use the knowledge in this article to implement full scrolling support in your own custom controls.
The custom component was derived from Control, which does provide the virtual function OnMouseWheel to handle vertical scrolling. The component also exposes the two scrollbars to manipulate.
First, take a look at Best Practices for Supporting Microsoft Mouse and Keyboard Devices, a good place to start learning about advanced mouse handling in Windows. Note that all of this requires IntelliPoint software to be installed.
Here’s some example code to get started with:
public class MyListView : GlacialComponents.Controls.GlacialList { }
As long as we’re talking about horizontal scrolling, let’s go ahead and discuss vertical scrolling with the mouse wheel. Add this override to the class:
protected override void OnMouseWheel(MouseEventArgs e)
{
base.OnMouseWheel(e);
}
It’s overriding from the Control class, not GlacialList. Assuming you’ve read the MS documentation referenced about, you’ll know that the scroll message includes the number of ticks, which is usually a multiple of 120. We need to accumulate this number and then scroll our view a corresponding amount.
First, some class variables:
private const int WHEEL_DELTA = 120; private int _wheelPos = 0; private int _wheelHPos = 0;
The _wheelHPos variable will be used later for horizontal scrolling. Then we modify our function to read like this:
protected override void OnMouseWheel(MouseEventArgs e)
{
base.OnMouseWheel(e);
_wheelPos += e.Delta;
while (_wheelPos >= WHEEL_DELTA)
{
ScrollLine(-1);
_wheelPos -= WHEEL_DELTA;
}
while (_wheelPos <= -120)
{
ScrollLine(1);
_wheelPos += WHEEL_DELTA;
}
Refresh();
}
After we accumulate the value, we scroll one line per WHEEL_DELTA value. (This code could certainly be optimized, but I think this version is clear.) After the scrolling we tell the view to refresh itself. The Best Practices recommend handling partial-line scrolling. In my case, since I just need to manipulate the scrollbars by one unit at a time it’s not applicable, but I encourage you to understand their sample code.
The ScrollLine() function will be application-dependent. For this class, it just needs to modify the scrollbars that were provided.
private void ScrollLine(int numLines) { vPanelScrollBar.Value = Math.Max(vPanelScrollBar.Minimum,
Math.Min(vPanelScrollBar.Maximum,
vPanelScrollBar.Value + numLines));
}
That was fairly easy. Horizontal scrolling with the tilt-wheel is only a little more complex. This is because it’s not natively supported by the .Net Framework, and to a certain extent it’s not really supported on Windows XP. Full native support of the tilt wheel starts in Windows Vista.
Fortunately the IntelliPoint drivers fake it for us by sending our listview window a WM_MOUSEHWHEEL message anyway. Since .Net 2.0 doesn’t know what to do with this message (not sure about .Net 3.0), we need to take control of the message-handling and manually handle this message. The WndProc function is the function that handles all of this and it is virtual just for this purpose.
protected override void WndProc(ref Message m) { base.WndProc(ref m); if (m.HWnd != this.Handle) { return; } switch (m.Msg) { case Win32Messages.WM_MOUSEHWHEEL: FireMouseHWheel(m.WParam, m.LParam); m.Result = (IntPtr)1; break; default: break; } }
If you’ve done Win32 programming this will look very familiar, if a little out of place in .Net code. There are a few things going on here. First of all, you must call the base-class version of WndProc or your window will be very unexciting and quite broken. Take a look at WndProc for any control in Reflector to see all the work it’s doing.
Next, there is the Win32Messages class. This is an abstract class of my own creation that serves merely as a place to put definitions for Windows’ message definitions.
abstract class Win32Messages { public const int WM_MOUSEHWHEEL = 0x020E;//discovered via Spy++ }
So how did I know it was supposed to be have the value of 0x020E? Well, I could look in the Vista SDK where it’s defined, or I could read the Best Practices document referenced before. I didn’t find that page until after I had finished this implementation and I just used Spy++ to discover the messages coming to my window when I hit the tilt button:
Before we get to the FireMouseHWheel function, notice that m.Result is set to 1. This is because the docs state that the message handling must return 1 to indicate to Intellitype that we’ve handled the message.
There are two versions of this function. One takes the raw WPARAM and LPARAM values from the message and the other takes more meaningful values. As you can guess, one should probably call the other.
public event EventHandler<MouseEventArgs> MouseHWheel; protected void FireMouseHWheel(IntPtr wParam, IntPtr lParam) { Int32 tilt = (Int16)Utils.HIWORD(wParam); Int32 keys = Utils.LOWORD(wParam); Int32 x = Utils.LOWORD(lParam); Int32 y = Utils.HIWORD(lParam); FireMouseHWheel(MouseButtons.None, 0, x, y, tilt); } protected void FireMouseHWheel(MouseButtons buttons,
int clicks, int x, int y, int delta) { MouseEventArgs args = new MouseEventArgs(buttons,
clicks, x, y, delta);
OnMouseHWheel(args);
//let everybody else have a crack at it
if (MouseHWheel != null)
{
MouseHWheel(this, args);
}
}
I declare an event that takes the same type of arguments as the vertical MouseWheel handler above. The first FireMouseHWheel function converts wParam and lParam into the real values according to the specification given. I ignore the keys value and pass the others to the second function which calls my handler and also raises the event to give class consumers the opportunity to be notified as well.
To “crack” the values, I have some simple utility functions:
abstract class Utils { internal static Int32 HIWORD(IntPtr ptr) { Int32 val32 = ptr.ToInt32(); return ((val32 >> 16) & 0xFFFF); } internal static Int32 LOWORD(IntPtr ptr) { Int32 val32 = ptr.ToInt32(); return (val32 & 0xFFFF); } }
The OnMouseHWheel is very similar to its cousin for vertical scrolling:
protected virtual void OnMouseHWheel(MouseEventArgs e) { _wheelHPos += e.Delta; const int pixelsToMove = 3; while (_wheelHPos >= WHEEL_DELTA) { ScrollHorizontal(pixelsToMove); _wheelHPos -= WHEEL_DELTA; } while (_wheelHPos <= -120) { ScrollHorizontal(-pixelsToMove); _wheelHPos += WHEEL_DELTA; } Refresh(); }
The pixelsToMove variable is noteworthy because it’s hard-coded to 3. It is kind of arbitrary because it really depends on the application and how the scrollbars are used. I’ve set it to 3 as a good value for my application.
The ScrollHorizontal function is similar to ScrollVertical and is also application-specific:
private void ScrollHorizontal(int amount) { hPanelScrollBar.Value = Math.Max(hPanelScrollBar.Minimum,
Math.Min(hPanelScrollBar.Maximum - hPanelScrollBar.mWidth,
hPanelScrollBar.Value + amount));
}
The Best Practices document states:
When an application receives a WM_MOUSEHWHEEL message, it is responsible for retrieving the characters-to-scroll user setting (SPI_GETWHEELSCROLLCHARS) by using the SystemParametersInfo API. This setting will not be available on Windows 2000 and Windows XP, so use the value of 1. IntelliType Pro and IntelliPoint will maintain a substitute value for the characters-to-scroll user setting and send the correct number of WM_MOUSEHWHEEL messages.
(Emphasis mine) Notice that last phrase. IntelliPoint can potentially send multiple WM_MOUSEHWHEEL messages for a single tilting action. This means that my strategy of refreshing on every message might not be entirely wise. It really depends on how long it takes to refresh the control. If it can be done smoothly and instantly, then this might not matter. Otherwise, you might need to come up with a way of accumulating ticks over multiple messages and scrolling all at once, perhaps after a timer expires. In my case, I think I’ll ignore this issue for now. I don’t really care if the control refreshes too often.
Have fun adding horizontal scrolling to your app!