带回调的唯一数组值

SO，

问题

第一种情况

我有一个带有一些值的数组 - 首先，让它们都是字符串（或者可以简单地视为字符串）。例：

$rgData = ['foo', 'feo', 'bar', 'baz', 'bee'];

现在，我想从中创建唯一的数组，其中两个项目之间的 Levenshtein 距离小于 2.即，如果levenshtein($x, $y) < 2，则项目$x和$y被视为相等。例如，foo和feo相等，也是bar和baz - 但不是bar和bee.

第二种情况

我有一个带有每个点坐标[x, y]数组，例如：

$rgData = [[0, 0.1], [-5, 4.5], [0, 0.5], [-5.5, 4.5]];

现在，我想从中创建唯一的数组，其中两点之间的距离小于 1.即，如果pow((pow($x[0]-$y[0], 2) + pow($x[1]-$y[1],2)), 0.5)<1，则点$x和$y被视为相等

很明显，这两种情况都可以通过一些函数来解决，该函数类似于标准 PHP array_unique（） - 但它接受比较函数来检查项目是否相等。我的问题是关于这个函数的。

我的方法

现在，我有最简单的功能解决方案：

function array_uunique($rgData, $fnCompare=null)
{
    if(!isset($fnCompare))
    {
        return array_unique($rgData);
    }
    if(!is_callable($fnCompare))
    {
        return null;
    }
    if(!count($rgData))
    {
        return array();
    }
    $rgResult = array();
    foreach($rgData as $mItem)
    {
        foreach($rgResult as $mTest)
        {
           if(!call_user_func_array($fnCompare, [$mItem, $mTest]))
           {
              continue 2;
           }
        }
        $rgResult[]=$mItem;
    }
    return $rgResult;
}

-它接受回调作为第二个参数，并返回与此比较规则不相等的元素，即对于 Levenshtein，描述的结果将是：

$rgResult = array_uunique(['foo', 'feo', 'bar', 'baz', 'bee'], function($x, $y)
{
   return levenshtein($x, $y)>1; //or !levenshtein($x, $y)<2
});

-这将导致

数组（3） {  [0]=>  字符串（3） "呜"  [1]=>  字符串（3） "酒吧"  [2]=>  字符串（3） "蜜蜂"}

-您可以使用此小提琴进行测试。

细节

如上所述，这是最简单的方法，但它内部包含 2 个嵌套的依赖循环。因此，这种结构的复杂性将是O(N^2)的 - 这很可悲 - 并且对我不起作用，特别是如果比较函数操作成本很高 - 因为我将在数据数组中有大量元素（~1E5..至少 1E6）。

我的问题是 - 如何改善这一点？也许还有另一种好的算法？或者我的代码可以以某种方式改进？

更新（基于下面的良好评论）：我知道在通常情况下，这样的问题会出现传递函数问题，即 xFy = yFz => xFz - 例如，levenshtein()不是可传递的。因此，在通常情况下，整个结果至少取决于项目顺序（但不仅取决于它） - 现在对我来说不是问题，因为我确定我的数据顺序和内容（或者，至少，如果通过levenshtein比较返回bar或baz不是问题）。因此，我的目标是最大限度地减少比较次数（我认为比较函数是否传递是否没有任何变化，因为我想优化甚至重新创建比较算法本身）