oop - 你如何在大海捞针中找到一根针？

Question

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

1. needle.find(haystack)

2. haystack.find(needle)

3. searcher.find(needle, haystack)

你更喜欢哪个？为什么？

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

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

score 55 · Accepted Answer

在这三个中，我更喜欢选项＃3。

单一职责原则使我不想将搜索功能放在我的 DTO 或模型上。他们的责任是做数据，而不是找到自己，针也不应该知道干草堆，干草堆也不应该知道针。

对于它的价值，我认为大多数 OO 从业者需要很长时间才能理解为什么 #3 是最佳选择。在我真正摸索它之前，我可能已经做了 OO 十年了。

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

score 53 · Accepted Answer

通常应该将操作应用于您正在执行的操作...在这种情况下是大海捞针，所以我认为选项 2 是最合适的。

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

haystack.find(needle, searcher)

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

score 16 · Accepted Answer

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

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

我认为这是 C++ 大喊“当着你的脸！”的一个很好的例子。到面向对象。这个想法是，OOP 不是任何类型的灵丹妙药。有时事物最好用行动来描述，有时用对象来描述，有时两者都不是，有时两者兼而有之。

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

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

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

遵循这些准则，你的代码会更清晰，更漂亮。

score 15 · Accepted Answer

我会说选项1完全没有。代码应该以一种告诉你它做什么的方式阅读。选项 1 让我觉得这根针会帮我找个干草堆。

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

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

您不控制有问题的对象的实现
IE：search.find(ObsecureOSObject, file)
对象 IE 之间没有常规或合理的关系
：nameMatcher.find(houses,trees.name)

score 11 · Accepted Answer

我和布拉德在一起。我在极其复杂的系统上工作得越多，我就越觉得需要真正解耦对象。他是对的。很明显，针不应该对干草堆一无所知，所以 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

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

score 6 · Accepted Answer

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

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

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

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

其次，搜索器现在在一个单独的类中，所有搜索代码都可以保存在一个地方，包括公共搜索代码。而如果将搜索代码放入 DAO 中，常见的搜索代码要么存储在复杂的类层次结构中，要么存储在 Searcher Helper 类中。

score 5 · Accepted Answer

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

例如，我正在研究一个（非 OOP）框架，其中查找算法因针和干草堆的类型而异。除了这需要在面向对象的环境中进行双重分派之外，这还意味着编写要么要么needle.find(haystack)编写haystack.find(needle).

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

score 5 · Accepted Answer

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

needle.find（干草堆）

haystack.find（针）

searcher.find（针，干草堆）

你更喜欢哪个？为什么？

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

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

score 4 · Accepted Answer

引用SICP的伟大作者的话，

必须编写程序供人们阅读，并且只是偶然地供机器执行

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

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

但有时，纯粹出于可读性的原因，我想把它翻过来。Ruby 没有自带in?方法，但它是单行的，所以我经常这样做：

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

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

score 3 · Accepted Answer

这取决于您的要求。

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

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

score 3 · Accepted Answer

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

如果针需要预处理，例如在 Knuth-Morris-Pratt 算法中，needle.findIn(haystack)（或pattern.findIn(text)）是有意义的，因为针对象包含为算法有效工作而创建的中间表
如果 haystack 需要预处理，比如在 trie 中，haystack.find(needle)(or words.hasAWordWithPrefix(prefix)) 效果更好。

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

score 2 · Accepted Answer

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

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

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

score 2 · Accepted Answer

真的是2和3的混合。

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

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

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

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

score 2 · Accepted Answer

这个问题的答案实际上应该取决于实施解决方案的领域。
如果您碰巧在物理大海捞针中模拟物理搜索，您可能有这些类

空间
稻草
针
寻找者

空间
知道哪些物体位于哪个坐标
执行自然法则（转换能量、检测碰撞等）

针、稻草
位于空间
对力作出反应

探索者
与空间互动：
移动手、施加磁场、燃烧干草、施加 X 射线、寻找针头……

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

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

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

但是矩阵是域，如果你的针不能在其他任何地方，它应该只被干草堆代替。

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

制作能够找到自己的针，例如他们经常问自己：我迷路了吗？如果答案是肯定的，他们会将 GPS 计算的位置发送给某人或开始发出哔哔声或其他任何东西：
needle.find(space)或needle.find(haystack) （解决方案 1）
在每根稻草上安装一个带有摄像头的干草堆，然后您可以询问干草堆蜂巢思维是否最近看到了针：
haystack.find(needle) （解决方案 2）
将 RFID 标签贴在您的针上，这样您就可以轻松地对它们进行三角测量

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

所以根据你的域来决定：

干草堆的目的是容纳针头吗？然后去解决方案2。
针在任何地方丢失是自然的吗？然后去解决方案1。
针会不小心丢进大海捞针吗？然后寻求解决方案 3。（或考虑另一种恢复策略）

score 2 · Accepted Answer

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

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

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

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

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

@彼得迈耶

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

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

score 1 · Accepted Answer

您还有第四个替代方案，我认为它比替代方案 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)它的简单性更好，所以我愿意为它牺牲一些“正确性”。

score 1 · Accepted Answer

1

haystack.magnet().filter(needle);

于 2008-08-24T22:58:36.250 回答

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

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();

score 1 · Accepted Answer

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

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

needle = haystack.findNeedle()

或者

needle = searcher.findNeedle(haystack)

无论哪种方式，我更喜欢有一个搜索器类。干草堆不知道如何搜索。从 CS 的角度来看，它只是一个包含大量您不想要的废话的数据存储。

score 1 · Accepted Answer

haystack 可以包含东西一种东西是 needle finder 是负责搜索东西的东西 finder 可以接受一堆东西作为在哪里找到东西的来源 finder 也可以接受它需要找到的东西的东西描述

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

干草堆 = IList<IStuff> 针：IStuff

Finder .Find(IStuff stuffToLookFor, IList<IStuff> stuffsToLookIn)

在这种情况下，您的解决方案不会仅仅依赖于 needle 和 haystack，而是可用于实现接口的任何类型

所以如果你想在海洋中找到一条鱼，你可以。

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

score 1 · Accepted Answer

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

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

score 1 · Accepted Answer

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());

score 0 · Accepted Answer

绝对是第三个，恕我直言。

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

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

score 0 · Accepted Answer

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

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

   }

}

score 0 · Accepted Answer

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

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

score 0 · Accepted Answer

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

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

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

oop - 你如何在大海捞针中找到一根针？

29 回答 29

Related

Reference