Where 및 Select가 Select보다 우수한 이유는 무엇입니까?
다음과 같은 수업이 있습니다.
public class MyClass
{
public int Value { get; set; }
public bool IsValid { get; set; }
}
실제로 그것은 훨씬 더 크지 만 이것은 문제 (이상성)를 재현합니다.
Value인스턴스가 유효한 의 합계를 얻고 싶습니다 . 지금까지 두 가지 해결책을 찾았습니다.
첫 번째는 이것입니다 :
int result = myCollection.Where(mc => mc.IsValid).Select(mc => mc.Value).Sum();
그러나 두 번째는 다음과 같습니다.
int result = myCollection.Select(mc => mc.IsValid ? mc.Value : 0).Sum();
가장 효율적인 방법을 원합니다. 처음에는 두 번째가 더 효율적이라고 생각했습니다. 그런 다음 저의 이론적 인 부분은 "음, 하나는 O (n + m + m)이고, 다른 하나는 O (n + n)입니다. 첫 번째는 더 많은 무효 인과 더 잘 수행해야하고, 두 번째는 더 나은 수행을해야합니다. 적은 " 나는 그들이 똑같이 수행 할 것이라고 생각했다. 편집 : 그런 다음 @Martin은 Where와 Select가 결합되어 실제로 O (m + n)이어야한다고 지적했습니다. 그러나 아래를 보면 관련이없는 것 같습니다.
그래서 테스트에 넣었습니다.
(100 줄 이상이므로 Gist로 게시하는 것이 더 좋다고 생각했습니다.)
결과는 ... 흥미로 웠습니다.
타이 공차가 0 % 인 경우 :
비늘의 찬성 Select과 Where~ 30 점에 대한 의해.
How much do you want to be the disambiguation percentage?
0
Starting benchmarking.
Ties: 0
Where + Select: 65
Select: 36
2 % 타이 공차로 :
일부의 경우 2 % 이내라는 점을 제외하면 동일합니다. 나는 그것이 최소한의 오차 한계라고 말하고 싶습니다. Select그리고 Where지금은 그냥 ~ 20 점 리드를 가지고있다.
How much do you want to be the disambiguation percentage?
2
Starting benchmarking.
Ties: 6
Where + Select: 58
Select: 37
5 % 타이 공차 :
이것이 내가 최대 오차 한계라고 말한 것입니다. 그것은 조금 나아지 Select지만 별로는 아닙니다.
How much do you want to be the disambiguation percentage?
5
Starting benchmarking.
Ties: 17
Where + Select: 53
Select: 31
10 % 타이 공차 :
이것은 내 오류 한계를 벗어난 방법이지만 여전히 결과에 관심이 있습니다. 그것이 지금 Select과 Where20 점의 리드를주기 때문입니다.
How much do you want to be the disambiguation percentage?
10
Starting benchmarking.
Ties: 36
Where + Select: 44
Select: 21
타이 공차가 25 % 인 경우 :
이것은 내 오류 한계를 벗어난 방법 이지만 Select, Where 여전히 (거의) 20 점을 유지 하기 때문에 결과에 관심이 있습니다. 그것은 몇 가지로 그것을 능가하는 것처럼 보이며, 그것이 리드를주는 것입니다.
How much do you want to be the disambiguation percentage?
25
Starting benchmarking.
Ties: 85
Where + Select: 16
Select: 0
지금, 나는 20 점 리드들이 모두 얻을되어있어 중간에서 온 것으로 추측하고있어 주위 동일한 성능을. 나는 그것을 시도하고 기록 할 수 있지만, 정보를 얻는 데 많은 양의 짐이 될 것입니다. 그래프가 더 좋을 것 같습니다.
그것이 제가 한 일입니다.
그것은 Select선이 꾸준히 유지 (예상)되고 Select + Where선이 위로 올라가는 것을 나타냅니다 (예상). 그러나 나를 당황스럽게하는 이유는 그것이 Select50 또는 그 이전에 충족되지 않는 이유 입니다. 실제로 Selectand에 대해 추가 열거자를 만들어야했기 때문에 실제로 50보다 일찍 기대했습니다 Where. 이것은 20 포인트 리드를 보여 주지만 그 이유를 설명하지는 않습니다. 이것이 내 질문의 요점이라고 생각합니다.
왜 이렇게 동작합니까? 믿을까요? 그렇지 않은 경우 다른 것을 사용해야합니까?
주석에서 @KingKong이 언급했듯이 Sum람다를 사용하는 의 과부하를 사용할 수도 있습니다 . 이제 두 가지 옵션이 다음과 같이 변경되었습니다.
먼저:
int result = myCollection.Where(mc => mc.IsValid).Sum(mc => mc.Value);
둘째:
int result = myCollection.Sum(mc => mc.IsValid ? mc.Value : 0);
조금 더 짧게 만들 것입니다.
How much do you want to be the disambiguation percentage?
0
Starting benchmarking.
Ties: 0
Where: 60
Sum: 41
How much do you want to be the disambiguation percentage?
2
Starting benchmarking.
Ties: 8
Where: 55
Sum: 38
How much do you want to be the disambiguation percentage?
5
Starting benchmarking.
Ties: 21
Where: 49
Sum: 31
How much do you want to be the disambiguation percentage?
10
Starting benchmarking.
Ties: 39
Where: 41
Sum: 21
How much do you want to be the disambiguation percentage?
25
Starting benchmarking.
Ties: 85
Where: 16
Sum: 0
20 점 리드는 여전히 있으며 이는 의견에서 @Marcin이 지적한 Where및 Select조합 과 관련이 없음을 의미합니다 .
내 성벽을 읽어 주셔서 감사합니다! 당신이 관심이 있다면 또한, 여기에 엑셀에 소요되는 CSV를 기록 수정 된 버전.
Select전체 집합에 대해 한 번 반복하고 각 항목에 대해 조건부 분기 (유효성 검사) 및 +작업을 수행합니다.
Where+Select유효하지 않은 요소를 건너 뛰고 (무효하지 않은) 반복자를 작성 하여 유효한 항목에 대해서만 yield수행 +합니다.
따라서 비용 Select은 다음과 같습니다.
t(s) = n * ( cost(check valid) + cost(+) )
그리고위한 Where+Select:
t(ws) = n * ( cost(check valid) + p(valid) * (cost(yield) + cost(+)) )
어디:
p(valid)목록의 항목이 유효 할 확률입니다.cost(check valid)유효성을 검사하는 지점의 비용입니다.cost(yield)where이터레이터 의 새로운 상태를 구성하는 비용은Select버전이 사용 하는 간단한 이터레이터보다 더 복잡 합니다.
보시다시피 주어진 n에 대해 Select버전은 상수 인 반면 Where+Select버전은 p(valid)변수 가있는 선형 방정식입니다 . 비용의 실제 값은 두 선의 교점을 결정하며와 cost(yield)다를 수 있으므로 cost(+)반드시 p(valid)= 0.5 에서 교차 할 필요는 없습니다 .
타이밍 차이를 일으키는 원인에 대한 자세한 설명은 다음과 같습니다.
Sum()에 대한 기능 IEnumerable<int>다음과 같다 :
public static int Sum(this IEnumerable<int> source)
{
int sum = 0;
foreach(int item in source)
{
sum += item;
}
return sum;
}
C #에서는 foreach.Net의 반복기 버전에 대한 구문 설탕입니다 (와 혼동하지 마십시오 ) . 위의 코드는 실제로 다음과 같이 번역됩니다.IEnumerator<T> IEnumerable<T>
public static int Sum(this IEnumerable<int> source)
{
int sum = 0;
IEnumerator<int> iterator = source.GetEnumerator();
while(iterator.MoveNext())
{
int item = iterator.Current;
sum += item;
}
return sum;
}
비교하는 두 줄의 코드는 다음과 같습니다.
int result1 = myCollection.Where(mc => mc.IsValid).Sum(mc => mc.Value);
int result2 = myCollection.Sum(mc => mc.IsValid ? mc.Value : 0);
이제 키커가 있습니다.
LINQ는 지연된 실행을 사용합니다 . 그것은 수있는 반면 따라서, 표시 그 result1두 번 컬렉션을 반복을 실제로 한 번만 반복 할 때. Where()조건은 실제로 동안 적용됩니다 Sum()에 대한 호출의 내부 MoveNext() (이의 마법 덕분에 가능하다 yield return) .
즉, for 루프 result1내부의 코드는while
{
int item = iterator.Current;
sum += item;
}
로 각 항목에 대해 한 번만 실행됩니다 mc.IsValid == true. 이에 비해 컬렉션의 모든 항목에 result2대해 해당 코드를 실행합니다 . 이것이 일반적으로 더 빠른 이유 입니다.result1
(비록, 호출하는 것으로 Where()내에서 조건을 MoveNext()여전히 작은 오버 헤드를 가지고, 그래서 대부분의 경우 / 모든 항목은 한 mc.IsValid == true, result2실제로 빨라집니다!)
바라건대 이제 왜 result2일반적으로 느린 지 분명 합니다. 이제 이러한 LINQ 성능 비교가 중요하지 않다는 의견에 왜 언급했는지 설명하고 싶습니다 .
LINQ 표현식을 만드는 것이 저렴합니다. 델리게이트 기능을 호출하는 것이 저렴합니다. 반복자를 할당하고 반복하는 것이 저렴합니다. 그러나 이러한 일 을 하지 않는 것이 훨씬 저렴합니다 . 따라서 LINQ 문이 프로그램의 병목 현상을 발견하면 LINQ없이 다시 작성 하면 다양한 LINQ 방법보다 항상 빠릅니다.
따라서 LINQ 워크 플로는 다음과 같아야합니다.
- 어디서나 LINQ를 사용하십시오.
- 프로필.
- 프로파일 러에 LINQ가 병목 현상의 원인이라고 표시되면 LINQ없이 해당 코드를 다시 작성하십시오.
다행히 LINQ 병목 현상은 거의 없습니다. 병목 현상은 드물다. 지난 몇 년 동안 수백 개의 LINQ 문을 작성했으며 결국 <1 %를 대체했습니다. 그리고 이들 중 대부분은 LINQ의 결함이 아니라 LINQ2EF 의 SQL 최적화가 잘못 되었기 때문 입니다.
그래서, 언제나처럼, 때까지 명확하고 합리적인 첫 번째 코드 및 대기 쓰기 후에 당신은 마이크로 최적화에 대한 걱정에 프로파일했습니다.
재밌어요 어떻게 Sum(this IEnumerable<TSource> source, Func<TSource, int> selector)정의되어 있는지 아십니까 ? 방법을 사용 Select합니다!
public static int Sum<TSource>(this IEnumerable<TSource> source, Func<TSource, int> selector)
{
return source.Select(selector).Sum();
}
실제로 모든 것이 거의 동일하게 작동해야합니다. 나는 내 자신에 대한 빠른 연구를했으며 그 결과는 다음과 같습니다.
Where -- mod: 1 result: 0, time: 371 ms
WhereSelect -- mod: 1 result: 0, time: 356 ms
Select -- mod: 1 result 0, time: 366 ms
Sum -- mod: 1 result: 0, time: 363 ms
-------------
Where -- mod: 2 result: 4999999, time: 469 ms
WhereSelect -- mod: 2 result: 4999999, time: 429 ms
Select -- mod: 2 result 4999999, time: 362 ms
Sum -- mod: 2 result: 4999999, time: 358 ms
-------------
Where -- mod: 3 result: 9999999, time: 441 ms
WhereSelect -- mod: 3 result: 9999999, time: 452 ms
Select -- mod: 3 result 9999999, time: 371 ms
Sum -- mod: 3 result: 9999999, time: 380 ms
-------------
Where -- mod: 4 result: 7500000, time: 571 ms
WhereSelect -- mod: 4 result: 7500000, time: 501 ms
Select -- mod: 4 result 7500000, time: 406 ms
Sum -- mod: 4 result: 7500000, time: 397 ms
-------------
Where -- mod: 5 result: 7999999, time: 490 ms
WhereSelect -- mod: 5 result: 7999999, time: 477 ms
Select -- mod: 5 result 7999999, time: 397 ms
Sum -- mod: 5 result: 7999999, time: 394 ms
-------------
Where -- mod: 6 result: 9999999, time: 488 ms
WhereSelect -- mod: 6 result: 9999999, time: 480 ms
Select -- mod: 6 result 9999999, time: 391 ms
Sum -- mod: 6 result: 9999999, time: 387 ms
-------------
Where -- mod: 7 result: 8571428, time: 489 ms
WhereSelect -- mod: 7 result: 8571428, time: 486 ms
Select -- mod: 7 result 8571428, time: 384 ms
Sum -- mod: 7 result: 8571428, time: 381 ms
-------------
Where -- mod: 8 result: 8749999, time: 494 ms
WhereSelect -- mod: 8 result: 8749999, time: 488 ms
Select -- mod: 8 result 8749999, time: 386 ms
Sum -- mod: 8 result: 8749999, time: 373 ms
-------------
Where -- mod: 9 result: 9999999, time: 497 ms
WhereSelect -- mod: 9 result: 9999999, time: 494 ms
Select -- mod: 9 result 9999999, time: 386 ms
Sum -- mod: 9 result: 9999999, time: 371 ms
다음 구현의 경우 :
result = source.Where(x => x.IsValid).Sum(x => x.Value);
result = source.Select(x => x.IsValid ? x.Value : 0).Sum();
result = source.Sum(x => x.IsValid ? x.Value : 0);
result = source.Where(x => x.IsValid).Select(x => x.Value).Sum();
mod의미 : mod항목의 1마다 유효하지 않음 : mod == 1모든 항목에 대해 유효하지 mod == 2않거나 홀수 항목에 대해 유효하지 않음 등. 콜렉션에 10000000항목이 포함되어 있습니다.
그리고 100000000아이템 으로 수집 한 결과 :
당신이 볼 수 있듯이, Select및 Sum결과 모두에서 매우 일관된 mod값. 그러나 where및 where+ select하지 않습니다.
내 생각에 Where가있는 버전은 0을 필터링하고 Sum의 주제가 아닙니다 (즉, 추가를 실행하지 않음). 추가 람다 식을 실행하고 여러 메서드를 호출하면 단순한 0을 추가하는 방법을 설명 할 수 없기 때문에 이것은 물론 추측입니다.
내 친구는 합계의 0이 오버플로 검사로 인해 심각한 성능 저하를 초래할 수 있다고 제안했습니다. 확인되지 않은 컨텍스트에서 이것이 어떻게 수행되는지 보는 것이 흥미로울 것입니다.
다음 샘플을 실행하면 Select +를 능가 할 수있는 유일한 시점이 실제로 목록에있는 잠재적 인 항목에 대해 충분한 양 (비공식 테스트에서 약 절반)을 버릴 때만 선택됩니다. 아래의 작은 예에서, Where가 10mil에서 약 4mil 항목을 건너 뛸 때 두 샘플에서 대략 같은 숫자를 얻습니다. 릴리스에서 실행하고 where + select vs select 실행을 동일한 결과로 다시 정렬했습니다.
static void Main(string[] args)
{
int total = 10000000;
Random r = new Random();
var list = Enumerable.Range(0, total).Select(i => r.Next(0, 5)).ToList();
for (int i = 0; i < 4000000; i++)
list[i] = 10;
var sw = new Stopwatch();
sw.Start();
int sum = 0;
sum = list.Where(i => i < 10).Select(i => i).Sum();
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
sw.Reset();
sw.Start();
sum = list.Select(i => i).Sum();
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);
}
속도가 필요한 경우 간단한 루프를 수행하는 것이 가장 좋습니다. 그리고 수행 for하는 것이보다 좋습니다 foreach(컬렉션이 무작위 액세스라고 가정).
다음은 10 %의 요소가 유효하지 않은 타이밍입니다.
Where + Select + Sum: 257
Select + Sum: 253
foreach: 111
for: 61
그리고 90 % 유효하지 않은 요소 :
Where + Select + Sum: 177
Select + Sum: 247
foreach: 105
for: 58
그리고 여기 내 벤치 마크 코드가 있습니다 ...
public class MyClass {
public int Value { get; set; }
public bool IsValid { get; set; }
}
class Program {
static void Main(string[] args) {
const int count = 10000000;
const int percentageInvalid = 90;
var rnd = new Random();
var myCollection = new List<MyClass>(count);
for (int i = 0; i < count; ++i) {
myCollection.Add(
new MyClass {
Value = rnd.Next(0, 50),
IsValid = rnd.Next(0, 100) > percentageInvalid
}
);
}
var sw = new Stopwatch();
sw.Restart();
int result1 = myCollection.Where(mc => mc.IsValid).Select(mc => mc.Value).Sum();
sw.Stop();
Console.WriteLine("Where + Select + Sum:\t{0}", sw.ElapsedMilliseconds);
sw.Restart();
int result2 = myCollection.Select(mc => mc.IsValid ? mc.Value : 0).Sum();
sw.Stop();
Console.WriteLine("Select + Sum:\t\t{0}", sw.ElapsedMilliseconds);
Debug.Assert(result1 == result2);
sw.Restart();
int result3 = 0;
foreach (var mc in myCollection) {
if (mc.IsValid)
result3 += mc.Value;
}
sw.Stop();
Console.WriteLine("foreach:\t\t{0}", sw.ElapsedMilliseconds);
Debug.Assert(result1 == result3);
sw.Restart();
int result4 = 0;
for (int i = 0; i < myCollection.Count; ++i) {
var mc = myCollection[i];
if (mc.IsValid)
result4 += mc.Value;
}
sw.Stop();
Console.WriteLine("for:\t\t\t{0}", sw.ElapsedMilliseconds);
Debug.Assert(result1 == result4);
}
}
BTW, 나는 Stilgar의 추측에 동의합니다 : 두 경우의 상대 속도는 유효하지 않은 항목의 비율에 따라 달라집니다. 단순히 Sum필요한 작업량이 "Where"사례에서 다양 하기 때문 입니다.
설명을 통해 설명하려고하기보다는 좀 더 수학적 접근을하겠습니다.
아래 코드에서 LINQ가 내부적으로 수행하는 작업을 근사화해야하는 상대 비용은 다음과 같습니다.
선택 만 : Nd + Na
Where + Select :Nd + Md + Ma
그들이 교차하는 지점을 파악하려면 약간의 대수를해야합니다. Nd + Md + Ma = Nd + Na => M(d + a) = Na => (M/N) = a/(d+a)
이것이 의미하는 바는 변곡점이 50 %가 되려면 델리게이트 호출 비용이 추가 비용과 거의 같아야한다는 것입니다. 실제 변곡점이 약 60 %임을 알고 있으므로 @ It'sNotALie에 대한 델리게이트 호출 비용이 실제로 추가 비용의 약 2/3에 불과하다는 것을 알 수 있습니다. 그의 숫자는 말합니다.
static void Main(string[] args)
{
var set = Enumerable.Range(1, 10000000)
.Select(i => new MyClass {Value = i, IsValid = i%2 == 0})
.ToList();
Func<MyClass, int> select = i => i.IsValid ? i.Value : 0;
Console.WriteLine(
Sum( // Cost: N additions
Select(set, select))); // Cost: N delegate
// Total cost: N * (delegate + addition) = Nd + Na
Func<MyClass, bool> where = i => i.IsValid;
Func<MyClass, int> wSelect = i => i.Value;
Console.WriteLine(
Sum( // Cost: M additions
Select( // Cost: M delegate
Where(set, where), // Cost: N delegate
wSelect)));
// Total cost: N * delegate + M * (delegate + addition) = Nd + Md + Ma
}
// Cost: N delegate calls
static IEnumerable<T> Where<T>(IEnumerable<T> set, Func<T, bool> predicate)
{
foreach (var mc in set)
{
if (predicate(mc))
{
yield return mc;
}
}
}
// Cost: N delegate calls
static IEnumerable<int> Select<T>(IEnumerable<T> set, Func<T, int> selector)
{
foreach (var mc in set)
{
yield return selector(mc);
}
}
// Cost: N additions
static int Sum(IEnumerable<int> set)
{
unchecked
{
var sum = 0;
foreach (var i in set)
{
sum += i;
}
return sum;
}
}
MarcinJuraszek의 결과가 It'sNotALie와 다른 점이 흥미 롭습니다. 특히 MarcinJuraszek의 결과는 4 개의 모든 구현에서 동일한 위치에서 시작하는 반면, Not'Alie의 결과는 중간에 걸쳐 교차합니다. 소스에서 어떻게 작동하는지 설명하겠습니다.
n총 요소와 m유효한 요소 가 있다고 가정합시다 .
이 Sum기능은 매우 간단합니다. 그것은 열거자를 통해 반복됩니다 : http://typedescriptor.net/browse/members/367300-System.Linq.Enumerable.Sum(IEnumerable%601)
간단하게하기 위해 컬렉션이 목록이라고 가정 해 봅시다. Select 와 WhereSelect 는 모두 를 만듭니다 WhereSelectListIterator. 이는 생성 된 실제 반복자가 동일 함을 의미합니다. 두 경우 모두 Sum반복자 위에 루프가 WhereSelectListIterator있습니다. 반복자의 가장 흥미로운 부분은 MoveNext 메소드입니다.
반복자가 동일하기 때문에 루프는 동일합니다. 유일한 차이점은 루프 본문에 있습니다.
이 람다의 몸은 매우 비슷한 비용이 있습니다. where 절은 필드 값을 반환하고 삼항 술어도 필드 값을 반환합니다. select 절은 필드 값을 반환하고 삼항 연산자의 두 분기는 필드 값 또는 상수를 반환합니다. 결합 된 select 절은 분기를 삼항 연산자로 가지지 만 WhereSelect는의 분기를 사용합니다 MoveNext.
그러나 이러한 모든 작업은 상당히 저렴합니다. 지금까지 가장 비싼 작업은 잘못된 예측으로 인해 비용이 발생하는 지점입니다.
여기서 또 다른 비싼 작업은 Invoke입니다. 브랑코 디미트리 예비치 (Branko Dimitrijevic)가 보여 주듯이, 함수를 호출하는 것은 값을 추가하는 것보다 시간이 조금 더 걸립니다.
또한 무게 측정은의 누적 누적입니다 Sum. 프로세서에 산술 오버플로 플래그가 없으면 검사 비용이 많이들 수 있습니다.
따라서 흥미로운 비용은 다음과 같습니다.
- (
n+m) * 호출 +m*checked+= n* 호출 +n*checked+=
따라서 Invoke 비용이 확인 된 누적 비용보다 훨씬 높으면 사례 2가 항상 좋습니다. 그것들이 짝수라면 요소의 약 절반이 유효 할 때 균형을 볼 것입니다.
MarcinJuraszek의 시스템처럼, checked + =는 무시할만한 비용이 있지만 It'sNotALie와 Branko Dimitrijevic의 시스템에서 checked + =는 상당한 비용이 듭니다. It'sNotALie의 시스템에서 가장 비싼 것처럼 보이며 중단 점도 훨씬 높습니다. 누적 비용이 호출보다 훨씬 많은 시스템에서 결과를 게시 한 것처럼 보이지 않습니다.
참고 URL : https://stackoverflow.com/questions/18331774/why-are-where-and-select-outperforming-just-select
'IT' 카테고리의 다른 글
| 귀하의 구성은 (0) | 2020.06.16 |
|---|---|
| IIS7 : HTTP-> HTTPS 정리 (0) | 2020.06.16 |
| Git이“블록 체인”으로 간주되지 않는 이유는 무엇입니까? (0) | 2020.06.16 |
| HTTP로 POST 메소드를 캐시 할 수 있습니까? (0) | 2020.06.16 |
| 자바 스크립트 이벤트를 마우스 오른쪽 버튼으로 클릭합니까? (0) | 2020.06.16 |