Здравствуйте! Это серия из 47 частей, в которой делается попытка дать введение в алгоритмы. Контент, который я использую здесь для написания этой серии, взят из MIT 6.006 Introduction to Algorithms, Fall 2011. Во второй части серии мы поговорим о моделях вычислений и алгоритме, называемом Document Distance.

Прежде чем говорить о чем-либо еще, давайте сначала попробуем определить алгоритм.

Что такое алгоритм?

По словам профессора MIT 6.006 Introduction to Algorithms, алгоритм Эрика Демейна - это

  • Вычислительная процедура для решения задачи
  • Алгоритм - математический аналог (математическая абстракция) компьютерной программы.

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

Модель вычислений

Модель расчета указывает

  • Какая операция разрешена по алгоритму
  • Сколько это стоит (что такое сложность?) (Время, пространство,…)
  • Стоимость алгоритма = сумма стоимости операции

Давайте поговорим о двух моделях вычислений

  • Машина с произвольным доступом (также известная как ОЗУ, а не память с произвольным доступом, это не опечатка)
  • Указатель машины

Машина с произвольным доступом

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

Что касается оперативной памяти, то это, по сути, большой массив. Оперативная память обычно организована по словам.

Чтобы вычислить с его помощью, мы можем сказать, что в Θ (1) (Постоянное время) алгоритм может

  • Загрузить Θ (1) постоянное количество слова из памяти
  • Выполните Θ (1) количество вычислений (+, -, *, /, ^, &, |)
  • Магазин Θ (1) слов

Эта машина с произвольным доступом - это то, как мы думаем о компьютерах, это точная модель вычислений, загрузка, вычисление и хранение которых занимают примерно Θ (1) постоянное количество времени. Мы можем манипулировать целым словом за постоянное время.

Некоторое время назад мы ввели слово, что означает слово

  • Мы знаем, что компьютер 32- и 64-битный, но, если быть немного более абстрактным, слово - это w бит.

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

Итак, машина произвольного доступа - это реалистичная модель, а также мощная модель, но во многих кодах не используются массивы, и они могут нам не понадобиться, поэтому мы должны думать о более абстрактных моделях, которые не так мощны, но предлагают более простые образ мыслей о вещах. Например, модель произвольного доступа не имеет динамического распределения памяти, мы знаем, что можем распределять память динамически, мы видели, как они реализованы на наших компьютерах. Но приятно подумать о какой-то модели, которая уже заботится о таких вещах, как динамическое распределение памяти. Это похоже на абстракцию программирования более высокого уровня. У нас есть одна модель, которая в основном помогает нам легко обойтись с динамическим распределением памяти, называемая Pointer Machine.

Указатель

Pointer Machine соответствует объектно-ориентированному программированию в более простой версии. Итак, у нас есть

  • Динамически размещаемые объекты
  • Объекты имеют постоянное количество Θ (1) полей
  • Поле = Слово (например, int) или указатель (здесь указатель получает свое имя). Что такое указатель? Указатель - это то, что указывает на другой объект или имеет специальное значение null.

Изображение выше показывает нам связанный список, связанный список имеет множество полей в каждом узле, у нас может быть указатель на предыдущий элемент, указатель на следующий элемент и некоторое значение. Чтобы быть точным, на изображении показан тип связанного списка под названием Двусвязный список, который мы называем Двойным, потому что каждый узел имеет два указателя, указывающих на предыдущий узел и следующий узел. Указатель prev начального узла и указатель next последнего узла указывают на нулевое значение. На самом деле у нас есть двухузловой двусвязный список на картинке.

Итак, это структура в машине указателя, это тип структуры данных, в python мы могли бы назвать это кортежем или объектом с тремя атрибутами, а значение в этой структуре можно назвать словом. Мы можем реализовать эту модель в машине произвольного доступа, и указатель станет индексом гигантской таблицы, которая в основном представляет собой массив в машине произвольного доступа. Собственно, именно так был реализован указатель на языке программирования C.

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

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

Это все касалось теории, поэтому давайте поговорим о практическом подходе с использованием модели Python.

Модель Python

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

