Найти объекты с наибольшим количеством соответствий эталонному объекту

Контрольный объект: { 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.
  1. Просканируйте все массивы и найдите максимальный элемент во всех списках. Вам нужно только проверить последний элемент в каждом списке. Назовите это Макс.
  2. Для каждого из списков m + 1 создайте соответствующий логический массив с элементами MAX и инициализируйте их значения нулем.
  3. Сканирование всех массивов и составление соответствующих индексов массивов 1.

    Например, соответствующий массив для примерного ссылочного объекта { 1, 5, 6, 9, 10, 11 } должен выглядеть следующим образом: {1,0,0,0,1,1,0,0,1,1,1,0,0,...}

  4. Теперь для каждой парной комбинации вы можете просто проверить соответствующие индексы и увеличить счетчик, если оба равны 1.

Вышеупомянутый алгоритм может быть выполнен с линейной временной сложностью относительно общего количества элементов в данных.

Другие вопросы по тегам