Как найти иголку в стоге сена?

из трех, я предпочитаю вариант № 3.

The Принцип Единой Ответственности заставляет меня не хотеть ставить возможности поиска на мои DTOs или модели. Их обязанность-быть данными, а не находить себя, и иголки не должны знать о стогах сена, а стога сена не должны знать о иголках.

для чего это стоит, я думаю, что большинству практиков ОО требуется много времени, чтобы понять, почему #3 является лучшим выбором. Я делал OO в течение десятилетия, вероятно, прежде чем я действительно грокнул его.

@wilhelmtell, C++ является одним из немногих языков со специализацией шаблона, которые делают такую систему реально работать. Для большинства языков метод общего назначения "найти" был бы ужасной идеей.

есть еще одна альтернатива, которая является подходом, используемым STL C++:

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

Я думаю, что это отличный пример того, как C++ кричит "в лицо!- к ОП. Идея состоит в том, что ООП-это не серебряная пуля любого рода; иногда вещи лучше всего описываются в терминах действий, иногда в терминах объектов, иногда ни то, ни другое, а иногда и то и другое.

Бьярне Страуструп сказал в TC++PL, что при проектировании системы вы должны стремиться отражать реальность под ограничения эффективного и действенного кода. Для меня это означает, что вы никогда не должны слепо следовать чему-либо. Подумайте о вещах под рукой (стог сена, Игла) и контекст, в котором мы находимся (поиск, вот о чем это выражение).

если акцент делается на поиске, то с помощью алгоритма (действия), который подчеркивает поиск (т. е. гибко подходит для стогов сена, океанов, пустынь, связанных списков). Если акцент делается на стоге сена, инкапсулируйте метод find внутри объект стога сена, и так далее.

тем не менее, иногда вы сомневаетесь и тяжело сделать выбор. В этом случае будьте объектно-ориентированными. Если вы передумаете позже, я думаю, что легче извлечь действие из объекта, а затем разделить действие на объекты и классы.

следуйте этим рекомендациям, и ваш код будет более четким и, ну, более красивым.

Я бы сказал, что Вариант 1 полностью вышла. Код должен читать таким образом, чтобы он говорил вам, что он делает. Вариант 1 заставляет меня думать, что эта игла собирается найти мне стог сена.

Вариант 2 выглядит хорошо, если стог сена должен содержать иглы. ListCollections всегда будут содержать ListItems, так что делать коллекцию.находка (предмет) естественна и выразительна.

Я думаю, что введение вспомогательного объекта уместно, когда:

1. вы не контролируйте реализацию рассматриваемых объектов
   Т. е.: поиск.найти (ObsecureOSObject, file)
2. нет регулярной или разумной связи между объектами
   Т. е.: nameMatcher. find(дома,trees.name)

Я с Брэдом на эту. Чем больше я работаю над чрезвычайно сложными системами, тем больше я вижу необходимость действительно отделить объекты. Он прав. Очевидно, что иголка ничего не должна знать о стоге сена, поэтому я определенно вышел. Но стог сена не должен ничего знать об игле.

если бы я моделировал стог сена, я мог бы реализовать его как коллекцию - но как коллекцию Сенной или соломы -- не коллекция иголок! Тем Не Менее, Я я бы принял во внимание, что материал действительно теряется в стоге сена, но я ничего не знаю о том, что именно это вещество. Я думаю, что лучше не заставлять стог сена искать предметы сам по себе (как умный это все равно стог сена). Правильный подход ко мне заключается в том, чтобы стог сена представлял собой набор вещей, которые находятся в нем, но не являются соломой или сеном или тем, что придает стогу сена его сущность.

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

вы поняли идею. Я думаю, что идти как можно более свободно - это хорошо, но, может быть, я немного увлекся! :)

Если и Игла, и стог сена являются DAOs, то о вариантах 1 и 2 не может быть и речи.

причина этого заключается в том, что DAOs должны отвечать только за сохранение свойств объектов реального мира, которые они моделируют, и иметь только методы getter и setter (или просто прямой доступ к свойствам). Это упрощает сериализацию DAOs в файл или создание методов для общего сравнения / общей копии, так как код не будет содержать целую кучу операторов " if пропустите эти вспомогательные методы.

Это просто оставляет вариант 3, который большинство согласится быть правильным поведением.

Вариант 3 имеет несколько преимуществ, причем самым большим преимуществом является модульное тестирование. Это связано с тем, что теперь и Игла, и стог сена могут быть легко высмеяны, тогда как если бы использовался вариант 1 или 2, внутреннее состояние иглы или стога сена должно было бы быть изменено до того, как можно было бы выполнить поиск.

во-вторых, с поисковиком теперь в a отдельный класс, весь код поиска можно держать в одном месте, включая общий код поиска. В то время как если бы код поиска был помещен в DAO, общий код поиска был бы либо сохранен в сложной иерархии классов, либо с помощью вспомогательного класса Searcher.

это полностью зависит от того, что меняется и что остается неизменным.

например, я работаю над a (non-OOP) рамки где алгоритм поиска отличается в зависимости как от типа иглы, так и от стога сена. Помимо того, что это потребует двойной отправки в объектно-ориентированной среде, это также означает, что не имеет смысла писать либо needle.find(haystack) и писать haystack.find(needle).

С другой стороны, ваше приложение может счастливо делегировать поиск в любой из обоих классов или придерживаться одного алгоритма в целом, и в этом случае решение является произвольным. В таком случае, я бы предпочел haystack.find(needle) путь, потому что кажется более логичным применить находку к стогу сена.

при реализации поиска иглы a стог сена в объектно-ориентированном виде, по существу есть три альтернативы:

1. игла.найти (стог сена)

2. сена.найти (игла)

3. искатель.найти (иголка, стог сена)

что вы предпочитаете, и почему?

поправьте меня, если я ошибаюсь, но во всех трех примерах вы уже есть ссылка на иглу, которую вы ищете, так что это не похоже на поиск ваших очков, когда они сидят на вашем носу? : p

Каламбур в сторону, я думаю, что это действительно зависит от того, что вы считаете ответственность стога сена, чтобы быть в пределах данного домена. Мы просто заботимся об этом в том смысле, что это вещь, которая содержит иглы (коллекция, по существу)? Потом стог сена.найти(needlePredicate) - это нормально. В противном случае, фермер.найти (предикат, стог сена) может быть более подходящим.

цитировать великих авторов SICP,

программы должны быть написаны для людей, чтобы читать, и только случайно для машин, чтобы выполнить

Я предпочитаю иметь оба метода 1 и 2 на руке. Используя ruby в качестве примера, он поставляется с .include? который используется так

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

иногда, хотя, чисто по причинам читаемости,я хочу перевернуть его. Руби не приходит с in? способ, но это один-лайнер, так что я часто делают так:

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

если" важнее " подчеркнуть стог сена или операцию поиска, я предпочитаю писать include?. Часто, однако, ни стог сена, ни поиск-это действительно то, что вас волнует, только то, что объект присутствует - в этом случае я нахожу in? лучше передает смысл программы.

Это зависит от ваших требований.

например, если вы не заботитесь о свойствах искателя (например, сила искателя, зрение и т. д.), то я бы сказал стог сена.найти (игла) было бы самым чистым решением.

но, если вы заботитесь о свойствах Искателя (или любых других свойствах в этом отношении), я бы ввел интерфейс ISearcher в конструктор haystack или функцию, чтобы облегчить это. Это поддерживает оба объектно-ориентированных дизайн (стог сена имеет иглы) и инверсия инъекции управления / зависимости (облегчает модульное тестирование функции "Найти").

Я могу думать о ситуациях, когда любой из первых двух вкусов имеет смысл:

1. если игла нуждается в предварительной обработке, как в алгоритме Кнута-Морриса-Пратта,needle.findIn(haystack) (или pattern.findIn(text)) имеет смысл, потому что объект иглы содержит промежуточные таблицы, созданные для эффективной работы алгоритма

2. если стог сена нуждается в предварительной обработке, как говорят в trie, то haystack.find(needle) (или words.hasAWordWithPrefix(prefix)) работает лучше.

в обоих вышеуказанных случаях один из иголок или стога сена знает о поиске. Кроме того, они оба знают друг о друге. Если вы хотите, чтобы иголка и стог сена не знали друг о друге или о поиске, searcher.find(needle, haystack) было бы уместно.

легко: сжечь стог сена! После этого останется только игла. Кроме того, вы можете попробовать магниты.

