文字列内で n 番目に出現する文字を見つけることに関するいくつかの質問に気付きました。 私は興味があったので (アプリケーションでこれをいくつか使用していますが、主に好奇心から)、Visual Studio 2010 でこれらのメソッドの 2 つをコーディングしてベンチマークしました。 2 ( ). 私が考えることができた唯一の理由は次のとおりです。 FindNthOccurrenceIndexOfNth
- ベンチマーク コードの問題
- アルゴリズムの問題
indexOf組み込みの .NET メソッドであるため、既に最適化されているという事実
私は＃2に傾いていますが、それでも知りたいです。これは関連するコードです。
コード
class Program
{
static void Main(string[] args)
{
char searchChar = 'a';
Random r = new Random(UnixTimestamp());
// Generate sample data
int numSearches = 100000, inputLength = 100;
List<String> inputs = new List<String>(numSearches);
List<int> nth = new List<int>(numSearches);
List<int> occurrences = new List<int>(numSearches);
for (int i = 0; i < numSearches; i++)
{
inputs.Add(GenerateRandomString(inputLength, "abcdefghijklmnopqrstuvwxyz"));
nth.Add(r.Next(1, 4));
}
// Timing of FindNthOccurrence
Stopwatch timeFindNth = Stopwatch.StartNew();
for (int i = 0; i < numSearches; i++)
occurrences.Add(FindNthOccurrence(inputs[i], searchChar, nth[i]));
timeFindNth.Stop();
Console.WriteLine(String.Format("FindNthOccurrence: {0} / {1}",
timeFindNth.ElapsedMilliseconds, timeFindNth.ElapsedTicks));
// Cleanup
occurrences.Clear();
// Timing of IndexOfNth
Stopwatch timeIndexOf = Stopwatch.StartNew();
for (int i = 0; i < numSearches; i++)
occurrences.Add(IndexOfNth(inputs[i], searchChar, nth[i]));
timeIndexOf.Stop();
Console.WriteLine(String.Format("IndexOfNth: {0} / {1}",
timeIndexOf.ElapsedMilliseconds, timeIndexOf.ElapsedTicks));
Console.Read();
}
static int FindNthOccurrence(String input, char c, int n)
{
int len = input.Length;
int occurrences = 0;
for (int i = 0; i < len; i++)
{
if (input[i] == c)
{
occurrences++;
if (occurrences == n)
return i;
}
}
return -1;
}
static int IndexOfNth(String input, char c, int n)
{
int occurrence = 0;
int pos = input.IndexOf(c, 0);
while (pos != -1)
{
occurrence++;
if (occurrence == n)
return pos;
pos = input.IndexOf(c, pos + 1);
}
return -1;
}
// Helper methods
static String GenerateRandomString(int length, String legalCharacters = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789")
{
if (length < 0) throw new ArgumentOutOfRangeException("length", "length cannot be less than zero.");
if (string.IsNullOrEmpty(legalCharacters))
throw new ArgumentException("allowedChars may not be empty.");
const int byteSize = 0x100;
var legalCharSet = new HashSet<char>(legalCharacters).ToArray();
if (byteSize < legalCharSet.Length)
throw new ArgumentException(String.Format("allowedChars may contain no more than {0} characters.", byteSize));
// Guid.NewGuid and System.Random are not particularly random. By using a
// cryptographically-secure random number generator, the caller is always
// protected, regardless of use.
using (var rng = new System.Security.Cryptography.RNGCryptoServiceProvider())
{
StringBuilder result = new StringBuilder();
var buf = new byte[128];
while (result.Length < length)
{
rng.GetBytes(buf);
for (var i = 0; i < buf.Length && result.Length < length; ++i)
{
// Divide the byte into legalCharSet-sized groups. If the
// random value falls into the last group and the last group is
// too small to choose from the entire legalCharSet, ignore
// the value in order to avoid biasing the result.
var outOfRangeStart = byteSize - (byteSize % legalCharSet.Length);
if (outOfRangeStart <= buf[i]) continue;
result.Append(legalCharSet[buf[i] % legalCharSet.Length]);
}
}
return result.ToString();
}
}
static int UnixTimestamp()
{
TimeSpan ts = (System.DateTime.UtcNow - new System.DateTime(1970, 1, 1, 0, 0, 0));
return (int)ts.TotalSeconds;
}
}
サンプル出力
すべての結果は、次のような時間を出力します (ミリ秒 / 経過ティック数):
FindNthOccurrence: 27 / 79716
IndexOfNth: 12 / 36492