¿Cómo se encuentra una aguja en un pajar?

StackOverflow https://stackoverflow.com/questions/23755

Pregunta

Al implementar una búsqueda con aguja en un pajar de forma orientada a objetos, básicamente tiene tres alternativas:

1. needle.find(haystack)

2. haystack.find(needle)

3. searcher.find(needle, haystack)

¿Cuál prefieres y por qué?

Sé que algunas personas prefieren la segunda alternativa porque evita introducir un tercer objeto.Sin embargo, no puedo evitar sentir que el tercer enfoque es más "correcto" conceptualmente, al menos si su objetivo es modelar "el mundo real".

¿En qué casos cree que está justificado introducir objetos auxiliares, como el buscador en este ejemplo, y cuándo deberían evitarse?

¿Fue útil?

Solución

Por lo general, las acciones deben aplicarse a aquello en lo que estás realizando la acción...en este caso el pajar, por lo que creo que la opción 2 es la más adecuada.

También tienes una cuarta alternativa que creo que sería mejor que la alternativa 3:

haystack.find(needle, searcher)

En este caso, te permite proporcionar la manera en la que deseas buscar como parte de la acción, y así puedes mantener la acción con el objeto que se está operando.

Otros consejos

De las tres, prefiero la opción número 3.

El Principio de responsabilidad única me hace no querer poner capacidades de búsqueda en mis DTO o modelos.Su responsabilidad es ser dato, no encontrarse a sí mismo, ni las agujas necesitan saber de los pajares, ni los pajares saber de las agujas.

Por si sirve de algo, creo que a la mayoría de los profesionales de OO les lleva MUCHO tiempo comprender por qué la opción número 3 es la mejor opción.Probablemente hice OO durante una década, antes de que realmente lo asimilase.

@wilhelmtell, C++ es uno de los pocos lenguajes con especialización en plantillas que hace que un sistema de este tipo realmente funcione.Para la mayoría de los idiomas, un método de "búsqueda" de propósito general sería una idea HORRIBLE.

Existe otra alternativa, que es el enfoque utilizado por el STL de C++:

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

Creo que es un gran ejemplo de gritos de C ++ "¡en tu cara!" para oop.La idea es que la programación orientada a objetos no es una solución milagrosa de ningún tipo;A veces las cosas se describen mejor en términos de acciones, a veces en términos de objetos, a veces ninguna de las dos cosas y otras veces ambas.

Bjarne Stroustrup dijo en TC++PL que cuando diseñas un sistema debes esforzarte por reflejar la realidad bajo las limitaciones de un código eficaz y eficiente.Para mí, esto significa que nunca debes seguir nada a ciegas.Pensar en las cosas que tenemos a mano (pajar, aguja) y el contexto en el que nos encontramos (buscando, de eso se trata la expresión).

Si el énfasis está en la búsqueda, entonces usar un algoritmo (acción) que enfatice la búsqueda (es decir,es flexible para adaptarse a pajares, océanos, desiertos, listas enlazadas).Si el énfasis está en el pajar, encapsule el método de búsqueda dentro del objeto del pajar, y así sucesivamente.

Dicho esto, a veces tienes dudas y te cuesta tomar una decisión.En este caso, esté orientado a objetos.Si cambia de opinión más tarde, creo que es más fácil extraer una acción de un objeto que dividir una acción en objetos y clases.

Siga estas pautas y su código será más claro y, bueno, más hermoso.

Yo diría que la opción 1 está completamente descartada.El código debe leerse de manera que le indique lo que hace.La opción 1 me hace pensar que esta aguja me va a buscar un pajar.

La opción 2 parece buena si se supone que un pajar debe contener agujas.ListCollections siempre contendrá ListItems, por lo que hacer collection.find(item) es natural y expresivo.

Creo que la introducción de un objeto auxiliar es apropiada cuando:

  1. No controlas la implementación de los objetos en cuestión.
    ES DECIR:search.find(ObsecureOSObject, archivo)
  2. No existe una relación regular o sensata entre los objetos.
    ES DECIR:nameMatcher.find(casas,árboles.nombre)

Estoy con Brad en este caso.Cuanto más trabajo en sistemas inmensamente complejos, más veo la necesidad de desacoplar verdaderamente los objetos.El tiene razón.Es obvio que una aguja no debería saber nada sobre el pajar, así que definitivamente estoy fuera.Pero un pajar no debería saber nada sobre una aguja.

