如何大海捞针？

Question

当以面向对象的方式实现大海捞针式搜索时，您基本上有三种选择：

1. needle.find(haystack)

2. haystack.find(needle)

3. searcher.find(needle, haystack)

您更喜欢哪一个，为什么？

我知道有些人更喜欢第二种选择，因为它避免引入第三个对象。 然而，我不禁觉得第三种方法在概念上更“正确”，至少如果你的目标是建模“现实世界”。

您认为在哪些情况下引入辅助对象（例如本例中的搜索器）是合理的，什么时候应该避免它们？

Answer 1

haystack.iterator.findFirst(/* pass here a predicate returning
                               true if its argument is a needle that we want */)

迭代器可以是任何不可变集合的接口，集合具有通用的 findFirst(fun: T => Boolean) 方法来完成这项工作。 只要干草堆是不可变的，就不需要向“外部”隐藏任何有用的数据。
当然，将自定义的非平凡集合的实现与其他一些具有 haystack 的东西结合在一起并不是一件好事。 分而治之，好吗？

Answer 2

在大多数情况下，我更喜欢能够在核心对象上执行这样的简单辅助操作，但根据语言的不同，相关对象可能没有足够或合理的可用方法。

即使在像 JavaScript 这样允许您增强/扩展内置对象的语言中，我发现它可能既方便又存在问题（例如，如果该语言的未来版本引入了一种更有效的方法，该方法会被自定义方法覆盖）。

本文很好地概述了此类场景。

Answer 3

这个问题的答案实际上应该取决于解决方案实施的领域。
类

• 如果您碰巧在物理干草堆中模拟物理搜索，您可能会拥有Space
• Straw
• Needle
• Seeker

Space
知道哪些对象位于哪些坐标
实现自然法则（转换能量、检测碰撞等）

针、吸管
位于太空
对力量做出反应

探索者
与空间互动：
   移动手，施加磁场，燃烧干草，应用 X 射线，寻找针...

因此  seeker.find(needle, space )   或   seeker.find(needle, space,strategy)

干草堆恰好位于您要寻找针的空间中。 当您将空间抽象为一种虚拟机（想想：矩阵）时，您可以使用 haystack 而不是空间来得到上面的内容（解决方案 3/3b）：

