Поиск различий между двумя массивами в PHP, Node и Golang.

Question

Поиск различий между двумя массивами в 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] всегда будет иметь самые большие значения, arr1 будет как минимум на порядок меньше и т. д.).
Абсолютные значения различий не учитываются при определении наименее разные. Только, количество различных индексов массива имеет значение.
Позиционные различия имеют вес. Таким образом, в моем примере stockArr1 является «более разные» подумал тоже — как и его 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).

Я новичок, когда дело доходит до Голанга, поэтому я не уверен, как бы я реализовал эту проблему там. Я заметил, что у Node есть модуль array_diff npm.

У меня была одна необычная идея — преобразовать массив в дополненную строку (меньшие элементы массива дополнены 0) и эффективно выполнить XOR для порядкового значения каждого символа, но отклонил это как, вероятно, довольно сумасшедшую вещь.

Я обеспокоен скоростью, но не любой ценой. В идеальном мире одно и то же решение (алгоритм) будет использоваться в каждом целевом языке, хотя в действительности различия между ними могут означать, что это невозможно / не очень хорошая идея.

Возможно, кто-то здесь мог бы указать мне на менее пешеходные способы достижения этой цели — то есть не только на порты array_diff.

-1

arrays go javascript node.js php

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

Вот эквивалент решения 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 меньше.

1