3
\$\begingroup\$

First let me address why I'm not using the built-in string interning. My code is used in a utility that needs to free all of its memory once it's closed. Strings that are interned are not likely to be freed until the CLR is restarted. I can't create that situation since my utility is used on servers that primarily run .NET based services. (See this reference on CLR not releasing interned strings)

On to the question:

I have created a custom string pool in C#, implemented as an extension method in a static class that contains the actual "pool" in the form of a dictionary:

internal static Dictionary<string, string> StringPool = new Dictionary<string, string>();

internal static string Pool(this string value)
{
    if (!string.IsNullOrEmpty(value) && value.Length <= 200)
    {
        string poolRef;

        if (StringPool.TryGetValue(value, out poolRef))
            value = poolRef;  
    else
        StringPool.Add(value, value);
}

return value;
}

To use it, I simply append .Pool() to any string in my project that I want to be pooled. The assumption I am making is that this approach is storing two copies of strings. My assumption comes from the fact that I can recover the actual strings by iterating the Keys in the StringPool object and printing or viewing their contents.

The question I have is whether anyone knows of another indexed object type that I could use as a StringPool object such that the string data would only be stored once, as the Key, rather than twice, as both Key and Value. Additionally I need the fast Key lookup feature that a Dictionary has.

Here's the pseudo code that I believe conveys what I'm after in practice:

internal static CoolClass<string> StringPool = new CoolClass<string>();

