C# LINQ Count와 loop 속도 비교

평소 LINQ를 애용하는 편이다.

직관적이고 담당하는 실무에서 탐색이나 정렬의 속도는 크게 중요하지 않기 때문이다.

 

최근 알고리즘 문제풀이를 하면서 로직의 일부에 자연수를 이진수로 바꾼 뒤 1의 개수를 세야 할 일이 있었다.

292 -> "100100100" -> 3개

83 -> "1010011" -> 4개

 

Count 함수를 이용해 아래와 같이 작성 후 테스트를 돌렸는데 절반 정도가 효율성 테스트에서 실패했다.

return Convert.ToString(num, 2).Count(d => d == '1');

 

다른 곳은 수정할만한 곳이 안 보여 loop문을 사용하도록 수정 후 테스트했더니 모두 통과했다.

var count = 0;
var binary = Convert.ToString(num, 2);

foreach (var item in binary)
{
	if (item == '1')
		count++;
}

return count;

 

정확한 테스트 케이스를 볼 수 없기에 직접 테스트 코드를 작성해 loop문이 어느 정도 더 빠른지 체크해봤다.

아래와 같이 action을 repeat만큼 반복하는데 걸리는 시간을 리턴해주는 함수를 하나 만들고

private TimeSpan GetRunningTime(Action action, int repeat)
{
	var stopWatch = new Stopwatch();
    
	stopWatch.Start();

	for (int i = 0; i < repeat; i ++)
		action.Invoke();

	stopWatch.Stop();

	return stopWatch.Elapsed;
}

 

Linq와 loop를 각각 사용하도록 하여 여러 번 돌려보았다.

public void CountingSpecificCharUseCount_MoreSlowerThenLoop_UseStringBinary()
{
	var linqRecord = GetRunningTime(() =>
	{
		var randomBinary = Convert.ToString(new Random().Next(), 2);

		randomBinary.Count(d => d == '1');
	}, 1);

	var loopRecord = GetRunningTime(() =>
	{
		var randomBinary = Convert.ToString(new Random().Next(), 2);

		var count = 0;

		foreach (var item in randomBinary)
		{
			if (item == '1')
				count++;
		}
	}, 1);

	Assert.IsTrue(linqRecord > loopRecord);
	Debug.WriteLine($"LinqRecord vs LoopRecord");
	Debug.WriteLine($"{linqRecord} vs {loopRecord}");
}

 

반복 횟수가 커짐에 따라 속도 차이가 줄어들긴 하지만 loop가 항상 더 빠른 결과를 내고 있음을 확인할 수 있다.

[1회]
LinqRecord vs LoopRecord
00:00:00.0021331 vs 00:00:00.0003779

[100회]
LinqRecord vs LoopRecord
00:00:00.0026233 vs 00:00:00.0005310

[1만 회]
LinqRecord vs LoopRecord
00:00:00.0295593 vs 00:00:00.0246875

[100만 회]
LinqRecord vs LoopRecord
00:00:02.3734790 vs 00:00:02.0551745

[1000만 회]
LinqRecord vs LoopRecord
00:00:21.7544479 vs 00:00:20.5143758

 

Count 함수 내부를 보면 loop를 사용하는 것은 마찬가지지만 Linq는 구조상 Validation check 등의 로직이 추가적으로 붙어있어 이러한 차이가 나는 것 같다.

public static int Count<TSource>(this IEnumerable<TSource> source) {
	if (source == null) throw Error.ArgumentNull("source");
	ICollection<TSource> collectionoft = source as ICollection<TSource>;
	if (collectionoft != null) return collectionoft.Count;
	ICollection collection = source as ICollection;
	if (collection != null) return collection.Count;
	int count = 0;
	using (IEnumerator<TSource> e = source.GetEnumerator()) {
		checked {
			while (e.MoveNext()) count++;
		}
	}
	return count;
}

코드 출처 : Microsoft.referencesource.System.Core.System.Linq github

 

결론 : 알고리즘 풀이에 효율성 테스트가 걸려있는 경우 직접 구현하는 것이 유리할 수 있다.