Найти объекты с наибольшим количеством соответствий эталонному объекту
Контрольный объект: { 1, 5, 6, 9, 10, 11 }
Другие объекты:
A { 2, 4, 5, 6, 8, 10, 11 }
B { 5, 7, 9, 10 }
C { 2, 5, 6, 7, 9, 12 }
D { 1, 3, 4, 5, 6, 8, 9, 10 }
E { 6, 8 }
F { 1, 2, 3, 4, 7, 8, 9, 13, 15 }
... { ... }
Сложность: она должна быть быстрее, чем O(n*m)
Результат должен быть:
Array
(
[D] => 5
[A] => 4
[C] => 3
[B] => 3
[F] => 2
[E] => 1
)
Медленное решение:
ref = array(1, 5, 6, 9, 10, 11);
foreach (A, B, C, D,.. AS row)
{
foreach (row AS col)
{
if ( exist(col, ref) )
{
result[row] += 1;
}
}
}
sort (result)
.. это решение, но его далеко не медленно.
Есть ли другой способ, такой как распознавание скороговорки, надеюсь, в O(log n)?
Можно сохранить каждый объект в другой записи, например:
ref = "15691011"
A = "2456811"
Но я не знаю, поможет ли это.
4 ответа
Если у вас есть все данные в ваших объектах отсортированы, вы можете сделать эту процедуру быстрее, сравнивая не отдельные значения в строке, а целую строку шаг за шагом.
foreach (A, B, C, D,.. AS row)
{
for (i = 0, j = 0; i < row.length && j < ref.length)
{
if (row[i] < ref[j]) i++;
elseif (row[i] > ref[j]) j++;
else {
result[row] += 1;
i++; j++;
}
}
}
В этом случае вы передаете ссылку только один раз для каждой строки, но этот алгоритм требует, чтобы все ваши данные были уже отсортированы.
Вы должны использовать другие методы, используемые в поисковых системах. Для каждого номера у вас есть список объектов, содержащих этот номер в отсортированном порядке. В твоем случае
1 -> {D, F}
5 -> {A, B, C, D}
6 -> {A, C, D, E}
9 -> {B, C, D, F}
10 -> {A, B, D}
11 -> {A}
Объединяя этот список, вы можете посчитать, как ваш объект похож на объекты в списке
A -> 4
B -> 3
C -> 2
D -> 5
E -> 1
F -> 2
После сортировки вы получите нужный результат. Если вам нужны только верхние k элементов, вы должны использовать приоритетную очередь.
Вы можете начать с самой большой последовательности (она имеет наибольшее изменение, чтобы иметь много ссылок). Когда вы найдете, например, 4 ссылки, вы можете безопасно пропустить все последовательности, содержащие менее 4 элементов.
Другой ранний выход - прервать проверку последовательности, когда текущая последовательность не может превысить максимальный ток. например: ваш текущий максимум составляет 6 элементов. Вы обрабатываете список размером 7, но первые два элемента не являются ссылками. Максимально достижимым для этого списка является 5, что ниже 6, прервать последовательность.
Проблема в обоих случаях заключается в том, что вы не можете построить полный массив результатов.
Предположения:
There are m lists apart from the reference object.
The lists are sorted initially.
There are no repetition of elements in any array.
- Просканируйте все массивы и найдите максимальный элемент во всех списках. Вам нужно только проверить последний элемент в каждом списке. Назовите это Макс.
- Для каждого из списков m + 1 создайте соответствующий логический массив с элементами MAX и инициализируйте их значения нулем.
Сканирование всех массивов и составление соответствующих индексов массивов 1.
Например, соответствующий массив для примерного ссылочного объекта { 1, 5, 6, 9, 10, 11 } должен выглядеть следующим образом: {1,0,0,0,1,1,0,0,1,1,1,0,0,...}
Теперь для каждой парной комбинации вы можете просто проверить соответствующие индексы и увеличить счетчик, если оба равны 1.
Вышеупомянутый алгоритм может быть выполнен с линейной временной сложностью относительно общего количества элементов в данных.