internal static string Pool(this string s)
{
    if (!string.IsNullOrEmpty(s) && s.Length <= 200)
    {
        string keyRef = null;

        // obtain reference to key in CoolClass if it already exists    
        if (StringPool.TryGetKey(s, out keyRef))
            s = keyRef;  
    else
        StringPool.AddKey(s);
}

return s;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ You may want to consider this class I wrote for JDOM: StringBin \$\endgroup\$ – rolfl Mar 10 '15 at 18:11
1
\$\begingroup\$

Data Structure

I think what you're looking for is simply just a List. Looking up the time complexities for List, we can see here:

  • Add O(1) [note: amortized, the O(n) on 'beyond capacity' is negligible]
  • Remove/RemoveAt O(n)
  • Item[i]/Find(i) O(1)

Just a note: you can verify these complexities in the MSDN(for example, going to List<T>.Add, one of the remarks will tell you the complexities), but I found the above table to be a nice and succinct way of showing multiple collections.

Not to attack Heslacher's implementation, but I found IndexOf to be O(n). I'm always dubious of roll-your-own array implementations.

Based on your problem description, though, the two main things you're going to be using are Add and Item[], and since those are O(1) I think List is an easy and efficient candidate.

Alternative - Unique Elements

If you want to guarantee uniqueness(no duplicates), then there's HashSet<T>. Here's an SO question on it. The time complexities are essentially the same. The catch is that if T hashes poorly and there's a lot of collision, the lookup is up to O(n)(this would mean all objects in the collection have the same hash and you essentially have an array). Strings typically hash well, so this shouldn't be a problem.

Code Review

I hate to say it but I just don't have anything to review. To be honest this question would do just as well or better on the Programmers SE. You covered the coding style with Heslacher, so other than that your code is well-formed, easily understood and there's not a whole lot of it. I could nitpick that Pool seems to be an Add and a Get, but the way you use it makes sense, and separating them would probably make the code more complex and ugly. At this point I'm just rambling because this is the code review SE...but I got nothing.

I focused a bit on complexities because your original problem included space complexity(double the strings, double the memory), and time complexities may not actually make a huge difference at run-time for you. So what you choose - array, list, hashset, etc - is really up to you and your environment.

\$\endgroup\$
  • \$\begingroup\$ I appreciate the thoroughness of your answer. Unfortunately, the List<T> Find method is actually O(n). See msdn.microsoft.com/en-us/library/x0b5b5bc(v=vs.110).aspx Luckily, the time factor is more important right now than memory, so my dictionary implementation is making my users happy. If I could process even larger log files with my utility without running servers into the page file, well, more's always better. =D \$\endgroup\$ – Jace Mar 13 '15 at 18:38
  • \$\begingroup\$ This looks like the best answer, especially the HashSet<T> idea. HashSets of strings perform very well, store the data once, and you can recover the string. \$\endgroup\$ – Jace May 20 at 14:03
2
\$\begingroup\$

So, you want a Collection which should hold your strings. The easiest and fastest would be to simply use an array. So let us do it.

Because you are using this for pooling strings, we we only need a string[] array. We should add a method bool TryGetValue(string key, out string value) and a string Add(string value).

If we use an array we need to initialize this array to a given capacity at the constructor level and add a possibility to let the array grow if needed.

I decided to use the name you want CoolClass but it should be better named to something more meaningful.

We need to check if a given "key" is in the array at two places, the TryGetValue() and the Add() method. So let us introduce another method int IndexOf(string key) which returns the index of the given keyand if it isn't in the array it returns -1, which should be extracted to a const.

This leads to

public class CoolClass
{
    private string[] array;
    private int capacity;
    private int lastElement = -1;
    private const int elementNotFound = -1;

    public CoolClass() : this(1024) { }
    public CoolClass(int capacity)
    {
        this.capacity = capacity;
        array = new string[capacity];
    }

    public bool TryGetValue(string key, out string value)
    {
        int i;
        if ((i = IndexOf(key)) != elementNotFound)
        {
            value = array[i];
            return true;
        }

        value = null;
        return false;
    }

    public void Add(String value)
    {
        if (value != null)
        {
            int i;
            if ((i = IndexOf(value)) != elementNotFound)
            {
                lastElement++;
                if (lastElement >= capacity)
                {
                    Grow();
                }
                array[lastElement] = value;
            }
        }
    }

    private int IndexOf(string key)
    {
        for (int i = 0; i < lastElement; i++)
        {
            if (array[i] == key)
            {
                return i;
            }
        }
        return elementNotFound;
    }

    private void Grow()
    {
        capacity = capacity * 2;
        Array.Resize(ref array, capacity);

    }
}  

But maybe we should think about this. Why shouldn't we rename the TryGetValue() to GetOrAdd() and remove the Add() method ? Because we don't want to handle cases where the string isn't pooled in the client code.

public class CoolClass
{
    private string[] array;
    private int capacity;
    private int lastElement = -1;
    private const int elementNotFound = -1;

    public CoolClass() : this(1024) { }
    public CoolClass(int capacity)
    {
        this.capacity = capacity;
        array = new string[capacity];
    }

    public string GetOrAdd(string key)
    {
        if (key == null) { return null; }

        int i;
        if ((i = IndexOf(key)) != elementNotFound)
        {
            return array[i];
        }

        lastElement++;
        if (lastElement >= capacity)
        {
            Grow();
        }

        array[lastElement] = key;
        return array[lastElement];

    }

    private int IndexOf(string key)
    {
        for (int i = 0; i < lastElement; i++)
        {
            if (array[i] == key)
            {
                return i;
            }
        }
        return elementNotFound;
    }

    private void Grow()
    {
        capacity = capacity * 2;
        Array.Resize(ref array, capacity);

    }
}

You reallay should use braces {} for singleline if statements too, this won't harm but makes the code less error prone.


Also it isn't mentioned explicitly in the naming guidelines how to name internal static variables, you should use camelCase casing for naming them.


By using a guard clause like

if (string.IsNullOrEmpty(value) || value.Length > 200) { return value; }  

you can return early and therefor you save horizontal spacing which improves the readability of the code.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the answer. It really gives me some food for thought. It certainly meets the storage optimization, beating out Dictionary<string, string> As an aside, your guard clause and mine are logically equivalent. =) As to naming convention, since the member is accessible outside the defining class, I chose Pascal Case since it better conveys the accessibility within the project. We reserve Camel Case for truly private members and parameters as the guide states "The camelCasing convention, used only for parameter names...". \$\endgroup\$ – Jace Mar 10 '15 at 16:50
  • 2
    \$\begingroup\$ Why do you propose a slow array instead of a simple map? Looking up the key by a linear search won't scale. \$\endgroup\$ – Roland Illig May 19 at 13:45
1
\$\begingroup\$

The correct solution to your problem is not what those above have suggested. Loaded strings may or may not be interned, they may even be duplicated in the intern pool. Creating your own string collection won't help this problem.

The solution you should use is to create a new AppDomain, run your code in that and then dispose of the domain (and therefore the intern pool) when you are done with it.

I was wrong about the intern pool being disposed on an app domain unload. It appears that there is indeed one string intern pool for the whole process

\$\endgroup\$
  • \$\begingroup\$ According to the MSDN article I linked to in my question, this would not be helpful.To wit: "The reason is that the CLR's reference to the interned String object can persist after your application, or even your application domain, terminates." See: docs.microsoft.com/en-us/dotnet/api/… \$\endgroup\$ – Jace May 15 at 14:56
  • \$\begingroup\$ @Jace I'll have play. I may have got something backwards then, I'll try to find where I read it. \$\endgroup\$ – BanksySan May 15 at 18:56
  • \$\begingroup\$ @Jace You're correct. Just did a test and strings remain interned even after the app domain has been torn down. \$\endgroup\$ – BanksySan May 19 at 13:06
0
\$\begingroup\$

The "200" string length constraint looks a bit like a magic number, I'd recommend replacing it with a well-named constant to improve code readability.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.