seeker.find(needle 、干草堆）    或     seeker.find(needle, haystack,strategy)

但是矩阵是域，如果你的针不能在其他地方，它只能被 haystack 替换。

话又说回来，这只是一个类比。 有趣的是，这为全新的方向打开了思路：
1. 最初为什么针会松动？ 你能改变这个过程，这样你就不会失去它吗？
2. 您是否必须找到丢失的针头，还是可以直接获取另一根针而忘记第一根针？ （如果针一会儿就溶解了就好了）
3. 如果您经常丢失针并且需要再次找到它们，那么您可能想要

• 制造能够自我找到的针，例如它们经常问自己：我迷路了吗？ 如果答案是肯定的，他们会将 GPS 计算出的位置发送给某人或开始发出蜂鸣声或其他什么：
  needle.find(space) 或 needle.find(haystack)       （解决方案1）

• 安装一个干草堆，每根吸管上都有一个摄像头，然后你可以询问干草堆蜂巢意识最近是否看到了针：
  haystack.find(needle) （解决方案 2）

• 将 RFID 标签附加到您的针上，以便您可以轻松地对它们进行三角测量

这一切只是为了说明，在您的实现中，您制作了针和大海捞针，并且大多数时候是某种级别上的矩阵。

因此，请根据您的领域来决定：

• 干草堆的目的是为了容纳针吗？ 然后采用解决方案 2。
• 针随处丢失是自然现象吗？ 然后去解决方案1。
• 针会不会不小心掉进大海捞针了？ 然后采用解决方案 3。（或考虑其他恢复策略）

Answer 4

class Haystack {//whatever
 };
class Needle {//whatever
 }:
class Searcher {
   virtual void find() = 0;
};

class HaystackSearcher::public Searcher {
public:
   HaystackSearcher(Haystack, object)
   virtual void find();
};

Haystack H;
Needle N;
HaystackSearcher HS(H, N);
HS.find();

Answer 5

干草堆可以装东西
一种东西是针
finder 是负责搜索东西的东西
finder 可以接受一堆东西作为在哪里找到东西的来源
finder 还可以接受需要查找的事物的内容描述，

因此，最好，对于灵活的解决方案，您可以执行以下操作：
IStuff 接口

Haystack = IList;
针：IStuff

Finder
.Find(IStuff stuffToLookFor, IListstuffsToLookIn)

在这种情况下，您的解决方案将不仅仅局限于针和干草堆，而是可用于实现该接口的任何类型，

因此如果您想在海洋中找到鱼，你可以。

var results = Finder.Find(鱼，海洋)

Answer 6

您还有第四种选择，我认为它比选择 3 更好：

haystack.find(针，搜索器)

我明白您的观点，但是如果 searcher 实现一个搜索接口，允许搜索除干草堆之外的其他类型的对象，并查找其他对象，该怎么办？里面有比针还多的东西？

该接口也可以使用不同的算法来实现，例如：

binary_searcher.find(needle, haystack)
vision_searcher.find(pitchfork, haystack)
brute_force_searcher.find(money, wallet)

但是，正如其他人已经指出的那样，我也认为这只有在您实际上有多个搜索算法或多个可搜索或可查找类时才有用。 如果不是，我同意 haystack.find(needle) 更好，因为它简单，所以我愿意为此牺牲一些“正确性”。

Answer 7

简单：烧掉干草堆！ 之后，只剩下针了。 另外，你可以尝试磁铁。

一个更难的问题：如何在一堆针中找到一根特定的针？

答案：将每个线程串起来，并将每串线程的另一端附加到排序索引（即指针）

Answer 8

确实是 2 和 3 的混合。

有些干草堆没有专门的搜索策略； 数组就是一个例子。 找到某些东西的唯一方法是从头开始并测试每个项目，直到找到您想要的。

对于这种事情，自由函数可能是最好的（如 C++）。

有些干草堆可以采用专门的搜索策略。 数组可以排序，例如允许您使用二分搜索。 一个自由函数（或一对自由函数，例如排序和binary_search）可能是最好的选择。

一些干草堆有一个集成的搜索策略作为其实施的一部分； 例如，关联容器（散列或有序集和映射）都可以。 在这种情况下，find可能是一个必不可少的查找方法，因此它可能应该是一个方法，即haystack.find(needle)。

Answer 9

这完全取决于什么变化和什么保持不变。

例如，我正在开发一个（非 OOP）框架，其中查找算法根据两者的不同而不同针和大海捞针的类型。 除了在面向对象的环境中需要双重调度这一事实之外，这还意味着编写 needle.find(haystack) 或编写 haystack 没有意义.find(针)。

另一方面，您的应用程序可以愉快地将查找委托给两个类中的任何一个，或者完全坚持使用一种算法，在这种情况下，决策是任意的。 在这种情况下，我更喜欢 haystack.find(needle) 方式，因为将发现应用到 haystack 似乎更合乎逻辑。

Answer 10

当实施针搜索时
以面向对象的方式进行干草堆，
你基本上有三个
替代方案：

1. needle.find(haystack)

2. haystack.find(针)

3. searcher.find(针，干草堆)

你更喜欢哪一个，为什么？

如果我错了，请纠正我，但在所有三个示例中，您已经拥有对您正在寻找的针的引用，所以这不是有点像在坐着时寻找您的眼镜吗在你的鼻子上吗？ ：p

双关语放在一边，我认为这实际上取决于您认为 haystack 在给定域内的责任。 我们是否只关心它是一个包含针的东西（本质上是一个集合）？ 那么 haystack.find(needlePredicate) 就可以了。 否则， farmBoy.find(predicate, haystack) 可能更合适。

Answer 11

引用 SICP 的伟大作者的话，

程序必须是为供人阅读，并且只是顺便供机器执行

我更喜欢同时拥有方法 1 和 2。 以 ruby​​ 为例，它带有 .include? ，这样使用

haystack.include? needle
=> returns true if the haystack includes the needle

有时，纯粹出于可读性的原因，我想翻转它。 Ruby 没有提供 in? 方法，但它是一个单行代码，所以我经常这样做：

needle.in? haystack
=> exactly the same as above

如果强调 haystack 或搜索操作“更重要”，我更喜欢编写include?。
但通常情况下，干草堆或搜索都不是您真正关心的，只是对象存在 - 在这种情况下，我发现 in? 更好地传达了程序的含义。

Answer 12

这取决于您的要求。

例如，如果您不关心搜索者的属性（例如搜索者的力量、视力等），那么我会说 haystack.find(needle) 将是最干净的解决方案。

但是，如果您确实关心搜索器的属性（或与此相关的任何其他属性），我会将 ISearcher 接口注入到 haystack 构造函数或函数中以促进这一点。 这支持面向对象的设计（大海捞针）和控制反转/依赖注入（使“查找”功能的单元测试更容易）。

Answer 13

我可以想到前两种风格中的任何一种都有意义的情况：

1. 如果针需要预处理，就像在 Knuth-Morris-Pratt 算法中一样，needle.findIn(haystack) (或pattern.findIn(text))是有道理的，因为needle对象保存了为算法有效工作而创建的中间表

2. 如果 haystack 需要预处理，比如在 trie 中，haystack.find(needle)（或 words.hasAWordWithPrefix(prefix)）可以工作更好。

在上述两种情况下，针或大海捞针之一都知道搜索。 而且，他们俩都互相了解。 如果您希望针和干草堆不知道彼此或搜索，searcher.find(needle, haystack) 是合适的。

Answer 14

还有另一种选择，就是 C++ 的 STL 使用的方法：

find(haystack.begin(), haystack.end(), needle)

我认为这是 C++ 大喊“在你面前！”的一个很好的例子。 面向对象编程。 这个想法是，OOP 并不是任何一种灵丹妙药；它只是一种灵丹妙药。 有时事物最好用动作来描述，有时用物体来描述，有时两者都不是，有时两者都是。

Bjarne Stroustrup 在 TC++PL 中说，当你设计一个系统时，你应该努力在有效且高效的代码约束下反映现实。 对我来说，这意味着你永远不应该盲目地遵循任何事情。 想想手头的事情（干草堆、针）和我们所处的上下文（搜索，这就是这个表达的意思）。

如果强调的是搜索，那么使用强调搜索的算法（动作）（即灵活地适应干草堆、海洋、沙漠、链表）。 如果重点是 haystack，则将 find 方法封装在 haystack 对象内部，以此类推。

也就是说，有时你会犹豫不决，很难做出选择。 在这种情况下，要面向对象。 如果您稍后改变主意，我认为从对象中提取操作然后将操作拆分为对象和类更容易。

遵循这些准则，您的代码将会更加清晰，而且更加美观。

Answer 15

这么多的答案，但其中许多似乎假设了很多关于搜索发生的情况（或者完全忽略它们，这与假设它们总是相同的相同）

这并不是（很大程度上）基于“纯粹”理论和更多的实践经验：

这取决于搜索/查找算法特定于什么

一个类应该“了解”特定于其自身的事物。
这意味着，如果搜索干草堆需要特定于干草堆的方法，特别是如果该方法可以更好地适应干草堆的特定实例，那么搜索方法应该是干草堆：

haystack.searchthishaystack(needle)
# Gets a description of what to look for and knows best how to efficiently
# iterate through this particular haystack

如果你的干草堆完全可以直接搜索任何对干草堆一无所知的算法，但你的针很难检测到，那么当然是针应该知道如何找出它在哪里：

    needle.findyourself_in(haystack)
    # unnecessary if it's really just a large number of objects that need
    # to be tested for identity with the `needle` object.
    # But maybe needles affect some of the haystack around them? If there
    # is some metaphorical magnet that can help traverse the haystack
    # quicker, then the needle (or its `metal_objects` superclass) should be
    # where it's defined.

前两个也可以以组合形式发生，在这种情况下，搜索算法必须分解：

    haystack.search(needle, detector=needle.detector)
    # The haystack contains a haystack-specific search pattern, but the
    # needle provides a needle-specific "detector" which provides information
    # about whether the search is moving closer or further from it, and at
    # which distance it is going to snap to the magnet. That information
    # should help speed things up.

那么也可能存在这样的情况：您有多个同一类但具有不同属性的对象，并且您正在尝试查找其他“匹配”的针“以特定方式参考针。 然后“needle”对象应该包含检查其他针是否匹配的方法。

    haystack.search(tester=needle.match_test)
    # this is very similar to the `needle.detector` case but concerns only
    # the task of checking whether a particular object matches the search
    # criteria or not

那么什么时候拥有 searcher 对象很有用呢？ ...显然，如果有关于我想如何在代码中搜索内容的具体内容！
就像，也许我们需要限制搜索活动以避免

    specific_searcher = searchlib.define_searcher(how_we_search_around_here)
    specific_searcher.search(where=haystack, what=needle)
    ...
    specific_searcher.search(where=szechwan, what=good_person)
    # now the searcher object contains specific information/knowledge about
    # something that is relevant in my code, and that makes it useful.

如果搜索干草堆或检测/识别针没有什么具体或特别的地方，那么实际上没有必要为任何事情创建特定于实例的方法。
在这种情况下，我不喜欢将动词转换为名词，其唯一目的是告诉名词动词：

    searcher = searchlib.define_searcher()
    searcher.search(where=haystack, what=needle)
    # Don't think this makes anything easier to read/type/understand/debug...
    # worse: If I see `searcher.search()`, I need to figure out the 
    # difference between this specific `searcher` object's `search' method
    # and any old generic search before I know what it does.
    # (Spoiler: there is no difference, but you can't be sure right away)

...相反，直接的方法是简单地陈述命令和参数：

    searchlib.search(where=haystack, what=needle)
    # plain, generic search for a generic object with a generic algorithm.
    # assumes that `haystack` is some generic iterable which yields objects
    # that are compared to `needle`
    # might be slower than a magnet but if all I have is a pitchfork,
    # this is the straightforward way.

Answer 16

在这一点上我和布拉德是一致的。 我在极其复杂的系统上工作得越多，我就越意识到真正解耦对象的必要性。 他是对的。 很明显，针不应该知道有关 haystack 的任何信息，因此 1 肯定会出局。 但是，干草堆应该对针一无所知。

如果我正在建模一个干草堆，我可能会将其实现为一个集合 - 但作为干草或稻草的集合 - 而不是针的集合！ 然而，我会考虑到东西确实会在大海捞针中丢失，但我对那些东西到底是什么一无所知。 我认为最好不要让干草堆本身寻找项目（无论如何智能是一个干草堆）。 对我来说，正确的方法是让干草堆呈现其中的一系列东西，但不是稻草或干草或任何赋予干草堆本质的东西。

class Haystack : ISearchableThingsOnAFarm {
   ICollection<Hay> myHay;
   ICollection<IStuffSmallEnoughToBeLostInAHaystack> stuffLostInMe;

   public ICollection<Hay> Hay {
      get {
         return myHay;
      }
   }

   public ICollection<IStuffSmallEnoughToBeLostInAHayStack> LostAndFound {
      get {
        return stuffLostInMe;
      }
   }
}

class Needle : IStuffSmallEnoughToBeLostInAHaystack {
}

class Farmer {
  Search(Haystack haystack, 
                 IStuffSmallEnoughToBeLostInAHaystack itemToFind)
}

实际上，我要输入更多内容并将其抽象为接口，然后我意识到我变得多么疯狂。 感觉就像我在大学的计算机科学课上...:P

你明白了。 我认为尽可能松散耦合是一件好事，但也许我有点得意忘形了！ :)

