Relazione tra orientamento degli oggetti e algoritmi

9

Mentre leggo alcuni libri di testo degli algoritmi, sono pieni di procedure intelligenti per alcuni problemi (ordinamento, percorso più breve) o alcuni metodi generali (algoritmi ricorsivi, divisione e conquista, programmazione dinamica ...). Ho trovato poche tracce di programmazione orientata agli oggetti lì; (Perché sono più orientati alla procedura?).

Allora stavo pensando:

  • Qual è la relazione tra algoritmi e OOP? Sono due argomenti indipendenti?
  • Ci sono alcuni problemi che possono essere presentati e risolti solo da OOP?
  • In che modo OOP può aiutare gli algoritmi? O in che direzione può influire?
posta Ahmad 06.02.2015 - 08:17
fonte

8 risposte

10

Per prima cosa, definiamo cosa intendiamo per OOP. Con OOP intendo principalmente:

  • Incapsulamento e occultamento dei dettagli in classe.
  • Polymorphism of behavior attraverso l'ereditarietà e metodi virtuali

Ora, per rispondere alla tua domanda:

What is the relation between algorithms and OOP? Are they two independent topics?

Sì.

Are there some problems which only can be presented and solved by OOP?

No. OOP primario offre convenienza e capacità di ragionare sul codice per programmatore. Non aumenta la tua potenza espressiva.

How OOP can help algorithms? Or in which direction it can affect it?

Come ho detto sopra. Entrambi i punti che ho descritto OOP si applicano qui. Essere in grado di nascondere i dettagli degli algoritmi e le loro strutture dati può aiutare a ragionare su tutto. Molti algoritmi contengono dettagli che non vogliono che l'utente di quell'algoritmo abbia a che fare. Nascondere questi dettagli aiuta molto.

Anche la capacità di avere un comportamento polimorfico è ottima. List è definito come in grado di aggiungere / rimuovere / cancellare gli elementi in qualsiasi punto della raccolta. Ma può essere implementato come array ridimensionabile, double-linked o single-linked, ecc. Avere un'unica API per implementazioni multiple può aiutare a riutilizzare.

Why algorithms textbook are more procedure-oriented?

Come ho detto, OOP non è necessario per implementare un algoritmo. Inoltre, molti algoritmi sono vecchi e creati quando OOP non era ancora diffuso. Quindi potrebbe anche essere una cosa storica.

    
risposta data 06.02.2015 - 08:39
fonte
15

Algorithms e OOP sono due termini disparati, che hanno solo in comune, che sono CS -terms. Semplicemente - Un algoritmo è come una ricetta cooking : per fare x hai bisogno dei seguenti ingredienti e fai il passo 1,2,3,4, 5,6 ... poi hai preparato il tuo pasto.

Detto questo, sembra che una naturale adatta per le algortihms sia descritta in modo procedurale . Procedurale significa nient'altro che: prima fai x e poi fai y .

Un problema comune è: »Come ordinare un set di x ?«. Una soluzione facile da capire è bubble-sort :

  1. Esegui l'iterazione sul set dall'ultimo elemento fino a quando non hai raggiunto il primo elemento e durante l'iterazione
  2. Avvia una seconda iterazione dall'inizio sull'elemento corrente della prima iterazione e
  3. Confronta l'elemento corrente di (2) con il suo successore
  4. Se maggiore, scambia le posizioni

Questa è la descrizione algoritmica / verbale del bubblesort -algorithm.

Ecco una implementazione procedurale / pseudocodice

bubbleSort(Array A)
  for (n=A.size; n>1; n=n-1){
    for (i=0; i<n-1; i=i+1){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
    } 
  } 
}

È stato facile.

In che modo questo si riallaccia a OOP ? Potresti usare questo algoritmo per trattare collections (un oggetto stesso) di objects :

Esempio in Javascript (anche se non c'è clean OO-Lingo , ma con quasi nessuna etichetta e facile da capire)

objects =[{"name":"Peter"}, {"name":"Paul"}, {"name":"Mary"}]

compareObjects=function(x,y){ return x.name>y.name };

sorted = objects.sort(compareObjects)

console.log(sorted)

Abbiamo a) una raccolta objects , b) un metodo comune a questa raccolta sort che contiene / astrae l'algoritmo di ordinamento e c) i nostri oggetti Peter , Paul e Mary . La Specifica per l'ordinamento si trova qui .

