让我们尝试分析一下问题：
如果有
N行，则
N*N在相似性函数中要考虑“对”。在一般情况下，对所有这些元素进行评估都是无可避免的（听起来很合理，但我无法证明这一点）。因此，您
至少具有O（n ^ 2）个时间复杂度 。
但是，您可以尝试使用时间复杂度 恒定的因素 。我发现的可能选项是：
1.并行化：
由于您有一些大型的
Dataframe，并行处理是最佳的选择。这将使您（几乎）在时间复杂度方面得到线性改善，因此，如果您有16名工作人员，您将获得（几乎）16倍的改进。
例如，我们可以将的行划分
df为不相交的部分，并分别处理每个部分，然后合并结果。一个非常基本的并行代码可能看起来像这样：
from multiprocessing import cpu_count,Pooldef work(part): """ Args: part (Dataframe) : a part (collection of rows) of the whole Dataframe. Returns: Dataframe: the same part, with the desired property calculated and added as a new column """ # Note that we are using the original df (pandas_df) as a global variable # But changes made in this function will not be global (a side effect of using multiprocessing). for index, _id, word in part.itertuples(): # iterate over the "part" tuples value = sum( pandas_df[pandas_df['word'] != word].apply( # Calculate the desired function using the whole original df lambda x: foo(x['word'], word), axis=1 ) < threshold ) part.loc[index, 'bar'] = value return part# New pre starts here ...cores = cpu_count() #Number of CPU cores on your systemdata_split = np.array_split(data, cores) # Split the Dataframe into partspool = Pool(cores) # Create a new thread poolnew_parts = pool.map(work , data_split) # apply the function `work` to each part, this will give you a list of the new partspool.close() # close the poolpool.join()new_df = pd.concat(new_parts) # Concatenate the new parts
注意：我试图使代码尽可能接近OP的代码。这只是一个基本的演示代码，并且存在许多更好的替代方法。
2.“低级”优化：
另一个解决方案是尝试优化相似度函数的计算和迭代/映射。与上一个或下一个选项相比，我认为这不会为您带来很大的提速。
3.取决于功能的修剪：
您可以尝试的最后一件事是依赖相似功能的改进。这在一般情况下不起作用，但如果您可以分析相似性函数，则将很好地工作。例如：
假设您使用的是Levenshtein距离（
LD），则可以观察到任意两个字符串之间的距离> =长度之间的差。即
LD(s1,s2) >=abs(len(s1)-len(s2))。
您可以使用此观察结果来修剪可能的相似对，以进行评估。因此，对于每个字符串长度
l1，只有具有长度的字符串比较它
l2有
abs(l1-l2) <=limit。（限制为所接受的最大相似度，在您提供的示例中为2）。
另一个观察是
LD(s1,s2) = LD(s2,s1)。这样可以将对数减少2倍。
该解决方案实际上可能使您陷入
O(n)时间复杂性（高度依赖于数据）的问题。
为什么？你可能会问。
这是因为，如果我们有
10^9行，但平均而言
10^3，每行只有“接近”长度的行，那么我们需要针对约
10^9 * 10^3 /2对而不是
10^9* 10^9对来评估函数。但这（再次）取决于数据。如果（在此示例中）您拥有长度均为3的字符串，则此方法将无用。
