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

Question

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

1. needle.find(haystack)

2. haystack.find(needle)

3. searcher.find(needle, haystack)

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

• Пробел
• Солома
• игла
• Искатель

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

Answer 4

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

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

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

Answer 5

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

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

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

Finder .Find (IStuff stuffToLookFor, IList stuffsToLookIn)

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

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

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

Answer 6

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

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

needle = haystack.findNeedle()

или

needle = searcher.findNeedle(haystack)

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

Answer 7

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

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

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

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

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

Answer 8

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 9

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

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

Answer 10

haystack.magnet().filter(needle);