What is the relation between algorithms and OOP? Are they two independent topics?

Da quello che è stato detto, dovrebbe essere chiaro, la risposta dovrebbe essere: sì, sono indipendenti.

How OOP can help algorithms? Or in which direction it can affect it?

OOP è solo uno stile di programmazione. Non può aiutare in alcun tipo. Altrimenti un algoritmo potrebbe essere implementato in un linguaggio OO per fare qualcosa agli oggetti (come mostrato)

Are there some problems which only can be presented and solved by OOP?

Non riesco a pensarne uno (ma ciò non significa che sia impossibile). Ma se lo guardi al contrario: OOP è utile, se vuoi modellare alcuni problemi e risolvere i problemi con un algoritmo appropriato. Supponiamo che tu abbia un record di friends potresti modellarli come objects con properties e se vuoi un list di friends ordinato in alcun modo, potresti usare l'esempio codice dato sopra per fare esattamente questo.

Why algorithms textbook are more procedure-oriented?

Come detto: è più naturale , poiché procedurale è il carattere degli algoritmi.

    
risposta data 06.02.2015 - 08:56
fonte
5

hai un problema

Il modello del dominio aziendale descrive il tuo problema e i concetti del dominio problematico con cui stai andando a trattare.

Algorithms descrive il modo in cui risolverete i vostri problemi, concettualmente; come sarà la tua implementazione; e come gestisci il tuo problema dopo averlo tradotto in termini di "Informatica".

Paradigma di programmazione se OOP, Funzionale, Logico, Procedurale o Anche non strutturato, descrivi come strutturerai la tua soluzione, che forma prenderà, quale "Ingegneria del Software" concetti che stai andando a fare, e quali concetti di "Programming Language Theory" intendi utilizzare.

Per dirla in modo più semplice, gli algoritmi descrivono in generale la soluzione al problema ("Questo è ciò che farò"). Mentre la programmazione del paradigma si occupa della tua effettiva implementazione ("Questo è come lo farò").

    
risposta data 06.02.2015 - 16:23
fonte
4

Algorithms = racconta la storia di " How " (ad esempio, come manipolare i dati di input utilizzando le strutture di dati in tempo per produrre i risultati desiderati)

OOP = una " Metodologia " facilitata dai linguaggi OO per scrivere programmi (= algoritmi + strutture di dati) che ti danno sicurezza e astrazione della memoria

OOP è solo un paradigma di algoritmi di implementazione.

Buona analogia : film

È possibile registrare scene impiegando uno stuntman oppure no. La sceneggiatura (algoritmo) non cambia. Le persone non dovrebbero vedere alcuna differenza nel risultato finale.

