컬렉션에 저장된 원소의 정렬되지 않은 쌍을 반복합니다.

Question

C#에서는 고유 한 요소 모음이 있고 각 정렬되지 않은 쌍의 코드를 효율적으로 실행하려고합니다. 예를 들어, 컨테이너가 {a, b, c}를 보유하고 있으면, 순서가없는 쌍은 (a, b), (a, c) 및 (b, c)입니다. 문제는 2-opt 최적화를 수행하는 범위에서 발생하므로 효율성이 문제입니다. 마찬가지로

• 나의 현재 용액 같다 : 분명히

  foreach(var a in container) 
  { 
      foreach(var b in container) 
      { 
       if (a < b) 
       { 
        // execute code  
       } 
      } 
  } 
  

  , 이것은 용이하게 변형 될 수있는 연산자 []는 (i 번째 요소를 얻기 위해 사용할 수있는 경우, 즉 기본 데이터 구조가 인 경우 그러나 다른 모든 컨테이너의 경우 솔루션은 일부 비교 함수의 존재에 의존하며 그다지 효율적이지 않습니다.

• 각 희망 쌍을 정확히 한 번 생성하는 LINQ 문을 기반으로 한 공식을 시도했습니다. 그러나 예상대로 첫 번째 방법보다 훨씬 느립니다. 이것은 ElementAt을 사용하는 솔루션에도 적용됩니다.

편집 :

var x = from a in container 
     from b in container 
     where a < b 
     select new KeyValuePair<int,int>(a,b); 

여전히 실행 다른 솔루션에 비해 3-5 배 정도 느린 여기 사용 된 (개) LINQ 코드이다. 여기

• 는 ++ (좋은 효율을 얻기) 나는 C에서 그것을 할 것이 방법입니다 : Unfortunatelly

  for(auto it1 = container.begin(); it1!=container.end(); ++it1) 
  { 
      auto it2 = it1; 
      for(++it2; it2!=container.end(); ++it2) 
      { 
       // execute code  
      } 
  } 
  

  , C 번호로이를 변환하는, (내부적으로 사용) 에뮬레이터를 복제하는 데 필요한 것 이는 언어 자체에서 지원되지 않습니다.

더 좋은 아이디어/해결책이 있습니까?

Answer 1

요소를 목록에 먼저 복사 한 다음 인덱서 ([i]) 연산자를 사용하여 알고리즘을 수행하려고 했습니까?알고리즘은 2 차 런타임을 가지고 있기 때문에 그 앞에서 선형 복사 작업을하는 것은 무시할 수 있습니다. 당신은 작은, 중간 및 대형 컨테이너에 대한 실제 런타임을 찾아야 할 것입니다 ...

나는 이것이 가치가 있을지도 모른다고 생각한다. 이것은 매번 비교 연산자로 작업하는 것보다 훨씬 빠르다.

또한 컨테이너의 유형이 IList<T>인지 확인하고 복사 작업을 뛰어 넘을 수 있습니다. 당신이 순서를 신경 쓰지 않는 경우

Answer 2

C#의 열거자는 사용자의 C++ 열거 자와 동일하지 않습니다. C#에서는 begin도 아니고 end 컨테이너 요소도 없습니다. Current 요소와 Next() 메소드 만 있습니다. 예를 들어 무한 시퀀스의 무작위 수를 열거 할 수 있습니다. 무작위 수는 분명히 시작이나 끝이 아닙니다.

그래서 C# 코드에서 IEnumerable 클래스 만 사용하면 C# 코드에서와 같이 할 수 없습니다. 가장 좋은 방법은 System.Collection.Generics.IList<T> 인터페이스를 사용하는 것입니다. 배열과 같은 많은 유형은이 인터페이스를 상속합니다.

IEnumerable을 사용하는 경우 유형 내에서 (대부분의 경우) 일부 컬렉션을 반복합니다. 이렇게하면 - 그냥 IList<T> 인터페이스를 구현할 수 있습니다.

다른 해결책이 있습니다 - C# 목록 및 참조 유형의 배열에는 객체에 대한 참조 만 포함됩니다. 따라서 데이터를 로컬 목록에 복사하고 함께 사용할 수 있습니다. 그러나 그것은 귀하의 메모리 및 성능 요구 사항에 따라 다릅니다.

Answer 3

, 당신은 이런 식으로 작업을 수행 할 수 있습니다 : 당신이 순서에 관심 않으면

int i = 0; 
foreach (var a in list) 
{ 
    int j = 0; 
    foreach (var b in list) 
    { 
     if (i <= j) 
      break; 

     // execute code  

     j++; 
    } 

    i++; 
} 

, 당신은 []를 포함하는, IList<T>를 구현하는 컬렉션에 자신을 제한 할 수 있습니다 운영자. 또는 먼저 컬렉션을 List<T>에 복사 한 다음 작업하십시오.

Answer 4

목록 또는 IList에 항목을 넣은 다음 C++ 코드와 매우 유사한 패턴으로 색인을 사용하여 항목에 액세스 할 수 있습니다.

for (int i = 0; i < container.Count(); i++) 
for (int j = i+1; j < container.Count(); j++) 
{ 
    var item1 = container.Item[i]; 
    var item2 = container.Item[j]; 
} 

나는 n^2 비교보다는 인덱스를 사용하여 순서가 지정된 컬렉션을 반복하는 것이 더 효율적일 것으로 기대합니다. 비교 연산자의 효율성은 중요하지만 전혀 비교할 필요가 없습니다.