Связь между ориентацией объекта и алгоритмами

Поскольку я читал некоторые учебники по алгоритмам, они полны умных процедур для некоторых задач (сортировка, кратчайший путь) или некоторых общих методов (рекурсивные алгоритмы, разделяй и властвуй, динамическое программирование ...). Я нашел несколько следов объектно-ориентированного программирования там; (Почему они более ориентированы на процедуры?).

Тогда я подумал:

• Какова связь между алгоритмами и ООП? Это две независимые темы?
• Существуют ли проблемы, которые могут быть представлены и решены только ООП?
• Как ООП может помочь алгоритмам? Или в каком направлении это может повлиять?

Во-первых, давайте определим, что мы подразумеваем под ООП. Под ООП я имею в виду прежде всего:

• Инкапсуляция и сокрытие деталей в классе.
• Полиморфизм поведения через наследование и виртуальные методы.

Теперь, чтобы ответить на ваш вопрос:

Какова связь между алгоритмами и ООП? Это две независимые темы?

Да.

Существуют ли проблемы, которые только могут быть представлены и решены ООП?

Нет. Основной ООП предлагает удобство и возможность рассуждать о коде для программиста. Это не увеличивает вашу выразительную силу.

Как ООП могут помочь алгоритмы? Или в каком направлении это может повлиять?

Как я уже говорил выше. Оба пункта, которые я описал ООП, применимы здесь. Возможность скрыть детали алгоритмов и их структур данных может помочь понять все это. Многие алгоритмы содержат детали, с которыми пользователь этого алгоритма не хочет возиться. Сокрытие этих деталей очень помогает.

Способность иметь полиморфное поведение также велика. Listопределяется как возможность добавлять / удалять / очищать элементы в любом месте коллекции. Но он может быть реализован в виде массива с изменяемыми размерами, двойного или односвязного и т. Д. Наличие одного API для нескольких реализаций может помочь в повторном использовании.

Почему алгоритмы учебника более процедурно-ориентированы?

Как я уже сказал, ООП не является необходимым для реализации алгоритма. Кроме того, многие алгоритмы старые и созданы, когда ООП еще не получил широкого распространения. Так что это также может быть исторической вещью.

Алгоритмы и ООП являются двумя несопоставимыми терминами, которые имеют только общее, что они являются CS- терминами. Просто - алгоритм похож на рецепт приготовления : чтобы сделать х, вам нужны следующие ингредиенты и выполните шаг 1, 2, 3, 4, 5, 6 ... затем приготовьте еду.

Тем не менее, это кажется естественным , пригодные для algortihms быть описано в процедурном способе. Процедурный означает не что иное, как: сначала сделать х, а затем сделать у .

Распространенной проблемой является: »Как отсортировать набор х ?«. Простое для понимания решение bubble-sort:

1. Выполните итерацию по набору из последнего элемента, если вы еще не достигли первого элемента и во время итерации
2. Начните 2-ю итерацию с начала до текущего элемента первой итерации и
3. Сравните текущий элемент (2) с его преемником
4. Если больше, поменяйте местами

Это алгоритмическое / словесное описание алгоритма bubblesort.

Здесь идет реализация процедурного / псевдокода

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

Это было легко.

Как это переводится в ООП ? Вы можете использовать этот алгоритм для обработки коллекций (сам объект) объектов :

Пример в Javascript (хотя нет чистого OO-Lingo , но практически нет шаблона и легко понять)

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

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

sorted = objects.sort(compareObjects)

console.log(sorted)

У нас есть а) коллекция objects, б) метод, общий для этой коллекции, sortкоторый содержит / абстрагирует алгоритм сортировки и в) наши объекты Питер , Пол и Мэри . Спецификация для сортировки находится здесь .

Какова связь между алгоритмами и ООП? Это две независимые темы?

Из сказанного должно быть понятно, ответ должен быть: да, они независимы.

Как ООП могут помочь алгоритмы? Или в каком направлении это может повлиять?

ООП - это всего лишь один стиль программирования. Это не может помочь ни в каком виде. В противном случае алгоритм может быть реализован на языке ОО, чтобы что-то делать с объектами (как показано).

Существуют ли проблемы, которые только могут быть представлены и решены ООП?

Я не могу думать об одном (но это не значит, что это невозможно). Но если посмотреть с другой стороны: ООП полезно, если вы хотите смоделировать некоторые проблемы и решить их с помощью соответствующего алгоритма. Скажем , у вас есть запись friendsвы могли моделировать их как objectsс , propertiesи если вы хотите listиз friends отсортированы в любом случае, вы могли бы использовать пример-приведенный выше код , чтобы сделать именно это.

Почему алгоритмы учебника более процедурно-ориентированы?

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