Answer 17

我想说，选项 1 完全不可行。 代码的阅读方式应该告诉您它的作用。 选项一让我觉得这根针会帮我找到大海捞针。

如果干草堆是用来装针的，那么选项 2 看起来不错。 ListCollections 总是包含 ListItems，因此 collection.find(item) 是自然且富有表现力的。

我认为在以下情况下引入辅助对象是合适的：

1. 您无法控制相关对象的实现
   IE：search.find(ObsecureOSObject, file)
2. 对象之间没有常规或合理的关系
   IE：nameMatcher.find(房屋，树木.名称)

Answer 18

在这三者中，我更喜欢选项#3。

单一职责原则让我不想在我的 DTO 或模型上添加搜索功能。 他们的责任是成为数据，而不是找到自己，针也不应该知道大海捞针，大海捞针也不应该知道针。

无论如何，我认为大多数面向对象实践者需要很长时间才能理解为什么#3 是最佳选择。 在我真正理解它之前，我可能已经研究了 OO 十年。

@wilhelmtell，C++ 是极少数具有模板专业化的语言之一，可以使这样的系统真正运行。 对于大多数语言来说，通用的“查找”方法将是一个可怕的想法。

Answer 19

@彼得·迈耶

你明白了。 我认为尽可能松散耦合是一件好事，但也许我有点得意忘形了！ :)

