Como você encontra uma agulha em um palheiro?
https://stackoverflow.com/questions/23755
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Ao implementar uma busca por agulha em um palheiro de maneira orientada a objetos, você tem essencialmente três alternativas:
1. needle.find(haystack)
2. haystack.find(needle)
3. searcher.find(needle, haystack)Qual você prefere e por quê?
Sei que algumas pessoas preferem a segunda alternativa porque evita a introdução de um terceiro objeto.No entanto, não posso deixar de sentir que a terceira abordagem é conceitualmente mais "correta", pelo menos se o seu objetivo for modelar "o mundo real".
Em quais casos você acha que se justifica introduzir objetos auxiliares, como o buscador neste exemplo, e quando eles devem ser evitados?
Solução
Normalmente as ações devem ser aplicadas ao que você está fazendo...neste caso o palheiro, então acho que a opção 2 é a mais adequada.
Você também tem uma quarta alternativa que acho que seria melhor que a alternativa 3:
haystack.find(needle, searcher)
Neste caso, permite fornecer a forma como deseja pesquisar como parte da ação, e assim manter a ação com o objeto que está sendo operado.
Outras dicas
Dos três, prefiro a opção nº 3.
O Princípio de Responsabilidade Única me faz não querer colocar recursos de pesquisa em meus DTOs ou modelos.A responsabilidade deles é ser dados, não se encontrarem, nem as agulhas precisam saber sobre os palheiros, nem os palheiros saberem sobre as agulhas.
Pelo que vale, acho que a maioria dos profissionais de OO leva MUITO tempo para entender por que o número 3 é a melhor escolha.Eu fiz OO por uma década, provavelmente, antes de realmente grocar.
@wilhelmtell, C++ é uma das poucas linguagens com especialização em modelos que fazem esse sistema realmente funcionar.Para a maioria dos idiomas, um método de "localização" de uso geral seria uma ideia HORRÍVEL.
Existe outra alternativa, que é a abordagem utilizada pelo STL do C++:
find(haystack.begin(), haystack.end(), needle)
Eu acho que é um ótimo exemplo de grito C ++ "na sua cara!" para oop.A ideia é que OOP não seja uma solução mágica de nenhum tipo;às vezes as coisas são melhor descritas em termos de ações, às vezes em termos de objetos, às vezes nenhuma delas e às vezes ambas.
Bjarne Stroustrup disse em TC++PL que ao projetar um sistema você deve se esforçar para refletir a realidade sob as restrições de um código eficaz e eficiente.Para mim, isso significa que você nunca deve seguir nada cegamente.Pense nas coisas que temos em mãos (palheiro, agulha) e no contexto em que estamos (procurando, é disso que trata a expressão).
Se a ênfase for na pesquisa, então usar um algoritmo (ação) que enfatize a pesquisa (ou seja,é flexível para caber em palheiros, oceanos, desertos, listas vinculadas).Se a ênfase for no palheiro, encapsule o método find dentro do objeto palheiro e assim por diante.
Dito isto, às vezes você fica em dúvida e tem dificuldade em fazer uma escolha.Neste caso, seja orientado a objetos.Se você mudar de ideia mais tarde, acho que é mais fácil extrair uma ação de um objeto do que dividir uma ação em objetos e classes.
Siga estas orientações e seu código ficará mais claro e, bem, mais bonito.
Eu diria que a opção 1 está completamente fora de questão.O código deve ser lido de uma forma que diga o que ele faz.A opção 1 me faz pensar que essa agulha vai me encontrar num palheiro.
A opção 2 parece boa se um palheiro for destinado a conter agulhas.ListCollections sempre conterão ListItems, portanto, fazer collection.find(item) é natural e expressivo.
Acho que a introdução de um objeto auxiliar é apropriada quando:
- Você não controla a implementação dos objetos em questão
Ou seja:search.find(ObsecureOSObject, arquivo) - Não existe uma relação regular ou sensata entre os objetos
Ou seja:nomeMatcher.find(casas,árvores.nome)
Estou com Brad nisso.Quanto mais trabalho em sistemas imensamente complexos, mais vejo a necessidade de desacoplar verdadeiramente os objetos.Ele tem razão.É óbvio que uma agulha não deveria saber nada sobre palheiro, então 1 está definitivamente fora.Mas um palheiro não deveria saber nada sobre uma agulha.
Se eu estivesse modelando um palheiro, poderia implementá-lo como uma coleção – mas como uma coleção de feno ou canudo - não uma coleção de agulhas!No entanto, eu levaria em consideração que essas coisas se perdem em um palheiro, mas não sei nada sobre o que exatamente são essas coisas.Eu acho que é melhor não fazer o palheiro procurar itens em si (como inteligente é um palheiro de qualquer maneira).A abordagem correta para mim é fazer com que o palheiro apresente uma coleção de coisas que estão nele, mas que não são palha, feno ou o que quer que dê essência ao palheiro.
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)
}
Na verdade, havia mais coisas que eu iria digitar e abstrair em interfaces e então percebi o quão louco estava ficando.Parecia que eu estava em uma aula de CS na faculdade...:P
Você entendeu a ideia.Acho que ser o mais flexível possível é uma coisa boa, mas talvez eu estivesse me empolgando um pouco!:)
Se Needle e Haystack forem DAOs, as opções 1 e 2 estão fora de questão.
A razão para isso é que os DAOs devem ser responsáveis apenas por manter as propriedades dos objetos do mundo real que estão modelando e ter apenas métodos getter e setter (ou apenas acesso direto às propriedades).Isso torna a serialização dos DAOs em um arquivo ou a criação de métodos para uma comparação genérica/cópia genérica mais fácil de escrever, já que o código não conteria um monte de instruções "if" para ignorar esses métodos auxiliares.
Isto deixa apenas a opção 3, que a maioria concordaria ser o comportamento correto.
A opção 3 tem algumas vantagens, sendo a maior vantagem o teste de unidade.Isso ocorre porque os objetos Needle e Haystack podem ser facilmente simulados agora, ao passo que se a opção 1 ou 2 fosse usada, o estado interno de Needle ou Haystack teria que ser modificado antes que uma pesquisa pudesse ser realizada.
Em segundo lugar, com o pesquisador agora em uma classe separada, todo o código de pesquisa pode ser mantido em um só lugar, incluindo o código de pesquisa comum.Considerando que, se o código de pesquisa fosse colocado no DAO, o código de pesquisa comum seria armazenado em uma hierarquia de classes complicada ou, de qualquer maneira, com uma classe Searcher Helper.
Isso depende inteiramente do que varia e do que permanece igual.
Por exemplo, estou trabalhando em um (não-OOP) estrutura onde o algoritmo de localização é diferente dependendo do tipo de agulha e do palheiro.Além do fato de que isso exigiria despacho duplo em um ambiente orientado a objetos, também significa que não faz sentido escrever needle.find(haystack) ou para escrever haystack.find(needle).
Por outro lado, seu aplicativo poderia delegar a descoberta para qualquer uma das duas classes ou ficar com um algoritmo, caso em que a decisão é arbitrária.Nesse caso, eu preferiria o haystack.find(needle) porque parece mais lógico aplicar a descoberta ao palheiro.
Ao implementar uma pesquisa de agulha de um palheiro de maneira orientada a objetos, você tem essencialmente três alternativas:
agulha.find(palheiro)
palheiro.find(agulha)
searcher.find(agulha, palheiro)
Qual você prefere e por quê?
Corrija-me se eu estiver errado, mas nos três exemplos você já ter uma referência à agulha que você está procurando, então não é como procurar seus óculos quando eles estão no seu nariz?:p
Trocadilhos à parte, acho que realmente depende do que você considera ser a responsabilidade do palheiro dentro de um determinado domínio.Será que nos preocupamos com isso apenas no sentido de ser uma coisa que contém agulhas (essencialmente uma coleção)?Então haystack.find(needlePredicate) está bem.Caso contrário, farmBoy.find(predicate, haystack) pode ser mais apropriado.
Para citar os grandes autores de SICP,
Os programas devem ser escritos para as pessoas lerem e apenas incidentalmente para as máquinas executarem.
Prefiro ter os dois métodos 1 e 2 em mãos.Usando Ruby como exemplo, ele vem com .include? que é usado assim
haystack.include? needle
=> returns true if the haystack includes the needle
Às vezes, porém, puramente por razões de legibilidade, quero inverter a situação.Ruby não vem com um in? método, mas é de uma linha, então costumo fazer isso:
needle.in? haystack
=> exactly the same as above
Se for “mais importante” enfatizar o palheiro, ou a operação de busca, prefiro escrever include?.Muitas vezes, porém, nem o palheiro nem a busca são realmente o que importa, apenas que o objeto esteja presente - neste caso, acho in? transmite melhor o significado do programa.
Depende de suas necessidades.
Por exemplo, se você não se importa com as propriedades do pesquisador (por exemplo,força do pesquisador, visão, etc.), então eu diria que haystack.find(needle) seria a solução mais limpa.
Mas, se você se preocupa com as propriedades do pesquisador (ou quaisquer outras propriedades), eu injetaria uma interface ISearcher no construtor do palheiro ou na função para facilitar isso.Isso suporta design orientado a objetos (um palheiro tem agulhas) e inversão de controle/injeção de dependência (torna mais fácil testar a unidade da função "encontrar").
Posso pensar em situações em que qualquer um dos dois primeiros sabores faça sentido:
Se a agulha precisar de pré-processamento, como no algoritmo Knuth-Morris-Pratt,
needle.findIn(haystack)(oupattern.findIn(text))faz sentido, porque o objeto agulha contém as tabelas intermediárias criadas para que o algoritmo funcione de forma eficazSe o palheiro precisar de pré-processamento, como, digamos, em uma tentativa, o
haystack.find(needle)(ouwords.hasAWordWithPrefix(prefix)) funciona melhor.
Em ambos os casos acima, alguém da agulha ou do palheiro está ciente da busca.Além disso, ambos estão cientes um do outro.Se você quer que a agulha e o palheiro não tenham consciência um do outro ou da busca, searcher.find(needle, haystack) seria apropriado.
Fácil:Queime o palheiro!Depois, restará apenas a agulha.Além disso, você pode tentar ímãs.
Uma pergunta mais difícil:Como você encontra uma agulha específica em um conjunto de agulhas?
Responder:enfie cada um deles e prenda a outra extremidade de cada fio a um índice classificado (ou seja,ponteiros)
A resposta a esta pergunta deve depender do domínio para o qual a solução é implementada.
Se acontecer de você simular uma busca física em um palheiro físico, você poderá ter as classes
- Espaço
- Canudo
- Agulha
- Buscador
Espaço
sabe quais objetos estão localizados em quais coordenadas
implementa as leis da natureza (converte energia, detecta colisões, etc.)
Agulha, Canudo
estão localizados no espaço
reagir às forças
Buscador
interage com o espaço:
move a mão, aplica campo magnético, queima feno, aplica raios X, procura agulha...
Por issoseeker.find(needle, space) ou seeker.find(needle, space, strategy)
Acontece que o palheiro está no espaço onde você procura a agulha.Quando você abstrai o espaço como uma espécie de máquina virtual (pense em:a matriz) você poderia obter o acima com palheiro em vez de espaço (solução 3/3b):
seeker.find(needle, haystack) ou seeker.find(needle, haystack, strategy)
Mas a matriz era o Domínio, que só deveria ser substituído pelo palheiro, se a sua agulha não pudesse estar em outro lugar.
E, novamente, foi apenas uma anologia.Curiosamente, isso abre a mente para direções totalmente novas:
1.Por que você perdeu a agulha em primeiro lugar?Você pode mudar o processo para não perdê-lo?
2.Você tem que encontrar a agulha perdida ou pode simplesmente pegar outra e esquecer a primeira?(Então seria bom se a agulha se dissolvesse depois de um tempo)
3.Se você perde suas agulhas regularmente e precisa encontrá-las novamente, você pode querer
faça agulhas que sejam capazes de se encontrar, por ex.eles regularmente se perguntam:Estou perdido?Se a resposta for sim, eles enviam sua posição calculada por GPS para alguém ou começam a apitar ou algo assim:
needle.find(space)ouneedle.find(haystack)(solução 1)instale um palheiro com uma câmera em cada canudo, depois você pode perguntar ao chefe da colmeia do palheiro se ele viu a agulha ultimamente:
palheiro.find(agulha) (solução 2)anexe etiquetas RFID às suas agulhas, para que você possa triangulá-las facilmente
Isso tudo só para dizer que na sua implementação você fez a agulha e o palheiro e, na maioria das vezes, a matriz em algum tipo de nível.
Então decida de acordo com o seu domínio:
- O propósito do palheiro é conter agulhas?Então vá para a solução 2.
- É natural que a agulha se perca em qualquer lugar?Então vá para a solução 1.
- A agulha se perde no palheiro por acidente?Então vá para a solução 3.(ou considere outra estratégia de recuperação)
haystack.find(needle), mas deve haver um campo de busca.
Eu sei que a injeção de dependência está na moda, então não me surpreende que haystack.find(needle, searcher) de @Mike Stone tenha sido aceito.Mas eu discordo:a escolha de qual buscador será utilizado parece-me uma decisão para o palheiro.
Considere dois ISearchers:O MagneticSearcher itera sobre o volume, movendo e pisando no ímã de maneira consistente com a força do ímã.QuickSortSearcher divide a pilha em duas até que a agulha fique evidente em uma das subpilhas.A escolha adequada do pesquisador pode depender do tamanho do palheiro (em relação ao campo magnético, por exemplo), de como a agulha entrou no palheiro (ou seja, a posição da agulha é verdadeiramente aleatória ou é tendenciosa?), etc.
Se você tem HayStack.find (agulha, pesquisador), está dizendo "cuja escolha é a melhor estratégia de pesquisa é melhor feita fora do contexto do palheiro". Eu não acho que é provável que esteja correto.Eu acho que é mais provável que "os palheiros saibam a melhor forma de pesquisar em si mesmos". Adicione um setter e você ainda poderá injetar manualmente o pesquisador se precisar substituir ou testar.
Pessoalmente, gosto do segundo método.Meu raciocínio é porque as principais APIs com as quais trabalhei usam essa abordagem e acho que faz mais sentido.
Se você tiver uma lista de coisas (palheiro), você procuraria (encontrar ()) a agulha.
@Peter Meyer
Você entendeu a ideia.Acho que ser o mais flexível possível é uma coisa boa, mas talvez eu estivesse me empolgando um pouco!:)
Err...sim...Eu acho que o IStuffSmallEnoughToBeLostInAHaystack meio que é uma bandeira vermelha :-)
Você também tem uma quarta alternativa que acho que seria melhor que a alternativa 3:
haystack.find(needle, searcher)
Entendo o que você quer dizer, mas e se searcher implementa uma interface de pesquisa que permite pesquisar outros tipos de objetos além de palheiros e encontrar outras coisas neles além de agulhas?
A interface também pode ser implementada com diferentes algoritmos, por exemplo:
binary_searcher.find(needle, haystack)
vision_searcher.find(pitchfork, haystack)
brute_force_searcher.find(money, wallet)
Mas, como outros já apontaram, também acho que isso só será útil se você realmente tiver vários algoritmos de pesquisa ou várias classes pesquisáveis ou localizáveis.Se não, eu concordo haystack.find(needle) é melhor por causa de sua simplicidade, então estou disposto a sacrificar alguma "correção" por isso.
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();
Uma mistura de 2 e 3, na verdade.
Alguns palheiros não possuem uma estratégia de busca especializada;um exemplo disso é uma matriz.A única maneira de encontrar algo é começar do início e testar cada item até encontrar o que deseja.
Para esse tipo de coisa, uma função gratuita provavelmente é melhor (como C++).
Alguns palheiros podem ter uma estratégia de busca especializada imposta a eles.Uma matriz pode ser classificada, permitindo usar pesquisa binária, por exemplo.Uma função livre (ou par de funções livres, por ex.sort e binary_search) é provavelmente a melhor opção.
Alguns palheiros possuem uma estratégia de busca integrada como parte de sua implementação;todos os contêineres associativos (conjuntos e mapas ordenados ou com hash), por exemplo.Nesse caso, encontrar é provavelmente um método de pesquisa essencial, portanto provavelmente deveria ser um método, ou seja,palheiro.find(agulha).
Haystack pode conter coisas que um tipo de coisa é o agulha Finder é algo responsável por pesquisar o Finder Stuff pode aceitar uma pilha de coisas como a fonte de onde encontrar o Finder Thing também pode aceitar uma descrição de coisa que precisa encontrar
então, de preferência, para uma solução flexível você faria algo como:Interface ISuff
Haystack = Ilistu003CIStuff> Agulha :Coisas
Finder .Find (istuff stuffTolookfor, ilistu003CIStuff> stuffstolookin)
Nesse caso, sua solução não ficará presa apenas a agulhas e palheiros, mas poderá ser utilizada para qualquer tipo que implemente a interface
então, se quiser encontrar um peixe no oceano, você pode.
var resultados = Finder.Find(peixe, oceano)
Se você tem uma referência ao objeto agulha, por que o procura?:) O domínio do problema e os casos de uso dizem que você não precisa de posição exata da agulha em um palheiro (como o que você pode obter da lista.IndexOF (elemento)), você só precisa de uma agulha.E você ainda não tem isso.Então minha resposta é algo assim
Needle needle = (Needle)haystack.searchByName("needle");
ou
Needle needle = (Needle)haystack.searchWithFilter(new Filter(){
public boolean isWhatYouNeed(Object obj)
{
return obj instanceof Needle;
}
});
ou
Needle needle = (Needle)haystack.searchByPattern(Size.SMALL,
Sharpness.SHARP,
Material.METAL);
Concordo que existem mais soluções possíveis baseadas em diferentes estratégias de pesquisa, por isso introduzem o pesquisador.Houve muitos comentários sobre isso, então não presto atenção nisso aqui.O que quero dizer é que as soluções acima esquecem os casos de uso - qual é o sentido de procurar algo se você já tem referência a ele?No caso de uso mais natural, você ainda não tem uma agulha, portanto não usa agulha variável.
Brad Wilson ressalta que os objetos devem ter uma única responsabilidade.No caso extremo, um objeto tem uma responsabilidade e nenhum estado.Então pode se tornar...uma função.
needle = findNeedleIn(haystack);
Ou você poderia escrever assim:
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());
O palheiro não deveria saber da agulha, e a agulha não deveria saber da agulha.O pesquisador precisa saber sobre ambos, mas se o palheiro deve ou não saber como pesquisar é o verdadeiro ponto em discórdia.
Então eu escolheria uma mistura de 2 e 3;o palheiro deve ser capaz de dizer a outra pessoa como revistá-lo, e quem está pesquisando deve ser capaz de usar essa informação para vasculhar o palheiro.
haystack.magnet().filter(needle);
O código está tentando encontrar uma agulha específica ou qualquer agulha?Parece uma pergunta estúpida, mas muda o problema.
Procurando uma agulha específica o código da pergunta faz sentido.Procurando por qualquer agulha seria mais parecido
needle = haystack.findNeedle()
ou
needle = searcher.findNeedle(haystack)
De qualquer forma, prefiro ter um pesquisador dessa classe.Um palheiro não sabe procurar.Do ponto de vista do CS, é apenas um armazenamento de dados com MUITA porcaria que você não quer.
Definitivamente o terceiro, IMHO.
A questão de uma agulha em um palheiro é um exemplo de tentativa de encontrar um objeto em uma grande coleção de outros, o que indica que será necessário um algoritmo de busca complexo (possivelmente envolvendo ímãs ou (mais provavelmente) processos filhos) e isso não acontece. Não faz muito sentido esperar que um palheiro faça gerenciamento de threads ou implemente pesquisas complexas.
Um objeto de pesquisa, no entanto, é dedicado à pesquisa e pode-se esperar que saiba como gerenciar threads filhos para uma pesquisa binária rápida ou usar propriedades do elemento pesquisado para restringir a área (ou seja:um ímã para encontrar itens ferrosos).
Outra maneira possível pode ser criar duas interfaces para objetos pesquisáveis, por exemplo.palheiro e objeto ToBeSearched, por exemplo.agulha.Então, isso pode ser feito desta forma
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 pode ser interface para qualquer coleção imutável, com coleções tendo findFirst(fun: T => Boolean) método fazendo o trabalho.Enquanto o palheiro for imutável, não há necessidade de ocultar quaisquer dados úteis “de fora”.E, claro, não é bom unir a implementação de uma coleção personalizada não trivial e outras coisas que tenham haystack.Divida e conquiste, ok?
Na maioria dos casos, prefiro poder executar operações auxiliares simples como essa no objeto principal, mas dependendo da linguagem, o objeto em questão pode não ter um método suficiente ou sensato disponível.
Mesmo em línguas como JavaScript) que permitem aumentar/estender objetos integrados, acho que isso pode ser conveniente e problemático (por exemplo,se uma versão futura da linguagem introduzir um método mais eficiente que seja substituído por um método personalizado).
Este artigo faz um bom trabalho ao delinear esses cenários.