EDIT: potresti provare un MOOC di buona qualità: link che intercala gli argomenti discussi (specialmente l'approccio OOP) e fornisce l'essenza di ciò che chiedi qui.

    
risposta data 06.02.2015 - 13:58
fonte
2

Alexander Stepanov è il creatore originale della libreria di modelli standard C ++ (STL), che è la libreria di algoritmi di base per C ++. C ++ è un linguaggio multi-paradigma che include funzionalità "Object Oriented", ma Alexander Stepanov ha questo da dire sull'Object Orientation:

link

STL is not object oriented. I think that object orientedness is almost as much of a hoax as Artificial Intelligence. I have yet to see an interesting piece of code that comes from these OO people.

I find OOP technically unsound. It attempts to decompose the world in terms of interfaces that vary on a single type. To deal with the real problems you need multisorted algebras - families of interfaces that span multiple types. I find OOP philosophically unsound. It claims that everything is an object. Even if it is true it is not very interesting - saying that everything is an object is saying nothing at all. I find OOP methodologically wrong. It starts with classes. It is as if mathematicians would start with axioms. You do not start with axioms - you start with proofs. Only when you have found a bunch of related proofs, can you come up with axioms. You end with axioms. The same thing is true in programming: you have to start with interesting algorithms. Only when you understand them well, can you come up with an interface that will let them work.

I spent years trying to find some use for inheritance and virtuals, before I understood why that mechanism was fundamentally flawed and should not be used.

Stepanov ha espresso la sua libreria di algoritmi non con Oggetti, ma con Iteratori generici .

    
risposta data 06.02.2015 - 15:39
fonte
2

Gli algoritmi descrivono cosa dovrebbe fare il computer. Struttura descrive come viene presentato l'algoritmo [nel codice sorgente]. OOP è uno stile di programmazione che sfrutta certe strutture "object oriented".

I libri algoritmici evitano spesso OOP perché sono focalizzati sull'algoritmo, non sulla struttura. Frammenti di codice che fanno molto affidamento sulla struttura tendono ad essere degli esempi scarsi da inserire in un libro di algoritmi. Allo stesso modo, i libri OOP spesso evitano gli algoritmi perché ingombrano la storia. Il punto di forza di OOP è la sua fluidità, e ancorarlo a un algoritmo lo fa apparire più rigido. Riguarda più il focus del libro che altro.

Nel codice della vita reale, userete entrambi affiancati. Non potete risolvere i problemi del computer senza algoritmi, per definizione, e troverete difficile scrivere algoritmi senza struttura ( OOP o altro).

Come esempio di dove si confondono, prendi la programmazione dinamica. In un libro di algoritmi, descriveresti come prendere un set di dati omogeneo in una matrice e utilizzare la programmazione dinamica per arrivare a una soluzione. In un libro OOP, potresti imbatterti in una struttura come Visitor, che è un modo per fare algoritmi arbitrari attraverso un insieme di oggetti eterogenei. L'esempio del libro DP potrebbe essere pensato come un visitatore molto semplice che opera su oggetti in un ordine generalmente bottom-up. Il modello Visitor può essere considerato lo scheletro di un problema DP, ma manca la carne e le patate. In realtà, troverai che spesso hai bisogno di entrambi insieme: usi il pattern Visitor per gestire l'eterogeneità tra i tuoi set di dati (DP è pessimo) e usi DP all'interno della struttura di Visitor per organizzare il tuo algoritmo per minimizzare il runtime (Visitatore non specifica un algoritmo).

Vediamo anche algoritmi che funzionano sopra i modelli di progettazione. I suoi esempi più difficili da pronunciare in un piccolo spazio, ma una volta che hai una struttura, inizi a voler manipolare quella struttura e usi gli algoritmi per farlo.

Are there some problems which can only be presented and solved by OOP?

Questa è una domanda più difficile a cui rispondere di quanto pensi sia. Per il primo ordine, non vi è alcun motivo computazionale per cui è necessario OOP per risolvere qualsiasi problema. La semplice dimostrazione è che ogni programma OOP viene compilato fino all'assemblaggio, che è un linguaggio decisamente non OOP.

Tuttavia, nello schema di cose più grande, la risposta inizia a essere timidi verso sì. raramente sei limitato semplicemente dalle metodologie di calcolo. Il più delle volte ci sono cose come le esigenze di business e le capacità di sviluppo che fanno parte dell'equazione. Molte applicazioni oggi non potrebbero essere scritte senza OOP, non perché l'OOP sia in qualche modo fondamentale per il compito, ma perché la struttura fornita da OOP era essenziale per mantenere il progetto in linea e al budget.

Questo non significa che non abbandoneremo mai OOP in futuro per qualche nuova struttura divertente. Si limita a dire che è uno degli strumenti più efficaci nella nostra casella degli strumenti per una porzione sorprendentemente ampia di attività di programmazione là fuori oggi. I problemi futuri possono indurci ad avvicinarci allo sviluppo usando strutture diverse. Per uno, mi aspetto che le reti neurali richiedano un approccio di sviluppo molto diverso, che potrebbe non essere "Orientato agli oggetti".

Non vedo OOP scomparire nel prossimo futuro a causa del modo in cui pensano i progettisti dell'algoritmo. Ad oggi, il solito schema è che qualcuno progetta un algoritmo che non fa leva su OOP. La comunità di OOP si rende conto che l'algoritmo non si adatta alla struttura di OOP, e in realtà non ne ha bisogno, quindi avvolgono l'intero algoritmo in una struttura OOP e iniziano a usarlo. Considera boost::shared_ptr . Gli algoritmi di conteggio dei riferimenti che riposano all'interno di shared_ptr non sono molto favorevoli all'OOP. Tuttavia, il pattern non è diventato popolare fino a quando shared_ptr ha creato attorno a sé un wrapper OOP che espone le funzionalità degli algoritmi in un formato strutturato OOP. Ora è così popolare che è diventato l'ultima specifica per C ++, C ++ 11.

Perché è così tanto successo? Gli algoritmi sono ottimi per risolvere i problemi, ma spesso richiedono un sostanziale investimento iniziale di ricerca per capire come usarli. Lo sviluppo orientato agli oggetti è molto efficace nel confezionare tali algoritmi e fornire un'interfaccia che richiede meno investimenti iniziali da apprendere.

    
risposta data 06.02.2015 - 19:17
fonte
1

Oltre alle ottime risposte, menzionerò una ulteriore comunanza concettuale tra OOP e Algorithms.

Sia OOP che Algorithms sottolineano con forza l'uso delle precondizioni e delle post-condizioni per garantire la correttezza del codice.

In generale, questa è una pratica standard in tutti i settori dell'informatica; tuttavia, questo principio guida si traduce in un percorso evolutivo in OOP che rende reciprocamente vantaggioso implementare algoritmi in ambiente OOP.

In OOP, un gruppo di oggetti in grado di soddisfare lo stesso contratto (precondizioni e postcondizioni) può essere realizzato per implementare un'interfaccia. L'utente di tale interfaccia non ha bisogno di sapere quale implementazione viene utilizzata nell'oggetto sottostante, tranne in alcune rare situazioni (in cui avviene l'astrazione che perde).