Si estuviera modelando un pajar, podría implementarlo como una colección, pero como una colección de heno o paja ¡No es una colección de agujas!Sin embargo, tomaría en consideración que las cosas se pierden en un pajar, pero no sé nada sobre qué son exactamente.Creo que es mejor no hacer que el pajar busque objetos en sí mismo (¿cómo? elegante es un pajar de todos modos).El enfoque correcto para mí es hacer que el pajar presente una colección de cosas que están en él, pero que no son paja o heno o lo que sea que le dé su esencia.

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

En realidad, iba a escribir y abstraer más cosas en las interfaces y luego me di cuenta de lo loco que me estaba volviendo.Me sentí como si estuviera en una clase de informática en la universidad...:PAG

Entiendes la idea.Creo que es bueno tener un acoplamiento lo más flexible posible, ¡pero tal vez me estaba dejando llevar un poco!:)

Si tanto Needle como Haystack son DAO, entonces las opciones 1 y 2 están fuera de discusión.

La razón de esto es que los DAO solo deben ser responsables de mantener las propiedades de los objetos del mundo real que están modelando, y solo deben tener métodos getter y setter (o simplemente acceso directo a las propiedades).Esto hace que serializar los DAO en un archivo o crear métodos para una comparación genérica/copia genérica sea más fácil de escribir, ya que el código no contendría un montón de declaraciones "if" para omitir estos métodos auxiliares.

Esto sólo deja la opción 3, que la mayoría estaría de acuerdo en que es el comportamiento correcto.

La opción 3 tiene algunas ventajas, siendo la mayor la prueba unitaria.Esto se debe a que ahora se pueden simular fácilmente los objetos Needle y Haystack, mientras que si se usaran las opciones 1 o 2, el estado interno de Needle o Haystack tendría que modificarse antes de poder realizar una búsqueda.

En segundo lugar, con el buscador ahora en una clase separada, todo el código de búsqueda se puede mantener en un solo lugar, incluido el código de búsqueda común.Mientras que si el código de búsqueda se colocara en el DAO, el código de búsqueda común se almacenaría en una jerarquía de clases complicada o, de todos modos, con una clase Searcher Helper.

Esto depende completamente de lo que varía y de lo que permanece igual.

Por ejemplo, estoy trabajando en un (no-OOP) estructura donde el algoritmo de búsqueda es diferente dependiendo tanto del tipo de aguja como del pajar.Aparte del hecho de que esto requeriría un doble envío en un entorno orientado a objetos, también significa que tampoco tiene sentido escribir needle.find(haystack) o escribir haystack.find(needle).

Por otro lado, su aplicación podría delegar felizmente la búsqueda a cualquiera de ambas clases, o seguir con un algoritmo por completo, en cuyo caso la decisión es arbitraria.En ese caso, preferiría el haystack.find(needle) manera porque parece más lógico aplicar el hallazgo al pajar.

Al implementar una búsqueda de aguja de un pajar de una manera orientada a objetos, esencialmente tiene tres alternativas:

  1. aguja.encontrar(pajar)

  2. pajar.buscar (aguja)

  3. buscador.encontrar(aguja, pajar)

¿Cuál prefieres y por qué?

Corrígeme si me equivoco, pero en los tres ejemplos ya tener una referencia a la aguja que estás buscando, entonces, ¿no es esto como buscar tus anteojos cuando están sobre tu nariz?:pag

Dejando a un lado el juego de palabras, creo que realmente depende de lo que consideres que es la responsabilidad del pajar dentro del dominio dado.¿Nos importa simplemente en el sentido de que es algo que contiene agujas (una colección, esencialmente)?Entonces haystack.find(needlePredicate) está bien.De lo contrario, farmBoy.find(predicate, haystack) podría ser más apropiado.

Para citar a los grandes autores de SICP,

Los programas deben escribirse para que las personas los lean y sólo incidentalmente para que las máquinas los ejecuten.

Prefiero tener a mano los métodos 1 y 2.Usando Ruby como ejemplo, viene con .include? que se usa así

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

A veces, sin embargo, simplemente por razones de legibilidad, quiero darle la vuelta.Ruby no viene con un in? método, pero es una sola línea, por lo que a menudo hago esto:

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

