Что такое нотация в программировании
Перейти к содержимому

Что такое нотация в программировании

  • автор:

Венгерская нотация

Венге́рская нота́ция в программировании — соглашение об именовании переменных, констант и прочих идентификаторов в коде программ. Своё название венгерская нотация получила благодаря программисту компании Microsoft венгерского происхождения Чарльзу Симони (венг. Simonyi Károly ), предложившему её ещё во времена разработки первых версий MS-DOS. Эта система стала внутренним стандартом Майкрософт [1] .

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

Применяемая система префиксов зависит от многих факторов:

  • языка программирования (чем более «либеральный» синтаксис, тем больше контроля требуется со стороны программиста, а значит, тем более развита система префиксов. К тому же использование в каждом из языков программирования своей терминологии также вносит особенности в выбор префиксов);
  • стиля программирования (объектно-ориентированный код может вообще не требовать префиксов, в то время как в «монолитном» для разборчивости они зачастую нужны);
  • предметной области (например, префиксы могут применяться для записи единиц измерения);
  • доступных средств автоматизации (генератор документации, навигация по коду, предиктивный ввод текста, автоматизированный рефакторинг и т. д.).

Примеры

Префиксы, задающие тип

Префикс Сокращение от Смысл Пример
s string строка sClientName
sz zero-terminated string строка, ограниченная нулевым символом szClientName
n, i int целочисленная переменная nSize, iSize
l long длинное целое lAmount
b boolean булева переменная bIsEmpty
a array массив aDimensions
t, dt time, datetime время, дата и время tDelivery , dtDelivery
p pointer указатель pBox
lp long pointer двойной (дальний) указатель lpBox
r reference ссылка rBoxes
h handle дескриптор hWindow
m_ member переменная-член m_sAddress
g_ global глобальная переменная g_nSpeed
C class класс CString
T type тип TObject
I interface интерфейс IDispatch
v void отсутствие типа vReserved

Как видно в приведённом примере, префикс может быть и составным. Например, для именования строковой переменной-члена класса использована комбинация префиксов «m_» и «s» ( m_sAddress ).

Префиксы, задающие смысл

Венгерская нотация для приложений:

Префикс Сокращение от Смысл Пример
i index Индекс int ix; Array[ix] = 10;
d delta Разница между значениями int a, b; . dc = b — a;
n number Количество size_t nFound = 0;

За и против

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

