The code i wrote a while ago recently caused a disaster and as I reviewed it I found it is the silliest code I’ve ever written,
static int BadMaximalMatch(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2)
{
if (count1 <= || count2 <= )
{
return ;
} bool eq = comparer.Equals(list1[start1], list2[start2]);
if (eq)
{
indices1.Add(start1);
indices2.Add(start2); return BadMaximalMatch(list1, start1+, count1-, list2, start2+, count2-, comparer, indices1, indices2) + ;
}
else
{
bool eq01 = count2 >= && comparer.Equals(list1[start1], list2[start2+]);
bool eq10 = count1 >= && comparer.Equals(list1[start1+], list2[start2]); int crossDiff;
if (eq01 && eq10)
{
crossDiff = ;
}
else if (eq01 && !eq10)
{
return BadMaximalMatch(list1, start1, count1, list2, start2+, count2-, comparer, indices1, indices2);
}
else if (!eq01 && eq10)
{
return BadMaximalMatch(list1, start1+, count1-, list2, start2, count2, comparer, indices1, indices2);
}
else
{
bool eq11 = count1 >= && count2 >= && comparer.Equals(list1[start1+], list2[start2+]);
if (eq11)
{
indices1.Add(start1+);
indices2.Add(start2+);
return BadMaximalMatch(list1, start1+, count1-, list2, start2+, count2-, comparer, indices1, indices2)+;
}
crossDiff = ;
} List<int> temp11, temp12, temp21, temp22;
int m1 = , m2 = ;
if (count1 < count2)
{
// calculate m1 first, as maximum of m1 is greater than that of m2
// maximum: min(count1, count2-crossDiff)
m1 = BadMaximalMatch(list1, start1, count1, list2, start2+crossDiff, count2-crossDiff, comparer, temp11, temp12);
if (m1 < count1 && m1 < count2-crossDiff)
{
// m1 hasn't reached its maximum possible value
// maximum: min(count1-crossDiff, count2)
m2 = BadMaximalMatch(list1, start1+crossDiff, count1-crossDiff, list2, start2, count2, comparer, temp21, temp22);
}
}
else
{
// calculate m2 first, as maximum of m2 is greater than that of m1
m2 = BadMaximalMatch(list1, start1+crossDiff, count1-crossDiff, list2, start2, count2, comparer, temp21, temp22);
if (m2 < count2 && m2 < count1-crossDiff)
{
// m2 hasn't reached its maximum possible value
// maximum: min(count1, count2-crossDiff)
m1 = BadMaximalMatch(list1, start1, count1, list2, start2+crossDiff, count2-crossDiff, comparer, temp11, temp12);
}
} if (m2 > m1)
{
for (int i = ; i < m2; i++)
{
indices1.Add(temp21[i]);
indices2.Add(temp22[i]);
}
return m2;
}
else
{
for (int i = ; i < m1; i++)
{
indices1.Add(temp11[i]);
indices2.Add(temp12[i]);
}
return m1;
}
}
}
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
static int MaximalSublistMatch_Slow(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2)
{
if (count1 <= || count2 <= )
{
return ;
} bool eq = comparer.Equals(list1[start1], list2[start2]);
if (eq)
{
indices1.Add(start1);
indices2.Add(start2); return MaximalSublistMatch_Slow(list1, start1 + , count1 - , list2, start2 + , count2 - , comparer, indices1, indices2) + ;
}
else
{
const T &v1 = list1[start1];
const T &v2 = list2[start2]; int l1Match=-, l2Match=-;
for (int i = start2 + ; i < start2+count2; i++)
{
if (list2[i] == v1)
{
l1Match = i;
break;
}
} for (int i = start1 + ; i < start1+count1; i++)
{
if (list1[i] == v2)
{
l2Match = i;
break;
}
} if (l1Match < && l2Match < )
{
return MaximalSublistMatch_Slow(list1, start1 + , count1 - , list2, start2 + , count2 - , comparer, indices1, indices2);
}
else
{
// try both
List<int> temp11, temp12, temp21, temp22;
int r2 = ;
int r1 = MaximalSublistMatch_Slow(list1, start1, count1, list2, start2 + , count2 - , comparer, temp11, temp12);
if (r1 < std::min(count1 - , count2))
{
r2 = MaximalSublistMatch_Slow(list1, start1 + , count1 - , list2, start2, count2, comparer, temp21, temp22);
}
if (r1 < r2)
{
for (int i = ; i < r2; i++)
{
indices1.Add(temp21[i]);
indices2.Add(temp22[i]);
}
return r2;
}
else
{
for (int i = ; i < r1; i++)
{
indices1.Add(temp11[i]);
indices2.Add(temp12[i]);
}
return r1;
}
}
}
}
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,
// this is a version of maximal match with a complexity of O(N)
static int MaximalMatch(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2)
{
int matchStart2 = start2;
for (int i1 = start1; i1 < start1 + count1; i1++)
{
const T &v1 = list1[i1];
for (int i2 = matchStart2; i2 < start2 + count2; i2++)
{
const T &v2 = list2[i2];
if (comparer.Equals(v1,v2))
{
indices1.Add(i1);
indices2.Add(i2);
matchStart2 = i2+;
break;
}
}
}
return indices1.GetCount();
}
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)
struct MaxMatchDPResult
{
bool Done;
List<int> Indices1;
List<int> Indices2;
}; // FB: 6462
// NOTE this is a version of maximal match using dynamic programming
// it has a time complexity of around O(N*N) and space complexity of about O(N^4)
// This is a recommended version as it provides optimal result and is fast
static int MaximalSublistMatch_DP(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2)
{
int maxSofar = ;
std::vector<std::vector<MaxMatchDPResult>> map;
for (int i = ; i < count1+; i++)
{
map.push_back(std::vector<MaxMatchDPResult>());
for (int j = ; j < count2+; j++)
{
map[i].push_back(MaxMatchDPResult());
map[i][j].Done = false;
}
}
return MaximalSublistMatch_DP(list1, start1, count1, list2, start2, count2, comparer, indices1, indices2, map);
} static int MaximalSublistMatch_DP_Lookup(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2, std::vector <std::vector<MaxMatchDPResult>> &map)
{
if (count1 <= || count2 <= )
{
return ;
}
const MaxMatchDPResult &result = map[count1][count2];
int r;
if (result.Done)
{
r = result.Indices1.GetCount();
for (int i = ; i < r; i++)
{
indices1.Add(result.Indices1[i]);
indices2.Add(result.Indices2[i]);
}
}
else
{
List<int> tempIndices1, tempIndices2;
r = MaximalSublistMatch_DP(list1, start1, count1, list2, start2, count2, comparer, tempIndices1, tempIndices2, map);
map[count1][count2].Done = true;
map[count1][count2].Indices1 = tempIndices1;
map[count1][count2].Indices2 = tempIndices2;
for (int i = ; i < r; i++)
{
indices1.Add(tempIndices1[i]);
indices2.Add(tempIndices2[i]);
}
}
return r;
} static int MaximalSublistMatch_DP(TListRef list1, int start1, int count1, TListRef list2, int start2, int count2,
const IEqualityComparer<T> &comparer, List<int> &indices1, List<int> &indices2, std::vector<std::vector<MaxMatchDPResult>> &map)
{
bool eq = comparer.Equals(list1[start1], list2[start2]);
if (eq)
{
indices1.Add(start1);
indices2.Add(start2);
int r = MaximalSublistMatch_DP_Lookup(list1, start1 + , count1 - , list2, start2 + , count2 - , comparer, indices1, indices2, map) + ;
return r;
} List<int> temp11, temp12, temp21, temp22;
int r2 = ;
int r1 = MaximalSublistMatch_DP_Lookup(list1, start1, count1, list2, start2 + , count2 - , comparer, temp11, temp12, map);
if (r1 <
#if defined(min)
min(count1 - , count2)
#else
std::min(count1 - , count2)
#endif
)
{
r2 = MaximalSublistMatch_DP_Lookup(list1, start1 + , count1 - , list2, start2, count2, comparer, temp21, temp22, map);
}
if (r2 > r1)
{
for (int i = ; i < r2; i++)
{
indices1.Add(temp21[i]);
indices2.Add(temp22[i]);
}
return r2;
}
else
{
for (int i = ; i < r1; i++)
{
indices1.Add(temp11[i]);
indices2.Add(temp12[i]);
}
return r1;
}
}
This was stupid, but classic!