у тебя проблема.

Модель бизнес-домена описывает вашу проблему, и концепции из проблемной области, с которыми вы собираетесь работать, будут иметь дело.

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

Парадигма программирования, будь то ООП, функциональная, логическая, процедурная или даже неструктурированная, описывает, как вы собираетесь структурировать свое решение, какую форму оно собирается принять, какие концепции «разработки программного обеспечения» вы собираетесь использовать и какие » Теория языка программирования "Понятия, которые вы собираетесь использовать.

Проще говоря, алгоритмы описывают в целом ваше решение проблемы («Это то, что я собираюсь сделать»). В то время как парадигма программирования имеет дело с вашей реальной реализацией («Вот как я собираюсь это сделать»).

Алгоритмы = рассказывают историю « как » (то есть, как манипулировать входными данными, используя структуры данных во времени для получения желаемых результатов)

ООП = « Методология », поддерживаемая ОО-языками для написания программ (= алгоритмы + структуры данных), обеспечивающая безопасность и абстракцию памяти

ООП - это просто парадигма реализации алгоритмов.

Хорошая аналогия : фильмы

Вы можете записывать сцены, используя каскадера или нет. Сценарий (алгоритм) не меняется. Люди не должны видеть никакой разницы в конечном результате.

РЕДАКТИРОВАТЬ: вы можете попробовать хорошее качество MOOC: https://www.coursera.org/course/algs4partI, который чередует обсуждаемые темы (особенно подход ООП) и дает суть того, что вы спрашиваете здесь.

Александр Степанов является первоначальным создателем стандартной библиотеки шаблонов C ++ (STL), которая является основой библиотеки алгоритмов для C ++. C ++ - это мультипарадигмальный язык, который включает в себя «объектно-ориентированные» функции, но у Александра Степанова есть что сказать об объектной ориентации:

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

STL не является объектно-ориентированным. Я думаю, что объектная ориентация почти такая же обман, как и искусственный интеллект. Мне еще предстоит увидеть интересный кусок кода, который исходит от этих OO людей.

Я считаю ООП технически необоснованным. Он пытается разложить мир с точки зрения интерфейсов, которые различаются по одному типу. Чтобы справиться с реальными проблемами, вам нужны многосортные алгебры - семейства интерфейсов, которые охватывают несколько типов. Я считаю ООП философски необоснованным. Он утверждает, что все является объектом. Даже если это правда, это не очень интересно - говорить, что все является объектом, вообще ничего не говорить. Я считаю, что ООП методологически неправильно. Начинается с занятий. Это как если бы математики начинали с аксиом. Вы не начинаете с аксиом - вы начинаете с доказательств. Только когда вы найдете кучу связанных доказательств, вы сможете придумать аксиомы. Вы заканчиваете аксиомами. То же самое верно в программировании: вы должны начать с интересных алгоритмов. Только когда вы их хорошо понимаете,

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

Степанов выражал свою библиотеку алгоритмов не объектами, а общими итераторами .

Алгоритмы описывают, что должен делать компьютер. Структура описывает, как алгоритм изложен [в исходном коде]. ООП - это стиль программирования, который использует определенные «объектно-ориентированные» структуры.

Книги по алгоритмам часто избегают ООП, потому что они сосредоточены на алгоритме, а не на структуре. Фрагменты кода, которые в значительной степени опираются на структуру, являются плохими примерами для размещения в книге алгоритмов. Аналогично, ООП книги часто избегают алгоритмов, потому что они загромождают историю. Преимущество ООП заключается в его плавности, и привязка к алгоритму делает его более жестким. Это больше о фокусе книги, чем что-либо еще.

В реальном коде вы будете использовать оба бок о бок. Вы не можете решить компьютерные проблемы без алгоритмов по определению, и вам будет сложно писать хорошие алгоритмы без структуры (ООП или иным образом).