Si es "más importante" enfatizar el pajar, o la operación de búsqueda, prefiero escribir include?.A menudo, sin embargo, ni el pajar ni la búsqueda son realmente lo que te importa, sólo que el objeto esté presente; en este caso encuentro que in? Transmite mejor el significado del programa.

Depende de tus requisitos.

Por ejemplo, si no le importan las propiedades del buscador (p. ej.fuerza del buscador, visión, etc.), entonces diría que haystack.find(needle) sería la solución más limpia.

Pero, si le importan las propiedades del buscador (o cualquier otra propiedad), inyectaría una interfaz ISearcher en el constructor del pajar o en la función para facilitar eso.Esto admite tanto el diseño orientado a objetos (un pajar tiene agujas) como la inversión de control/inyección de dependencia (facilita la prueba unitaria de la función "buscar").

Puedo pensar en situaciones en las que cualquiera de los dos primeros sabores tiene sentido:

  1. Si la aguja necesita un procesamiento previo, como en el algoritmo Knuth-Morris-Pratt, needle.findIn(haystack) (o pattern.findIn(text))tiene sentido, porque el objeto aguja contiene las tablas intermedias creadas para que el algoritmo funcione de manera efectiva

  2. Si el pajar necesita un procesamiento previo, como por ejemplo en un trie, el haystack.find(needle) (o words.hasAWordWithPrefix(prefix)) funciona mejor.

En ambos casos anteriores, uno de la aguja o el pajar está al tanto de la búsqueda.Además, ambos se conocen el uno al otro.Si quieres que la aguja y el pajar no se den cuenta ni de la búsqueda, searcher.find(needle, haystack) Sería apropiado.

Fácil:¡Quema el pajar!Después sólo quedará la aguja.Además, puedes probar con imanes.

Una pregunta más difícil:¿Cómo encuentras una aguja en particular en un charco de agujas?

Respuesta:Enhebra cada uno y une el otro extremo de cada hilo a un índice ordenado (es decir,punteros)

La respuesta a esta pregunta debería depender del dominio para el que se implemente la solución.
Si simulas una búsqueda física en un pajar físico, es posible que tengas las clases

  • Espacio
  • Paja
  • Aguja
  • Buscador

Espacio
sabe qué objetos están ubicados en qué coordenadas
implementa las leyes de la naturaleza (convierte energía, detecta colisiones, etc.)

Aguja, Paja
están ubicados en el espacio
reaccionar a las fuerzas

Buscador
interactúa con el espacio:
    mueve la mano, aplica campo magnético, quema heno, aplica rayos X, busca aguja...

De este modoseeker.find(needle, space) o seeker.find(needle, space, strategy)

El pajar resulta estar en el espacio donde buscas la aguja.Cuando abstraes el espacio como una especie de máquina virtual (piensa en:la matriz) podrías obtener lo anterior con pajar en lugar de espacio (solución 3/3b):

seeker.find(needle, haystack) o seeker.find(needle, haystack, strategy)

Pero la matriz era el Dominio, que sólo debería ser reemplazado por un pajar, si tu aguja no podía estar en ningún otro lugar.

Y, de nuevo, era sólo una analogía.Curiosamente, esto abre la mente a direcciones totalmente nuevas:
1.¿Por qué perdiste la aguja en primer lugar?¿Puedes cambiar el proceso para no perderlo?
2.¿Tienes que encontrar la aguja perdida o puedes simplemente conseguir otra y olvidarte de la primera?(Entonces sería bueno si la aguja se disolviera después de un tiempo)
3.Si pierde las agujas con regularidad y necesita encontrarlas nuevamente, es posible que desee

  • fabricar agujas que puedan encontrarse a sí mismas, p.se preguntan regularmente:¿Estoy perdido?Si la respuesta es sí, envían su posición calculada por GPS a alguien o empiezan a emitir un pitido o lo que sea:
    needle.find(space) o needle.find(haystack)    (solución 1)

  • instala un pajar con una cámara en cada paja, luego puedes preguntarle a la colmena del pajar si vio la aguja últimamente:
    pajar.buscar (aguja) (solución 2)

  • coloque etiquetas RFID en sus agujas para poder triangularlas fácilmente

Todo esto solo para decir que en su implementación tú Hizo la aguja y el pajar y la mayoría de las veces la matriz en algún tipo de nivel.