Преимущества

  • Если встроенного механизма типизации не хватает, венгерская нотация позволяет записывать подтип переменной — например, int cPrice может означать, что переменная имеет не просто целый тип, а валютный (currency). Именно такое применение префиксов было предложено Симони [2] . Это может пригодиться:
    • В низкоуровневом программировании (когда набор доступных типов настолько узок, что, например, целый тип не отличается от булевого).
    • В языках с динамической типизацией, например PHP, где одна и та же переменная может хранить значения любого типа.
    • В инженерных расчётах (для записи единиц измерения). Это позволяет избавиться от немалого количества ошибок простым подсчётом размерностей.
    • В других местах, где переменные одного и того же типа предназначены для хранения разнородных данных — например, в коде защиты от компьютерных взломщиков префикс может указывать на «безопасные» и «небезопасные» данные (SQL-инъекция, XSS).

    Этот стиль выбора имён называется «венгерской» записью по названию родины руководителя отдела программирования Microsoft Чарльза Симони, который его изобрёл. (А не потому, что его использование придаёт программам такой вид, будто они написаны на венгерском языке [3] )

    А. Голуб. Верёвка достаточной длины.

    Недостатки

    • Некоторые программисты считают, что использование префиксов делает имена переменных менее понятными и, таким образом, ухудшает читаемость кода. [4]
    • Если известно имя переменной без префиксов, подчас трудно восстановить её префиксы.
    • Система автодокументации, если она не понимает системы префиксов, отсортирует алфавитный список по префиксу, что может отрицательно сказаться на качестве документации. Впрочем, имена функций обычно префиксами не снабжают.
    • Запись нескольких префиксов из-за частого использования заглавных букв и знаков подчёркивания может стать «пляской на кнопке ⇧ Shift».
    • Средства навигации, которые включены в современные редакторы кода, и так позволяют видеть тип любой переменной и быстро переходить к точке, где она определена — то есть, использование префиксов может быть избыточным.
    • При изменении типа потребуется изменять имя переменной (большинство программистских редакторов не могут делать это автоматически). [4]
    • Существуют и другие средства задания типа переменной в её имени: например, слова is, has и т. д. для булевского типа ( IsLoggedIn ), count для счётчика ( RefCount ), множественное число для массива ( UserIds ). В языках, в которых заглавные буквы не эквивалентны строчным, регистр букв также может кодировать что-либо.

    Известный противник венгерской нотации — Линус Торвальдс: «Вписывание типа переменной в её имя (так называемая венгерская нотация) ущербно — компилятор и так знает типы и может проверить их, и это запутывает программиста» [5] .

    См. также

    Примечания

    1. Hungarian Notation
    2. Джоэл Спольски. Как заставить неправильный код выглядеть неправильно
    3. Венгерский язык, хоть и имеет латинский алфавит, считается крайне неудобочитаемым для неосведомлённых.
    4. 12Inside C++ — Венгерская нотация
    5. «Linux kernel coding style». Документация по ядру Linux (на английском).
    • Стандарт оформления кода

    Нотации выражений

    Средства описания данных декларируют элементы и типы данных, используемые в программе.

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

    Методы для описания синтаксиса выражений автоматически распространяются на остальные средства ЯП.

    ЯП вносят некоторую специфику в запись математических выражений. Например, математическое выражение

    на языке FORTRAN записывается в виде

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

    Префиксная нотация выражения

    (в сегменте -Ь), а sqrt записана перед выражением, к которому она применяется.

    Различают три нотации: инфиксную, префиксную и постфиксную [3, 31, 32, 84].

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

    В инфиксной нотации бинарная операция записывается между ее операндами: a + Ь. В префиксной нотации операция записывается первой: + a Ь, а в постфиксной нотации операция записывается последней: a Ь +.

    Выражение может заключаться в скобки, это не влияет на его значение. Выражение Е, как правило, имеет то же значение, что и (Е).

    Венгерская нотация (Hungarian Notation)

    «Венгерское соглашение» об именах идентификаторов Чарльза Симонии.

    Примечание от dr. GUI

    Еще во времена разработки первых версий DOS, доктор Чарльз Симонии представил соглашение об именах идентификаторов, в котором для указания функционального назначения объекта, представленного идентификатором используется добавление префикса к имени идентификатора.

    Данная система является широко используемым внутренним стандартом фирмы Microsoft. Причиной для этого является то, что префиксы к именам делают просмотр исходных текстов и спецификаций более простым. Название «Венгерская нотация» появилось из-за того, что имена переменных как бы написаны на иностранном языке, и сам доктор Симонии родом из Венгрии.

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

    Возможно самой важной публикацией, пропагандирующей Венгерскую нотацию была первая книга, читаемая почти каждым Windows — программистом: «Windows programmin» Чарльза Петцольда. В книге данное соглашение использовалось для примеров и примечаний и было кратко описано в первой главе.

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

    Соглашение об идентификаторах в программе.

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

    При введении нового идентификатора в программу, хороший программист учитывает следующие факторы:

    1. мнемоническое значение: идентификатор должен легко запоминаться
    2. смысловое значение: роль идентификатора должна быть ясна из его названия
    3. преемственность: часто рассматривается как чисто эстетическая идея, но все же, похожие объекты должны иметь похожие идентификаторы.
    4. скорость решения: придумывание, ввод и редактирование идентификатора не должны занимать слишком много времени, идентификатор не должен быть слишком длинным.

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

    Преимущества Соглашений

    Данные соглашения об идентификаторах обеспечивают удобную технологию для формирования имен, удовлетворяющих вышеупомянутым критериям. Основной идеей является передача основных характеристик идентификатора как части в его названии. Эта простая идея, безусловно, требует уточнения (что, например, предполагается под «критерием», что делать если они(критерии) не уникальны?). Однако, давайте сначала оговорим общие положения.

    Названия будут мнемоническими в строго определенном смысле: идентификатор будет очевиден для того, кто помнит название характеристики или принцип его построения.

    Названия имеют смысловое значение: должна быть возможность отобразить любое название в наборе характеристик.

    Названия будут непротиворечивы, так как произведены теми же самыми правилами.

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

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

    Правила обозначения

    Предлагаются следующие правила обозначения:

    1) Описание характеристики идентификатора входит в идентификатор. Удобной пунктуацией является указание характеристики перед названием, с разделением их (началом названия с большой буквы в Cи, например: rowFirst: row — характеристика, Fist — название).

    2) Название отличают идентификаторы, имеющие один и тот же тип и существующие в одном контексте. Контекстом может являться как система в целом, так и блок, процедура, структура данных в зависимости от среды программирования. Если существует стандартное название, оно должно быть использовано. Выбор должен быть максимально простым, так как требуется уникальность идентификатора только в пределах определенного контекста.

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

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

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

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

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

    Например мы создаем графическую программу. В данном случае у нас существует тип данных «цвет». Естественным желанием является сделать префикс color для обозначения цвета. Однако при детальном рассмотрении может оказаться, что применение термина color более удобно в приложении к названию, например: LineColor. Для обозначения цвета более выгодным является сокращение, например clr. clrDefault.

    Обозначение для упрощения написания.

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

    Обозначение для процедур.

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

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

    2) Начинайте название процедуры с тега типа возвращаемого значения, если таковое существует.

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

    4) В конец названия можно добавить список тегов некоторых или всех формальных параметров, если есть смысл.

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

    Таблица 1. Некоторые примеры для названий процедуры

    Описание Название
    InitSy Берет sy как его параметр и инициализирует его.
    OpenFn fn — параметр. Процедура «откроет» fn. Никакое значение не будет возвращено.
    FcFromBnRn Возвращает fc, для переданной пары Bn,Rn (Названия не передают нам информации о типе данных для Fc, Rn, Bn).

    Далее приведен список стандартных конструкций, X и Y замещают произвольные теги.

    Таблица 2. Стандартные конструкции типа

    pX Указатель на X.
    dX Различие между двумя образцами типа X. X + dX имеет тип X.
    cX Индекс образцов типа X.
    mpXY Массив Ys, индексированного по X.
    rgX Массив Xs.
    iX Индекс массива rgX.
    grpX Группа Xs, сохраненных последовательно. Используется когда X элементы имеют переменный размер и не применима стандартная индексация. Элементы X индексируются способом, отличным от обычного.
    bX относительное смещение к типу X. Используется для обращений к полям переменной длины в структурах. Смещение может быть указано в байтах или словах, в зависимости от вида индексации.
    cbX Размер X в байтах.
    cwX Размер X в словах.

    C конструкциями такого типа существует одна проблема. Например, является ли pfc собственно тегом или это указатель на fc. Ответ на такой вопрос может дать только человек, знакомый с принятой в рамках контекста системой именования.

    Далее приведены стандартные имена. X замещает любой тег типа, записанный в нижнем регистре.

    Таблица 3. Стандартные спецификаторы

    XFirst первый элемент в упорядоченном наборе X
    XLast последний элемент в упорядоченном наборе X
    XLim строгий верхний предел набора значений X. Границей цикла должно быть X
    XMax строгий верхний предел набора значений X. Если X начинается с 0, то XMax равен числу различных значений X.
    XT временное значение X.

    Таблица 4. Некоторые базовые типы

    f Флажок (Булева переменная, логическое значение). Используемое название должно относиться к истинному состоянию. Исключение: константы fTrue и fFalse.
    w Машинное слово
    ch Символ, обычно в тексте ASCII.
    b Байт
    sz Указатель на строку терминированную нулем (ASCIZ)

    Примечание от Николая Гехта

    Ниже приведены префиксы типов данных, наиболее часто используемые на данный момент при разработке для Win32

    Таблица 5. Базовые префиксы типов данных Win32

    g_ префикс для глобальной переменной
    m_ префикс для переменной класса
    c константа (префикс для типа) const
    l длинный (префикс для типа) far, long
    p указатель (префикс для типа) *
    ch char char
    b байт BYTE, unsinged char
    w 16-битное слово (2 байта) WORD, unsigned short
    dw 32-битное слово (4 байта) DWORD, unsigned long
    n,i целое int
    flt с плавающей точкой float
    dbl с плавающей точкой double
    f логическое BOOL
    sz ASCIZ строка char[]
    psz ASCIZ строка char *
    pcsz константа ASCIZ строка const char *
    pv произвольный указатель void *
    ppv указатель на произвольный указатель void **
    h хендл HANDLE, void *
    unk OLE объект IUnknown
    punk указатель на OLE объект IUnknown *
    disp Automation объект IDispatch
    pdisp указатель на Automation объект IDispatch *

    Что такое «O» большое в программировании?

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

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

    Но как выяснить, эффективна ли программа? Есть ли способ это определить? Как проверить, при передаче каких входных данных программа работает лучше всего?

    Прежде чем перейти к ответам, разберемся с тем, как вообще работает эффективная программа. И в этом поможет одна забавная история.

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

    Один метод заключался в использовании почтового голубя, к лапке которого привязали USB-флешку.

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

    Самое интересное заключалось в том, что голубь обогнал интернет. Но как?

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

    Перейдем к вычислительным сложностям

    Вот две сложности, связанные с программированием.

    • Временная: время, необходимое для обработки входных данных.
    • Пространственная: количество места, требуемое для обработки входных данных.

    Что такое нотация “О” большое?

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

    Проще говоря, термином “О” большое определяется, как время выполнения растет по мере увеличения входных данных.

    • Увеличение времени выполнения. Поскольку время, необходимое для выполнения программы, зависит от процессора компьютера, используется “О” большое, чтобы показать, как меняется время выполнения.
    • Ввод данных. Поскольку проверяется не только время, которое требуется для выполнения программы, но и ввод, в нотации “О” большое есть “n”, которое определяет количество элементов обрабатываемых входных данных. Поскольку время выполнения растет с увеличением размера входных данных, эту величину можно представить в виде O(n).
    • По мере увеличения входных данных. По мере увеличения входных данных программам иногда требуется больше времени для выполнения, что приводит к проблемам с производительностью. Поэтому разрабатываемую программу нужно проверять по мере увеличения входных данных.

    Визуализированные примеры

    O(1) не увеличивается с изменением размера входных данных. Таким образом, время обработки O(1) — величина постоянная независимо от того, какие входные данные были переданы.

    Пример:

    let names = ['Atit', 'mahesh', 'ramesh', 'kamlesh'];
    let data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
    function checkLength(data) return data.length;
    >
    console.log(checkLength(names)); // 4
    console.log(checkLength(data)); // 10

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

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

    Пример:

    function print(array) for (var i = 0; i < array.length; i++) console.log(array[i]); 
    >
    >
    print(names) //4 times
    print(data) //10 times

    Показывает производительность пропорционально размеру входных данных. O(n²) представляет наихудшую производительность.

    Пример:

    function testdata(data) data.forEach(function(items) console.log('values ', data); 
    items.forEach(function(number) console.log('Marks', number); //
    >);
    >);
    >
    const test = [
    ['maths', 52],
    ['science', 65],
    ['english', 72]
    ]
    testdata(test)

    Логарифмическая | O(log n)

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

    Пример:

    function log(n) for (let i = 1; i < n; i = i * 2) const result = i; 
    console.log(result);
    >
    >
    log(4); //2

    Для данной программы с любыми итерациями значение i = i*2. Поэтому на n-й итерации значение i= i*n и i всегда меньше размера самого цикла (N).

    Следовательно, можно получить:

    2^n < N
    log(2^n) < log(N)
    n < log(N)

    Таким образом, наихудшая временная сложность такого алгоритма будет равна O(log(n)).

    Отбросим константы

    Существует вероятность того, что O(N) код быстрее, чем O(1) код для определенных входных данных. “О” большое просто описывает скорость увеличения. По этой причине мы отбрасываем константу, что означает, что O(3N) на самом деле O(N):

    Можно отбросить не только константы, но и неглавные члены:

    • O(N3+N) → O(N3)
    • O(N+logN) → O(N)
    • O(2∗2N + 1000N100) → O(2N)

    Как вычислить сложность?

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

    Циклы (Loops)

    • Внутри цикла операторы повторяются n раз. Если для выполнения кода требуется сложность O(m), то внутри n раз повторенного цикла она будет равна n∗O(m) или O(n∗m).
    for (let i in arr1) print(i);
    >
    • Количество циклов будет равно 4, а выполнение кода внутри цикла равно O(1), поэтому суммарное выполнение будет равно O(4).

    Вложенные циклы ( Nestedloops )

    • Если один цикл находится внутри другого цикла, сложность будет расти экспоненциально. Другими словами, если сложность простого цикла равна O(n), добавление еще одного цикла внутри этого цикла сделает сложность O(n²).
    for (let i in arr1) print(i); 
    for (let j in i) <>
    >
    • Здесь сложность первого цикла равна O(5), поскольку количество массивов равно 5, поэтому вложенный цикл также выполняется с той же сложностью 5 раз, а значит, оба цикла будут O(5²).
    • Важные аспекты математики в науке о данных — «что» и «почему»
    • Решение алгоритмических проблем: Поиск повторяющихся элементов в массиве
    • 8 показателей эффективности классификации

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *