Палиндромы и многое другое

Автор оригинала: Fernando Pelliccioni.

Я решил написать эту статью, исходя из вопроса, который я видел в stackoverflow.com

Здесь ссылка на вопрос.

Спрашивающий пытается написать алгоритм, чтобы определить, является ли “слово” палиндромом или это не так. Алгоритм написан с использованием языка программирования Java

Я не хочу анализировать алгоритм, предложенный задающим вопрос, но я хочу проанализировать алгоритм ответа, за который проголосовали больше всего. У последнего 73 голоса против 65 голосов, которые приняли ответ (на сегодняшнюю дату, 6 июня 2016 года).

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

Вот код:

public static boolean isPalindrome(String str) {
    return str.equals(
       new StringBuilder(str)
       .reverse()
       .toString()
    );
}

Алгоритм работает правильно, а логика очень интуитивно понятна. В основном сравнивает равенство входное слово с его обратным значением.

Проблема с этим алгоритмом заключается в том, что он очень неэффективен по сравнению с оптимальным алгоритмом.

Я сделал комментарий автору алгоритма на Stackoverflow: “Сравните сложность вашего алгоритма с другими. ” Пользователь @aioobe ответил: “Я думаю, что это та же сложность, что и другие решения, не так ли?”

Он прав. Я не был очень конкретен в своем комментарии. @aioobe наверняка предположил, что я имел в виду асимптотическую вычислительную сложность и он в порядке, потому что обычно, когда мы говорим “сложность”, не указывая ничего другого, предполагается, что мы имеем в виду асимптотическую вычислительную сложность .

Асимптотическая Вычислительная Сложность

Асимптотический асимптотический вычислительный означает, как алгоритмы реагируют во времени и пространстве по мере роста входных данных. It is usually associated with the O-notation introduced by Павел Бахман in his book Аналитическая теория чисел//в 1894 г. [1]

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

Хотя это очень полезно во многих обстоятельствах, этот метод измерения не является точным, но он приближен .

Для получения дополнительной информации о O-нотации и асимптотической сложности см. [2] .

Конкретная Вычислительная Сложность

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

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

Вернемся к палиндромам

Опять же, код алгоритма.

public static boolean isPalindrome(String str) {
    return str.equals(
       new StringBuilder(str)
       .reverse()
       .toString()
    );
}

Я позвонил Алгоритм Я к предыдущему коду. (“Я” как неэффективное).

Мы могли бы сказать, что Алгоритм I is O(n) , но как мы можем гарантировать это, не зная сложности компонентов, на которых основан алгоритм?

Для этого мы должны ознакомиться с документацией Java. Например, рассмотрим функцию String.equals () . [3]

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

Чтобы продолжить попытки указать сложность Алгоритм Я , у нас нет выбора, мы должны просмотреть исходный код классов Java. Рассмотрим исходный код String.equals() (нажмите на ссылку и найдите функцию equals.)

Как вы можете убедиться, строка кода.equals() имеет линейную сложность во времени, O(n) . В частности, String.equals() выполняет n сравнения ( неравенство ). (Помимо шума, создаваемого Java, такого как приведения, instanceof и т. Д.).

Пространственная сложность String.equals() постоянна, то есть O(1) . Это означает, что он использует постоянную память за пределами ввода алгоритма.

Определение сложности

Мы определим сложность Алгоритм I анализ каждого компонента.

Строка.равно() . Линейное время, n |/сравнение неравенства . Постоянное пространство.

StringBuilder.обратный() . Линейное время, 2 * этаж(n/2) задания. Постоянное пространство.

StringBuilder.toString() . Линейное время, n задания. Линейное пространство, n элементов.

Конструктор StringBuilder . Линейное время, n + 16 задания. Линейное пространство, n + 16 элементов.

Таким образом, общая сложность Алгоритм Я есть:

Время : В худшем случае, когда слово является палиндромом , этот алгоритм принимает n | неравенство сравнения и 2n + 2 этажа(n/2) + 16 назначений. Пространство : 2n + 16 элементы.

Как вы можете видеть, этот алгоритм очень неэффективен, он использует много памяти (без необходимости) и, как описано ниже, берет на себя 8x операций оптимальный алгоритм .

Улучшение алгоритма (наивная версия)

Вызовите следующий код Алгоритм N (N как наивный). Алгоритм N представляет собой существенное улучшение по сравнению с Алгоритм I .

public static boolean isPalindrome(String str) {
    int n = str.length();
    for (int i = 0; i < n; ++i) {
        if (str.charAt(i) != str.charAt(n-i-1)) return false;
    }
    return true;
}