Así que decide según tu dominio:

  • ¿El propósito del pajar es contener agujas?Luego opte por la solución 2.
  • ¿Es natural que la aguja se pierda por cualquier lado?Luego opte por la solución 1.
  • ¿Se pierde la aguja en el pajar por accidente?Luego opte por la solución 3.(o considere otra estrategia de recuperación)

haystack.find(aguja), pero debería haber un campo de búsqueda.

Sé que la inyección de dependencia está de moda, por lo que no me sorprende que hayastack.find(needle, searcher) de @Mike Stone haya sido aceptado.Pero no estoy de acuerdo:La elección de qué buscador se utiliza me parece una decisión para el pajar.

Considere dos ISearchers:MagneticSearcher itera sobre el volumen, moviendo y haciendo avanzar el imán de una manera consistente con la fuerza del imán.QuickSortSearcher divide la pila en dos hasta que la aguja sea evidente en una de las subpilas.La elección adecuada del buscador puede depender de qué tan grande es el pajar (en relación con el campo magnético, por ejemplo), cómo entró la aguja en el pajar (es decir, ¿la posición de la aguja es realmente aleatoria o está sesgada?), etc.

Si tiene Haystack.find (aguja, buscador), está diciendo "cuya elección es la mejor estrategia de búsqueda se hace mejor fuera del contexto del Haystack". No creo que sea correcto.Creo que es más probable que "los paystacks sepan la mejor manera de buscar en sí mismos". Agregue un setter y aún puede inyectar manualmente al buscador si necesita anular o para probar.

Personalmente, me gusta el segundo método.Mi razonamiento es que las principales API con las que he trabajado utilizan este enfoque y creo que tiene más sentido.

Si tiene una lista de cosas (pajar), buscará (encontrará()) la aguja.

@Peter Meyer

Entiendes la idea.Creo que es bueno tener un acoplamiento lo más flexible posible, ¡pero tal vez me estaba dejando llevar un poco!:)

Err...sí...Pienso que el IStuffSmallEnoughToBeLostInAHaystack algo así como una señal de alerta :-)

También tienes una cuarta alternativa que creo que sería mejor que la alternativa 3:

haystack.find(needle, searcher)

Entiendo tu punto, pero ¿y si searcher ¿Implementa una interfaz de búsqueda que permite buscar otros tipos de objetos además de los pajares y encontrar otras cosas además de agujas en ellos?

La interfaz también podría implementarse con diferentes algoritmos, por ejemplo:

binary_searcher.find(needle, haystack)
vision_searcher.find(pitchfork, haystack)
brute_force_searcher.find(money, wallet)

Pero, como ya han señalado otros, también creo que esto sólo es útil si realmente tienes múltiples algoritmos de búsqueda o múltiples clases que se pueden buscar o encontrar.Si no, estoy de acuerdo haystack.find(needle) es mejor por su simplicidad, por lo que estoy dispuesto a sacrificar algo de "corrección" por ello.

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

Una mezcla de 2 y 3, de verdad.

Algunos pajares no tienen una estrategia de búsqueda especializada;un ejemplo de esto es una matriz.La única forma de encontrar algo es empezar desde el principio y probar cada elemento hasta encontrar el que desea.

Para este tipo de cosas, probablemente sea mejor una función gratuita (como C++).

A algunos pajares se les puede imponer una estrategia de búsqueda especializada.Se puede ordenar una matriz, lo que le permite utilizar la búsqueda binaria, por ejemplo.Una función libre (o un par de funciones libres, p. ej.sort y binario_search) es probablemente la mejor opción.

Algunos pajares tienen una estrategia de búsqueda integrada como parte de su implementación;los contenedores asociativos (conjuntos y mapas hash u ordenados) lo hacen, por ejemplo.En este caso, encontrar es probablemente un método de búsqueda esencial, por lo que probablemente debería ser un método, es decir,pajar.buscar (aguja).

Haystack puede contener cosas que un tipo de cosas es que el buscador de agujas es algo que es responsable de buscar al que Finder puede aceptar un montón de cosas, ya que la fuente de dónde encontrar las cosas que Finder también puede aceptar una descripción de cosas que necesita encontrar

entonces, preferiblemente, para una solución flexible harías algo como:Interfaz IStuff

Haystack = ilistu003CIStuff> Aguja :I cosas

Finder .Find (Istuff Stufftolookfor, ilistu003CIStuff> StuffStolookin)

En este caso, su solución no se limitará solo a una aguja y un pajar, sino que se puede utilizar para cualquier tipo que implemente la interfaz.

