Darkest page of my coding life
44061 단어 life
1 static int BadMaximalMatch(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
2 const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2)
3 {
4 if (count1 <= 0 || count2 <= 0)
5 {
6 return 0;
7 }
8
9 bool eq = comparer.Equals(list1[start1], list2[start2]);
10 if (eq)
11 {
12 indices1.Add(start1);
13 indices2.Add(start2);
14
15 return BadMaximalMatch(list1, start1+1, count1-1, list2, start2+1, count2-1, comparer, indices1, indices2) + 1;
16 }
17 else
18 {
19 bool eq01 = count2 >= 2 && comparer.Equals(list1[start1], list2[start2+1]);
20 bool eq10 = count1 >= 2 && comparer.Equals(list1[start1+1], list2[start2]);
21
22 int crossDiff;
23 if (eq01 && eq10)
24 {
25 crossDiff = 1;
26 }
27 else if (eq01 && !eq10)
28 {
29 return BadMaximalMatch(list1, start1, count1, list2, start2+1, count2-1, comparer, indices1, indices2);
30 }
31 else if (!eq01 && eq10)
32 {
33 return BadMaximalMatch(list1, start1+1, count1-1, list2, start2, count2, comparer, indices1, indices2);
34 }
35 else
36 {
37 bool eq11 = count1 >= 2 && count2 >= 2 && comparer.Equals(list1[start1+1], list2[start2+1]);
38 if (eq11)
39 {
40 indices1.Add(start1+1);
41 indices2.Add(start2+1);
42 return BadMaximalMatch(list1, start1+2, count1-2, list2, start2+2, count2-2, comparer, indices1, indices2)+1;
43 }
44 crossDiff = 2;
45 }
46
47 List<int> temp11, temp12, temp21, temp22;
48 int m1 = 0, m2 = 0;
49 if (count1 < count2)
50 {
51 // calculate m1 first, as maximum of m1 is greater than that of m2
52 // maximum: min(count1, count2-crossDiff)
53 m1 = BadMaximalMatch(list1, start1, count1, list2, start2+crossDiff, count2-crossDiff, comparer, temp11, temp12);
54 if (m1 < count1 && m1 < count2-crossDiff)
55 {
56 // m1 hasn't reached its maximum possible value
57 // maximum: min(count1-crossDiff, count2)
58 m2 = BadMaximalMatch(list1, start1+crossDiff, count1-crossDiff, list2, start2, count2, comparer, temp21, temp22);
59 }
60 }
61 else
62 {
63 // calculate m2 first, as maximum of m2 is greater than that of m1
64 m2 = BadMaximalMatch(list1, start1+crossDiff, count1-crossDiff, list2, start2, count2, comparer, temp21, temp22);
65 if (m2 < count2 && m2 < count1-crossDiff)
66 {
67 // m2 hasn't reached its maximum possible value
68 // maximum: min(count1, count2-crossDiff)
69 m1 = BadMaximalMatch(list1, start1, count1, list2, start2+crossDiff, count2-crossDiff, comparer, temp11, temp12);
70 }
71 }
72
73 if (m2 > m1)
74 {
75 for (int i = 0; i < m2; i++)
76 {
77 indices1.Add(temp21[i]);
78 indices2.Add(temp22[i]);
79 }
80 return m2;
81 }
82 else
83 {
84 for (int i = 0; i < m1; i++)
85 {
86 indices1.Add(temp11[i]);
87 indices2.Add(temp12[i]);
88 }
89 return m1;
90 }
91 }
92 }It simply finds out the maximum common sublist of two. And I was dumb enough to not realize it was a very simple problem and be spending quite a while on a complex recursive algorithm as above to solve that. So far there's no evidence it's buggy, but it's as bad as buggy when dealing with just more than 20 data points. A random test today showed that the code above is problematic in that it doesn't take into account some of the possible options that goes across the one that it believes is optimal. Basically the algorithm should only step forward when the current item from either list has no match in the other. So the correct one should be
1 static int MaximalSublistMatch_Slow(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
2 const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2)
3 {
4 if (count1 <= 0 || count2 <= 0)
5 {
6 return 0;
7 }
8
9 bool eq = comparer.Equals(list1[start1], list2[start2]);
10 if (eq)
11 {
12 indices1.Add(start1);
13 indices2.Add(start2);
14
15 return MaximalSublistMatch_Slow(list1, start1 + 1, count1 - 1, list2, start2 + 1, count2 - 1, comparer, indices1, indices2) + 1;
16 }
17 else
18 {
19 const T &v1 = list1[start1];
20 const T &v2 = list2[start2];
21
22 int l1Match=-1, l2Match=-1;
23 for (int i = start2 + 1; i < start2+count2; i++)
24 {
25 if (list2[i] == v1)
26 {
27 l1Match = i;
28 break;
29 }
30 }
31
32 for (int i = start1 + 1; i < start1+count1; i++)
33 {
34 if (list1[i] == v2)
35 {
36 l2Match = i;
37 break;
38 }
39 }
40
41 if (l1Match < 0 && l2Match < 0)
42 {
43 return MaximalSublistMatch_Slow(list1, start1 + 1, count1 - 1, list2, start2 + 1, count2 - 1, comparer, indices1, indices2);
44 }
45 else
46 {
47 // try both
48 List<int> temp11, temp12, temp21, temp22;
49 int r2 = 0;
50 int r1 = MaximalSublistMatch_Slow(list1, start1, count1, list2, start2 + 1, count2 - 1, comparer, temp11, temp12);
51 if (r1 < std::min(count1 - 1, count2))
52 {
53 r2 = MaximalSublistMatch_Slow(list1, start1 + 1, count1 - 1, list2, start2, count2, comparer, temp21, temp22);
54 }
55 if (r1 < r2)
56 {
57 for (int i = 0; i < r2; i++)
58 {
59 indices1.Add(temp21[i]);
60 indices2.Add(temp22[i]);
61 }
62 return r2;
63 }
64 else
65 {
66 for (int i = 0; i < r1; i++)
67 {
68 indices1.Add(temp11[i]);
69 indices2.Add(temp12[i]);
70 }
71 return r1;
72 }
73 }
74 }
75 }A simpler version naive alternative (not equivalent, but ok for most use; and minor change to it can improve accuracy not so sure of what significance this method can be, with a fast optimum approach found available) is
It's equivalent is,
1 // this is a version of maximal match with a complexity of O(N)
2 static int MaximalMatch(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
3 const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2)
4 {
5 int matchStart2 = start2;
6 for (int i1 = start1; i1 < start1 + count1; i1++)
7 {
8 const T &v1 = list1[i1];
9 for (int i2 = matchStart2; i2 < start2 + count2; i2++)
10 {
11 const T &v2 = list2[i2];
12 if (comparer.Equals(v1,v2))
13 {
14 indices1.Add(i1);
15 indices2.Add(i2);
16 matchStart2 = i2+1;
17 break;
18 }
19 }
20 }
21 return indices1.GetCount();
22 }Of course this is is epically faster, simpler and less error-prone than the previous one. but it doesn't provide the optimal result.You can imagine how an application would suffer from the exp(N)-complexity shit.
The fast equivalent should be using dynamic programming and go as follows
(The standard C# version has been updated to the QSharp library at https://qsharp.codeplex.com/SourceControl/latest#QSharp/QSharp.Scheme.Classical.Sequential/MaxSublistMatch.cs )
1 struct MaxMatchDPResult
2 {
3 bool Done;
4 List<int> Indices1;
5 List<int> Indices2;
6 };
7
8
9 // FB: 6462
10 // NOTE this is a version of maximal match using dynamic programming
11 // it has a time complexity of around O(N*N) and space complexity of about O(N^4)
12 // This is a recommended version as it provides optimal result and is fast
13 static int MaximalSublistMatch_DP(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
14 const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2)
15 {
16 int maxSofar = 0;
17 std::vector<std::vector<MaxMatchDPResult>> map;
18 for (int i = 0; i < count1+1; i++)
19 {
20 map.push_back(std::vector<MaxMatchDPResult>());
21 for (int j = 0; j < count2+1; j++)
22 {
23 map[i].push_back(MaxMatchDPResult());
24 map[i][j].Done = false;
25 }
26 }
27 return MaximalSublistMatch_DP(list1, start1, count1, list2, start2, count2, comparer, indices1, indices2, map);
28 }
29
30 static int MaximalSublistMatch_DP_Lookup(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
31 const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2, std::vector <std::vector<MaxMatchDPResult>> &map)
32 {
33 if (count1 <= 0 || count2 <= 0)
34 {
35 return 0;
36 }
37 const MaxMatchDPResult &result = map[count1][count2];
38 int r;
39 if (result.Done)
40 {
41 r = result.Indices1.GetCount();
42 for (int i = 0; i < r; i++)
43 {
44 indices1.Add(result.Indices1[i]);
45 indices2.Add(result.Indices2[i]);
46 }
47 }
48 else
49 {
50 List<int> tempIndices1, tempIndices2;
51 r = MaximalSublistMatch_DP(list1, start1, count1, list2, start2, count2, comparer, tempIndices1, tempIndices2, map);
52 map[count1][count2].Done = true;
53 map[count1][count2].Indices1 = tempIndices1;
54 map[count1][count2].Indices2 = tempIndices2;
55 for (int i = 0; i < r; i++)
56 {
57 indices1.Add(tempIndices1[i]);
58 indices2.Add(tempIndices2[i]);
59 }
60 }
61 return r;
62 }
63
64 static int MaximalSublistMatch_DP(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
65 const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2, std::vector<std::vector<MaxMatchDPResult>> &map)
66 {
67 bool eq = comparer.Equals(list1[start1], list2[start2]);
68 if (eq)
69 {
70 indices1.Add(start1);
71 indices2.Add(start2);
72 int r = MaximalSublistMatch_DP_Lookup(list1, start1 + 1, count1 - 1, list2, start2 + 1, count2 - 1, comparer, indices1, indices2, map) + 1;
73 return r;
74 }
75
76 List<int> temp11, temp12, temp21, temp22;
77 int r2 = 0;
78 int r1 = MaximalSublistMatch_DP_Lookup(list1, start1, count1, list2, start2 + 1, count2 - 1, comparer, temp11, temp12, map);
79 if (r1 <
80 #if defined(min)
81 min(count1 - 1, count2)
82 #else
83 std::min(count1 - 1, count2)
84 #endif
85 )
86 {
87 r2 = MaximalSublistMatch_DP_Lookup(list1, start1 + 1, count1 - 1, list2, start2, count2, comparer, temp21, temp22, map);
88 }
89 if (r2 > r1)
90 {
91 for (int i = 0; i < r2; i++)
92 {
93 indices1.Add(temp21[i]);
94 indices2.Add(temp22[i]);
95 }
96 return r2;
97 }
98 else
99 {
100 for (int i = 0; i < r1; i++)
101 {
102 indices1.Add(temp11[i]);
103 indices2.Add(temp12[i]);
104 }
105 return r1;
106 }
107 }This was stupid, but classic!
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
우선 순위 및 생산성 향상 방법“However beautiful the strategy, you should occasionally look at the results.” 생산성에 대해 이야기할 때 많은 작업을 수행하는 것과 결과를 생성하는 것 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
