다차원 배열보다 들쭉날쭉한 배열을 선호하십시오

Question

Visual Studio (Prefer jagged arrays over multidimensional)에서 성능 문제가 발생합니다.
바꿀 코드는 "// 매트릭스"입니다.
내 코드로 어떻게 할 수 있습니까?

 public static int LevenshteinDistance(string s, string t) 
    { 
     int n = s.Length; //length of s 
     int m = t.Length; //length of t 

     int[,] d = new int[n + 1, m + 1]; // matrix 

     int cost; // cost 
     // Step 1 
     if (n == 0) return m; 
     if (m == 0) return n; 
     // Step 2 
     for (int i = 0; i <= n; d[i, 0] = i++) ; 
     for (int j = 0; j <= m; d[0, j] = j++) ; 
     // Step 3 
     for (int i = 1; i <= n; i++) 
     { 
      //Step 4 
      for (int j = 1; j <= m; j++) 
      { 
       // Step 5 
       cost = (t.Substring(j - 1, 1) == s.Substring(i - 1, 1) ? 0 : 1); 
       // Step 6 
       d[i, j] = System.Math.Min(System.Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1), 
          d[i - 1, j - 1] + cost); 
      } 
     } 
     // Step 7 
     return d[n, m]; 
    } 

Answer 1

다음은 1 차원 배열 만 사용하는 버전입니다.

public static int LevenshteinDistance(string s, string t) 
{ 
    int n = s.Length; //length of s 
    int m = t.Length; //length of t 

    int stride = m+1; 
    int[] d = new int[(n + 1)*stride]; 
    // note, d[i*m + i + j] holds (i,j) 

    int cost; 
    // Step 1 
    if (n == 0) return m; 
    if (m == 0) return n; 
    // Step 2, adjusted to skip (0,0) 
    for (int i = 0, k = stride; k < d.Length; k += stride) d[k] = ++i; 
    for (int j = 1; j < stride; ++j) d[j] = j; 
    // Step 3 
    int newrow = stride * 2; 
    char si = s[0]; 
    for (int i=0, j=0, k = stride + 1; k < d.Length; ++k) 
    { 
     // don't overwrite d[i,0] 
     if (k == newrow) { 
      newrow += stride; 
      j=0; 
      si=s[++i]; 
      continue; 
     } 

     // Step 5 
     cost = (t[j] == si ? 0 : 1); 

     // Step 6 
     d[k] = System.Math.Min(System.Math.Min(
      d[k-stride] + 1, /* up one row */ 
      d[k-1] + 1  /* left one */ ), 
      d[k-stride-1] + cost /* diagonal */); 
    } 

    // Step 7 
    return d[d.Length-1]; 
} 

이 성능을 3 가지 방법 개선해야 캐시 동작을 개선, 반복 순서와 일치하는

변경된 메모리 레이아웃을 정리하는

• 없음 문자열 비교와 GC에 아무도 - 문자열의 쓰레기를
• 경계 검사를 줄여야하는 단일 차원 배열 및 최적화 프로그램에 익숙한 관용구

그러나 두 개의 벡터를 사용하는 mike z의 제안을 적용하면 훨씬 명확한 코드를 작성할 수있을 것입니다.