Así que si quieres encontrar un pez en el océano, puedes hacerlo.

var resultados = Finder.Find(pez, océano)

Si tienes una referencia a un objeto aguja, ¿por qué lo buscas?:) El dominio del problema y los casos de uso le dicen que no necesita una posición exacta de aguja en un pajar (como lo que podría obtener de list.indexof (elemento)), solo necesita una aguja.Y aún no lo tienes.Entonces mi respuesta es algo como esto.

Needle needle = (Needle)haystack.searchByName("needle");

o

Needle needle = (Needle)haystack.searchWithFilter(new Filter(){
    public boolean isWhatYouNeed(Object obj)
    {
        return obj instanceof Needle;
    }
});

o

Needle needle = (Needle)haystack.searchByPattern(Size.SMALL, 
                                                 Sharpness.SHARP, 
                                                 Material.METAL);

Estoy de acuerdo en que hay más soluciones posibles que se basan en diferentes estrategias de búsqueda, por eso introducen el buscador.Hubo suficientes comentarios sobre esto, así que no le presto atención aquí.Mi punto es que las soluciones anteriores se olvidan de los casos de uso: ¿cuál es el punto de buscar algo si ya tiene una referencia a él?En el caso de uso más natural, todavía no tienes una aguja, por lo que no utilizas una aguja variable.

Brad Wilson señala que los objetos deberían tener una única responsabilidad.En el caso extremo, un objeto tiene una responsabilidad y ningún estado.Entonces puede convertirse...Una función.

needle = findNeedleIn(haystack);

O podrías escribirlo así:

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

El pajar no debería saber nada de la aguja, y la aguja no debería saber nada del pajar.El buscador necesita saber acerca de ambos, pero el verdadero punto de discusión es si el pajar debe saber cómo buscarse a sí mismo o no.

Entonces elegiría una combinación de 2 y 3;el pajar debería poder decirle a otra persona cómo buscarlo, y el buscador debería poder utilizar esa información para buscar en el pajar.

haystack.magnet().filter(needle);

¿El código intenta encontrar una aguja específica o cualquier aguja?Parece una pregunta estúpida, pero cambia el problema.

Al buscar una aguja específica, el código de la pregunta tiene sentido.Buscando cualquier aguja sería más bien

needle = haystack.findNeedle()

o

needle = searcher.findNeedle(haystack)

De cualquier manera, prefiero tener un buscador de esa clase.Un pajar no sabe buscar.Desde una perspectiva de CS, es solo un almacén de datos con MUCHA basura que no quieres.

Definitivamente el tercero, en mi humilde opinión.

La cuestión de una aguja en un pajar es un ejemplo de un intento de encontrar un objeto entre una gran colección de otros, lo que indica que necesitará un algoritmo de búsqueda complejo (que posiblemente involucre imanes o (más probablemente) procesos secundarios) y no No tiene mucho sentido esperar que un pajar administre hilos o implemente búsquedas complejas.

Sin embargo, un objeto de búsqueda está dedicado a la búsqueda y se puede esperar que sepa cómo administrar subprocesos secundarios para una búsqueda binaria rápida, o usar propiedades del elemento buscado para limitar el área (es decir:un imán para encontrar objetos ferrosos).

Otra forma posible puede ser crear dos interfaces para objetos de búsqueda, p.pajar y objeto ToBeSearched, p.aguja.Entonces se puede hacer de esta manera 

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 puede ser una interfaz para cualquier colección inmutable, con colecciones que tengan elementos comunes findFirst(fun: T => Boolean) método para realizar el trabajo.Mientras el pajar sea inmutable, no es necesario ocultar ningún dato útil del "exterior".Y, por supuesto, no es bueno unir la implementación de una colección personalizada no trivial y algunas otras cosas que sí tienen haystack.Divide y vencerás, ¿vale?

En la mayoría de los casos, prefiero poder realizar operaciones auxiliares simples como esta en el objeto principal, pero dependiendo del lenguaje, es posible que el objeto en cuestión no tenga un método suficiente o sensato disponible.

Incluso en idiomas como javascript) que le permiten aumentar/ampliar objetos integrados, creo que puede ser conveniente y problemático (p. ej.si una versión futura del lenguaje introduce un método más eficiente que se anula por uno personalizado).

Este artículo hace un buen trabajo al describir tales escenarios.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top