В качестве примера того, где они размываются, возьмем динамическое программирование. В книге по алгоритмам вы опишете, как получить однородный набор данных в массиве и использовать динамическое программирование для достижения решения. В книге ООП вы можете встретить такую ​​структуру, как Visitor, которая позволяет создавать произвольные алгоритмы для множества разнородных объектов. Пример книги DP можно представить как очень простого посетителя, работающего с объектами в порядке снизу вверх. Шаблон Visitor можно рассматривать как скелет проблемы DP, но при этом не хватает мяса и картофеля. В действительности вы часто обнаружите, что вам часто нужно и то и другое вместе: вы используете шаблон Visitor для работы с неоднородностью по всему набору данных (в этом DP плохо), и вы используете DP в структуре Visitor, чтобы организовать свой алгоритм для минимизации времени выполнения (Visitor Безразлично»

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

Существуют ли проблемы, которые могут быть представлены и решены только ООП?

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

Тем не менее, в более широком плане, ответ начинает стесняться в сторону да. Вы редко ограничены просто компьютерными методологиями. В большинстве случаев есть такие вещи, как бизнес-потребности и навыки разработчика, которые учитываются в уравнении. Многие приложения сегодня не могут быть написаны без ООП, не потому, что ООП каким-то образом является фундаментальным для этой задачи, а потому, что структура, предоставляемая ООП, была необходима для поддержания проекта в нужном русле и в рамках бюджета.

Это не означает, что в будущем мы никогда не откажемся от ООП из-за какой-то забавной новой структуры. Это просто говорит о том, что это один из самых эффективных инструментов в нашем наборе инструментов для удивительно большой части задач программирования сегодня. Будущие проблемы могут побудить нас подойти к разработке с использованием различных структур. Во-первых, я ожидаю, что нейронные сети потребуют совершенно другого подхода к разработке, который может оказаться или не оказаться «объектно-ориентированным».

Я не вижу исчезновения ООП в ближайшем будущем из-за того, как думают разработчики алгоритмов. На сегодняшний день обычным примером является то, что кто-то разрабатывает алгоритм, который не использует ООП. Сообщество ООП понимает, что алгоритм не совсем соответствует структуре ООП, и на самом деле в этом нет необходимости, поэтому они оборачивают весь алгоритм в структуру ООП и начинают его использовать. Посмотрим boost::shared_ptr. Алгоритмы подсчета ссылок, которые shared_ptrлежат внутри , не очень удобны для ООП. Однако шаблон не стал популярным до тех пор, пока shared_ptrвокруг него не была создана оболочка ООП, раскрывающая возможности алгоритмов в структурированном формате ООП. Теперь он настолько популярен, что превратил его в новейшую спецификацию для C ++, C ++ 11.

Почему это так успешно? Алгоритмы хороши в решении проблем, но они часто требуют значительных начальных инвестиций в исследования, чтобы понять, как их использовать. Объектно-ориентированная разработка очень эффективна для обертывания таких алгоритмов и обеспечения интерфейса, который требует меньших начальных вложений для обучения.

В дополнение к отличным ответам, я упомяну дополнительную концептуальную общность между ООП и алгоритмами.

И ООП, и Алгоритмы настоятельно подчеркивают использование предусловий и постусловий для обеспечения правильности кода.

В общем, это стандартная практика во всех областях информатики; однако этот руководящий принцип приводит к эволюционному пути в ООП, что делает его взаимовыгодным для реализации алгоритмов в среде ООП.

В ООП для реализации интерфейса может быть создана группа объектов, которые могут удовлетворять одному и тому же контракту (предусловия и постусловия). Пользователю такого интерфейса не нужно знать, какая реализация используется в базовом объекте, за исключением некоторых редких ситуаций (в которых происходит утечка абстракции).

Алгоритм - это реализация шагов, используемых для выполнения вычислений, которые принимают предварительное условие и создают постусловие.

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

Реализуя алгоритмы в ООП, можно сделать эти меньшие шаги взаимозаменяемыми.

Наконец, имейте в виду, что FP и OOP не являются взаимоисключающими. Все, что описано выше, может быть в равной степени применимо и к FP.

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

Алгоритмы о том, как решить проблему (Как генерировать вывод из заданного ввода), ООП о том, как сформулировать или выразить наше решение (шаги алгоритма).

Алгоритм может быть описан на естественном языке или на ассемблере, но понятия, которые мы имеем на естественном языке, помогают нам лучше понять и понять его. Например, алгоритм для пузырьковой сортировки может быть:

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

Чтобы скрыть детали swapи связать их с используемым Aнами синтаксисом и функцией ООП, ОО делает алгоритм ближе к нашему естественному языку и пониманию.

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

Нет, если вы считаете, что любая программа (или алгоритм) на компьютере будет преобразована в набор инструкций, выполняемых на CPU ( машине Тьюринга ), и если мы рассматриваем эти инструкции как основной алгоритм, который решает проблему на компьютере , то ООП не могу сделать что-то дальше. Это просто делает его ближе к человеческому пониманию и рассуждению. Это способ упаковки наших процедур и структур данных.

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

Это может помочь сформулировать или сформулировать алгоритм проще или более понятным. Он может скрывать детали и предоставлять общую картину решения.

Теоретически алгоритм является первым и реализует его вторым . Но в действительности мы не можем быть уверены, что наш алгоритм работает так, как ожидается, пока мы не проследим его или не создадим ожидаемый результат. Компьютеры помогают нам в этом, но вы не ожидаете писать это на машинном языке (ассемблер).

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