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

https://stackoverflow.com/questions/23755

09-06-2019
|

Вопрос

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

1. needle.find(haystack)

2. haystack.find(needle)

3. searcher.find(needle, haystack)

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

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

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

Решение

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

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

haystack.find(needle, searcher)

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

Другие советы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вы не контролируете реализацию объектов, о которых идет речь
Т. Е.:search.find(защищенный объект, файл)
Между объектами не существует регулярной или разумной взаимосвязи
Т. Е.:nameMatcher.найти (дома,trees.name)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Стог сена просто случайно оказывается в том месте, где вы ищете иголку.Когда вы абстрагируетесь от пространства как от своего рода виртуальной машины (подумайте о:матрица) вы могли бы получить вышеприведенное с помощью haystack вместо space (решение 3/3 b):

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

Но матрица была Доменом, который должен быть заменен на haystack только в том случае, если ваша иголка не может быть где-то еще.

И опять же, это была просто анология.Интересно, что это открывает возможности для совершенно новых направлений:
1.Почему вы вообще потеряли иглу?Можете ли вы изменить процесс, чтобы не потерять его?
2.Вам нужно найти потерянную иглу или вы можете просто взять другую и забыть о первой?(Тогда было бы неплохо, если бы игла через некоторое время растворилась)
3.Если вы регулярно теряете свои иглы и вам нужно найти их снова, то, возможно, вам захочется

сделайте иглы, которые способны находить сами себя, напримерони регулярно задают себе этот вопрос:Я заблудился?Если ответ положительный, они отправляют кому-нибудь свое местоположение, рассчитанное по GPS, или начинают подавать звуковые сигналы, или что-то еще:
needle.find(space) или needle.find(haystack) (решение 1)
установите стог сена с камерой на каждую соломинку, после чего вы можете спросить у улья haystack hive mind, видел ли он иголку в последнее время:
стог сена.найти (иголку) (решение 2)
прикрепите RFID-метки к вашим иглам, чтобы вы могли легко триангулировать их

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

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

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

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

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

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

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

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

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

@Питер Мейер

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

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

итак, желательно, чтобы для гибкого решения вы сделали что-то вроде:Интерфейс iStuff

Стог сена = Список<IStuff> Иголка :ИСтуфф

Finder .Найти(я использую Stufftolook for, я использую список<IStuff> stuffsToLookIn)

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

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

var results = поисковик.Найти (рыбу, океан)

Если у вас есть ссылка на объект 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);

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

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

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

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

Другим возможным способом может быть создание двух интерфейсов для объекта с возможностью поиска, напримерстог сена и обнаруженный объект, напримеригла.Итак, это можно сделать таким образом

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

Эта статья делает хорошую работу по описанию таких сценариев.

Лицензировано под: CC-BY-SA с атрибуция

Не связан с StackOverflow