반응형
문자열 내에서 문자열 (실제로 문자)의 발생 횟수를 어떻게 계산합니까?
나는 /문자열에서 몇 개의 s를 찾을 수 있는지 세고 싶다는 것을 깨달았고 , 여러 가지 방법이 있다는 것을 깨달았지만 가장 좋은 (또는 가장 쉬운) 것이 무엇인지 결정할 수 없었습니다. .
현재 나는 다음과 같이 갈 것입니다.
string source = "/once/upon/a/time/";
int count = source.Length - source.Replace("/", "").Length;
그러나 나는 그것을 전혀 좋아하지 않습니다.
나는 이것을 위해 정말로 파고 싶지 않습니다 RegEx.
내 문자열에 내가 검색하는 용어가있을 것임을 알고 있으므로 다음과 같이 가정 할 수 있습니다.
물론 길이> 1 인 문자열의 경우 ,
string haystack = "/once/upon/a/time";
string needle = "/";
int needleCount = ( haystack.Length - haystack.Replace(needle,"").Length ) / needle.Length;
.NET 3.5를 사용하는 경우 LINQ를 사용하여 한 줄로이 작업을 수행 할 수 있습니다.
int count = source.Count(f => f == '/');
LINQ를 사용하지 않으려면 다음과 같이 할 수 있습니다.
int count = source.Split('/').Length - 1;
당신의 원래 기술이 이들 중 어느 것보다 약 30 % 더 빠른 것 같다는 사실에 놀랄 것입니다! 방금 "/ once / upon / a / time /"으로 빠른 벤치 마크를 수행했으며 결과는 다음과 같습니다.
귀하의 원본 = 12s
source.Count = 19s source. Split =
17s
foreach ( bobwienholt의 답변에서 ) = 10s
(시간은 50,000,000 회 반복이므로 실제 세계에서 큰 차이를 느끼지 못할 것입니다.)
string source = "/once/upon/a/time/";
int count = 0;
foreach (char c in source)
if (c == '/') count++;
source.Replace()그 자체 보다 빨라야 합니다.
int count = new Regex(Regex.Escape(needle)).Matches(haystack).Count;
문자뿐만 아니라 전체 문자열을 검색 할 수 있도록하려면 다음을 수행하십시오.
src.Select((c, i) => src.Substring(i))
.Count(sub => sub.StartsWith(target))
"문자열의 각 문자에 대해 해당 문자에서 시작하는 나머지 문자열을 하위 문자열로 취합니다. 대상 문자열로 시작하면 계산합니다."
몇 가지 조사를 해본 결과 Richard Watson의 솔루션이 대부분의 경우 가장 빠르다는 것을 알았습니다 . 그것은 게시물의 모든 솔루션의 결과가 포함 된 테이블입니다 ( "test {test"와 같은 문자열을 구문 분석하는 동안 예외가 발생하기 때문에 Regex를 사용하는 경우 제외 ).
Name | Short/char | Long/char | Short/short| Long/short | Long/long |
Inspite | 134| 1853| 95| 1146| 671|
LukeH_1 | 346| 4490| N/A| N/A| N/A|
LukeH_2 | 152| 1569| 197| 2425| 2171|
Bobwienholt | 230| 3269| N/A| N/A| N/A|
Richard Watson| 33| 298| 146| 737| 543|
StefanosKargas| N/A| N/A| 681| 11884| 12486|
짧은 문자열 (10-50 자)에서 짧은 부분 문자열 (1-5 자)의 발생 횟수를 찾는 경우 원래 알고리즘이 선호됨을 알 수 있습니다.
또한 다중 문자 하위 문자열의 경우 다음 코드를 사용해야합니다 ( Richard Watson의 솔루션 기반 ).
int count = 0, n = 0;
if(substring != "")
{
while ((n = source.IndexOf(substring, n, StringComparison.InvariantCulture)) != -1)
{
n += substring.Length;
++count;
}
}
LINQ는 모든 컬렉션에서 작동하며 문자열은 문자 모음 일 뿐이므로이 멋진 한 줄짜리는 어떻습니까?
var count = source.Count(c => c == '/');
되어 있는지 확인하십시오 using System.Linq;으로, 코드 파일의 맨 위에 .Count해당 네임 스페이스에서 확장 방법이다.
string source = "/once/upon/a/time/";
int count = 0;
int n = 0;
while ((n = source.IndexOf('/', n)) != -1)
{
n++;
count++;
}
내 컴퓨터에서는 5 천만 번의 반복을위한 for-every-character 솔루션보다 약 2 초 더 빠릅니다.
2013 년 개정 :
문자열을 char []로 변경하고이를 반복합니다. 50m 반복의 총 시간을 1 ~ 2 초 더 단축합니다!
char[] testchars = source.ToCharArray();
foreach (char c in testchars)
{
if (c == '/')
count++;
}
여전히 더 빠릅니다.
char[] testchars = source.ToCharArray();
int length = testchars.Length;
for (int n = 0; n < length; n++)
{
if (testchars[n] == '/')
count++;
}
좋은 측정을 위해 배열의 끝에서 0으로 반복하는 것이 약 5 %만큼 가장 빠른 것 같습니다.
int length = testchars.Length;
for (int n = length-1; n >= 0; n--)
{
if (testchars[n] == '/')
count++;
}
나는 이것이 왜 그렇게 될 수 있고 인터넷 검색이 가능한지 궁금했고 (역방향 반복이 더 빠르다는 것을 기억합니다) 이미 문자열을 char [] 기술로 성가 시게 사용하는이 SO 질문을 받았습니다. 하지만 이러한 맥락에서 반전 트릭은 새로운 것이라고 생각합니다.
C #에서 문자열의 개별 문자를 반복하는 가장 빠른 방법은 무엇입니까?
둘 다 단일 문자 검색어에 대해서만 작동합니다 ...
countOccurences("the", "the answer is the answer");
int countOccurences(string needle, string haystack)
{
return (haystack.Length - haystack.Replace(needle,"").Length) / needle.Length;
}
긴 바늘에 더 나은 것으로 판명 될 수 있습니다 ...
그러나 더 우아한 방법이 있어야합니다. :)
편집하다:
source.Split('/').Length-1
C #에서 멋진 String SubString 카운터는 예기치 않게 까다로운 동료입니다.
public static int CCount(String haystack, String needle)
{
return haystack.Split(new[] { needle }, StringSplitOptions.None).Length - 1;
}
Regex.Matches(input, Regex.Escape("stringToMatch")).Count
private int CountWords(string text, string word) {
int count = (text.Length - text.Replace(word, "").Length) / word.Length;
return count;
}
원래 솔루션이 문자에 대해 가장 빠르기 때문에 문자열에도 적용됩니다. 여기 제 공헌이 있습니다.
컨텍스트 : 로그 파일에서 '실패'및 '성공'과 같은 단어를 찾고있었습니다.
Gr, Ben
string s = "65 fght 6565 4665 hjk";
int count = 0;
foreach (Match m in Regex.Matches(s, "65"))
count++;
문자열 확장 방법을 사용할 준비가 된 사람을 위해,
여기에 게시 된 답변 중 가장 좋은 것을 기반으로 사용하는 것이 있습니다.
public static class StringExtension
{
/// <summary> Returns the number of occurences of a string within a string, optional comparison allows case and culture control. </summary>
public static int Occurrences(this System.String input, string value, StringComparison stringComparisonType = StringComparison.Ordinal)
{
if (String.IsNullOrEmpty(value)) return 0;
int count = 0;
int position = 0;
while ((position = input.IndexOf(value, position, stringComparisonType)) != -1)
{
position += value.Length;
count += 1;
}
return count;
}
/// <summary> Returns the number of occurences of a single character within a string. </summary>
public static int Occurrences(this System.String input, char value)
{
int count = 0;
foreach (char c in input) if (c == value) count += 1;
return count;
}
}
public static int GetNumSubstringOccurrences(string text, string search)
{
int num = 0;
int pos = 0;
if (!string.IsNullOrEmpty(text) && !string.IsNullOrEmpty(search))
{
while ((pos = text.IndexOf(search, pos)) > -1)
{
num ++;
pos += search.Length;
}
}
return num;
}
이를 수행하는 가장 쉬운 방법은 정규 표현식을 사용하는 것입니다. 이렇게하면 myVar.Split ( 'x')를 사용할 수있는 것과 동일한 분할 수를 얻을 수 있지만 여러 문자 설정에서 사용할 수 있습니다.
string myVar = "do this to count the number of words in my wording so that I can word it up!";
int count = Regex.Split(myVar, "word").Length;
string search = "/string";
var occurrences = (regex.Match(search, @"\/")).Count;
이것은 프로그램이 정확하게 "/ s"를 찾을 때마다 (대소 문자 구분) 계산되며,이 횟수는 변수 "occurrences"에 저장됩니다.
문자열 발생에 대한 일반 함수 :
public int getNumberOfOccurencies(String inputString, String checkString)
{
if (checkString.Length > inputString.Length || checkString.Equals("")) { return 0; }
int lengthDifference = inputString.Length - checkString.Length;
int occurencies = 0;
for (int i = 0; i < lengthDifference; i++) {
if (inputString.Substring(i, checkString.Length).Equals(checkString)) { occurencies++; i += checkString.Length - 1; } }
return occurencies;
}
string source = "/once/upon/a/time/";
int count = 0, n = 0;
while ((n = source.IndexOf('/', n) + 1) != 0) count++;
Richard Watson의 답변에 대한 변형으로, 문자열에서 문자가 더 많이 발생하고 코드가 적을수록 효율성이 향상되어 약간 더 빠릅니다!
모든 시나리오를 광범위하게 테스트하지 않고도 다음을 사용하여 속도가 매우 크게 향상되었습니다.
int count = 0;
for (int n = 0; n < source.Length; n++) if (source[n] == '/') count++;
var conditionalStatement = conditionSetting.Value;
//order of replace matters, remove == before =, incase of ===
conditionalStatement = conditionalStatement.Replace("==", "~").Replace("!=", "~").Replace('=', '~').Replace('!', '~').Replace('>', '~').Replace('<', '~').Replace(">=", "~").Replace("<=", "~");
var listOfValidConditions = new List<string>() { "!=", "==", ">", "<", ">=", "<=" };
if (conditionalStatement.Count(x => x == '~') != 1)
{
result.InvalidFieldList.Add(new KeyFieldData(batch.DECurrentField, "The IsDoubleKeyCondition does not contain a supported conditional statement. Contact System Administrator."));
result.Status = ValidatorStatus.Fail;
return result;
}
문자열에서 조건문을 테스트하는 것과 유사한 작업을 수행해야합니다.
내가 찾고 있던 것을 단일 캐릭터로 대체하고 단일 캐릭터의 인스턴스를 계산했습니다.
분명히 사용중인 단일 문자가 잘못된 개수를 방지하기 위해 문자열에 존재하지 않는지 확인해야합니다.
문자열의 문자열 :
".. JD JD JD JD 등 JDJDJDJDJDJDJDJD 등"에서 "etc"를 찾습니다.
var strOrigin = " .. JD JD JD JD etc. and etc. JDJDJDJDJDJDJDJD and etc.";
var searchStr = "etc";
int count = (strOrigin.Length - strOrigin.Replace(searchStr, "").Length)/searchStr.Length.
이것을 불건전하거나 어색한 것으로 버리기 전에 성능을 확인하십시오.
안전하지 않은 바이트 단위 비교와 같은 특정 종류의 하위 문자열 계산이 부족하다고 느꼈습니다. 나는 원래 포스터의 방법과 내가 생각할 수있는 방법을 모았다.
이것들은 내가 만든 문자열 확장입니다.
namespace Example
{
using System;
using System.Text;
public static class StringExtensions
{
public static int CountSubstr(this string str, string substr)
{
return (str.Length - str.Replace(substr, "").Length) / substr.Length;
}
public static int CountSubstr(this string str, char substr)
{
return (str.Length - str.Replace(substr.ToString(), "").Length);
}
public static int CountSubstr2(this string str, string substr)
{
int substrlen = substr.Length;
int lastIndex = str.IndexOf(substr, 0, StringComparison.Ordinal);
int count = 0;
while (lastIndex != -1)
{
++count;
lastIndex = str.IndexOf(substr, lastIndex + substrlen, StringComparison.Ordinal);
}
return count;
}
public static int CountSubstr2(this string str, char substr)
{
int lastIndex = str.IndexOf(substr, 0);
int count = 0;
while (lastIndex != -1)
{
++count;
lastIndex = str.IndexOf(substr, lastIndex + 1);
}
return count;
}
public static int CountChar(this string str, char substr)
{
int length = str.Length;
int count = 0;
for (int i = 0; i < length; ++i)
if (str[i] == substr)
++count;
return count;
}
public static int CountChar2(this string str, char substr)
{
int count = 0;
foreach (var c in str)
if (c == substr)
++count;
return count;
}
public static unsafe int CountChar3(this string str, char substr)
{
int length = str.Length;
int count = 0;
fixed (char* chars = str)
{
for (int i = 0; i < length; ++i)
if (*(chars + i) == substr)
++count;
}
return count;
}
public static unsafe int CountChar4(this string str, char substr)
{
int length = str.Length;
int count = 0;
fixed (char* chars = str)
{
for (int i = length - 1; i >= 0; --i)
if (*(chars + i) == substr)
++count;
}
return count;
}
public static unsafe int CountSubstr3(this string str, string substr)
{
int length = str.Length;
int substrlen = substr.Length;
int count = 0;
fixed (char* strc = str)
{
fixed (char* substrc = substr)
{
int n = 0;
for (int i = 0; i < length; ++i)
{
if (*(strc + i) == *(substrc + n))
{
++n;
if (n == substrlen)
{
++count;
n = 0;
}
}
else
n = 0;
}
}
}
return count;
}
public static int CountSubstr3(this string str, char substr)
{
return CountSubstr3(str, substr.ToString());
}
public static unsafe int CountSubstr4(this string str, string substr)
{
int length = str.Length;
int substrLastIndex = substr.Length - 1;
int count = 0;
fixed (char* strc = str)
{
fixed (char* substrc = substr)
{
int n = substrLastIndex;
for (int i = length - 1; i >= 0; --i)
{
if (*(strc + i) == *(substrc + n))
{
if (--n == -1)
{
++count;
n = substrLastIndex;
}
}
else
n = substrLastIndex;
}
}
}
return count;
}
public static int CountSubstr4(this string str, char substr)
{
return CountSubstr4(str, substr.ToString());
}
}
}
테스트 코드 다음에 ...
static void Main()
{
const char matchA = '_';
const string matchB = "and";
const string matchC = "muchlongerword";
const string testStrA = "_and_d_e_banna_i_o___pfasd__and_d_e_banna_i_o___pfasd_";
const string testStrB = "and sdf and ans andeians andano ip and and sdf and ans andeians andano ip and";
const string testStrC =
"muchlongerword amuchlongerworsdfmuchlongerwordsdf jmuchlongerworijv muchlongerword sdmuchlongerword dsmuchlongerword";
const int testSize = 1000000;
Console.WriteLine(testStrA.CountSubstr('_'));
Console.WriteLine(testStrA.CountSubstr2('_'));
Console.WriteLine(testStrA.CountSubstr3('_'));
Console.WriteLine(testStrA.CountSubstr4('_'));
Console.WriteLine(testStrA.CountChar('_'));
Console.WriteLine(testStrA.CountChar2('_'));
Console.WriteLine(testStrA.CountChar3('_'));
Console.WriteLine(testStrA.CountChar4('_'));
Console.WriteLine(testStrB.CountSubstr("and"));
Console.WriteLine(testStrB.CountSubstr2("and"));
Console.WriteLine(testStrB.CountSubstr3("and"));
Console.WriteLine(testStrB.CountSubstr4("and"));
Console.WriteLine(testStrC.CountSubstr("muchlongerword"));
Console.WriteLine(testStrC.CountSubstr2("muchlongerword"));
Console.WriteLine(testStrC.CountSubstr3("muchlongerword"));
Console.WriteLine(testStrC.CountSubstr4("muchlongerword"));
var timer = new Stopwatch();
timer.Start();
for (int i = 0; i < testSize; ++i)
testStrA.CountSubstr(matchA);
timer.Stop();
Console.WriteLine("CS1 chr: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrB.CountSubstr(matchB);
timer.Stop();
Console.WriteLine("CS1 and: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrC.CountSubstr(matchC);
timer.Stop();
Console.WriteLine("CS1 mlw: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrA.CountSubstr2(matchA);
timer.Stop();
Console.WriteLine("CS2 chr: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrB.CountSubstr2(matchB);
timer.Stop();
Console.WriteLine("CS2 and: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrC.CountSubstr2(matchC);
timer.Stop();
Console.WriteLine("CS2 mlw: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrA.CountSubstr3(matchA);
timer.Stop();
Console.WriteLine("CS3 chr: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrB.CountSubstr3(matchB);
timer.Stop();
Console.WriteLine("CS3 and: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrC.CountSubstr3(matchC);
timer.Stop();
Console.WriteLine("CS3 mlw: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrA.CountSubstr4(matchA);
timer.Stop();
Console.WriteLine("CS4 chr: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrB.CountSubstr4(matchB);
timer.Stop();
Console.WriteLine("CS4 and: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrC.CountSubstr4(matchC);
timer.Stop();
Console.WriteLine("CS4 mlw: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrA.CountChar(matchA);
timer.Stop();
Console.WriteLine("CC1 chr: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrA.CountChar2(matchA);
timer.Stop();
Console.WriteLine("CC2 chr: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrA.CountChar3(matchA);
timer.Stop();
Console.WriteLine("CC3 chr: " + timer.Elapsed.TotalMilliseconds + "ms");
timer.Restart();
for (int i = 0; i < testSize; ++i)
testStrA.CountChar4(matchA);
timer.Stop();
Console.WriteLine("CC4 chr: " + timer.Elapsed.TotalMilliseconds + "ms");
}
결과 : CSX는 CountSubstrX에 해당하고 CCX는 CountCharX에 해당합니다. "chr"은 문자열에서 '_'를 검색하고, "and"는 문자열에서 "and"를 검색하고, "mlw"는 문자열에서 "muchlongerword"를 검색합니다.
CS1 chr: 824.123ms
CS1 and: 586.1893ms
CS1 mlw: 486.5414ms
CS2 chr: 127.8941ms
CS2 and: 806.3918ms
CS2 mlw: 497.318ms
CS3 chr: 201.8896ms
CS3 and: 124.0675ms
CS3 mlw: 212.8341ms
CS4 chr: 81.5183ms
CS4 and: 92.0615ms
CS4 mlw: 116.2197ms
CC1 chr: 66.4078ms
CC2 chr: 64.0161ms
CC3 chr: 65.9013ms
CC4 chr: 65.8206ms
마지막으로 360 만 자의 파일이 생겼습니다. 10 만회 반복 된 "derp adfderdserp dfaerpderp deasderp"였습니다. 위의 방법으로 파일 내에서 "derp"를 100 번 검색했습니다.
CS1Derp: 1501.3444ms
CS2Derp: 1585.797ms
CS3Derp: 376.0937ms
CS4Derp: 271.1663ms
그래서 내 4 번째 방법이 확실히 승자이지만 현실적으로 360 만 개의 문자 파일이 100 번이나 더 나쁜 경우 1586ms 만 걸린다면이 모든 것은 매우 무시할 만합니다.
그건 그렇고, 100 회 CountSubstr 및 CountChar 메서드를 사용하여 360 만 문자 파일에서 'd'문자를 검색했습니다. 결과 ...
CS1 d : 2606.9513ms
CS2 d : 339.7942ms
CS3 d : 960.281ms
CS4 d : 233.3442ms
CC1 d : 302.4122ms
CC2 d : 280.7719ms
CC3 d : 299.1125ms
CC4 d : 292.9365ms
이것에 따르면 원래 포스터 방법은 큰 건초 더미에서 단일 문자 바늘에 매우 나쁩니다.
참고 : 모든 값이 릴리스 버전 출력으로 업데이트되었습니다. 처음 게시했을 때 실수로 릴리스 모드에서 빌드하는 것을 잊었습니다. 내 진술 중 일부가 수정되었습니다.
string Name = "Very good nice one is very good but is very good nice one this is called the term";
bool valid=true;
int count = 0;
int k=0;
int m = 0;
while (valid)
{
k = Name.Substring(m,Name.Length-m).IndexOf("good");
if (k != -1)
{
count++;
m = m + k + 4;
}
else
valid = false;
}
Console.WriteLine(count + " Times accures");
string s = "HOWLYH THIS ACTUALLY WORKSH WOWH";
int count = 0;
for (int i = 0; i < s.Length; i++)
if (s[i] == 'H') count++;
문자열의 모든 문자를 확인하고 문자가 검색중인 문자이면 하나를 추가하여 계산합니다.
이 웹 페이지 를 확인 하면 병렬 루프 사용을 포함하여이를 수행하는 15 가지 방법이 벤치마킹됩니다.
가장 빠른 방법은 단일 스레드 for 루프 (.Net 버전 <4.0이있는 경우) 또는 parallel.for 루프 (수천 번의 검사와 함께 .Net> 4.0을 사용하는 경우)를 사용하는 것 같습니다.
"ss"가 검색 문자열이라고 가정하고, "ch"는 문자 배열 (찾고있는 문자가 둘 이상인 경우), 단일 스레드 실행 시간이 가장 빠른 코드의 기본 요점은 다음과 같습니다.
for (int x = 0; x < ss.Length; x++)
{
for (int y = 0; y < ch.Length; y++)
{
for (int a = 0; a < ss[x].Length; a++ )
{
if (ss[x][a] == ch[y])
//it's found. DO what you need to here.
}
}
}
자체 테스트를 실행할 수 있도록 벤치 마크 소스 코드도 제공됩니다.
내 확장 방법을 링에 던질 것이라고 생각했습니다 (자세한 내용은 주석 참조). 나는 공식적인 벤치 마킹을하지 않았지만 대부분의 시나리오에서 매우 빨라야한다고 생각합니다.
편집 : OK-그래서이 질문은 현재 구현의 성능이 여기에 제시된 일부 솔루션에 대해 어떻게 누적되는지 궁금해하게했습니다. 나는 약간의 벤치마킹을하기로 결정했고 큰 문자열 (100Kb +), 큰 부분 문자열 (32Kb + ) 및 많은 임베디드 반복 (10K +). 그 시점에서 우리의 솔루션은 약 2 배에서 4 배 더 느 렸습니다. 이 점과 Richard Watson이 제시 한 솔루션이 정말 마음에 든다는 사실을 감안할 때 그에 따라 솔루션을 리팩토링했습니다. 나는 그 혜택을 누릴 수있는 모든 사람들에게 이것을 제공하고 싶었습니다.
당사의 원래 솔루션 :
/// <summary>
/// Counts the number of occurrences of the specified substring within
/// the current string.
/// </summary>
/// <param name="s">The current string.</param>
/// <param name="substring">The substring we are searching for.</param>
/// <param name="aggressiveSearch">Indicates whether or not the algorithm
/// should be aggressive in its search behavior (see Remarks). Default
/// behavior is non-aggressive.</param>
/// <remarks>This algorithm has two search modes - aggressive and
/// non-aggressive. When in aggressive search mode (aggressiveSearch =
/// true), the algorithm will try to match at every possible starting
/// character index within the string. When false, all subsequent
/// character indexes within a substring match will not be evaluated.
/// For example, if the string was 'abbbc' and we were searching for
/// the substring 'bb', then aggressive search would find 2 matches
/// with starting indexes of 1 and 2. Non aggressive search would find
/// just 1 match with starting index at 1. After the match was made,
/// the non aggressive search would attempt to make it's next match
/// starting at index 3 instead of 2.</remarks>
/// <returns>The count of occurrences of the substring within the string.</returns>
public static int CountOccurrences(this string s, string substring,
bool aggressiveSearch = false)
{
// if s or substring is null or empty, substring cannot be found in s
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(substring))
return 0;
// if the length of substring is greater than the length of s,
// substring cannot be found in s
if (substring.Length > s.Length)
return 0;
var sChars = s.ToCharArray();
var substringChars = substring.ToCharArray();
var count = 0;
var sCharsIndex = 0;
// substring cannot start in s beyond following index
var lastStartIndex = sChars.Length - substringChars.Length;
while (sCharsIndex <= lastStartIndex)
{
if (sChars[sCharsIndex] == substringChars[0])
{
// potential match checking
var match = true;
var offset = 1;
while (offset < substringChars.Length)
{
if (sChars[sCharsIndex + offset] != substringChars[offset])
{
match = false;
break;
}
offset++;
}
if (match)
{
count++;
// if aggressive, just advance to next char in s, otherwise,
// skip past the match just found in s
sCharsIndex += aggressiveSearch ? 1 : substringChars.Length;
}
else
{
// no match found, just move to next char in s
sCharsIndex++;
}
}
else
{
// no match at current index, move along
sCharsIndex++;
}
}
return count;
}
수정 된 솔루션은 다음과 같습니다.
/// <summary>
/// Counts the number of occurrences of the specified substring within
/// the current string.
/// </summary>
/// <param name="s">The current string.</param>
/// <param name="substring">The substring we are searching for.</param>
/// <param name="aggressiveSearch">Indicates whether or not the algorithm
/// should be aggressive in its search behavior (see Remarks). Default
/// behavior is non-aggressive.</param>
/// <remarks>This algorithm has two search modes - aggressive and
/// non-aggressive. When in aggressive search mode (aggressiveSearch =
/// true), the algorithm will try to match at every possible starting
/// character index within the string. When false, all subsequent
/// character indexes within a substring match will not be evaluated.
/// For example, if the string was 'abbbc' and we were searching for
/// the substring 'bb', then aggressive search would find 2 matches
/// with starting indexes of 1 and 2. Non aggressive search would find
/// just 1 match with starting index at 1. After the match was made,
/// the non aggressive search would attempt to make it's next match
/// starting at index 3 instead of 2.</remarks>
/// <returns>The count of occurrences of the substring within the string.</returns>
public static int CountOccurrences(this string s, string substring,
bool aggressiveSearch = false)
{
// if s or substring is null or empty, substring cannot be found in s
if (string.IsNullOrEmpty(s) || string.IsNullOrEmpty(substring))
return 0;
// if the length of substring is greater than the length of s,
// substring cannot be found in s
if (substring.Length > s.Length)
return 0;
int count = 0, n = 0;
while ((n = s.IndexOf(substring, n, StringComparison.InvariantCulture)) != -1)
{
if (aggressiveSearch)
n++;
else
n += substring.Length;
count++;
}
return count;
}
내 초기 테이크는 다음과 같은 것을 얻었습니다.
public static int CountOccurrences(string original, string substring)
{
if (string.IsNullOrEmpty(substring))
return 0;
if (substring.Length == 1)
return CountOccurrences(original, substring[0]);
if (string.IsNullOrEmpty(original) ||
substring.Length > original.Length)
return 0;
int substringCount = 0;
for (int charIndex = 0; charIndex < original.Length; charIndex++)
{
for (int subCharIndex = 0, secondaryCharIndex = charIndex; subCharIndex < substring.Length && secondaryCharIndex < original.Length; subCharIndex++, secondaryCharIndex++)
{
if (substring[subCharIndex] != original[secondaryCharIndex])
goto continueOuter;
}
if (charIndex + substring.Length > original.Length)
break;
charIndex += substring.Length - 1;
substringCount++;
continueOuter:
;
}
return substringCount;
}
public static int CountOccurrences(string original, char @char)
{
if (string.IsNullOrEmpty(original))
return 0;
int substringCount = 0;
for (int charIndex = 0; charIndex < original.Length; charIndex++)
if (@char == original[charIndex])
substringCount++;
return substringCount;
}
대체 및 분할을 사용하는 건초 더미 방식의 바늘은 21 초 이상을 산출하지만 약 15.2가 소요됩니다.
substring.Length - 1charIndex에 추가 할 비트를 추가 한 후 편집하면 11.6 초가됩니다.
편집 2 : 26 개의 2 자 문자열이있는 문자열을 사용했습니다. 동일한 샘플 텍스트로 업데이트 된 시간은 다음과 같습니다.
건초 더미의 바늘 (OP 버전) : 7.8 초
권장 메커니즘 : 4.6 초.
편집 3 : 단일 문자 코너 케이스를 추가하면 1.2 초가되었습니다.
편집 4 : 컨텍스트 : 5 천만 번의 반복이 사용되었습니다.
str="aaabbbbjjja";
int count = 0;
int size = str.Length;
string[] strarray = new string[size];
for (int i = 0; i < str.Length; i++)
{
strarray[i] = str.Substring(i, 1);
}
Array.Sort(strarray);
str = "";
for (int i = 0; i < strarray.Length - 1; i++)
{
if (strarray[i] == strarray[i + 1])
{
count++;
}
else
{
count++;
str = str + strarray[i] + count;
count = 0;
}
}
count++;
str = str + strarray[strarray.Length - 1] + count;
이것은 캐릭터 발생을 계산하기위한 것입니다. 이 예제의 경우 출력은 "a4b4j3"입니다.
문자열 구분 기호의 경우 (주제가 말한대로 문자 대소 문자가 아님) :
string source = "@@@ once @@@ upon @@@ a @@@ time @@@";
int count = source.Split (new [] { "@@@"}, StringSplitOptions.RemoveEmptyEntries) .Length-1;
포스터의 원래 소스 값 ( "/ once / upon / a / time /") 자연 구분 기호는 char '/'이고 응답은 source.Split (char []) 옵션을 설명합니다.
System.Linq 사용;
int CountOf => "A :: BC :: D".Split ( "::"). Length-1;
반응형
'Programing' 카테고리의 다른 글
| Java에서 InputStream을 바이트 배열로 변환 (0) | 2020.09.29 |
|---|---|
| substr과 substring의 차이점은 무엇입니까? (0) | 2020.09.29 |
| jQuery를 사용하여 드롭 다운 목록의 선택한 값 변경 (0) | 2020.09.29 |
| 파이썬 프로그램 실행 시간을 어떻게 얻습니까? (0) | 2020.09.29 |
| 시간 초과로 Redux 작업을 전달하는 방법은 무엇입니까? (0) | 2020.09.29 |