Давайте потратим немного времени на то, чтобы выяснить, какая работа Python выполняется быстрее, а какая медленнее.

Возьмем операцию L [i] = L [j] + 5, где L - это список. В python эта операция всегда будет занимать Θ (1) раз (этот пример напоминает машину произвольного доступа). В других языках программирования это может занять линейное время, так как он должен сканировать список L до j, добавить 5 и поместить результат, снова просмотрев список L до i.

Объекты (похожие на модель указателя) с атрибутами O (1). x = x.next здесь x - указатель в связанном списке, когда есть такая операция, она также занимает Θ (1) времени в модели Python.

Я уже давно говорю о постоянном времени Θ (1), мы не особо заботимся об этом постоянном времени, потому что нас интересует только масштабируемость с n, а в этом случае n нет.

Список (в Python массивы называются списком)

L.append (x) (здесь L - список) Чтобы понять, сколько это стоит, нам следует подумать о том, как это реализовано с точки зрения базовой операции (L [i] = L [j] + 5, объекты x = x.next). Большинство вещей, которые мы делаем, можно свести к этим двум терминам. Итак, вернемся к добавлению. В основном, думая о том, как работает добавление, у нас есть определенный размер массива и мы хотим добавить элемент, чтобы сделать его на один элемент больше, как нам это сделать? Очевидный способ - создать новый массив, размер которого на один больше, чем у исходного, скопировать все содержимое в новый массив и добавить последний элемент. Если вы раньше писали программу на C, то именно так работает malloc / realloc. Этот подход хорош, но требует линейного времени. В случае с python это не так, мы подробно поговорим о том, как это работает, в более позднем сообщении в блоге, а пока скажем, что он просто выполняет что-то, называемое удвоением таблицы, которое стоит примерно постоянно. время Θ (1) большую часть времени.

L = L1 + L2 (L, L1, L2 - списки)

добавление занимает Θ (1) раз

Θ (| L1 |) порядок длины L1

Θ (| L2 |) порядок длины L2

Наконец эта операция берет Θ (1+ | L1 | + | L2 |), откуда взялась 1? Если длина L1 и L2 равна нулю, для построения пустого массива по-прежнему требуется постоянное время.

В большинстве случаев люди путаются и говорят, что операция L = L1 + L2 занимает постоянное время, потому что они видят + на операции. Это занимает постоянное время, только если L1 и L2 - простые переменные, но в нашем случае это не целые данные. структура называется списком (массивом), поэтому при анализе алгоритма мы должны учитывать используемую структуру данных.

x в L (L - список)

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

len (L) (L - список)

Эта операция занимает Θ (1) времени. Каким образом эта операция в Python занимает постоянное время? Потому что в python список реализован со встроенным счетчиком, что упрощает определение длины списка. В других языках программирования эта операция может занять линейное время, так как для подсчета длины списка необходимо пройти через весь список, честно говоря, все это связано с тем, как операция реализована на языке программирования.

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

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

В. Предположим, у нас есть два длинных целых числа x и y, сколько стоит их сложить?

Проблема с расстоянием до документа

В задаче о расстоянии документа у нас есть два документа D1 и D2, и мы хотим вычислить расстояние между ними, представленное как:

d(D1, D2)

Итак, большой вопрос в том, что означает расстояние?

Расстояние здесь означает выяснение того, похожи ли два документа или нет / Дубликаты или нет

Документ = Последовательность слов

Слово = последовательность буквенно-цифровых символов

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

Мы также можем рассматривать документ как вектор, поэтому

D [W] = # вхождение слова W в документе D

Например

Возьмем два документа

D1 = «кот»

D2 = «собака»

Мы можем представить их в трехмерном пространстве, потому что здесь, в нашем документе, есть три разных слова D1 и D2.

D1 и D2 на рисунке выше являются векторами.

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

d’(D1, D2) = D1.D2 = wD1[W].D2[W]

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

d’’(D1, D2) = (D1.D2)/(|D1|.|D2|)

Что ж, это был довольно длинный блог. Надеюсь, вы поняли то, что я имел в виду в этом блоге. Если вам нужна ссылка, откуда я взял контент для написания этого блога, тогда ссылка будет указана ниже.