Время : В худшем случае, когда слово является палиндромом , этот алгоритм принимает n | неравенство сравнения. Пространство : Постоянный

Не требует дополнительного использования памяти и работает примерно 1/4 операций что Алгоритм I . Хотя сейчас код немного сложнее, это легко понятный код, возросшая сложность кода незначительна по сравнению с повышением эффективности.

Оптимальный алгоритм

Как мы видим на рисунке ниже, нет необходимости проводить n сравнения, чтобы определить, является ли слово палиндромом .

Этого достаточно, чтобы сделать только (примерно) половину сравнений:

• Если n четно, он выполняет n/2 сравнения
• Если n нечетно, он выполняет (n - 1)/2 сравнения.

Следующий код будет называться Алгоритм O (O как оптимальное).

public static boolean isPalindrome(String str) {
    int n = str.length();
    for (int i = 0; i < n/2; ++i) {
        if (str.charAt(i) != str.charAt(n-i-1)) return false;
    }
    return true;    
}

Время : В худшем случае, когда слово является палиндромом , этот алгоритм выполняет пол(n/2) | неравенство сравнения. Пространство : Постоянный

Алгоритм I, детальный анализ

Как объяснялось ранее, Алгоритм I гораздо более неэффективен, чем Алгоритмы N и Алгоритмы O . Но помимо анализа сложности, мы должны рассмотреть другие вопросы, которые влияют на эффективность Алгоритм I .

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

Строительство струностроителя

• Динамическое выделение памяти объекта StringBuilder ( куча, свободное хранилище или как вы это называете).
• Ноль-Инициализация членов StringBuilder. [4]
• Динамическое выделение памяти внутреннего массива Stringbuilder. Согласно документации, размер внутреннего массива равен 16 символам плюс размер исходной строки. [5]
• Ноль-Инициализация членов массива. Длина и сам массив. [4]
• Скопируйте байты исходной строки во внутренний массив Stringbuilder.

обратный() (строковый конструктор)

• Упомянуто выше. Эта функция не использует дополнительную память и эффективна во время выполнения.

toString() (строковый конструктор)

• Динамическое выделение памяти объекта String ( куча, свободное хранилище или как вы это называете).
• Ноль-Инициализация элементов строки. [4]
• Динамическое выделение памяти внутреннего массива строки.
• Ноль-Инициализация членов массива. Длина и сам массив. [4]
• Скопируйте байты из внутреннего массива Stringbuilder во внутренний массив Строки.

равно() (Строка)

• Упомянуто выше. Эта функция не использует дополнительную память и эффективна во время выполнения.

Вывоз Мусора

• GC должен освободить любую дополнительную память (ненужную), которая использовалась, и, очевидно, эта операция не является “бесплатной”.

Пропуски в кэше Данных

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

Объем памяти

Для анализа потребления памяти Алгоритм Я , мы будем использовать конкретный пример. Мы будем использовать 9-символьный палиндром ,

isPalindrome("evitative");

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

В основном в нашем примере создаются два объекта, один StringBuilder и одна строка.

Строковый конструктор:

Объекты StringBuilder имеют следующее представление в памяти.

Объект StringBuilder состоит из двух частей (не обязательно смежных в памяти):

