Związek między orientacją obiektu a algorytmami

9

Gdy czytam niektóre podręczniki algorytmów, są one pełne sprytnych procedur dla niektórych problemów (sortowanie, najkrótsza ścieżka) lub niektórych ogólnych metod (algorytmy rekurencyjne, dzielenie i podbijanie, programowanie dynamiczne ...). Znalazłem tam niewiele śladów programowania obiektowego; (Dlaczego są bardziej zorientowane na procedury?).

Potem pomyślałem:

  • Jaki jest związek między algorytmami a OOP? Czy to dwa niezależne tematy?
  • Czy są jakieś problemy, które OOP może przedstawić i rozwiązać?
  • W jaki sposób OOP może pomóc algorytmom? Lub w jakim kierunku może to wpłynąć?
Ahmad
źródło
4
Nie duplikat, ale pokrewne programatory.stackexchange.com/questions/239045/…
Doc Brown
@DocBrown Dziękuję, to było bardzo pomocne, jednak tutaj możemy rozważyć niektóre koncepcje dotyczące OO, takie jak dziedziczenie, polimorfizm ...
Ahmad
1
„Dlaczego podręcznik algorytmów jest bardziej zorientowany na procedury?” Java jest również zorientowana na procedury. Java jest zorientowanym obiektowo językiem proceduralnym.
Pieter B
1
@gnat Zmodyfikowałem swoje pytanie, nie wiem, czy to wyjaśnienie było konieczne, czy dobre. Przyznaję jednak, że pytanie, na które zwrócił się doktor Brown, zawiera więcej odpowiedzi związanych z moimi obawami.
Ahmad

Odpowiedzi:

10

Po pierwsze, zdefiniujmy, co rozumiemy przez OOP. Przez OOP mam na myśli przede wszystkim:

  • Hermetyzacja i ukrywanie szczegółów w klasie.
  • Polimorfizm zachowania poprzez dziedziczenie i metody wirtualne.

Teraz, aby odpowiedzieć na twoje pytanie:

Jaki jest związek między algorytmami a OOP? Czy to dwa niezależne tematy?

Tak.

Czy są jakieś problemy, które OOP może przedstawić i rozwiązać?

Nie. OOP podstawowy oferuje wygodę i możliwość wnioskowania o kodzie dla programisty. Nie zwiększa twojej siły wyrazu.

W jaki sposób OOP może pomóc algorytmom? Lub w jakim kierunku może to wpłynąć?

Tak jak powiedziałem powyżej. Oba punkty, które opisałem OOP jako obowiązujące tutaj. Umiejętność ukrywania szczegółów algorytmów i ich struktur danych może pomóc w uzasadnieniu całości. Wiele algorytmów zawiera szczegóły, z którymi użytkownik tego algorytmu nie powinien się bawić. Ukrywanie tych szczegółów bardzo pomaga.

Świetna jest także zdolność do zachowania polimorficznego. Listdefiniuje się jako możliwość dodawania / usuwania / usuwania elementów w dowolnym miejscu w kolekcji. Ale można go zaimplementować jako tablicę o zmiennym rozmiarze, podwójnie połączoną lub pojedynczo połączoną itp. Posiadanie jednego interfejsu API dla wielu implementacji może pomóc w ponownym użyciu.

Dlaczego podręcznik algorytmów jest bardziej zorientowany na procedury?

Jak powiedziałem, OOP nie jest konieczne do implementacji algorytmu. Ponadto wiele algorytmów jest starych i utworzonych, gdy OOP wciąż nie było rozpowszechnione. Może to być także kwestia historyczna.

Euforyk
źródło
1
Pomimo wieku tekstów, prawdopodobnie nie chciałbyś zamaczać wody algorytmu za pomocą OOP, tylko dlatego, że jest nowoczesny.
Gusdor,
15

Algorytmy i OOP są dwoma odmiennymi terminami, które mają tylko wspólną cechę, że są terminami CS . Po prostu - algorytm jest jak przepis na gotowanie : aby zrobić x , potrzebujesz następujących składników i wykonaj kroki 1,2,3,4,5,6 ... następnie przygotujesz swój posiłek.