более сложный вопрос: Как вы находите одну конкретную иглу в пуле игл?

ответ: проденьте каждый из них и прикрепите другой конец каждой нити нити к отсортированному индексу (т. е. указателям)

ответ на этот вопрос должен фактически зависеть от домена, для которого реализовано решение.
Если вы имитируете физический поиск в физическом стоге сена, у вас могут быть классы

• пробел
• соломы
• игла
• Искатель

пробел
знает, какие объекты находятся в каких координатах
реализует законы природы (преобразует энергию, обнаруживает столкновений и т. д.)

игла,соломы
расположены в пространстве
реагируйте на силы

Искатель
взаимодействует с пространством:
    двигает рукой, применяет магнитное поле, сжигает сено, применяет рентгеновские лучи, ищет иглу...

seeker.find(needle, space) или seeker.find(needle, space, strategy)

стог сена просто оказывается в том месте, где вы ищете иглу. Когда вы абстрагируетесь away space как своего рода виртуальная машина (подумайте: матрица) вы могли бы получить выше с 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 hive mind, если он видел иглу в последнее время:
  стог сена.найти (игла)(решение 2)

• прикрепить RFID метки, чтобы иглы, так что вы можете легко вычислить их

что все просто сказать, что в реализации вы сделал иголку и стог сена и большую часть времени матрицу на каком-то уровне.

так что решайте в соответствии с вашим доменом:

• это цель стога сена, чтобы содержать иглы? Затем перейдите к решению 2.
• естественно ли, что игла теряется где угодно? Затем перейдите к решению 1.
• тут игла заблудиться в стоге сена случайно? Затем перейдите к решению 3. (или рассмотрим другую стратегию восстановления)

сена.найти (игла), но там должно быть поле поиска.

Я знаю, что инъекция зависимости-это все ярость, поэтому меня не удивляет, что @Mike Stone's haystack.поиск (игла, поисковик) был принят. Но я не согласен: выбор того, какой поисковик используется, кажется мне решением для стога сена.

рассмотрим два ISearchers: MagneticSearcher перебирает объем, перемещая и шагая Магнит в соответствии с силой магнита. QuickSortSearcher делит стопку на две части, пока игла не будет видна в одном из подпайлов. Правильный выбор искателя может зависеть от того, насколько велик стог сена (например, относительно магнитного поля), как игла попала в стог сена (т. е. действительно ли положение иглы случайно или оно смещено?), прием.

Если у вас есть сена.find (игла, поисковик), вы говорите: "выбор лучшей стратегии поиска лучше всего делать вне контекста стога сена." Я не думаю, что это будет правильно. Я думаю, что более вероятно ,что " стога сена знают, как лучше всего искать себя."Добавьте сеттер, и вы все равно можете вручную ввести поисковик, если вам нужно переопределить или для тестирования.

лично мне нравится второй способ. Мои рассуждения связаны с тем, что основные API, с которыми я работал, используют этот подход, и я считаю, что это имеет наибольший смысл.

Если у вас есть список вещей (стог сена), вы будете искать (найти()) иглу.

@Peter Meyer

вы поняли идею. Я думаю, что идти как можно более свободно - это хорошо, но, может быть, я немного увлекся! :)

Errr... угу... Я думаю, что IStuffSmallEnoughToBeLostInAHaystack вид красного флага : -)

у вас также есть четвертая альтернатива, которая я думаю, будет лучше, чем вариант 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) лучше из-за его простоты, поэтому я готов пожертвовать некоторой "правильностью" для него.

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

смесь 2 и 3, На самом деле.

некоторые стога сена не имеют специализированной стратегии поиска; примером этого является массив. Единственный способ найти что-то, чтобы начать с самого начала и проверить каждый элемент, пока вы не найдете тот, который вы хотите.

для такого рода вещей, свободная функция, вероятно, лучше всего (например, C++).

некоторые стога сена могут иметь специализированную стратегию поиска, наложенную на них. Массив может быть отсортирован, что позволяет использовать двоичный поиск, для образец. Свободная функция (или пара свободных функций, например sort и binary_search), вероятно, является лучшим вариантом.

некоторые стога сена имеют интегрированную стратегию поиска как часть их реализации; ассоциативные контейнеры (хэшированные или упорядоченные наборы и карты) все это делают, например. В этом случае поиск, вероятно, является важным методом поиска, поэтому он, вероятно, должен быть методом, т. е. стогом сена.найти (игла).

