有一个数组，其中除了一个单元格之外的所有单元格都是 0，我们想要找到该单个非零单元格的索引。问题是，每次检查此数组中的单元格时，该非零元素将执行以下操作之一:
例如，如果该元素当前位于位置 10，并且我检查
arr[5] 中的内容，那么在我检查 arr[5] 后，该元素可能位于位置 9、10 或 11 .我们只需要找到元素当前所在的位置，而不是它开始的位置(这是不可能的)。
困难的部分是，如果我们写一个 for 循环，真的没有办法知道元素当前是在你的前面还是在你的后面。
如果有帮助，请提供更多上下文:
最佳答案
Tl;博士:最好的办法是依次检查数组中的每个偶数索引，根据需要循环多次，直到找到目标。平均而言，您会在第二次通过时偶然发现目标。
首先，正如许多人已经说过的那样，确实不可能确保在任何给定的时间内找到目标元素。如果元素知道您的下一个样本将在哪里，它总是可以及时将自己放置在其他地方。您能做的最好的事情是以最小化预期访问次数的方式对数组进行采样 - 因为在每次采样之后，除了成功与否之外您什么也学不到，并且成功意味着您停止采样，因此可以描述最佳策略简单地作为应该检查的索引序列，仅取决于您正在查看的数组的大小。我们可以通过自动化手段依次测试每个策略，看看它们的表现如何。结果将取决于问题的具体情况，所以让我们做一些 假设 :
算法 我测试过的是:
结果:
结果显示为[平均值]±[标准推导]。
在这一点上，我意识到我的代码中存在一个围栏错误。好在我们有一个对照样本。这也证实了我们有两到三位数的有用精度 (sqrt #samples)，这与其他此类测试一致。
我们的目标通过网井挤压的机会抵消了目标平均花费 n/2 次到达网的效果。该算法的平均表现并不比随机样本好，但它的性能更加一致，而且实现起来也不难。
虽然我们的网移动缓慢意味着我们的目标可能会在第一次扫网时被网夹住，不需要第二次扫网，但这也意味着第一次扫网需要两倍的时间。总而言之，依靠目标移动到我们身上似乎有点低效。
这……起初有点令人惊讶。虽然每隔一步跳过意味着我们以两倍的圈数完成每一圈，但每一圈也减少了实际遇到目标的机会。一个更好的 View 是在扫帚空间中比较 Sweep 和 FastSweep:旋转每个样本，以便被采样的索引始终为 0，并且目标向左漂移得更快一点。在 Sweep 中，目标每一步以 0、1 或 2 的速度移动。与斐波那契基数的快速平行告诉我们，目标应该有 62% 的时间击中扫帚/网。如果未命中，则需要再过 100 回合才能返回。在 FastSweep 中，目标每一步以 1、2 或 3 的速度移动，这意味着它更频繁地错过，但重试也需要一半的时间。由于重试时间比命中率下降得更多，因此使用 FastSweep 比使用 Sweep 更有优势。
大多数情况下就像一个普通的扫描，它的分数和标准推导反射(reflect)了这一点。结果并不出人意料。
在这一点上，我不得不承认我的代码中有一个错误:这个算法严重依赖于它的初始行为(Aziuth 未指定它并在我的测试中被随机选择)。但性能问题意味着该算法每次将始终选择相同的随机顺序。结果是随机化的特征，而不是整个算法的特征。
总是选择最有可能的位置应该尽快找到我们的目标，对吧？不幸的是，这种复杂的算法几乎无法与 Sweep 3x 竞争。为什么？我意识到这只是推测，但让我们看看 Smart Greedy 实际生成的序列:在第一遍期间，每个单元格包含目标的概率相等，因此算法必须选择。如果它随机选择，它可以在概率下降到达所有单元格之前在 20% 的单元格中找到它们。之后，在最近没有对数组进行采样的地方，景观大部分是平滑的，因此算法最终会停止扫描并开始随机跳跃。真正的问题是该算法过于贪婪，并不真正关心放牧目标，因此它可以更轻松地选择目标。
尽管如此，这种复杂的算法确实比简单的 Sweep 和随机采样器要好。然而，它仍然无法与 FastSweep 的简单性和惊人的效率相媲美。重复测试表明，初始随机化可以使效率在 80% 运行时间(20% 加速)和 90% 运行时间(10% 加速)之间摆动。
最后，这里是 代码用于生成结果:
class WalkSim
attr_reader :limit, :current, :time, :p_stay
def initialize limit, p_stay
@p_stay = p_stay
@limit = limit
@current = rand (limit + 1)
@time = 0
end
def poke n
r = n == @current
@current += (rand(2) == 1 ? 1 : -1) if rand > @p_stay
@current = [0, @current, @limit].sort[1]
@time += 1
r
end
def WalkSim.bench limit, p_stay, runs
histogram = Hash.new{0}
runs.times do
sim = WalkSim.new limit, p_stay
gen = yield
nil until sim.poke gen.next
histogram[sim.time] += 1
end
histogram.to_a.sort
end
end
class Array; def sum; reduce 0, :+; end; end
def stats histogram
count = histogram.map{|k,v|v}.sum.to_f
avg = histogram.map{|k,v|k*v}.sum / count
variance = histogram.map{|k,v|(k-avg)**2*v}.sum / (count - 1)
{avg: avg, stddev: variance ** 0.5}
end
RUNS = 1_000_000
PSTAY = 1.0/3
LIMIT = 100
puts "random sampling"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) {
Enumerator.new {|y|loop{y.yield rand (LIMIT + 1)}}
}
puts "sweep"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) {
Enumerator.new {|y|loop{0.upto(LIMIT){|i|y.yield i}}}
}
puts "x0.5 speed sweep"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) {
Enumerator.new {|y|loop{0.upto(LIMIT){|i|2.times{y.yield i}}}}
}
(2..5).each do |speed|
puts "x#{speed} speed sweep"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) {
Enumerator.new {|y|loop{speed.times{|off|off.step(LIMIT, speed){|i|y.yield i}}}}
}
end
puts "sweep LR"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) {
Enumerator.new {|y|loop{
0.upto(LIMIT){|i|y.yield i}
LIMIT.downto(0){|i|y.yield i}
}}
}
$sg_gen = Enumerator.new do |y|
probs = Array.new(LIMIT + 1){1.0 / (LIMIT + 1)}
loop do
ix = probs.each_with_index.map{|v,i|[v,rand,i]}.max.last
probs[ix] = 0
probs = [probs[0] * (1 + PSTAY)/2 + probs[1] * (1 - PSTAY)/2,
*probs.each_cons(3).map{|a, b, c| (a + c) / 2 * (1 - PSTAY) + b * PSTAY},
probs[-1] * (1 + PSTAY)/2 + probs[-2] * (1 - PSTAY)/2]
y.yield ix
end
end
$sg_cache = []
def sg_enum; Enumerator.new{|y| $sg_cache.each{|n| y.yield n}; $sg_gen.each{|n| $sg_cache.push n; y.yield n}}; end
puts "smart greedy"
p stats WalkSim.bench(LIMIT, PSTAY, RUNS) {sg_enum}
关于arrays - 查找数组中的元素，但是元素可以跳转，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/36149346/