4

参考对象：{ 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

4 回答 4

1

如果您对对象中的所有数据进行了排序，则可以通过逐步比较行中的单个值而不是整行来更快地执行此例程。

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++;
        }
    }
}

在这种情况下，您只为每一行传递一次引用，但此算法需要您的所有数据都已排序。

于 2013-09-17T10:39:24.143 回答
0

您应该使用搜索引擎中使用的其他技术。对于每个数字，您都有一个按排序顺序包含此数字的对象列表。在你的情况下

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 个元素，则应使用优先级队列。

于 2013-09-17T15:37:28.323 回答
0

你可以从最大的序列开始（它有很多引用的最大变化）。当您找到 - 例如 - 4 个参考时，您可以安全地跳过所有元素少于 4 个的序列。

另一个提前退出是在当前序列不能超过当前最大值时中止检查序列。例如：您当前的最大值为 6 个元素。您正在处理大小为 7 的列表，但前两个元素不是参考。此列表的最高可达性为 5，低于 6，中止序列。

这两种情况的问题是您无法构建完整的结果数组。

于 2013-09-17T09:55:00.193 回答
0

假设：

There are m lists apart from the reference object.
The lists are sorted initially.
There are no repetition of elements in any array.
  1. 扫描所有数组并找出所有列表中的最大元素。您只需要检查每个列表中的最后一个元素。称之为MAX。
  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 时增加计数。

上述算法可以相对于数据中元素的总数以线性时间复杂度完成。

于 2013-09-17T10:31:59.767 回答