这种模式有什么优雅的解决方案？多级搜索

假设我们有多个整数数组。您可以将每个数组视为一个级别。我们试图找到一系列元素，每个数组中只有一个元素，然后用相同的谓词继续下一个数组。例如，我们有v1, v2, v3作为数组：这种模式有什么优雅的解决方案？多级搜索

v1 | v2 | v3 
----------------- 
1 | 4 | 16 
2 | 5 | 81 
3 | 16 | 100 
4 | 64 | 121

我可以说，谓语是：next_element == previous_element^2
从上面的例子有效的顺序是：2 -> 4 -> 16
实际上，在这个例子中不存在另一有效的序列。我可以写三个循环来蛮力的提到的例子，但如果数组的数量是可变的，但知道当然知道，你会如何解决这个问题？

提示或参考设计模式非常赞赏。我会用C++来做，但我只是需要这个想法。

谢谢，

来源

2010-03-19 AraK

您需要_algorithm_，而不是_pattern_。这将是一个_problem_的解决方案。 – ima 2010-03-19 21:37:51

这里存在一个问题：看起来你的谓词可以是任意复杂的，因此可以同时对N个数组进行操作......很难想出一个解决方案可以用于整个事情。 – 2010-03-20 12:54:32

另外，是否有重复的可能性，如果有的话，你如何处理它们（你想要为每个副本提供1个解决方案，还是只需要一个解决方案？） – 2010-03-20 12:55:17

如果您事先订购您的阵列，搜索可以做得更快。您可以从较小的数组开始，然后在每个数组上搜索预期的数字。这将是O（n klogM），n是最小阵列的尺寸，k是阵列的数量，M是较大阵列的尺寸

如果使用Hashmaps，则可以更快地完成此操作的阵列。这会让你在O（n * k）中搜索。

如果使用反向函数（在较早的数组中搜索）不是一个选项，那么您应该从第一个数组开始，并且n =第一个数组的大小。

为了简单起见，我会从第一阵列

//note the 1-based arrays 
for (i : 1 until allArrays[1].size()) { 
    baseNumber = allArrays[1][i]; 
    for (j: 2 until allArrays.size()) { 
    expectedNumber = function(baseNumber); 
    if (!find(expectedNumber, allArrays[j])) 
     break; 
    baseNumber = expectedNumber; 
    } 
}

你或许可以做一些null检查，并在那里添加一些布尔开始知道如果序列存在或不

来源

2010-03-19 19:22:53

我刚刚在我的问题中给出了一个谓词示例。对于我使用的谓词，元素实际上并没有排序，我不认为它们可以针对谓词进行排序。我试图想出的方法是，如果数组**的数量是可变的**，就可以找到元素的序列。 – AraK 2010-03-19 19:30:05

@AraK现在我的答案有帮助吗？ – 2010-03-19 19:36:58

非常感谢，我认为这是我正在寻找:) – AraK 2010-03-19 19:37:49

您可以生成一个将索引从一个数组映射到另一个索引的独立索引。从索引中，您可以快速查看解决方案是否存在。

生成索引需要强力方法，但是你只能做一个。如果您想改进数组搜索，请考虑使用更合适的数据结构以实现快速搜索（例如红黑树，而不是阵列）。

来源

2010-03-19 19:22:58 Cthutu

以前的海报建议用二分查找排序数组 - 这比红黑树要快得多。如果你需要在数组中间插入很多项目，我会考虑使用列表而不是数组。这确实是内存使用和速度之间的折衷。 – Cthutu 2010-03-19 19:24:49

我会保留所有载体为heaps所以我可以有O(log n)复杂性，当搜索一个元素。因此，对于一个总k载体，你会得到一个复杂像O(k * log n)

来源

2010-03-19 19:26:46

（设计模式适用于类和API设计，提高代码质量，但它们不是解决计算问题。）

根据例如：

如果数组以随机顺序出现，并且您的空间需求有限，那么brute-force是唯一的解决方案。 O（N ^k）时间（k = 3），O（1）空间。
如果谓词不可逆（例如，SHA1(next_elem) xor SHA1(prev_elem) == 0x1234），那么蛮力也是唯一的解决方案。
如果您可以使用费用空间，然后为v2和v3创建散列集，那么您可以快速找到满足谓词的下一个元素。 O（N + b ^k）时间，O（kN）空间。（b =满足给定prev_elem的谓词的next_elem的最大数目）
如果数组被排序并且有界，则还可以使用二分搜索而不是散列表来避免使用空间。 O（N（log N）^k-1 + b ^k）时间，O（1）空间。

（所有的空间计数的未考虑到堆栈用法由于递归。）

消耗最多至O的一般方法（NB ^ķ）空间是由生成解决方案连续过滤，例如

solutions = [[1], [2], ... [N]] 

filterSolution (Predicate, curSols, nextElems) { 
    nextSols = [] 
    for each curSol in curSols: 
     find elem in nextElems that satisfy the Predicate 
     append elem into a copy of curSol, then push into nextSols 
    return nextSols 
} 

for each levels: 
    solutions = filterSolution(Predicate, solutions, all elems in this level) 
return solutions

来源

2010-03-19 19:32:54 kennytm

我喜欢这种流水线的想法！ – 2010-03-20 12:53:02

如果谓词保留了数组中的排序（例如，对于您的示例，如果所有值都保证非负），则可以调整合并算法。考虑每个数组作为最终值的关键（根据需要为所有数组应用谓词后所得到的结果）。

如果谓词不保留排序（或者数组没有按顺序启动），则可以先按最终值排序，但是需要这样做则表明另一种方法可能更好（如哈希表在其他地方建议）。

基本上，检查所有数组的下一个结束值是否相等。如果不是，请跳过最低点（仅在一个数组中）并重复。如果你们三个人平分秋色，那是一个（可能的）解决方案 - 在搜索下一个之前，先搜索所有三个解决方案。

“可能的”解决方案，因为您可能需要执行检查 - 如果谓词函数可以将多个输入值映射到相同的输出值，则可能会遇到某些数组中的值（但不是第一或最后）是错误的。

编辑 - 当谓词不会将每个输入映射到唯一输出时可能会出现更大的问题 - 此刻无法想象。基本上，合并方法可以很好地工作，但只适用于某些类型的谓词函数。

来源

2010-03-19 19:43:01 Steve314

这种模式有什么优雅的解决方案？多级搜索

回答

相关问题