Имплементация паттерна прототипа

предыдущая серия

На высшем уровне абстракции имплементация паттерна свойств задается минималистичным API. Это базовый API для любой структуры, которая раскладывает имена/ключи на значения.

get(name)
put(name, value)
has(name)
remove(name)

В идеале, объекты, поддерживающие такой API (Стив упоминает тип Map из Java — стандартный словарь), желательно связывать в графы. Так, рекомендовано названия некоторых ключей резервировать — например, «parent» будет указывать на родительский объект. Зачем нужен родитель? Чтобы обращаться к нему (и далее по цепочке вверх), если запрошенного у текущего объекта свойства (ключа) нету.

Вот это всё, собственно, и есть абстрактный паттерн свойств/прототипов!

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

Ключи

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

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

Цитирование

Удобная фишка в JavaScript — это возможность применения «нецитируемых» ключей. То есть случай

var person = { name: "Bob" }

аналогичен

var person = { "name": "Bob" }

Символическое имя свойства name на самом деле не трактуется как идентификатор, а просто разрешает значение через таблицу символов.

Стив тут отсылает к Питону — типа, сравните с ним. Да, похожая схема реализована в одном из больших проектов на Python, где я участвовал. Там был создан специальный тип S с хорошим синтаксическим сахарком, экземпляры которого могли иметь как свойства-атрибуты, так и идентичные символические ключи. Этот тип очень удачно применялся в реалтаймовой highload-подсистеме файлового хранения, и вот теперь я могу привести свой пример в качестве эталонной реализации паттерна свойств!
То есть, синтаксис допускался такой:

s = S()
s.name = "abcd"
s["name"] = "efgh"

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

Отсутствующие ключи

Что делать в таком случае? Тут надо рассмотреть наиболее популярные внутрипроектные практики. Например, если свойства часто добавляются и удаляются, обращение к отсутствующему свойству может возвращать null (в таком случае удаляемый ключ на самом деле остаётся в объекте, но получает пустое значение). Это скорее вопрос микро-оптимизации на низком уровне.

Структуры данных

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

Следующий массовый способ — хэш-таблица. Она уже допускает поиск/вставку/удаление за фиксированное время, но требует побольше памяти, ну и само время доступа тоже зависит от сложности хэш-функции. Стив оценивает, что хэш-таблицу имеет смысл применять, когда количество свойств достигает 40-50. Если же по каким-то причинам мы хотим использовать упорядоченные имена свойств, лучше задействовать упорядоченное двоичное дерево.

На самом деле, хотя Steve Yegge уделяет этой теме довольно большое внимание, я считаю, что в реальных крупных и сложных проектах проблема эффективности паттерна свойств скорее всего никогда не попадёт даже во вторую десятку «узких горлышек». Здесь вполне можно задействовать стандартную структуру данных Map (Dictionary/словарь) под нужные типы данных.

Единственное, отмечу такой рекомендованный Стивом финт, как перемещение запрошенного элемента списка в голову списка. Таким образом часто запрашиваемые свойства всегда будут «пузыриться» в начале списка, и экономия тут может быть очень внушительная.

продолжение

Поделиться статьей ...Share on Facebook0Share on Google+0Tweet about this on TwitterShare on LinkedIn0Share on VKPrint this page

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

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