呃...是的...我认为 IStuffSmallEnoughToBeLostInAHaystack 是一个危险信号:-)

Answer 20

就我个人而言，我喜欢第二种方法。 我的理由是因为我使用过的主要 API 都使用这种方法，而且我发现它最有意义。

如果你有一个东西列表（干草堆），你会搜索（find()）针。

Answer 21

如果 Needle 和 Haystack 都是 DAO，那么选项 1 和 2 就不可能了。

原因是 DAO 应该只负责保存它们正在建模的现实世界对象的属性，并且只有 getter 和 setter 方法（或者只是直接属性访问）。 这使得将 DAO 序列化到文件或创建通用比较/通用副本的方法更容易编写，因为代码不会包含一大堆“if”语句来跳过这些辅助方法。

只剩下选项 3，大多数人都认为这是正确的行为。

选项 3 有一些优点，其中最大的优点是单元测试。 这是因为 Needle 和 Haystack 对象现在都可以轻松模拟，而如果使用选项 1 或 2，则必须在执行搜索之前修改 Needle 或 Haystack 的内部状态。

其次，由于搜索器现在处于单独的类中，因此所有搜索代码都可以保存在一个位置，包括公共搜索代码。 然而，如果将搜索代码放入 DAO 中，则公共搜索代码要么存储在复杂的类层次结构中，要么存储在 Searcher Helper 类中。