Un algoritmo è un'implementazione dei passaggi usati per eseguire un calcolo, uno che prenderà il presupposto e produrrà la post-condizione.

Pertanto, si può prendere in prestito l'idea di astrazione in termini di precondizioni e postcondizioni e applicarla agli algoritmi. Scoprirai che a volte gli algoritmi complicati possono essere scomposti in passi più piccoli, e questi piccoli passi possono consentire diverse strategie di implementazione purché siano soddisfatte le stesse condizioni preliminari e post-condizioni.

Implementando algoritmi in OOP, è possibile rendere questi passaggi più piccoli intercambiabili.

Infine, tieni presente che FP e OOP non si escludono a vicenda. Qualunque cosa sopra descritta può essere ugualmente applicabile anche a FP.

    
risposta data 06.02.2015 - 14:33
fonte
-1
What is the relation between algorithms and OOP? Are they two independent topics?

Gli algoritmi sono circa come risolvere un problema (Come generare output dall'input dato), OOP parla di come formulare o esprimere la nostra soluzione (i passi di l'algoritmo).

Un algoritmo può essere descritto in linguaggio naturale o in linguaggio assembly, ma i concetti che abbiamo in un linguaggio naturale ci aiutano a scrivere e comprenderlo meglio. Ad esempio l'algoritmo per bubble-sort potrebbe essere:

bubbleSort(Array A)
  for (n=A.size; n>1; n=n-1){
    for (i=0; i<n-1; i=i+1){
      if (A[i] > A[i+1]){
        A.swap(i, i+1)
    } 
  } 
}

Per nascondere i dettagli di swap e per metterlo in relazione con A abbiamo usato una sintassi e una funzionalità OOP, quindi OO rende l'algoritmo più vicino al nostro linguaggio naturale e alla comprensione.

Are there some problems which can only be presented and solved by OOP?

No, se si considera che qualsiasi programma (o algoritmo) su un computer sarà tradotto in un insieme di istruzioni eseguite sulla CPU ( Turing Machine ) e se consideriamo queste istruzioni come l'ultimo algoritmo che risolve il problema su un computer , OOP non può fare altro. Rende solo più vicino alla comprensione e al ragionamento umano. È un modo per impacchettare le nostre procedure e strutture dati.

How OOP can help algorithms? Or in which direction it can affect it?

Può aiutare a stabilire o formulare un algoritmo più facile o più comprensibile. Può nascondere i dettagli e fornire un quadro generale della soluzione.

In teoria, l'algoritmo è prima e l'implementazione del secondo . Ma in realtà, non possiamo essere sicuri che il nostro algoritmo funzioni come previsto finché non lo tracciamo o generiamo l'output atteso. I computer ci aiutano a farlo, ma non ti aspetti di scriverlo in linguaggio macchina (assembly).

A questo proposito, OOP facilita l'implementazione, il test e il perfezionamento del nostro algoritmo sui computer e lo scrive per un computer in una lingua vicina al nostro linguaggio naturale.

    
risposta data 06.02.2015 - 13:59
fonte

Leggi altre domande sui tag