我需要比较一个一维数组中的每个元素。该数组包含按长度从长到短排序的字符串列表。该数组中没有两个相同的项，但是可能有相同长度的项。目前，我正在进行N*(N+1)/2（1278亿）次比较，并试图减少总体比较次数。
我已经实现了一个功能，基本上是说：如果两个字符串的长度相差超过x%，则它们不相等，而且比这个字符串更短的其他字符串也不相等，因此跳出循环并转到下一个元素。
我目前正试图通过以下方式进一步减少：如果元素A与元素C和D匹配，则可以推断出元素C和D也会匹配，因此不要检查它们（即跳过该操作）。这是我的极限，因为我目前不知道能够做到这一点的数据结构。
问题是：有人知道这样的数据结构吗？或者有人知道我如何进一步减少比较？
根据估计，我的当前实现需要在10小时内完成3.5天的执行时间（即时间太长），我唯一剩下的选择是减少执行时间（可能可行，也可能不可行）或将工作负载分散到数十个系统上（可能不切实际）。
更新：抱歉，请将“相等”一词替换为“接近匹配”。我正在计算Levenstein距离。
想法是找出数组中是否有其他与每个元素接近匹配的字符串。输出是一个数据库映射，其中包含紧密相关的字符串。
以下是该方法的部分代码。在执行此代码块之前，有一个将项加载到数据库中的代码。
我已经实现了一个功能，基本上是说：如果两个字符串的长度相差超过x%，则它们不相等，而且比这个字符串更短的其他字符串也不相等，因此跳出循环并转到下一个元素。
我目前正试图通过以下方式进一步减少：如果元素A与元素C和D匹配，则可以推断出元素C和D也会匹配，因此不要检查它们（即跳过该操作）。这是我的极限，因为我目前不知道能够做到这一点的数据结构。
问题是：有人知道这样的数据结构吗？或者有人知道我如何进一步减少比较？
根据估计，我的当前实现需要在10小时内完成3.5天的执行时间（即时间太长），我唯一剩下的选择是减少执行时间（可能可行，也可能不可行）或将工作负载分散到数十个系统上（可能不切实际）。
更新：抱歉，请将“相等”一词替换为“接近匹配”。我正在计算Levenstein距离。
想法是找出数组中是否有其他与每个元素接近匹配的字符串。输出是一个数据库映射，其中包含紧密相关的字符串。
以下是该方法的部分代码。在执行此代码块之前，有一个将项加载到数据库中的代码。
public static void RelatedAddressCompute() {
TableWipe("RelatedAddress");
decimal _requiredDistance = Properties.Settings.Default.LevenshteinDistance;
SqlConnection _connection = new SqlConnection(Properties.Settings.Default.AML_STORE);
_connection.Open();
string _cacheFilter = "LevenshteinCache NOT IN ('','SAMEASABOVE','SAME')";
SqlCommand _dataCommand = new SqlCommand(@"
SELECT
COUNT(DISTINCT LevenshteinCache)
FROM
Address
WHERE
" + _cacheFilter + @"
AND
LEN(LevenshteinCache) > 12", _connection);
_dataCommand.CommandTimeout = 0;
int _addressCount = (int)_dataCommand.ExecuteScalar();
_dataCommand = new SqlCommand(@"
SELECT
Data.LevenshteinCache,
Data.CacheCount
FROM
(SELECT
DISTINCT LevenshteinCache,
COUNT(LevenshteinCache) AS CacheCount
FROM
Address
WHERE
" + _cacheFilter + @"
GROUP BY
LevenshteinCache) Data
WHERE
LEN(LevenshteinCache) > 12
ORDER BY
LEN(LevenshteinCache) DESC", _connection);
_dataCommand.CommandTimeout = 0;
SqlDataReader _addressReader = _dataCommand.ExecuteReader();
string[] _addresses = new string[_addressCount + 1];
int[] _addressInstance = new int[_addressCount + 1];
int _itemIndex = 1;
while (_addressReader.Read()) {
string _address = (string)_addressReader[0];
int _count = (int)_addressReader[1];
_addresses[_itemIndex] = _address;
_addressInstance[_itemIndex] = _count;
_itemIndex++;
}
_addressReader.Close();
decimal _comparasionsMade = 0;
decimal _comparisionsAttempted = 0;
decimal _comparisionsExpected = (decimal)_addressCount * ((decimal)_addressCount + 1) / 2;
decimal _percentCompleted = 0;
DateTime _startTime = DateTime.Now;
Parallel.For(1, _addressCount, delegate(int i) {
for (int _index = i + 1; _index <= _addressCount; _index++) {
_comparisionsAttempted++;
decimal _percent = _addresses[i].Length < _addresses[_index].Length ? (decimal)_addresses[i].Length / (decimal)_addresses[_index].Length : (decimal)_addresses[_index].Length / (decimal)_addresses[i].Length;
if (_percent < _requiredDistance) {
decimal _difference = new Levenshtein().threasholdiLD(_addresses[i], _addresses[_index], 50);
_comparasionsMade++;
if (_difference <= _requiredDistance) {
InsertRelatedAddress(ref _connection, _addresses[i], _addresses[_index], _difference);
}
}
else {
_comparisionsAttempted += _addressCount - _index;
break;
}
}
if (_addressInstance[i] > 1 && _addressInstance[i] < 31) {
InsertRelatedAddress(ref _connection, _addresses[i], _addresses[i], 0);
}
_percentCompleted = (_comparisionsAttempted / _comparisionsExpected) * 100M;
TimeSpan _estimatedDuration = new TimeSpan((long)((((decimal)(DateTime.Now - _startTime).Ticks) / _percentCompleted) * 100));
TimeSpan _timeRemaining = _estimatedDuration - (DateTime.Now - _startTime);
string _timeRemains = _timeRemaining.ToString();
});
}
InsertRelatedAddress是一个更新数据库的函数，数组中有500,000个项目。