• Первая часть: размер использования массива (длина() StringBuilder) и ссылка на массив, в котором хранятся данные.
• Вторая часть: размер массива (емкость() StringBuilder) и массив. Размер массива составляет 16 символов плюс количество символов исходной строки (“evitative”) [5] . На картинке эти 16 дополнительных символов выделены красным цветом, чтобы подчеркнуть, что это пустая трата памяти. В Java символы имеют размер 2 байта. [6] Таким образом, в нашем примере массив будет иметь размер 2 * (9 + байт.

В Java все объекты имеют заголовок (если известна какая-либо реализация, в которой ее нет, дайте мне знать ) в нашей платформе заголовок составляет 12 байт. В других популярных платформах может быть 8 или 16 байт, смотрите здесь [7] .

Еще одна вещь , которую следует учитывать, – это заполнение , которое в основном представляет собой пространство памяти, добавляемое для выполнения требования выравнивания . В нашем случае объекты должны быть размещены по 8-кратным адресам памяти.

Таким образом, наш объект StringBuilder имеет следующий размер памяти (в байтах):

Первая часть: 24 Вторая часть: 16 + 2n + 32 + дополнение [8]

Итого: 8(ceil(n/4) + 9) байт

Строка:

Объекты String имеют следующее представление в памяти.

Строковый объект состоит из двух частей (не обязательно смежных в памяти):

• Первая часть: ссылка на массив (где хранятся данные) и хэш .
• Вторая часть: размер массива (длина() строки) и массива.

Описанный здесь строковый объект принадлежит Java 8 . В более старых версиях Java класс String имел больше полей, поэтому объем памяти был больше. [7]

Таким образом, наш строковый объект имеет следующий размер памяти (в байтах):

Первая часть: 24 Первая часть: 16 + 2n + дополнение [8]

Итого: 8(ceil(n/4) + 5) байт

Общий объем памяти:

Общая память, используемая нашим StringBuilder и строковыми объектами, составляет 16(ceil(n/4) + 7) байт.

В нашем примере n , поэтому используется память 16(ceil(9/4) + 7) байты, которые представляют 160 байт дополнительной памяти, только для того, чтобы определить, является ли “evitative” палиндромом или нет. Помните, что эти 160 байт-совершенно ненужное потребление памяти.

Контрольные показатели

Я делал некоторые тесты, в которых видно, что Алгоритм I примерно 8.5 x медленнее, чем алгоритмы O и Н .

Я опускаю некоторые другие критерии, которые показывают ~500x разницу по сравнению с Алгоритм I .

Вы можете увидеть исходный код тестов в моей учетной записи GitHub .

Объяснение критериев и кодекса будет представлено в следующей статье.

Алгоритм N по сравнению с Алгоритмом

Хотя ранее мы видели, что Алгоритм O выполняет половину операций, чем Алгоритм N , в худшем случае; на время выполнения обоих алгоритмов влияет несколько факторов, в том числе: длина слова, является ли слово палиндромом или нет, и другие факторы, относящиеся к платформе.

Во многих случаях Алгоритм N работает быстрее, чем Алгоритм O .

Мы обсудим это в одной из будущих статей.

Окончательное решение?

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

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

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

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

Нерешенные вопросы

Повторите Алгоритм ввода в C# и проанализируйте его эффективность по времени выполнения и потреблению памяти.

Выводы

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

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

Хотя абстракции хороши, у них есть большой недостаток. Они заставляют нас забыть, как работает машина. Современные программисты часто злоупотребляют абстракциями, и у них нет знаний об очень важных вещах, которые влияют на поведение наших программ, таких как память, кэш, буферы загрузки/хранения, предсказание ветвлений, конвейеры, модели памяти, векторные инструкции (SIMD) и т.д…

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

Я не хочу забывать упомянуть, что лучшая из всех абстракций была открыта Лейбниц |/в 1679 г. Эта абстракция и позволяет нам моделировать реальный мир на компьютере. Эта абстракция является битом .

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

public static boolean isPalindrome(String str) {
    //postcondition: Result := reverse(str) = str
    int n = str.length();
    for (int i = 0; i < n/2; ++i) {
        if (str.charAt(i) != str.charAt(n-i-1)) return false;
    }
    return true;    
}

Признание

Я хочу поблагодарить Марио дал Лаго и Хавьера Велилью за рецензию на статью и предложения по исправлению. И, наконец , поскольку мы можем сказать, что мы обязаны своими жизнями палиндромам , так что им отдельное спасибо.

Записи

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

Платформа, используемая для анализа в этой статье:

• ЦП
  • Процессор Intel Core i7-4700MQ ПРОЦЕССОР @ 2,40 ГГц, Хасвелл
  • 4 Ядра, 8 Потоков
  • Размер кэша данных L1 4 x 32 Кбайт
  • Размер кэша инструкций L1 4 x 32 Кбайт
  • L2 Унифицированный размер кэша 4 x 256 Кбайт
  • Размер унифицированного кэша L3 6144 Кбайт
• ОПЕРАТИВНАЯ память: 8192 Мбайт, DDR3
• Операционная система: Windows 10 Home 64-разрядная
• Ява
  • Версия 1.8.0_60
  • Среда выполнения Java(TM) SE (сборка 1.8.0_60-b27)
  • 64-разрядная Горячая виртуальная машина .
  • Сжатые Упс включены.
  • Выравнивание объектов : 8 байт.

Для анализа на других платформах, пожалуйста, обратитесь к [7] .

Рекомендации

Смотрите ссылки в полной статье: Смотрите ссылки в полной статье:

Оригинал: “https://www.codementor.io/@fernandopelliccioni/palindromes-and-more-z21xwpn37”