如何大海捞针？

Question

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

1. needle.find(haystack)

2. haystack.find(needle)

3. searcher.find(needle, haystack)

你更偏向于哪个，为什么？

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

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

Answer 1

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

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

haystack.find(needle, searcher)

在这种情况下，它允许您提供希望作为操作一部分进行搜索的方式，因此您可以将操作与正在操作的对象一起保留。

Answer 2

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

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

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

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

Answer 3

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

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

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

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

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

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

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

Answer 4

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

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

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

1. 您无法控制相关对象的实现
   IE：搜索.find（ObsecureOSObject，文件）
2. 对象之间不存在规则或合理的关系
   IE：nameMatcher.find(房屋,树木.名称)

Answer 5

在这一点上我和布拉德是一致的。我在极其复杂的系统上工作得越多，我就越意识到真正解耦对象的必要性。他是对的。很明显，针不应该知道有关 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)
}

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

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

Answer 6

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

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

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

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

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

Answer 7

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

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

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

Answer 8

在以面向对象的方式实施针对干草堆的针头搜索时，您实际上有三个替代方法：

1. 针.find（干草堆）

2. haystack.find(针)

3. searcher.find（针，干草堆）

你更偏向于哪个，为什么？

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

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

Answer 9

引用伟大作家的话 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

如果强调大海捞针或搜索操作“更重要”，我更喜欢写 include?。但通常情况下，干草堆或搜索都不是你真正关心的，只是对象存在 - 在这种情况下我发现 in? 更好地传达了节目的意思。

Answer 10

这取决于您的要求。

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

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

Answer 11

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

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

2. 如果干草堆需要预处理，就像在特里树中一样， haystack.find(needle) （或者 words.hasAWordWithPrefix(prefix)）效果更好。

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

Answer 12

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

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

回答：线程化每个线程并将每条线程的另一端附加到排序索引（即指针）

Answer 13

这个问题的答案实际上应该取决于解决方案实施的领域。
如果您碰巧在物理干草堆中模拟物理搜索，您可能会拥有以下类

• 空间
• 稻草
• 针
• 探索者

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

针, 稻草
位于太空
对力量做出反应

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

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

大海捞针恰好就在你寻找针的地方。当您将空间抽象为一种虚拟机时（想想：矩阵）你可以用 haystack 而不是 space 得到上面的内容 （解决方案 3/3b）:

seeker.find(needle, haystack) 或者 seeker.find(needle, haystack, strategy)

但矩阵是领域，如果你的针不能在其他地方，它只能被干草堆取代。

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

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

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

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

这只是说在你的实施中 你 在某种层面上制作了针和大海捞针以及大多数时候的矩阵。

所以根据您的域来决定：

• 干草堆的目的是为了装针吗？然后转到解决方案 2。
• 针随处丢失是自然现象吗？然后去解决方案1。
• 针会不会不小心掉进大海里了？然后转到解决方案 3。（或考虑另一种恢复策略）

Answer 14

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

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

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

如果您有haystack.find（针，搜索者），则说“选择最好的搜索策略是在干草堆的上下文之外完成的。”我认为这可能是不正确的。我认为“ Haystacks知道如何最好地寻找自己”。添加一个设置器，如果需要覆盖或进行测试，仍然可以手动注入搜索器。

Answer 15

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

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

Answer 16

@彼得·迈耶

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

呃……是的...我觉得 IStuffSmallEnoughToBeLostInAHaystack 有点是危险信号:-)

Answer 17

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

haystack.find(needle, searcher)

我明白你的意思，但是如果 searcher 实现一个搜索接口，允许搜索除干草堆之外的其他类型的对象，并在其中找到除针之外的其他东西？

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

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

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

Answer 18

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 19

确实是 2 和 3 的混合。

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

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

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

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

Answer 20

干草堆可以包含东西，一种类型的东西是针头查找器，是负责搜索物品的东西，发现器可以接受一堆东西，因为找到东西的来源，查找器也可以接受需要找到的东西的东西描述

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

Haystack = iListu003CIStuff>针：我的东西

finder .find（istuff squittolookfor，iListu003CIStuff> Stuffstolookin）

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

因此，如果您想在海洋中找到一条鱼，您就可以做到。

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

Answer 21

如果您有对 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);

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

Answer 22

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 23

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

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

Answer 24

haystack.magnet().filter(needle);

Answer 25

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

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

needle = haystack.findNeedle()

或者

needle = searcher.findNeedle(haystack)

不管怎样，我更喜欢在这门课上有一个搜索者。干草堆不知道如何搜索。从计算机科学的角度来看，它只是一个包含大量您不想要的垃圾的数据存储。

Answer 26

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

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

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

Answer 27

另一种可能的方法是为可搜索对象创建两个接口，例如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 28

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

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

Answer 29

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

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

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