To powiedziawszy, wydaje się naturalne, że algorytmy można opisać w sposób proceduralny . Procedura oznacza nic innego jak: najpierw zrób x, a następnie zrób y .

Częstym problemem jest: »Jak posortować zestaw x ?«. Łatwe do zrozumienia rozwiązanie to bubble-sort:

  1. Iteruj po zestawie od ostatniego elementu, dopóki nie dotrzesz do pierwszego elementu i podczas iteracji
  2. Rozpocznij drugą iterację od początku do bieżącego elementu pierwszej iteracji i
  3. Porównaj bieżący element (2) z jego następcą
  4. Jeśli większe, zamień pozycje

To jest algorytmiczny / słowny opis bubblesortalgorytmu.

Nadchodzi implementacja proceduralna / pseudokod

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

To było łatwe.

Jak to się ma do OOP ? Możesz użyć tego algorytmu do traktowania kolekcji (samego obiektu) obiektów :

Przykład w Javascripcie (chociaż nie ma czystego OO-Lingo , ale prawie nie ma płyty kotłowej i jest łatwy do zrozumienia)

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

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

sorted = objects.sort(compareObjects)

console.log(sorted)

Mamy a) kolekcję objects, b) metodę wspólną dla tej kolekcji, sortktóra zawiera / streszcza algorytm sortowania oraz c) nasze obiekty: Piotr , Paweł i Maryja . Specyfikacja sortowania znajduje się tutaj .

Jaki jest związek między algorytmami a OOP? Czy to dwa niezależne tematy?

Z tego, co zostało powiedziane, powinno być jasne, odpowiedź powinna brzmieć: tak, są niezależni.

W jaki sposób OOP może pomóc algorytmom? Lub w jakim kierunku może to wpłynąć?

OOP to tylko jeden styl programowania. Nie może pomóc w żaden sposób. W przeciwnym razie można by zaimplementować algorytm w języku OO, aby zrobić coś z obiektami (jak pokazano)

Czy są jakieś problemy, które OOP może przedstawić i rozwiązać?

Nie mogę myśleć o jednym (ale to nie znaczy, że jest to niemożliwe). Ale jeśli spojrzysz na to odwrotnie: OOP jest przydatne, jeśli chcesz modelować niektóre problemy i rozwiązywać je za pomocą odpowiedniego algorytmu. Załóżmy, że masz rejestr friendswas mógłby modelować je jako objectsze propertiesi jeśli chcesz listz friends posortowane w jakikolwiek sposób, można użyć przykładowy kod podany wyżej dokładnie to zrobić.

Dlaczego podręcznik algorytmów jest bardziej zorientowany na procedury?

Jak powiedziano: jest to bardziej naturalne , ponieważ procedura ma charakter algorytmów.

Thomas Junk
źródło
7
Ta odpowiedź zakłada, że ​​algorytmy są z natury proceduralne. Z pewnością niektóre z nich są, ale istnieje coś takiego jak algorytmy funkcjonalne. Powód, dla którego książki z algorytmami są proceduralne, prawdopodobnie ma więcej wspólnego z faktem, że koncentrują się one na wydajności, więc czytelnik musi martwić się wymuszaniem abstrakcji, a także dlatego, że języki rozkazujące są bardziej popularne niż języki funkcjonalne.
Doval
Myślę, że to nie do końca prawda. Mówiąc o funkcjonalnych językach programowania, mówisz o implementacji , a nie o samym algorytmie. Weźmy na przykład Haskell za quicksort wiki.haskell.org/Introduction#Quicksort_in_Haskell by oboje zgadzamy się, że jest to funkcjonalne wdrożenie do Quicksort-algortihm. Ale jeśli opisać , co się robi, trzeba awaryjne w trybie prodecural opisu. Z tego opisu można wdrożyć implementację proceduralną.
Thomas Junk
1
@ThomasJunk Ty nie musiał spaść z powrotem do trybu procesowego opisu, ponieważ realizacja funkcjonalny mówi, jakie rzeczy , a nie sekwencja kroków. Jak podasz sekwencyjny opis czystego i leniwego obliczenia? Nie wiadomo z góry, ile wyrażeń będzie ocenianych, ani w jakiej kolejności będą obliczane ich podwyrażenia.
Doval,
2
Niestety nie mam dyplomu CS, więc nie mam szerokiego zestawu umiejętności, aby udowodnić, co następuje: ale myślę, że każdy algorytm można opisać w taki czy inny sposób, więc nie ma prawdziwego czysto funkcjonalnego algorytmu. Czy nie jest to, co w konsekwencji oznacza kompletność tras koncertowych?
Thomas Junk
2
@Doval dobrze, ponieważ sam Turing udowodnił, że rachunek lambda i maszyny Turinga są równoważne, to oczywiste, że wszystko, co możesz podać w funkcjonalny sposób, możesz zrobić imperatywnie. Równie trywialne jest przekształcanie leniwych obliczeń w postać imperatywną - kompilator Haskella robi to cały czas ... Ostatecznie jest to tylko kwestia preferencji. Czasami funkcjonalne są bardziej odpowiednie, a czasem konieczne, a innym razem logiczne jest najlepsze ...
AK_
5

