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

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

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

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

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

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

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

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

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

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

Обычно действия следует применять к тому, что вы делаете, в данном случае - к стогу сена, поэтому я думаю, что вариант 2 является наиболее подходящим.

У вас также есть четвертая альтернатива, которая, я думаю, будет лучше, чем альтернатива 3:

haystack.find(needle, searcher)

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

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

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

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

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

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

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

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

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

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

Как бы то ни было, я думаю, большинству практикующих ОО требуется ДОЛГОЕ время, чтобы понять, почему № 3 - лучший выбор. Я занимался объектно-ориентированным дизайном в течение десяти лет, прежде чем по-настоящему понял это.

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

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

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

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

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

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

Процитирую великих авторов SICP,

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

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

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

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

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

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

@Peter Meyer

You get the idea. I think going as loosely coupled as possible is a good thing, but maybe I was getting a bit carried away! :)

Эээ ... да ... Я думаю, что IStuffSmallEnoughToBeLostInAHaystack - это красный флаг :-)

You also have a fourth alternative that I think would be better than alternative 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) лучше из-за своей простоты, поэтому я готов пожертвовать некоторой "правильностью" ради него.

When implementing a needle search of a haystack in an object-oriented way, you essentially have three alternatives:

1. needle.find(haystack)

2. haystack.find(needle)

3. searcher.find(needle, haystack)

Which do you prefer, and why?

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

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

haystack.magnet().filter(needle);

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

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

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

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

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

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), вероятно, лучший вариант.

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

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

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

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

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

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

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

needle = haystack.findNeedle()

или же

needle = searcher.findNeedle(haystack)

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

Если и Needle, и Haystack являются DAO, то варианты 1 и 2 исключены.

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

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

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

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

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

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

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

Finder .Find (IStuff stuffToLookFor, IListstuffsToLookIn)

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

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

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

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

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

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

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

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

Таким образом, 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. (или рассмотрите другую стратегию восстановления)

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

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

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

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

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

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

Однозначно третье, ИМХО.

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

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

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

   }

}

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

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

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

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