哪一个会更快？
假设我有一个数组，大小为 40。我要查找的元素位于位置 38。 有一个简单的循环，需要 38 个步骤，对吗？ 但是，有两个并行运行的循环和一个变量“找到” 设置为 false，并在找到元素时更改为 true。
第一个循环将从索引 0 开始 第二个循环将从索引 40 开始。
所以基本上，它只需要 4 个步骤，对吗？来找到该元素。最坏的情况是元素位于数组的中间。正确的？
let's say i have an array, size 40. and the element im looking for is in position 38.
having a simple loop, it will take 38 steps right?
but, having, 2 loops, running in parallel, and a variable, "found"
set to false, and changes to true when the element is found.
the first loop, will start from index 0
the second loop, will start from index 40.
so basically, it will take only, 4 steps right? to find the element. the worst case will be if the element is in the middle of the array. right?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
这取决于同步两个线程之间的状态需要做多少工作。
如果需要 0 工作量，那么平均而言，这将比直通算法快 50%。
另一方面，如果它需要比 X 更多的工作，它将开始变得更慢（这很可能是这种情况）。
从算法的角度来看，我认为这不是你想要的。即使有 2 个线程，运行时间仍然是 O(n)。您可能需要对数据进行排序 (n log n )，然后进行二分搜索来获取数据。特别是您可以对它进行一次排序并使用它进行多次搜索......
It depends how much work it takes to synchronize the state between the two threads.
If it takes 0 work, then this will be, on average, 50% faster than a straight through algorithm.
On the other hand, if it takes more work than X, it will start to get slower (which is very likely the case).
From an algorithm standpoint, I don't think this is how you want to go. Even 2 threads is still going to be O(n) runtime. You would want to sort the data (n log n ), and then do a binary search to get the data. Especially you can sort it 1 time and use it for many searches...
如果您谈论算法复杂性，这仍然是线性搜索。仅仅因为每次迭代搜索两个元素并不会改变算法为 O(n) 的事实。
就您将看到的实际性能而言，该算法可能比使用单个处理器的线性搜索慢。由于搜索中每个元素完成的工作很少，因此该算法将受到内存限制，因此使用多个处理器不会有任何好处。此外，由于您在两个位置进行搜索，因此该算法的缓存效率不高。然后，正如 bwawok 指出的那样，同步会损失大量时间。
If you're talking about algorithmic complexity, this is still a linear search. Just because you're searching two elements per iteration doesn't change the fact that the algorithm is O(n).
In terms of actual performance you would see, this algorithm is likely to be slower than a linear search with a single processor. Since very little work is done per-element in a search, the algorithm would be memory bound, so there would be no benefit to using multiple processors. Also, since you're searching in two locations, this algorithm would not be as cache efficient. And then, as bwawok points out, there would be a lot of time lost in synchronization.
当您并行运行时您将 CPU 功率一分为二+产生一些开销。如果您的意思是您正在使用您提出的算法在多核计算机上运行搜索，那么最坏的情况是 20 个步骤。您不会对复杂性类别进行任何更改。那么您提到的这 4 个步骤是从哪里来的呢？
When you are running in parallel you are dividing your CPU power into two + creating some overhead. If you mean you are running the search on a say, a multicore machine, with your proposed algorithm then the worse case is 20 steps. You are not making any change in the complexity class. So where those 4 steps, that you mentioned, are coming from?
平均运行时没有什么不同。
举例来说，如果您正在搜索 10 项中的一项。
原始算法将按以下搜索顺序进行处理：
最坏的情况是最后一项（需要 10 步）。
而第二个算法将按以下搜索顺序进行处理：
这种情况下最坏的情况是第 6 项（需要 10 个步骤）。
在某些情况下，算法 1 更快。
在某些情况下，算法 2 更快。
两者平均花费相同的时间 - O(n)。
附带说明一下，将其与二分搜索顺序（在排序数组上）进行比较很有趣。
最多需要 4 个步骤才能完成。
On average there is no different in runtime.
Take for example if you are searching for an item out of 10.
The original algorithm will process in the following search order:
The worse case is the last item (taking 10 steps).
While the second algorithm will process in the following search order:
The worse case in this scenario is item 6 (taking 10 steps).
There are some cases where algorithm 1 is faster.
There are some cases where algorithm 2 is faster.
Both take the same time on average - O(n).
On a side note, it is interesting to compare this to a binary search order (on a sorted array).
Taking at most 4 steps to complete.