masz problem.

Model domeny biznesowej opisuje twój problem i pojęcia z dziedziny problemu, z którą zamierzasz się zmierzyć.

Algorytmy opisują sposób, w jaki zamierzasz rozwiązać swoje problemy, koncepcyjnie; jak będzie wyglądać twoja implementacja; i jak radzisz sobie z problemem po przetłumaczeniu go na terminy „Informatyka”.

Paradygmat programowania, niezależnie od tego, czy jest to OOP, funkcjonalne, logiczne, proceduralne, a nawet niestrukturalne, opisuje, w jaki sposób zamierzasz ustrukturyzować swoje rozwiązanie, jaką formę przyjmie, jakie koncepcje inżynierii oprogramowania zastosujesz, a które „ Programowanie teorii języka ”, które zamierzasz zastosować.

Mówiąc prościej, algorytmy ogólnie opisują twoje rozwiązanie problemu („To właśnie zamierzam zrobić”). Podczas programowania paradygmat dotyczy twojej faktycznej implementacji („Tak właśnie to zrobię”).

AK_
źródło
Zauważ, że w możliwie niedoskonały sposób deklaratywne języki mają na celu zmniejszenie lub wyeliminowanie kroku „jak”. Ich celem jest, abyś po prostu powiedział „tego właśnie chcę” (na przykład pisząc równania wysokiego poziomu). Pomyśl o typowym zapytaniu SQL: bardzo niewiele z nich jest „algorytmicznych”; po prostu powiedz bazie danych, czego chcesz, i zależy od tego, jak obsłuży twoje żądanie (oczywiście z pewnymi ograniczeniami).
Andres F.,
4

Algorytmy = opowiadanie historii „ jak ” (tj. Jak manipulować danymi wejściowymi za pomocą struktur danych w czasie, aby uzyskać pożądane wyniki)

OOP = „ metodologia ” obsługiwana przez języki OO do pisania programów (= algorytmy + struktury danych), która zapewnia bezpieczeństwo pamięci i abstrakcję

OOP to tylko paradygmat implementacji algorytmów.

Dobra analogia : filmy

Możesz nagrywać sceny, korzystając z kaskadera lub nie. Scenariusz (algorytm) się nie zmienia. Ludzie nie powinni widzieć żadnej różnicy w końcowym wyniku.

EDYCJA: możesz wypróbować dobrej jakości MOOC: https://www.coursera.org/course/algs4partI, który przeplata omawiane tematy (zwłaszcza podejście OOP) i daje istotę tego, o co tutaj pytasz.

Marcin Wachulski
źródło
Naprawdę podobała mi się twoja analogia do filmu. Pożyczę to w przyszłości.
Marc LaFleur,
2

Alexander Stepanov jest oryginalnym twórcą biblioteki standardowych szablonów C ++ (STL), która jest podstawową biblioteką algorytmów dla C ++. C ++ jest językiem opartym na wielu paradygmatach, który zawiera funkcje „Object Objected”, ale Alexander Stepanov ma to do powiedzenia na temat Object Orientation:

http://www.stlport.org/resources/StepanovUSA.html

STL nie jest zorientowany obiektowo. Myślę, że orientacja obiektowa jest niemal tak samo mistyfikacją jak Sztuczna Inteligencja. Nie widziałem jeszcze interesującego fragmentu kodu pochodzącego od tych ludzi z OO.

Uważam, że OOP nie jest technicznie uzasadnione. Próbuje rozłożyć świat na interfejsy, które różnią się w zależności od jednego typu. Aby poradzić sobie z prawdziwymi problemami, potrzebujesz wielosortowanych algeb - rodzin interfejsów obejmujących wiele typów. Uważam, że OOP jest nieuzasadnione filozoficznie. Twierdzi, że wszystko jest przedmiotem. Nawet jeśli to prawda, nie jest to bardzo interesujące - powiedzenie, że wszystko jest przedmiotem, w ogóle nic nie mówi. Uważam OOP za niepoprawny metodologicznie. Zaczyna się od zajęć. To tak, jakby matematycy zaczynali od aksjomatów. Nie zaczynasz od aksjomatów - zaczynasz od dowodów. Tylko wtedy, gdy znajdziesz kilka powiązanych dowodów, możesz wymyślić aksjomaty. Kończysz aksjomatami. To samo dotyczy programowania: musisz zacząć od interesujących algorytmów. Tylko wtedy, gdy dobrze je zrozumiesz,

Spędziłem lata próbując znaleźć zastosowanie do dziedziczenia i wirtuozów, zanim zrozumiałem, dlaczego ten mechanizm jest zasadniczo wadliwy i nie powinien być używany.

Stepanov wyraził swoją bibliotekę algorytmów nie za pomocą Objects, ale Generic Iterators .

James Brock
źródło
Cóż, myli się ... głównie dlatego, że STL jest bardzo zorientowany obiektowo ... Zorientowany obiektowo w bardziej nowoczesnym od tego czasu ...
AK_
1
@AK_ - Nie sądzę, żeby się mylił. STL nie jest nawet w przybliżeniu OO w żadnym znaczeniu tego terminu. Możesz przetłumaczyć STL bezpośrednio na język inny niż OO, który ma polimorfizm parametryczny (np. Haskell lub SML), bez potrzeby jego znacznej zmiany.
Jules
2

Algorytmy opisują, co powinien zrobić komputer. Struktura opisuje sposób rozmieszczenia algorytmu [w kodzie źródłowym]. OOP to styl programowania, który wykorzystuje pewne struktury „obiektowe”.

Książki o algorytmach często unikają OOP, ponieważ koncentrują się na algorytmie, a nie na strukturze. Fragmenty kodu, które w dużym stopniu opierają się na strukturze, są raczej złymi przykładami do umieszczenia w książce algorytmów. Podobnie książki OOP często unikają algorytmów, ponieważ zaśmiecają historię. Zaletą OOP jest jego płynność, a powiązanie go z algorytmem sprawia, że ​​wydaje się on sztywniejszy. Chodzi bardziej o temat książki niż o cokolwiek innego.

W prawdziwym kodzie będziesz używać obu stron obok siebie. Z definicji nie można rozwiązać problemów z komputerem bez algorytmów i trudno będzie napisać dobre algorytmy bez struktury (OOP lub w inny sposób).

