Как вы находите иголку в стоге сена?

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

@wilhelmtell, C++ - один из немногих языков со специализацией шаблонов, которые делают такую ​​систему действительно работающей. Для большинства языков универсальный метод поиска будет УЖАСНОЙ идеей.

Answer 3

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

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

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

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

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

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

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

Answer 4

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

Вариант 2 выглядит хорошо, если в стоге сена должны быть иглы. ListCollections всегда будет содержать ListItems, поэтому выполнение collection.find (item) является естественным и выразительным.

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

1. Вы не контролируете реализацию рассматриваемых объектов
   IE: search.find(ObsecureOSObject, file)
2. Между объектами нет регулярных или разумных отношений
   IE: nameMatcher.find(дома, деревья.имя)

Answer 5

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

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

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

Если Игла и Хейстек являются DAO, то варианты 1 и 2 исключены.

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

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

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

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

Answer 7

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

1. needle.find (стог)

2. haystack.find (иглы)

3. searcher.find (иголка, стог сена)

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

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

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

Answer 8

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

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

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

Answer 9

По словам великих авторов 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? лучше передает смысл программы.

Answer 10

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

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

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

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

Answer 11

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

Например, если вас не волнуют свойства искателя (например, сила искателя, зрение и т. Д.), То я бы сказал, что haystack.find(игла) будет самым чистым решением.

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

Answer 12

Сочетание 2 и 3, действительно.

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

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

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

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

Answer 13

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

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

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

Answer 14

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

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

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

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

Answer 15

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

• Космос
• Солома
• игла
• Искатель

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

Игла, Солома
расположены в космосе
реагировать на силы

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

таким образом seeker.find(needle, space) или же seeker.find(needle, space, strategy)

Стог сена просто случается в том месте, где вы ищете иглу. Когда вы абстрагируете пространство как виртуальную машину (представьте: матрицу), вы можете получить вышеупомянутое с помощью стога сена вместо пространства (решение 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 16

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

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

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

Finder.Find (IStuff stuffToLookFor, IList stuffsToLookIn)

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

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

var results = Finder.Find (рыба, океан)

Answer 17

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 18

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

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

Answer 19

haystack.magnet().filter(needle);

Answer 20

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

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

needle = haystack.findNeedle()

или же

needle = searcher.findNeedle(haystack)

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

Answer 21

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

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 22

Если у вас есть ссылка на объект иглы, почему вы ищете его?:) Проблемная область и сценарии использования говорят вам, что вам не нужно точное положение иглы в стоге сена (например, что вы можете получить из 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 23

У вас также есть четвертый вариант, который, я думаю, будет лучше, чем вариант 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 24

Хейстек не должен знать о иголке, а иголка не должна знать о стоге сена. Поисковик должен знать об обоих, но реальный момент спора - должен ли стог сена знать, как искать себя.

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

Answer 25

@ Питер Мейер

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

Э-э-э... да... я думаю IStuffSmallEnoughToBeLostInAHaystack вид это красный флаг:-)

Answer 26

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

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

Эта статья хорошо описывает такие сценарии.

Answer 27

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 28

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

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

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

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