読者です 読者をやめる 読者になる 読者になる

tech.guitarrapc.cóm

C#, PowerShell, Unity, Cloud, Serverless Technical Update and Features

Anagram check in C#

There are no chance of me to write Anagram check in C#.

Anagram - Wikipedia, the free encyclopedia

Let's see some article posted.

blog.agile.esm.co.jp

It says he met anagram question with code interview and answer was as follows.

def anagram(s1, s2)
  s1.chars.sort == s2.chars.sort
end

Let's try in C#.

Contents

Enumerable.Except

First, I thought it's not good to use Sort for performance issue, and imagine to use Enumerable.Except.

Enumerable.Except(TSource) Method (IEnumerable(TSource), IEnumerable(TSource)) (System.Linq)

But soon I forgive it. Except will be worth when duplicate character is accepted but may take too much check if no allowed. You can see #7 failed with "aba == bab" was true!

gist.github.com

f:id:guitarrapc_tech:20161004034110p:plain

Same issue will happen with Enumerable.All.

Enumerable.All(TSource) Method (System.Linq)

gist.github.com

f:id:guitarrapc_tech:20161004034209p:plain

O(n log n) : Sort with Enumerable.SequenceEqual

May be one of the easiest way is sort array then check. Let's use Enumerable.SequenceEqual() to sorted array.

Enumerable.SequenceEqual(TSource) Method (IEnumerable(TSource), IEnumerable(TSource)) (System.Linq)

It passes all tests. But is O(n log n)....

gist.github.com

f:id:guitarrapc_tech:20161004040316p:plain

string null conditional check ?. will cause duplicate null check, so it may take bit more time.

No LINQ

I like LINQ but let's try no LINQ. Looks like better performance, 181ms.

gist.github.com

f:id:guitarrapc_tech:20161004040246p:plain

O(n) : Dictionary

Let's remove sort and just count with Dictionary. This bring much better performance, only 124ms.

gist.github.com

f:id:guitarrapc_tech:20161004044404p:plain

Also here's my friend @ichiohta's code.

gist.github.com

f:id:guitarrapc_tech:20161004044620p:plain

It takes much time in .GroupBy().ToDictionary(). Swap with my code brings 267ms -> 127ms.

gist.github.com

f:id:guitarrapc_tech:20161004044747p:plain

Dictionary is much better performance than Sort algorithm.

Conclusion

Pattern Algorithm time in 12 test x 100000
Sort (LINQ : Enumerable.SequenceEqual) O(n log n) 280ms
Sort (LINQ : Enumerable.SequenceEqual + ?.) O(n log n) 290ms - 580ms
Sort (NO LINQ) O(n log n) 181ms
Dictionary (NO LINQ) O(n) 124ms
Dictionary (LINQ : GroupBy().ToDictionary()) O(n) 267ms

What's the most readable and fast enough code for you? More idea is much appreciated.