стог сена может содержать вещества один тип материала игла Finder-это то, что отвечает за поиск материала finder может принять кучу материалов в качестве источника, где найти вещь finder также может принять описание вещи, которую ему нужно найти

поэтому, предпочтительно, для гибкого решения вы бы сделали что-то вроде: IStuff интерфейс

Стог Сена = IList Игла : IStuff

Искатель .Найти (IStuff stuffToLookFor, IList stuffsToLookIn)

в этом случае ваше решение не будет привязано только к игле и стогу сена, но оно может использоваться для любого типа, реализующего интерфейс

Так что если вы хотите найти рыба в океане, вы можете.

var results = Finder.Найти(рыба, океан)

Если у вас есть ссылка на объект Иглы, почему вы его ищете? :) Проблемная область и случаи использования говорят вам, что вам не нужно точное положение иглы в стоге сена (например, что вы могли бы получить из списка.indexOf (элемент)), вам просто нужна игла. А у вас его еще нет. Так что мой ответ что-то вроде этого

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

Я согласен, что есть еще возможные решения, которые основаны на различных поисковых стратегии, поэтому они вводят searcher. Было достаточно комментариев по этому поводу, поэтому я не обращаю на это внимания. Я хочу сказать, что решения выше забывают о прецедентах-какой смысл искать что-то, если у вас уже есть ссылка на него? В самом естественном случае использования у вас еще нет иглы, поэтому вы не используете переменную иглу.

Брэд Уилсон указывает, что объекты должны иметь единую ответственность. В крайнем случае, объект несет одну ответственность и не имеет государства. Тогда это может стать... функция.

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

стог сена не должен знать об игле, а игла не должна знать о стоге сена. Искатель должен знать об обоих, но должен ли стог сена знать, как искать себя, является реальной точкой соприкосновения.

поэтому я бы пошел со смесью 2 и 3; стог сена должен быть в состоянии сказать кому-то еще, как его искать, и поисковик должен иметь возможность использовать эту информацию для поиска стога сена.

haystack.magnet().filter(needle);

код пытается найти конкретную иглу или просто любую иглу? Это звучит как глупый вопрос, но это меняет проблему.

поиск конкретной иглы код в вопросе имеет смысл. Глядя на любую иглу это было бы больше похоже

needle = haystack.findNeedle()

или

needle = searcher.findNeedle(haystack)

в любом случае, я предпочитаю иметь поисковик классе. Стог сена не знает, как искать. С точки зрения CS это просто хранилище данных с большим количеством дерьма, которого вы не делаете хотеть.

определенно третий, ИМХО.

вопрос о игле в стоге сена является примером попытки найти один объект в большой коллекции других, что указывает на то, что ему потребуется сложный алгоритм поиска (возможно, с использованием магнитов или (более вероятно) дочерних процессов), и не имеет большого смысла ожидать, что стог сена будет выполнять управление потоками или осуществлять сложные поиски.

объект поиска, однако, предназначен для поиска и может быть ожидается, что вы знаете, как управлять дочерними потоками для быстрого двоичного поиска или использовать свойства искомого элемента для сужения области (например: магнит для поиска черных элементов).

другим возможным способом может быть создание двух интерфейсов для объекта поиска, например 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

   }

}

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

iterator может быть интерфейс к любой неизменяемой коллекции, с коллекциями, имеющими общие findFirst(fun: T => Boolean) метод выполнения задания. Пока стог сена остается неизменным, нет необходимости скрывать какие-либо полезные данные "извне". И, конечно же, нехорошо связывать реализацию пользовательской нетривиальной коллекции и некоторые другие вещи, которые имеют haystack. Разделяй и властвуй, хорошо?

в большинстве случаев я предпочитаю иметь возможность выполнять простые вспомогательные операции, подобные этому, на основном объекте, но в зависимости от языка у объекта, о котором идет речь, может не быть достаточного или разумного метода.

даже в таких языках, как JavaScript), которые позволяют вам увеличивать / расширять встроенные объекты, я считаю, что это может быть как удобно, так и проблематично (например, если будущая версия языка вводит более эффективный метод, который переопределяется пользовательским один.)

в этой статье делает хорошую работу по изложению таких сценариев.