Answer 22

haystack.find(needle)，但应该有一个搜索字段。

我知道依赖注入非常流行，所以 @Mike Stone 的 haystack.find(needle, searcher) 被接受并不让我感到惊讶。 但我不同意：在我看来，选择使用什么搜索器似乎是大海捞针的决定。

考虑两个 ISearcher：MagneticSearcher 迭代体积，以与磁体强度一致的方式移动和步进磁体。 QuickSortSearcher 将堆栈一分为二，直到其中一个子堆中出现明显的针。 搜索器的正确选择可能取决于大海捞针有多大（例如，相对于磁场）、针如何进入大海捞针（即针的位置是真正随机的还是有偏差的？）等

。你有 haystack.find(needle, searcher)，你是说“最好在干草堆的上下文之外选择最好的搜索策略。” 我认为这不太可能是正确的。 我认为更有可能的是“干草堆知道如何最好地自我搜索”。 添加设置器，如果您需要覆盖或进行测试，您仍然可以手动注入搜索器。

Answer 23

代码是试图找到特定的针还是只是任何针？ 这听起来像是一个愚蠢的问题，但它改变了问题。

寻找特定的针，问题中的代码是有意义的。 寻找任何针它会更像

needle = haystack.findNeedle()

或

needle = searcher.findNeedle(haystack)

无论哪种方式，我更喜欢有一个这样的搜索器。 干草堆不知道如何搜索。 从计算机科学的角度来看，它只是一个包含大量您不想要的垃圾的数据存储。

Answer 24

毫无疑问是第三个，恕我直言。

大海捞针的问题是试图在一大堆其他对象中找到一个对象的一个​​例子，这表明它需要一个复杂的搜索算法（可能涉及磁铁或（更有可能）子进程），但它并不需要。期望干草堆进行线程管理或实现复杂的搜索没有多大意义。

