javascript - 在PHP，Node和Golang中找到两个数组之间的差异

这是我需要做的一个典型例子

$testArr = array(2.05080E6,29400,420);

$stockArrays =  array(
                      array(2.05080E6,29400,0),
                      array(2.05080E6,9800,420),
                      array(1.715E6,24500,280),
                      array(2.05080E6,29400,140),
                      array(2.05080E6,4900,7));

我需要确定最小的stockArray。一些澄清

确保每个位置的数组元素的数值都不重叠。 (即arr [0]始终具有最大值，arr 1至少要小10个数量级，依此类推)。

确定最小差异时，差异的绝对值不计算在内。仅，不同的数组索引的数量很重要。

位置差异确实具有权重。因此，在我的示例中，stockArr 1也是“更加不同”的，就像它的stockArr [0]和stockArr [3]一样，仅在一个索引位置上有所不同，因为该索引位置更大。

stockArrays元素的数量通常少于10个，但有可能更多(尽管永远不会成3个数字)

库存数组将始终具有相同数量的元素。测试数组将具有相同或更少的元素。但是，当将填充较少的testArr时，可能匹配的元素将始终与stockArray位于同一位置。例如

$ testArray(29400,140)

将转化为

$testArray(0,29400,140);

在进行差异测试之前。

最后，可以打平。例如，我上面的匹配示例是stockArrays [0]和stockArrays [3]。

在我的示例中，结果将是

$result = array(0=>array(0,0,1),3=>array(0,0,1));

表示差异最小的股票阵列位于索引0和3，差异位于位置2。

在PHP中，我将使用array_diff作为所有起点。对于Node / JavaScript，我可能会倾向于php.js array_diff端口，尽管鉴于在最坏的转换情况下它是O(n2)事件，所以我倾向于探索一点。

我是Golang的新手，因此不确定在该如何实现此问题。我注意到Node确实有一个array_diff npm模块。

我曾经有一个另类的想法，就是将数组转换为填充字符串(较小的数组元素为0填充)，并有效地对每个字符的序数值进行XOR运算，但认为这可能是一件相当棘手的事情。

我关心速度，但不惜一切代价。在理想情况下，每种目标语言都将使用相同的解决方案(算法)，尽管实际上它们之间的差异可能意味着不可能/不是一个好主意。

也许这里的某人可能会指出一些不太行人的方式来实现此目的-即不仅仅是array_diff端口。

最佳答案

这等效于array_diff解决方案:(假设我没有记错)

package main

import "fmt"

func FindLeastDifferent(needle []float64, haystack [][]float64) int {
    if len(haystack) == 0 {
        return -1
    }
    var currentIndex, currentDiff int
    for i, arr := range haystack {
        diff := 0
        for j := range needle {
            if arr[j] != needle[j] {
                diff++
            }
        }
        if i == 0 || diff < currentDiff {
            currentDiff = diff
            currentIndex = i
        }
    }

    return currentIndex
}

func main() {
    idx := FindLeastDifferent(
        []float64{2.05080E6, 29400, 420},
        [][]float64{
            {2.05080E6, 29400, 0},
            {2.05080E6, 9800, 420},
            {1.715E6, 24500, 280},
            {2.05080E6, 29400, 140},
            {2.05080E6, 4900, 7},
            {2.05080E6, 29400, 420},
        },
    )
    fmt.Println(idx)
}

就像您所说的O(n * m)，其中n是针状数组中的元素数，而m是干草堆中的数组数。

如果您不提前知道大海捞针，那么您可能无能为力。但是，相反，如果您将此列表存储在数据库中，则我认为您对字符串搜索的直觉很有潜力。例如，PostgreSQL支持字符串相似性索引。 (这是对正则表达式的类似想法的解释:http://swtch.com/~rsc/regexp/regexp4.html)

另一个想法:如果数组很大，则可以计算模糊哈希(http://ssdeep.sourceforge.net/)，这会使n变小。