Jako przykład tego, gdzie się rozmazują, weź Programowanie dynamiczne. W książce algorytmów opisałbyś, jak wziąć jednorodny zestaw danych do tablicy i użyć programowania dynamicznego, aby znaleźć rozwiązanie. W książce OOP możesz natknąć się na strukturę taką jak Visitor, która jest sposobem na wykonywanie dowolnych algorytmów na zbiorze heterogenicznych obiektów. Przykład książki DP można uznać za bardzo prostego gościa działającego na obiektach w ogólnie oddolnej kolejności. Wzorzec gościa można uznać za szkielet problemu DP, ale brakuje mu mięsa i ziemniaków. W rzeczywistości często okazuje się, że często potrzebujesz obu razem: używasz wzorca gościa, aby radzić sobie z heterogenicznością w zestawie danych (DP jest w tym zły), i używasz DP w strukturze gościa, aby zorganizować algorytm w celu zminimalizowania czasu działania (odwiedzający nie robi

Widzimy także algorytmy działające ponad wzorami projektowymi. Przykłady trudniejsze do sformułowania na małej przestrzeni, ale kiedy już masz strukturę, zaczynasz chcieć manipulować tą strukturą i używasz do tego algorytmów.

Czy są jakieś problemy, które OOP może przedstawić i rozwiązać?

To trudniejsze pytanie, niż ci się wydaje. W pierwszym rzędzie nie ma żadnego obliczeniowego powodu, dla którego potrzebujesz OOP do rozwiązania jakiegokolwiek problemu. Prostym dowodem jest to, że każdy program OOP jest kompilowany do asemblera, który jest zdecydowanie językiem innym niż OOP.

Jednak w szerszym schemacie rzeczy odpowiedź zaczyna być nieśmiała w kierunku „tak”. Rzadko jesteś ograniczony po prostu metodami obliczeniowymi. Przez większość czasu na takie równanie wpływają potrzeby biznesowe i umiejętności programistyczne. Wiele aplikacji dzisiaj nie mogłoby być napisanych bez OOP, nie dlatego, że OOP jest w jakiś sposób fundamentalny dla zadania, ale dlatego, że struktura dostarczona przez OOP była niezbędna do utrzymania projektu na właściwym poziomie i budżetu.

Nie oznacza to, że nigdy nie porzucimy OOP w przyszłości z powodu jakiejś śmiesznej nowej struktury. Mówi jedynie, że jest to jedno z najskuteczniejszych narzędzi w naszym zestawie narzędzi dla zaskakująco dużej części zadań programistycznych. Przyszłe problemy mogą skłonić nas do podejścia do rozwoju przy użyciu różnych struktur. Po pierwsze, oczekuję, że sieci neuronowe będą wymagały zupełnie innego podejścia programistycznego, które może, ale nie musi, być „obiektowe”.

Nie widzę, aby OOP znikało w najbliższej przyszłości ze względu na sposób myślenia projektantów algorytmów. Do tej pory zwykłym wzorem jest to, że ktoś projektuje algorytm, który nie wykorzystuje OOP. Społeczność OOP zdaje sobie sprawę, że algorytm tak naprawdę nie pasuje do struktury OOP i naprawdę nie musi tego robić, więc zawijają cały algorytm w strukturę OOP i zaczynają go używać. Zastanów się boost::shared_ptr. Algorytmy zliczania referencji, które znajdują shared_ptrsię w środku, nie są zbyt przyjazne dla OOP. Jednak wzorzec ten nie stał się popularny, dopóki nie shared_ptrutworzono wokół niego opakowania OOP, które ujawniło możliwości algorytmów w formacie strukturalnym OOP. Teraz jest tak popularny, że stał się najnowszą specyfikacją dla C ++, C ++ 11.

Dlaczego to tak udane? Algorytmy świetnie sprawdzają się w rozwiązywaniu problemów, ale często wymagają znacznych inwestycji początkowych w badania, aby zrozumieć, jak z nich korzystać. Rozwój zorientowany obiektowo jest bardzo skuteczny w pakowaniu takich algorytmów i zapewnianiu interfejsu, który wymaga mniejszej inwestycji początkowej.

Cort Ammon
źródło
1

Oprócz świetnych odpowiedzi wspomnę o dodatkowej pojęciowej podobieństwie między OOP i algorytmami.

Zarówno OOP, jak i Algorytmy silnie podkreślają użycie warunków wstępnych i końcowych w celu zapewnienia poprawności kodu.

Zasadniczo jest to standardowa praktyka we wszystkich obszarach informatyki; jednak ta zasada przewodnia prowadzi do ewolucyjnej ścieżki w OOP, co sprawia, że ​​wzajemnie korzystne jest wdrażanie algorytmów w środowisku OOP.

W OOP można stworzyć grupę obiektów, które mogą spełnić ten sam kontrakt (warunki wstępne i dodatkowe) w celu implementacji interfejsu. Użytkownik takiego interfejsu nie będzie musiał wiedzieć, która implementacja jest używana w obiekcie bazowym, z wyjątkiem niektórych rzadkich sytuacji (w których występuje nieszczelna abstrakcja).

Algorytm jest implementacją kroków służących do wykonania obliczeń, które wezmą warunek wstępny i wytworzą warunek końcowy.

Dlatego można zapożyczyć ideę abstrakcji na zasadzie warunków wstępnych i następczych i zastosować ją do algorytmów. Przekonasz się, że czasami skomplikowane algorytmy można rozłożyć na mniejsze etapy, a te mniejsze etapy mogą pozwolić na różne strategie implementacyjne, o ile zostaną spełnione te same warunki wstępne i końcowe.

Implementując algorytmy w OOP, można uczynić te mniejsze kroki wymiennymi.

Na koniec należy pamiętać, że FP i OOP nie wykluczają się wzajemnie. Wszystko opisane powyżej może mieć również zastosowanie do FP.

rwong
źródło
Dziękuję za punkt! Jak powiedziałeś, jeśli algorytm to tylko kilka kroków, OOP może pomóc nam w zapewnieniu bardziej abstrakcyjnych kroków. Wskazałeś na „wdrażanie algorytmów w OOP”. Zmodyfikowałem moje pytanie, aby zadać pytanie, czy zawsze jest korzystne?
Ahmad
1
mylisz OOP z „Design by Contract”. Jest bardzo przydatny bez OOP, a większość języków OOP (C #, Java) nie zapewnia rzeczywistego wsparcia (obsługują proste interfejsy, a nie warunki przed / po)
AK_
1
@AK_ Zgadzam się, że Design by Contract to poprawna nazwa dla podobieństwa opisanego w mojej odpowiedzi. Twierdzę, że OOP jako paradygmat projektowania silnie obejmuje Design by Contract - wystarczy przeczytać dowolny podręcznik OOP. Moja pierwotna odpowiedź wspomina również, że ta podobieństwo nie dotyczy wyłącznie OOP.
rwong
-1
What is the relation between algorithms and OOP? Are they two independent topics?

Algorytmy dotyczą sposobu rozwiązania problemu (generowania danych wyjściowych na podstawie danych wejściowych), OOP polega na tym, jak sformułować lub wyrazić nasze rozwiązanie (etapy algorytmu).

Algorytm można opisać w języku naturalnym lub asemblerze, ale pojęcia, które mamy w języku naturalnym, pomagają nam pisać i rozumieć go lepiej. Na przykład algorytm sortowania bąbelkowego mógłby wyglądać następująco:

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

Aby ukryć szczegóły swapi odnieść je do Azastosowanej składni i funkcji OOP, OO przybliża algorytm do naszego naturalnego języka i zrozumienia.

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

Nie, jeśli uważasz, że dowolny program (lub algorytm) na komputerze zostanie przetłumaczony na zestaw instrukcji wykonywanych na procesorze ( maszynie Turinga ) i jeśli uznamy te instrukcje za ostateczny algorytm rozwiązujący problem na komputerze , wówczas OOP nie mogę zrobić nic więcej. Po prostu przybliża to ludzkie rozumienie i rozumowanie. To sposób na spakowanie naszych procedur i struktur danych.

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

Może pomóc w określeniu lub sformułowaniu algorytmu łatwiejszym lub bardziej zrozumiałym. Może ukrywać szczegóły i zapewniać duży obraz rozwiązania.

Teoretycznie algorytm jest pierwszy, a implementacja drugi . Ale w rzeczywistości nie możemy być pewni, że nasz algorytm działa zgodnie z oczekiwaniami, dopóki go nie prześledzimy lub nie wygenerujemy oczekiwanego wyniku. Komputery pomagają nam to zrobić, ale nie spodziewasz się, że napiszesz je w języku maszynowym (asembler).

W związku z tym OOP ułatwia wdrożenie, testowanie i udoskonalenie naszego algorytmu na komputerach i napisanie go dla komputera w języku zbliżonym do naszego języka naturalnego.

Ahmad
źródło