然而，搜索对象专用于搜索，并且可以期望知道如何管理子线程以进行快速二分搜索，或使用搜索元素的属性来缩小区域（即：用于查找含铁物品的磁铁） 。

Answer 25

另一种可能的方法是为可搜索对象（例如 haystack）和 ToBeSearched 对象（例如针）创建两个接口。
所以，可以用这种方式完成

public Interface IToBeSearched
{}

public Interface ISearchable
{

    public void Find(IToBeSearched a);

}

Class Needle Implements IToBeSearched
{}

Class Haystack Implements ISearchable
{

    public void Find(IToBeSearched needle)

   {

   //Here goes the original coding of find function

   }

}

Answer 26

haystack.magnet().filter(needle);

Answer 27

干草堆不应该知道针，针也不应该知道干草堆。 搜索者需要了解两者，但大海捞针是否应该知道如何搜索本身才是真正争论的焦点。

所以我会混合使用 2 和 3； 干草堆应该能够告诉其他人如何搜索它，并且搜索者应该能够使用该信息来搜索干草堆。

Answer 28

Brad Wilson 指出对象应该有单一的责任。 在极端情况下，一个对象只有一个责任，没有状态。 那么它就可以变成……一个函数。

needle = findNeedleIn(haystack);

或者你可以这样写：

SynchronizedHaystackSearcherProxyFactory proxyFactory =
    SynchronizedHaystackSearcherProxyFactory.getInstance();
StrategyBasedHaystackSearcher searcher =
    new BasicStrategyBasedHaystackSearcher(
        NeedleSeekingStrategies.getMethodicalInstance());
SynchronizedHaystackSearcherProxy proxy =
    proxyFactory.createSynchronizedHaystackSearcherProxy(searcher);
SearchableHaystackAdapter searchableHaystack =
    new SearchableHaystackAdapter(haystack);
FindableSearchResultObject foundObject = null;
while (!HaystackSearcherUtil.isNeedleObject(foundObject)) {
    try {
        foundObject = proxy.find(searchableHaystack);
    } catch (GruesomeInjuryException exc) {
        returnPitchforkToShed();  // sigh, i hate it when this happens
        HaystackSearcherUtil.cleanUp(hay); // XXX fixme not really thread-safe,
                                           // but we can't just leave this mess
        HaystackSearcherUtil.cleanup(exc.getGruesomeMess()); // bug 510000884
        throw exc; // caller will catch this and get us to a hospital,
                   // if it's not already too late
    }
}
return (Needle) BarnyardObjectProtocolUtil.createSynchronizedFindableSearchResultObjectProxyAdapterUnwrapperForToolInterfaceName(SimpleToolInterfaces.NEEDLE_INTERFACE_NAME).adapt(foundObject.getAdaptable());

Answer 29

通常，操作应该应用于您正在执行的操作...在本例中是干草堆，所以我认为选项 2 是最合适的。

您还有第四种替代方案，我认为它比替代方案 3 更好：

haystack.find(needle, searcher)

在这种情况下，它允许您提供要作为操作一部分进行搜索的方式，这样您就可以将操作与以下对象保持一致：正在手术中。

Answer 30

如果您有对 Needle 对象的引用，为什么要搜索它？ :)
问题域和用例告诉您，您不需要大海捞针的确切位置（就像您可以从 list.indexOf(element) 获得的那样），您只需要一根针。 而你还没有。 所以我的答案是这样的

Needle needle = (Needle)haystack.searchByName("needle");

，或者

Needle needle = (Needle)haystack.searchWithFilter(new Filter(){
    public boolean isWhatYouNeed(Object obj)
    {
        return obj instanceof Needle;
    }
});

我

Needle needle = (Needle)haystack.searchByPattern(Size.SMALL, 
                                                 Sharpness.SHARP, 
                                                 Material.METAL);

同意有更多可能的解决方案基于不同的搜索策略，所以他们引入了搜索器。 这方面的评论已经够多了，这里就不关注了。 我的观点是，上面的解决方案忘记了用例——如果您已经参考过某个东西，那么搜索它还有什么意义呢？
在最自然的用例中，您还没有针，因此您不使用可变针。