Click here to Skip to main content
15,867,141 members
Please Sign up or sign in to vote.
5.00/5 (2 votes)
I have a method which is called thousands time. Because of its complexity, my code is working slow. Is there any better technique? Unsafe methods are allowed.

Thank you.


It simply checks letters of input string whether it could be made of the letters of other string.

My current method;

C#
public static bool IsStringMadeOf(this string str, string from)
{
    for (int i = 0; i < str.Length; i++)
    {
        int index = from.IndexOf(str[i]);
        if (index != -1)
        {
            from = from.Remove(index, 1);
        }
        else
        {
            return false;
        }
    }
    return true;
}

Console.WriteLine(IsStringMadeOf("SLOW","WSOL"));
//True

Console.WriteLine(IsStringMadeOf("SLOW","WTOL"));
//False

Console.WriteLine(IsStringMadeOf("ASIA","XZYABSTRIB"));
//False

Console.WriteLine(IsStringMadeOf("ASIA","XZYABSTRIAB"));
//True



EDIT

Benchmark Results:
http://pastebin.com/uJcYNAe1[^]

I am not satisfied with results but I will go for unsafe method, in best case it works best but in average case it is same as mine.

EDIT2

I tried calling method from unmanaged library but didn't get a better result.

http://pastebin.com/uzkXhFy4[^]
Posted
Updated 13-Nov-14 11:25am
v7
Comments
Mehdi Gholam 13-Oct-14 4:04am    
How about using str.Contains("string") ?
Emre Ataseven 13-Oct-14 4:05am    
It searches string in a string as block, my point is checking letters.
Mehdi Gholam 13-Oct-14 4:11am    
So you are looking for anagrams?
BillWoodruff 13-Oct-14 6:03am    
If you are sure the two strings are of equal length then, sure, you don't need to check for unequal length: but, is that the case here ?
Emre Ataseven 13-Oct-14 6:54am    
No, lengths must not be same

How crazy do you want to go?
If you're up for some un-safe code you can go ~70% faster by using pointers;
C#
public unsafe static bool IsStringMadeOf3(this string str, string from) {
    char[] copy = new char[from.Length];
    from.CopyTo(0, copy, 0, copy.Length);
    fixed (char* s = str) {
        fixed (char* f = copy) {
            var l = str.Length;
            for (int i = 0; i < l; ++i) {
                var index = from.IndexOf(s[i]);
                if (index != -1)
                    f[index] = '\0';
                else
                    return false;
            }
            return true;
        }
    }
}

It's essentially your algorithm but it modifies the from (or rather a copy of it) in place instead of doing a String.Remove on it.

I'd probably stay away from this solution, pointers are never nice to play with, especially not in C# (although they are awesome).

Hope this helps,
Fredrik
 
Share this answer
 
Comments
BillWoodruff 13-Oct-14 7:36am    
+5 excellent: the OP says 'unsafe is okay, and you provide that.
Fredrik Bornander 13-Oct-14 7:55am    
Cheers. I just ran the figures; on my box I get 70% faster going unsafe with pointers and about twice as slow going with linq. I would still probably go with the linq method you suggested unless proven beyond a doubt that this method is the biggest performance hog. Pointers will come back to bite your a** I think.
Emre Ataseven 13-Oct-14 8:26am    
Thank you for answer. I tested this method, I changed
var index = from.IndexOf(s[i]);
as;
var index=Array.IndexOf(copy,s[i]);
Seems like 30 % faster than mine. I can accept this as an answer but want to wait little more if any better answer will be posted.
Fredrik Bornander 13-Oct-14 8:27am    
Was it faster for you?
Emre Ataseven 13-Oct-14 9:02am    
Yes 30% faster
It would be interesting to time this approach using Linq (requires .NET 3.5 or later):
C#
private bool IsCharMatch(string stringToMatch, string stringToTest)
{
    return 
        // implement test for length equality ?
        //stringToMatch.Length == stringToTest.Length
        //&&
        stringToMatch.OrderBy(s => s).SequenceEqual(stringToTest.OrderBy(s => s));
}
Edit:

Here's an "experimental" approach, using Linq 'GroupBy and 'ToDictionary methods, that addresses (hopefully) what we have learned from the OP via dialogue about the results desired:
C#
private bool IsCharMatch2(string stringToMatch, string stringToTest)
{
    if (stringToMatch.Length > stringToTest.Length) return false;

    // construct Dictionaries where each Key is a character
    // and each Value is the number of occurrences of the character
    // in the string

    Dictionary<char, int> seqSource = stringToMatch.GroupBy(c => c)
        .ToDictionary(key => key.Key, value => value.Count());

    Dictionary<char, int> seqTest = stringToTest.GroupBy(c => c)
        .ToDictionary(key => key.Key, value => value.Count());

    int count;

    foreach(var kvp in seqSource)
    {
        if (! seqTest.TryGetValue(kvp.Key, out count) || kvp.Value > count) return false;
    }

    return true;
}
Here's the result of some simple tests:
C#
// true
bool match1 = IsCharMatch2("hello", "olelh");
// true
bool match2 = IsCharMatch2("A", "AA");
// false
bool match3 = IsCharMatch2("AA", "A");
// false
bool match4 = IsStringMadeOf("eroerfwyhpw", "whyfore");
// false
bool match5 = IsStringMadeOf("eroerfwyhw", "whyfore");
// true
bool match6 = IsStringMadeOf("eroerfwyhw", "wheyrxf123oryeeewz");
 
Share this answer
 
v3
Comments
Fredrik Bornander 13-Oct-14 6:30am    
That won't yield the same result as his implementation, though.
IsStringMadeOf("A", "AA") will return true whereas IsCharMatch would be false for those parameters.
BillWoodruff 13-Oct-14 6:37am    
That is exactly why I asked the OP in my comment if testing for length equality was necessary: I assume it is. Even though a length equality test is not required in my solution, I put one in ... commented out ... on the assumption that if there were a high-frequency of tests where the strings were of unequal length then a length test just might improve performance.
Fredrik Bornander 13-Oct-14 6:41am    
Yeah, a spec on what to achieve rather than just a view of OPs current implementation would have been good.
Maciej Los 13-Oct-14 6:41am    
Linq rocks! In other words: why to force the door wide open, if there is a method to comapre strings?
+5!
BillWoodruff 13-Oct-14 6:52am    
If I had time, it would be interesting to compare the performance of using Linq in this way to the other way. I am not, unfortunately, at a level of understanding of what IL the compiler will produce in cases like this to even guess at that now.
Sounds, like you're looking for 'similarity algorithm', which provides a way to compare strings and return result as a percentage of similarity ;)

BTW: Few years ago i asked similar question[^].

Please, see:
http://stackoverflow.com/questions/653157/a-better-similarity-ranking-algorithm-for-variable-length-strings[^]
http://stackoverflow.com/questions/3576211/string-similarity-algorithms[^]
http://en.wikipedia.org/wiki/String_metric[^]
 
Share this answer
 

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)



CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900