...

суббота, 21 мая 2016 г.

Генерация классов из БД с помощью DataGrip

Открытые лекции для школьников и студентов про типизацию в языках программирования

Генерация классов из БД с помощью DataGrip

Открытые лекции для школьников и студентов про типизацию в языках программирования

Генерация классов из БД с помощью DataGrip

Открытые лекции для школьников и студентов про типизацию в языках программирования

Генерация классов из БД с помощью DataGrip


В этой небольшой заметке будет показано, как написать DataGrip расширение для генерации кода (в данном случае POCO (C#) классов) на основе таблиц из почти любой БД (SQL Server, Oracle, DB2, Sybase, MySQL, PostgreSQL, SQLite, Apache Derby, HyperSQL, H2).


Предисловие



DataGrip это относительно новая IDE от JetBrains для работы с разными СУБД имеющая некоторый API для расширения функционала. Задача — используя его написать генератор POCO (C#) классов.
Если вы не хотите читать все это, а желаете просто начать генерировать классы, то вот ссылка на репозиторий со скриптом в заключении.


Написание скрипта


DataGrip позволяет расширить свою функциональность с помощью скриптов (Scripted Extensions). Поддерживаются языки Groovy, Clojure и JavaScript. Документация на сайте об этом довольно краткая, но в распоряжении есть примеры и архив с API в виде исходного кода на Java. Исходный код можно найти в <DataGrip_installation_dir>/lib/src/src_database-openapi.zip. Примеры можно посмотреть в самой IDE в панели Files -> Scratches. Так же DataGrip поддерживает скрипты для экспорта данных в различные форматы (extractors, в данной статье рассмотрены не будут), примеры для форматов csv, json и html тоже находятся в панели Scratches.


Итак, для написания скрипта мы будем использовать Clojure, за основу был взят пример генератора POJO из IDE.
Подсветки синтаксиса и автодополнения для Clojure в DataGrip конечно же нет, поэтому можно использовать любой другой редактор.
Для начала настроим маппинги типов из БД на C# типы и объявим некоторые константы.


Код
(def usings "using System;")
(def default-type "string")
(def type-mappings
    [
        [["bit"] "bool"]
        [["tinyint"] "byte"]
        [["uniqueidentifier"] "Guid"]
        [["int"] "long"]
        [["char"] "char"]
        [["varbinary" "image"] "byte[]" true] ; cannot be null
        [["double" "float" "real"] "double"]
        [["decimal" "money" "numeric" "smallmoney"] "decimal"]
        [["datetime" "timestamp" "date" "time"] "DateTime"]
        [["datetimeoffset"] "DateTimeOffset"]
    ])
(def new-line "\r\n")


Далее напишем функцию которая приводит строку к PascalCase.


Код
(defn- poco-name [name]
    (apply str (map clojure.string/capitalize (re-seq #"(?:[A-Z]+)?[a-z\d]*" name))))

Матчинг типа из БД на тип в C# основываясь на маппингах которые мы определили ранее.


Код
(defn- poco-type [data-type is-null]
    (let [spec                (.. data-type getSpecification toLowerCase)
          spec-matches?       (fn [pattern] (= (re-find #"^\w+" spec) pattern))
          mapping-matches?    (fn [[ps t n]] (when (some spec-matches? ps) [t n]))
          [type cant-be-null]  (some mapping-matches? type-mappings)
          nullable-type       (if (and type (not cant-be-null) is-null) (str type "?") type)]
        (or nullable-type default-type)))

Функция которая получает все столбцы из таблицы, вызывает функцию матчинга и собирает нужный нам объект для дальнейшего сохранения. Здесь мы используем методы из API, например com.intellij.database.util.DasUtil/getColumns, все эти методы можно посмотреть в архиве src_database-openapi.zip упомянутом выше.


Код
(defn- field-infos [table]
    (let [columns    (com.intellij.database.util.DasUtil/getColumns table)
          field-info (fn [column] {:name (poco-name (.getName column))
                                   :type (poco-type (.getDataType column) (not (.isNotNull column)))})]
        (map field-info columns)))

Генерация текста для свойств и классов, ничего особенного просто конкатенация строк. А так же функция записи этого текста в файл.


Код
(defn- property-text [field-info]
    (let [type  (:type field-info)
          name  (:name field-info)]
        (str "  public " type " " name " { get; set; } " new-line)))

(defn- poco-text [class-name fields]
    (apply str (flatten
        [usings new-line new-line
         "public class " class-name " " new-line "{" new-line
         (interpose new-line (interleave (map property-text fields)))
         "}" new-line])))

(defn- generate-poco [directory table]
    (let [class-name (poco-name (.getName table))
          fields     (field-infos table)
          file       (java.io.File. directory (str class-name ".cs"))
          text       (poco-text class-name fields)]
        (com.intellij.openapi.util.io.FileUtil/writeToFile file text)))

И наконец функция открытия диалога выбора директории для сохранения файлов и функция которая определяет выбранные таблицы и запускает генерацию.


Код
(defn- generate-pocos [directory]
    (let [table? (partial instance? com.intellij.database.model.DasTable)]
        (doseq [table (filter table? SELECTION)]
            (generate-poco directory table))))

(.chooseDirectoryAndSave FILES
                         "Choose directory"
                         "Choose where to generate POCOs to"
                         (proxy [com.intellij.util.Consumer] []
                            (consume [directory]
                                (generate-pocos directory)
                                (.refresh FILES directory))))

Установка скрипта



Полный код скрипта на GitHub.
Для установки надо просто скопировать файл Generate POCO.clj в IDE > Files > Scratches > Extensions > DataGrip > schema.
И в контекстном меню таблиц появится соотвествующий пункт подменю в разделе Scripted Extensions.


Результат


Из следующей таблицы


Было
CREATE TABLE Users
(
    Id INT PRIMARY KEY NOT NULL IDENTITY,
    first_name NVARCHAR(255),
    Last_Name NVARCHAR(255),
    Email VARCHAR(255) NOT NULL,
    UserGuid UNIQUEIDENTIFIER,
    Age TINYINT NOT NULL,
    Address NVARCHAR(MAX),
    photo IMAGE,
    Salary MONEY,
    ADDITIONAL_INFO NVARCHAR(42)
);

будет сгенерирован следующий класс:


Стало
using System;

public class Users 
{
  public long Id { get; set; } 

  public string FirstName { get; set; } 

  public string LastName { get; set; } 

  public string Email { get; set; } 

  public Guid? UserGuid { get; set; } 

  public byte Age { get; set; } 

  public string Address { get; set; } 

  public byte[] Photo { get; set; } 

  public decimal? Salary { get; set; } 

  public string AdditionalInfo { get; set; } 
}

Заключение


Вот таким довольно простым способом можно генерировать C# классы которые описывают ваши таблицы в БД и сделать жизнь чуть менее рутинной. Конечно же, вы не ограничены только POCO классами C#, можно написать генератор чего угодно, для другого языка, фреймворка и т.д.

Комментарии (1)

    Let's block ads! (Why?)

    Открытые лекции для школьников и студентов про типизацию в языках программирования

    Генерация классов из БД с помощью DataGrip


    В этой небольшой заметке будет показано, как написать DataGrip расширение для генерации кода (в данном случае POCO (C#) классов) на основе таблиц из почти любой БД (SQL Server, Oracle, DB2, Sybase, MySQL, PostgreSQL, SQLite, Apache Derby, HyperSQL, H2).


    Предисловие



    DataGrip это относительно новая IDE от JetBrains для работы с разными СУБД имеющая некоторый API для расширения функционала. Задача — используя его написать генератор POCO (C#) классов.
    Если вы не хотите читать все это, а желаете просто начать генерировать классы, то вот ссылка на репозиторий со скриптом в заключении.


    Написание скрипта


    DataGrip позволяет расширить свою функциональность с помощью скриптов (Scripted Extensions). Поддерживаются языки Groovy, Clojure и JavaScript. Документация на сайте об этом довольно краткая, но в распоряжении есть примеры и архив с API в виде исходного кода на Java. Исходный код можно найти в <DataGrip_installation_dir>/lib/src/src_database-openapi.zip. Примеры можно посмотреть в самой IDE в панели Files -> Scratches. Так же DataGrip поддерживает скрипты для экспорта данных в различные форматы (extractors, в данной статье рассмотрены не будут), примеры для форматов csv, json и html тоже находятся в панели Scratches.


    Итак, для написания скрипта мы будем использовать Clojure, за основу был взят пример генератора POJO из IDE.
    Подсветки синтаксиса и автодополнения для Clojure в DataGrip конечно же нет, поэтому можно использовать любой другой редактор.
    Для начала настроим маппинги типов из БД на C# типы и объявим некоторые константы.


    Код
    (def usings "using System;")
    (def default-type "string")
    (def type-mappings
        [
            [["bit"] "bool"]
            [["tinyint"] "byte"]
            [["uniqueidentifier"] "Guid"]
            [["int"] "long"]
            [["char"] "char"]
            [["varbinary" "image"] "byte[]" true] ; cannot be null
            [["double" "float" "real"] "double"]
            [["decimal" "money" "numeric" "smallmoney"] "decimal"]
            [["datetime" "timestamp" "date" "time"] "DateTime"]
            [["datetimeoffset"] "DateTimeOffset"]
        ])
    (def new-line "\r\n")
    
    

    Далее напишем функцию которая приводит строку к PascalCase.


    Код
    (defn- poco-name [name]
        (apply str (map clojure.string/capitalize (re-seq #"(?:[A-Z]+)?[a-z\d]*" name))))
    

    Матчинг типа из БД на тип в C# основываясь на маппингах которые мы определили ранее.


    Код
    (defn- poco-type [data-type is-null]
        (let [spec                (.. data-type getSpecification toLowerCase)
              spec-matches?       (fn [pattern] (= (re-find #"^\w+" spec) pattern))
              mapping-matches?    (fn [[ps t n]] (when (some spec-matches? ps) [t n]))
              [type cant-be-null]  (some mapping-matches? type-mappings)
              nullable-type       (if (and type (not cant-be-null) is-null) (str type "?") type)]
            (or nullable-type default-type)))
    

    Функция которая получает все столбцы из таблицы, вызывает функцию матчинга и собирает нужный нам объект для дальнейшего сохранения. Здесь мы используем методы из API, например com.intellij.database.util.DasUtil/getColumns, все эти методы можно посмотреть в архиве src_database-openapi.zip упомянутом выше.


    Код
    (defn- field-infos [table]
        (let [columns    (com.intellij.database.util.DasUtil/getColumns table)
              field-info (fn [column] {:name (poco-name (.getName column))
                                       :type (poco-type (.getDataType column) (not (.isNotNull column)))})]
            (map field-info columns)))
    

    Генерация текста для свойств и классов, ничего особенного просто конкатенация строк. А так же функция записи этого текста в файл.


    Код
    (defn- property-text [field-info]
        (let [type  (:type field-info)
              name  (:name field-info)]
            (str "  public " type " " name " { get; set; } " new-line)))
    
    (defn- poco-text [class-name fields]
        (apply str (flatten
            [usings new-line new-line
             "public class " class-name " " new-line "{" new-line
             (interpose new-line (interleave (map property-text fields)))
             "}" new-line])))
    
    (defn- generate-poco [directory table]
        (let [class-name (poco-name (.getName table))
              fields     (field-infos table)
              file       (java.io.File. directory (str class-name ".cs"))
              text       (poco-text class-name fields)]
            (com.intellij.openapi.util.io.FileUtil/writeToFile file text)))
    

    И наконец функция открытия диалога выбора директории для сохранения файлов и функция которая определяет выбранные таблицы и запускает генерацию.


    Код
    (defn- generate-pocos [directory]
        (let [table? (partial instance? com.intellij.database.model.DasTable)]
            (doseq [table (filter table? SELECTION)]
                (generate-poco directory table))))
    
    (.chooseDirectoryAndSave FILES
                             "Choose directory"
                             "Choose where to generate POCOs to"
                             (proxy [com.intellij.util.Consumer] []
                                (consume [directory]
                                    (generate-pocos directory)
                                    (.refresh FILES directory))))
    

    Установка скрипта



    Полный код скрипта на GitHub.
    Для установки надо просто скопировать файл Generate POCO.clj в IDE > Files > Scratches > Extensions > DataGrip > schema.
    И в контекстном меню таблиц появится соотвествующий пункт подменю в разделе Scripted Extensions.


    Результат


    Из следующей таблицы


    Было
    CREATE TABLE Users
    (
        Id INT PRIMARY KEY NOT NULL IDENTITY,
        first_name NVARCHAR(255),
        Last_Name NVARCHAR(255),
        Email VARCHAR(255) NOT NULL,
        UserGuid UNIQUEIDENTIFIER,
        Age TINYINT NOT NULL,
        Address NVARCHAR(MAX),
        photo IMAGE,
        Salary MONEY,
        ADDITIONAL_INFO NVARCHAR(42)
    );
    

    будет сгенерирован следующий класс:


    Стало
    using System;
    
    public class Users 
    {
      public long Id { get; set; } 
    
      public string FirstName { get; set; } 
    
      public string LastName { get; set; } 
    
      public string Email { get; set; } 
    
      public Guid? UserGuid { get; set; } 
    
      public byte Age { get; set; } 
    
      public string Address { get; set; } 
    
      public byte[] Photo { get; set; } 
    
      public decimal? Salary { get; set; } 
    
      public string AdditionalInfo { get; set; } 
    }
    

    Заключение


    Вот таким довольно простым способом можно генерировать C# классы которые описывают ваши таблицы в БД и сделать жизнь чуть менее рутинной. Конечно же, вы не ограничены только POCO классами C#, можно написать генератор чего угодно, для другого языка, фреймворка и т.д.

    Комментарии (1)

      Let's block ads! (Why?)

      Открытые лекции для школьников и студентов про типизацию в языках программирования

      Открытые лекции для школьников и студентов про типизацию в языках программирования

      Опыт перехода сайта на Single Page Application с упором на SEO

      пятница, 20 мая 2016 г.

      LinkedIn: просто ещё одна площадка для резюме

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

      Но, как говорится, всё тайное когда-нибудь становится явным. Выяснилось, что представители соцсети LinkedIn, помогающая людям расширять свои бизнес-связи, несколько лукавили, когда в 2012 году сообщили о краже 6,5 млн паролей своих пользователей — их было украдено 117 млн. То есть 27% всей текущей базы данных LinkedIn. Сейчас украденные данные всплыли на чёрном рынке. Учитывая, что это сеть не просто для общения, а для поиска и установления деловых контактов, то и ожидания пользователей относительно качества услуг сервиса всё-таки выше. В свете этого возникает вопрос: насколько привлекательным сегодня представляется LinkedIn с точки зрения налаживания бизнес-связей?

      Посещаемость после регистрации


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

      Неудобство и запутанность интерфейса


      Из-за того, что сервис пытается угодить нескольким категориям пользователей — работодателям, ищущим работу и рекрутёрам — интерфейс получился довольно неудобным и запутанным. Красноречивый факт: 78 место из 87 в рейтинге Global Brand Simplicity Index 2015, составленном на основании опроса 12 000 человек из 8 стран мира. В сети нередко можно встретить жалобы пользователей на трудность работы с интерфейсом LinkedIn. Справедливости ради стоит сказать, что разработчики знают об этом и работают над упрощением своего сервиса.

      Отсутствие отечественных аналогов


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

      Спам от сервиса рассылки LinkedIn


      Трудно найти что-то связанное с сетью, что раздражает больше, чем спам. Увы, к этому методу продвижения/продажи/рекламы прибегают очень многие компании. Не брезгует этим и LinkedIn: наверное, многие из вас получали письма, в которых кто-то из пользователей приглашал вас присоединиться к этому сервису. Иными словами, компания использует не самые чистоплотные методы увеличения аудитории. Кстати, некоторые HR-компании также рассылают спам с помощью сервиса рассылки LinkedIn.

      Проблемы с безопасностью


      Спустя пару лет после эпохальной утечки аккаунтов 2012 года была обнародована информация о том, что из-за недостатков реализации SSL-шифрования данные пользователей могли перехватываться с помощью атаки «человек посередине». Любопытно, что проблема была обнаружена в 2013 году, о чем LinkedIn сообщали неоднократно, при этом чаще всего подобная информация игнорировалась сервисом.

      В том же 2014 году LinkedIn попыталась в судебном порядке пресечь распространение стороннего плагина для Chrome, позволявшего любому человеку собирать адреса электронной почты пользователей LinkedIn. Другой пример разгильдяйства — сбор и передача данных о пользователях в незашифрованном виде iOS-клиентом. В общем, трудно сказать, какие ещё серьёзные бреши в безопасности могли использоваться злоумышленниками и были втихую закрыты разработчиками LinkedIn. Или не закрыты до сих пор.

      За всё приходится платить


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

      Если вы ищете работу, то вам предложат аккаунт «Поиск вакансий» (Job Seeker). За $29,99 в месяц вы получите доступ к такому функционалу:

      За абонентскую плату в $47,99 («Бизнес Плюс») вы получите возможность:

      Далее идёт аккаунт за $64,99 (Sales Navigator Professional):

      И наконец, аккаунт для тех, кто ищет сотрудников ($99,95, Recruiter Lite):

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

      Ещё одна площадка


      Тезис о несоответствии позиционирования LinkedIn сложившейся модели его использования — и восприятия — подтверждается некоторыми фактами. К концу 2013 года аудитория насчитывала 225 млн человек, к тому времени сеть существовала 10 лет. Спустя три года аудитория выросла почти вдвое, до 433 млн. Менее года назад русскоязычная аудитория оценивалась примерно в 3 млн, сейчас — больше 5 млн. При этом количество уникальных посетителей оценивается сегодня в 106 млн человек в месяц.

      Столь быстрый рост аудитории сервиса, воспринимаемого как площадка для поиска работы, говорит о том, что сегодня очень значительная часть пользователей — это те, кто в связи с экономическим кризисом или потерял работу, или рискует скоро стать безработным, или ищет что-то понадёжнее. Именно три года назад отмечен небывалый рост популярности LinkedIn как площадки для поиска работы. Кстати, если в Google осуществить поиск по LinkedIn с использованием ключевой фразы «настоящее время» (когда у человека указано в резюме, что он где-то работает «по настоящее время»), то получим 390 000 результатов (из 5 млн). Конечно, это не точные данные, и можно попытаться использовать другие ключевые слова.

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

      Понятно, что количество работодателей и тех, кто ищет деловых партнёров на LinkedIn пренебрежимо мало по сравнению с массой обычных соискателей, далеко не всех из которых можно охарактеризовать как «профессионалы». Раз уж LinkedIn не слишком удовлетворяет понятию «социальная сеть», то давайте примем очевидное и будем оценивать его как ещё один job-сайт. Однако и с этой точки зрения привлекательность ресурса не слишком велика: большинство работодателей — это компании-ритейлеры, набирающие продавцов и мерчендайзеров, и банковский сектор, который печально известен высокой текучестью кадров. Естественно, что целевая аудитория всех этих организаций в массе своей не является высококлассными специалистами.

      Актуальность и достоверность


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

      И ключи от дома, где деньги лежат


      Если вы думаете, что спам — единственное проявление нечистоплотности LinkedIn при выборе методов ведения бизнеса, то как вам запрос пароля от электронной почты во время регистрации нового пользователя?

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

      Большой Брат может следить за тобой


      Тема сотрудничества больших корпораций и силовых структур США давно уже перешла из разряда теории заговоров в подтверждённый факт. Хотя широкая общественность обычно узнаёт о случаях, когда компании пытаются сопротивляться требованиям силовиков о предоставлении информации о пользователях. А сотрудничество замалчивается всеми сторонами. Тем не менее, шила в мешке не утаить: начиная с 2014 года LinkedIn подозревается в передаче пользовательских данных ФБР. С одной стороны, россиян это волновать и не должно. С другой стороны, есть все основания предполагать, что LinkedIn может сотрудничать со спецслужбами и других стран.

      Заключение


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

      Ситуация усугубляется значительным количеством недостоверной/неактуальной информации в пользовательских профилях, проблемами с безопасностью данных, далеко не самым удобным интерфейсом, регулярными спам-рассылками и ограниченным функционалом бесплатного аккаунта. Главное преимущество LinkedIn на российском рынке — отсутствие отечественного конкурента, «настоящей» социальной сети для профессионалов. Хотя то же самое можно сказать и многих других странах. И хотя сервис мало соответствует усиленно создаваемому образу, перепозиционирование вряд ли возможно: многим десяткам миллионов людей в глубине души льстит принадлежность к «сообществу профессионалов». Так что можно предположить, что пользователи постепенно начнут всё больше разочаровываться, не получая от использования LinkedIn ожидаемого результата.

      Комментарии (0)

        Let's block ads! (Why?)

        Внимание: ИП в IT под ударом?

        Конкурс по программированию на JS: Классификатор слов (дополнение)

        Спасибо всем, кто уже поучаствовал или собирается участвовать в нашем конкурсе по программированию!

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

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

        Для отправки работ осталась ещё неделя. Если этот пост помог Вам найти ошибку, ещё есть время её исправить.

        Часто задаваемые вопросы


        • Как же я смогу прочитать файл words.txt, если нельзя загрузить модуль fs? А можно ли скачать его из интернета? Можно ли использовать process.binding?
          Ваша программа не будет иметь доступа к файлу words.txt. В этом и смысл. Если бы можно было просто прочитать этот файл, задача была бы тривиальной. Ничего нельзя скачать, потому что для этого понадобились бы такие модули, как http или net. Включить словарь в своё решение тоже не получится из-за ограничения по размеру.
          Это означает, что написать решение, всегда дающее правильные ответы, скорее всего, невозможно. Но можно написать программу, которая чаще угадывает правильно, чем неправильно, и тот, чья программа точнее угадывает, победит.
        • В словаре есть некоторые слова с прописными буквами. Могут ли они попасться в тестах?
          Могут, но они будут переведены в нижний регистр.
        • Что означает «64 КиБ»?
          64*1024 = 65536 байт.
        • Если мой файл данных сжат методом gzip, то должен ли его размер до или после сжатия укладываться в 64 КиБ вместе с текстом программы?
          Учитывается размер после сжатия.
        • Что за странный словарь! Там полно каких-то непонятных слов.
          Мы знаем, что он странный. Это самый большой словарь английского языка для проверки правописания, в который входит большое число аббревиатур, заимствований, редких слов, диалектизмов и даже невозможных словоформ. Тем не менее, мы выбрали именно этот словарь, поэтому для данной задачи «английское слово» — это то, которое встречается конкретно в этом словаре.
        • Какого размера набор «не-слов», используемый в генераторе тестов?
          Генератор тестов не использует какого-либо фиксированного набора «не-слов». Он генерирует псевдослучайные слова, похожие на английские, непосредственно при запросе по алгоритму, который мы опубликуем при подведении итогов конкурса.
        • Как тестовая система будет учитывать дубликаты, то есть слова, встречающиеся более чем в одном из блоков по 100 слов?
          Каждое вхождение будет учитываться как отдельное слово. Посмотрите, как устроен наш скрипт для тестирования.
        • Что, если победителю ссылку на конкурс прислали два человека?
          Премию получит тот, кто прислал её первым.

        Типичные ошибки


        К сожалению, во многих решениях, которые мы получили на сегодняшний день, содержатся похожие технические ошибки:
        • Функции test и init не экспортированы или экспортированы неправильно. Недостаточно просто объявить функции, их надо экспортировать из модуля. Если Вы не уверены, что сделали это правильно, проверьте свою программу нашим тестовым скриптом.
        • Функция init работает со своим аргументом data как с текстовой строкой, тогда как в условии явно сказано, что это будет Buffer.
        • Программа использует файл данных, но он не приложен.
        • Файл данных упакован методом gzip, но соответствующая опция в форме отправки не выбрана.
        • Опция gzip в форме отправки выбрана, но файл вместо gzip представляет собой zip-архив. Это не одно и то же!
        • Программа пытается использовать require или process.binding. Это запрещено правилами.

        Удачи всем участникам!

        Комментарии (0)

          Let's block ads! (Why?)

          Google-oriented programming

          Разжёвываем линейно-квадратичный регулятор для управления перевёрнутым маятником

          Преамбула


          Продолжаю подробное описание использования линейно-квадратичного регулятора на примере управления перевёрнутым маятником. К слову сказать, термин «ЛКР» очень неточно отражает суть происходящего, как мне уже подсказали в комментариях, в русской школе теории управления этот подход называется «аналитическим конструированием регуляторов», что существенно точнее.

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

          Итак, это уже четвёртая статья, для лучшего понимания происходящего неплохо бы прочитать предыдущие три:

          Вот фотография системы (кликабельно):



          Используемые датчики


          У меня только два источника информации о происходящем в системе, это два инкрементальных энкодера, один (1000 импульсов на оборот) показывает положение каретки, второй (2000 импульсов на оборот) даёт положение самого маятника. В предыдущей статье я считал импульсы при помощи самой же ардуины, но это довольно неточно и слабо устойчиво к зашумлённым показаниям энкодеров. Кроме того, это тратит и без того слабые вычислительные ресурсы атмеги. Сейчас я поставил одну микросхему HCTL-2032 (примерно пять евро штука на алиэкспрессе), она умеет считать импульсы двух энкодеров, предоставляя для этого 32-битные счётчики. Чтобы сэкономить ноги ардуины, между счётчиком и самой ардуиной стоит 74hc165, читающая один байт в параллель и отдающая этот байт последовательно.

          Измеряем параметры двигателя ещё раз


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

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

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

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

          Если бы у меня в системе не было бы трения, то этот график был бы линейным, и моя модель строилась бы как v_{k+1} = a*v_k + b*u_k. И ведь он практически линеен на своей положительной и отрицательной частях одновременно, но эти две прямые не проходят через ноль. Это (в том числе) из-за трения. Мы видим, что если при положительном напряжении мы добавим, а при отрицательном отнимем буквально долю вольта, то график пройдёт через ноль и станет линейным.

          Если мы хотим учитывать трение в системе, то модель строится следующим образом (не забудьте прочитать предыдущую статью, если неясно, откуда берётся эта формула):

          Итак, имея данные, нам нужно найти значения a, b и c. Фиттинг можно делать как угодно, учитывая, что он делается только один раз на десктопе, можно просто сделать три вложенных цикла. Вот код фиттинга, который мне говорит, что для дискретизации в 20мс между измерениями a=.4, b = .06, c=-.01. То есть, напряжение, необходимое для компенсации трения у меня в системе, равно одной десятой вольта. Кривые, полученные таким приближением, наложены на реальное измерение на картинке выше.

          Контролируем прикладываемую силу, а не напряжение


          Итого, на данный момент наша система может быть записана следующим образом:

          К сожалению, это не является линейным дифференциальным уравнением вида x_{k+1} = A x_k + B u_k, которое нужно для линейно-квадратичного регулятора. Кроме того, даже если бы не это, то мне нужно добавить ещё и маятник на каретку, а я не знаю как вывести зависимость положения и угловой скорости маятника от напряжения. Я бы предпочёл, чтобы у меня в качестве управления было бы не напряжение, а непосредственно ускорение каретки:

          Окей, предположим, что мой регулятор использует ускорение в качестве управления. Но ведь в реальности-то я должен подать напряжение на мотор. Как его получить? Очень просто:

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

          Несложная, но длинная математика или добавляем маятник


          Уравнения движения маятника


          Итак, задача добавить маятник в нашу систему и записать соответствующие линейные уравнения для регулятора. Давайте приведём полный список необходимых для этого физических величин:
          • m: масса маятника
          • M: масса каретки
          • f: сила, приложенная мотором к каретке через ремень
          • 2l: длина маятника (l — это расстояние от петли до центра масс маятника)
          • I: момент инерции маятника (к слову, а ваши шрифты позволяют видеть разницу между I и l?)
          • θ(t): угол отклонения маятника от вертикали, в положении неустойчивого равновесия нулевой, увеличивается по часовой стрелке
          • x(t): положение каретки

          Итого, переменными моей системы будет четырёхмерный вектор, состоящий из положения каретки, её скорости, угла отклонения маятника и его угловой скорости. Задача на сейчас записать систему линейных дифференциальных уравнений вот такого вида:

          Если мы сумеем её записать в непрерывном виде, то потом просто дискретизуем и мы выиграли бой. Обратите внимание, что тут я использую в качестве управления приложенную силу, а не ускорение, но второй закон Ньютона нам покажет, как это сделать. Итак, нам нужно найти неизвестные матрицы A и B.

          Запишем второй закон Ньютона для каретки: ускорение каретки, помноженное на массу, равняется сумме двух горизонтальных сил: первая сила — это наше управление, сила, приложенная через ремень электромотором. Вторая сила — это сила, с которой маятник, стараясь упасть или подняться, толкает каретку вбок. Чтобы её найти, можно записать координаты центра массс маятника как двумерный вектор (x(t) + l sin(θ(t)), l cos(θ(t))). Если мы продифференцируем дважды координату, то получим ускорение, а сила — это ускорение на массу. Поскольку нас интересует только горизонтальная составляющая, то имеет смысл брать только вторую производную от x(t) + l sin(θ(t). Итого:

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

          Тогда предыдущее уравнение может быть приближено линейным:

          Теперь запишем второй закон Ньютона (версия для вращения) для маятника. Для начала, что такое второй закон Ньютона для вращения? Это сумма моментов равна угловому ускорению, помноженному на момент инерции. Момент инерции — это такой аналог массы для поступательного движения. Нас интересует проекция всех сил на прямую, перпендикулярную маятнику (ведь вращает только перпендикулярная составляющая, правда?) Ну и разумеется, эти силы надо помножить на плечо, чтобы получить момент. Сил, действующих на маятник, три: гравитация и горизонтальная и вертикальная составляющие силы реакции опоры, которые мы можем получить как и в прошлый раз, дважды взяв производную по времени от координат центра масс маятника:

          Приблизим его линейным уравнением:

          Запишем уравнения (1) и (2) в систему:

          Для удобства назовём определитель матрицы буквой D:

          Обратим матрицу:

          Теперь запишем наши дифференциальные уравнения, по факту, мы нашли матрицы A и B:

          Дискретизируем линейную систему

          Итак, мы записали неперывное дифференциальное уравнение:

          Для постоянного шага Δt получаем следующее:

          Если мы обозначим через E единичную матрицу 4x4, то можно записать:

          Момент инерции для стержня, который вращается вокруг конца, можно посмотреть здесь, поэтому упрощаем всё что можно:

          Это и есть самое главное уравнение движения маятника.

          Линейно-квадратичный регулятор


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

          Итак, ЛКР нам говорит, что если взять управляющую силу f_k = 24.95 x_k + 18.54 v_k + 70.44 θ_k + 14.96 ω_k, то отклонив маятник на 12° от вертикали, и уведя каретку на 20 сантиметров от положения рановесия, то мы должны получить следующее поведение системы:

          x_k — положение каретки, v_k — её скорость, θ_k — угол маятника, ω_k — его угловая скорость. Напряжение на графике дано в десятках вольт, чтобы примерно сравнять масштабы трёх графиков.

          Забиваем коэффициенты в ардуину


          Вот таким у меня получился маятник, управляющий код можно посмотреть здесь:

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

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

          Давайте посмотрим на следующий график:

          Я записал угол маятника в течение нескольких секунд, он показан красным. График слегка зашумлён из-за разрешения энкодера, но в общем и целом довольно гладкий. Скорость нам приходится находить синтетически из истории положения маятника. Если мы возьмём напрямую разность двух соседних положения и поделим на 20 миллисекунд, то это нам даст синий график. Польза конечных разностей в том, что они очень просто программируются. Их недостаток в том, что они драматическим образом усиливают любой шум измерений.

          Если взять такую оценку скорости, то регулятор сходит с ума:

          Единственная разница с предыдущим видео — это оценка скорости, ничего больше.

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

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

          Stay tuned!

          Комментарии (0)

            Let's block ads! (Why?)

            Тест производительности: удивительно и просто

            Так сложилось, что последние полгода я активно занимался тестами производительности и мне кажется, что в этой области IT царит абсолютное непонимание происходящего. В наше время, когда рост вычислительных мощностей снизился (vertical scalability), а объем задач растет с прежней скоростью, проблема производительности становится всё острее. Но прежде, чем броситься на борьбу с производительностью, необходимо получить количественную характеристику.

            Краткое содержание статьи:

            Предыстория


            Однажды, путешествуя в поезде, я захотел посчитать, каково расстояние между столбами электропередач. Вооружившись обычными часами и оценивая среднюю скорость поезда 80-100км/ч (25 м/с), я засекал время между 2-мя столбами. Как ни странно, этот наивный метод давал очень удручающие результат, вплоть до 1.5-2 кратной разницы. Естественно метод несложно было исправить, что я и сделал, достаточно было засечь 1 минуту и посчитать количество столбов. И не важно, что мгновенная скорость на протяжении минуты может варьироваться и даже не важно посчитаем мы последний столб или минута истечет посередине, потому как измерений вполне достаточно для требуемого результата.
            Смысл теста в том, чтобы получить убедительные для себя и для других измерения.
            Тесты «на коленке»

            Эта история мне напоминает то, что происходит с тестированием производительности в Software Engineering. Достаточно частое явление — запуск 1-2 тестов, построение графиков и получение выводов о scalability система. Даже, если есть возможность применить МНК или узнать стандартную ошибку, это не делается за «ненадобностью.» Особенно интересная ситуация, когда после этих 2 измерений, люди обсуждают насколько быстрая система, как она масштабируется и сравнивают её с другими системами по личным ощущениям.
            Конечно, оценить, насколько быстро выполняется команда, не сложно. С другой стороны, быстрее не значит лучше. Системы ПО имеют свыше 10 различных параметров, от hardware на котором они работают до input, которые вводит пользователь в разные моменты времени. И зачастую 2 эквивалентных алгоритма могут давать совершенно разные параметры масштабируемости в разных условиях, что делает выбор совсем не очевидным.
            Недоверие к тестам

            С другой стороны результаты измерений всегда остаются источником спекуляций и недоверий.
            — Вчера мы меряли было X, а сегодня 1.1*X. Кто-то что-то менял? — 10% — это нормально, у нас теперь больше записей в БД.
            — При проведении теста был отключен антивирус, скайп, анимация заставки?
            — Не-не, для нормальных тестов нам надо закупить кластер серверов, установить микросекундную синхронизацию времени между ними… удалить ОС, запускать в защищенном режиме…
            — Сколько пользователей мы поддерживаем? У нас 5000 зарегистрированных пользователей, вдруг 20% из них залогинится, надо запускать тесты с 1000 параллельными агентами.


            Что же нам делать?

            Во-первых, стоит признать, что железо, которое мы имеем, у нас уже есть и надо получить максимум результатов именно на нём. Другой вопрос, как мы сможем объяснить поведение на других машинах (production/quality testing). Те кто ратует, за эксперименты «чистой комнаты», попросту вам не доверяют, так как вы не даете достаточно объяснений или данных, «чистая комната» — это иллюзия.
            Во-вторых, самое главное преимущество в тестировании программ — это дешевизна тестов. Если бы физики могли провести 100 тестов упрощенной ситуации вместо 5 полноценных, они бы точно выбрали 100 (и для проверки результатов 5 полноценных :) ). Ни в коем случае, нельзя лишаться дешевизны тестов, запускайте их у себя, у коллеге, на сервере, утром и в обед. Не поддавайтесь соблазну «реальных» часовых тестов с тысячами пользователей, важнее понимать, как ведет себя система, нежели знать пару абсолютных чисел.
            В-третьих, храните результаты. Ценность тестов представляют сами измерения, а не выводы. Выводы гораздо чаще бывают неправильными, чем сами измерения.

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


            Простейший тест


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

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

              long t = - System.currentTimeMillis();
              int count = 100;
              while (count -- > 0)  operation();
              long time = (t + System.currentTimeMillis()) / 100;
            
            
            Запись результата измерения

            Запустив один раз мы получаем число X. Запускаем еще раз получаем 1.5*X, 2 *X, 0.7*X. На самом деле тут можно и нужно остановиться, если мы делаем временный замер и нам не надо вставлять это число в отчет. Если же мы хотим поделиться этим числом с кем-то, нам важно, чтобы оно сходилось с другими измерениями и не вызывало подозрений.
            Первым «логичным» шагом кажется положить числа X и усреднить их, но, на самом деле, усреднение средних ни что иное, как увеличение count для одного теста. Как ни странно увеличение count может привести к еще более не стабильным результатам, особенно если вы будете запускать тест и делать что-то одновременно.
            Минимальное время исполнения как лучшая статистика

            Проблема в том, что среднее является не стабильной характеристикой, одного заваленного теста, выполнявшегося в 10 раз дольше, будет достаточно, чтобы ваши результаты не совпадали с другими. Как не парадоксально для простых performance тестов желательно брать минимальное время исполнения . Естественно operation() должна быть измеряемая в данном контектсе, обычно 100 мс — 500 мс для системы более, чем достаточно. Конечно, минимальное время не будет 1 к 1 совпадать с наблюдаемым эффектом или с реальным, но это число будет сравнимо с другими измерениями.
            Квантили

            Квантили 10%, 50% (медиана), 90% являются более стабильными, чем среднее, и гораздо информативнее. Мы можем узнать с какой вероятностью запрос будет выполняться время 0.5*X или 0.7*X. С ними есть другая проблема, посчитать квантили на коленке гораздо сложнее чем взять min, max.
            JMeter предоставляет измерение медианы и 90% в Aggregate Report из коробки, чем естественно следует пользоваться.


            Параметризованный тест


            В результате измерений мы получаем некоторое число (медиану, минимум или другое), но что мы можем сказать о нашей системе (функции) по одному числу? Представьте вы автоматизируете процесс получения этого числа и каждый день вы будете его проверять, когда вам надо бить тревогу и искать виноватых? К примеру, вот типичный график один и тот же тест каждый день.
            Скрытый текст
            Daily test

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

            Тест с одним параметром

            Рассмотрим систему с одним числовым параметром. Прежде всего необходимо выбрать значения параметров. Не имеет смысла выбирать числа из разных диапазонов, как [1, 100, 10000], вы попросту проводите 3 абсолютно разных несвязных теста и найти зависимость на таких числах будет невозможно. Представьте вы хотите построить график, какие числа вы бы выбрали? Что-то похожее на [X*1, X * 2, X*3, X*4,X*5, ].

            Итак выбираем 5-10 (7 лучшее) контрольных точек, для каждой точки проводим 3-7 измерений, берем минимальное число для каждой точки и строим график.
            Scalability parameter day graph

            Сложность алгоритма

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

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

            Метод наименьших квадратов (линейная модель)

            Для поиска коэффициентов линейной зависимости имеется простой и оптимальный метод МНК. Преимущество этого метода в том, что формулы можно запрограммировать в 10 строчек и они абсолютно понятны.
            y = a + bx 
            a = ([xy] - b[x])/[x^2]
            b = ([y] - a[x])/ n
            
            

            Представим наши вычисления в таблице.
            Table results

            В выделенная строчке мы видим линейный коэффициент нашей модели, он равняется 95.54, свободный коэффициент 2688. Теперь мы можем проделать простой, но не очевидный фокус, мы можем придать значение этим числам. 95.54 измеряется в миллисекундах (как и наши измерения), 95.54 — время которое мы тратим, на каждую компоненту, а 2688 мс время, которое мы тратим на саму систему, не зависит от количества компонент. Данный метод позволил нам выделить достаточно точно время внешней системы, в данном случае БД, хотя оно в десятки раз превышает время 1-й компоненты. Если бы мы пользовались формулой Time_with_N_component/N нам бы пришлось замерять для N>1000, чтобы погрешность оказалась меньше 10%.

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

            На графике результаты независимых запусков теста в разное время, что подтверждает большую стабильность линейного коэффициента, чем отдельно взятых тестов.
            Scalability parameter many days graph

            Оценка линейности модели и коэффициент Пирсона

            Используя график мы можем наглядно увидеть, что наши измерения действительно удовлетворяют линейной модели, но этот метод далеко не точный и мы не можем его автоматизировать. В этом случае нам может помочь коэффициент Пирсона. Этот метод действительно показывает отклонения от прямой линии, но для 5-10 измерений его явно недостаточно. Ниже приведен пример, явно не линейной зависимости, но коэффициент Пирсона достаточно высок.

            Возвращаясь к нашей таблице, зная ovehead системы (свободный коэффициент) мы можем посчитать линейный коэффициент для каждого измерения, что в таблице и сделано. Как мы видим числа (100, 101, 93, 96, 102, 81, 94, 100, 93, 98) — достаточно случайно распределены около 95, что и дает нам весомые основания полагать, что зависимость линейная. Следуя букве математике, на самом деле отклонения от средней величины должны удовлетворять нормальному распределения, а для проверки нормального распределения достаточно проверить критерий Колмогорова-Смирнова, но это мы оставим для искушенных тестировщиков.

            Как это ни странно, не все зависимости являются линейными. Первое, что приходит на ум, это квадратичная зависимость. На самом деле квадратичная зависимость очень опасна, она убивает performance сначала медленно, а затем очень быстро. Даже если у вас для 1000 элементов все выполняется за доли секунды, то для 10000 это уже будут десятки секунд (умножается на 100). Другим примером, является сортировка, которая не может быть решена за линейное время. Посчитаем насколько применим метод линейной анализа для алгоритмов со сложность O(n*log n)

            (10n log 10n )/ (n log n)= 10 + (10*log 10)/(log n)
            
            

            То есть для n >= 1000, отклонение будет в пределах 10%, что существенно, но в некоторых случаях может применяться, особенно если коэффициент при log достаточно большой.

            Рассмотрим пример нелинейной зависимости.

            Нелинейная сложность алгоритма
            Table results : not linear dependency

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

            Естественно, что большинство систем не состоят из одного параметра. К примеру, программа чтения из таблицы уже состоит из 2-х параметров, колонок и строк. Используя параметризованные тесты, мы можем посчитать каковы затраты на чтение строки из 100 колонок (пусть 100мс) и каковы затраты на чтение колонки для 100 строк (пусть 150мс). 100*100мс != 100*150мс и это не парадокс, просто мы не учитываем, что в скорости чтения строк уже заложен overhead чтения 100 колонок. То есть 100мс/100 колонок= 1мс — это не скорость чтения одной ячейки! На самом деле 2-х измерений будет недостаточно для расчета скорости чтения одной ячейки. Общая формула такова, где A — затраты на одну ячейку, B — на одну строчку, C — на колонку:
            Time(row, column) = A * row * column + B * row + C * column + Overhead

            Составим систему уравнений, учитывая имеющиеся значения и еще одно необходимое измерение:

              Time(row, 100) = 100 * A * row + B * row + o = 100 * row + o.
              Time(row, 50) = 50 * A * row + B * row + o = 60 * row + o.
              Time(100, column) = 100 * B * column + C * column + o = 150 * column + o.
            
              100 * A + B = 100.
              50 * A + B = 55.
              100 * B + C = 150.
            
            

            Отсюда, получаем A = 0.9 мс, B = 10 мс, C = 50 мс.

            Конечно, имея формулу на подобие ЛМНК для данного случая, все расчеты бы упростились и автоматизировались. В общем случае, к нам не применим общий ЛМНК, потому как функция, которая линейная по каждому из аргументов, отнюдь не многомерная линейная функция (гиперплоскость в N-1 пространстве). Возможно воспользоваться градиентным методом нахождения коэффициентов, но это уже не будет аналитический способ.


            Многопользовательские тесты и тесты многоядерных систем


            Миф «throughput per core»

            Одним из любимых занятий с performance тестами является экстраполяция. Особенно люди любят экстраполировать в ту область, для которых они не могут получить значений. К примеру, имея в системе 2 ядра или 1 ядро, хочется проэкстраполировать как бы система вела себя с 10 ядрами. И конечно же первое неверное допущение в том, что зависимость линейна. Для нормального определения линейной зависимости необходимо от 5 точек, что конечно же невозможно получить на 2х ядрах.
            Закон Амдала

            Одним из самых близких приближений является закон Амдала.
            Amdahl law
            Он основан на расчете процента паралеллизируемого кода α ( вне блока синхронизации) и синхронизируемоего кода (1 — α). Если один процесс занимает время T на одном ядре, тогда при множественных запущенных задачах N время будет T' = T*α + (1-α)*N*T. В среднем конечно же N/2, но Amdahl допускает N. Параллельное ускорение соответственно S = N*T/T' = N / (α + (1-α)*N)=1 / (α/N + (1- α)).

            Конечно же, приведенный выше график, не настолько драматичен в реальности (там ведь логарифмическая шкала по X). Однако существенным недостатком блоков синхронизации, является асимптота. Условно говоря, не возможно наращивая мощность преодолеть предел ускорения lim S= 1 / (1- α). И этот предел достаточно жесткий, то есть для 10% синхронизированного кода, предел 10, для 5% (что очень хорошо) предел 20.

            Функция имеет предел, но она постоянно растет, из этого возникает, странная на первый взгляд, задача: оценить какое hardware оптимально для нашего алгоритма. В реальности увеличить процент параллизированного бывает достаточно сложно. Вернемся к формуле T' = T*α + (1-α)*N*T, оптимальным с точки зрения эффективности: если ядро будет простаивать, столько же времени сколько и будет работать. То есть T*α=(1-α)*N*T, отсюда получаем N =
            α/(1-α). Для 10% — 9 ядер, для 5% — 19 ядер.

            Связь количества пользователей и количества ядер. Идеальный график.

            Модель ускорения вычислений является теоретически возможной, но не всегда реальной. Рассмотрим ситуацию клиент-сервер, когда N клиентов постоянно запускают некоторую задачу на сервере, одной за одной, и мы не испытываем никаких затрат на синхронизацию результатов, так как клиенты полностью не зависимы! Ведение статистики к примеру вводит элемент синхронизации. Имея M-ядерную машину, мы ожидаем, что среднее время запроса T когда N < M одинаково, а когда N > M время запроса растет пропорционально количеству ядер и пользователей. Посчитаем throughput как количество запросов обрабатываемых в секунду и получим следующие «идеальный» график.
            Идеальные графики
            Idea graph
            Idea throughput graph
            Экспериментальные измерения

            Естественно идеальные графики достижимы, если мы имеем 0% synchronized блоков (критических секций). Ниже приведены реальные измерения одного алгоритма с разными значения параметра.
            Core/throughput

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

            Экспериментальные измерения, используя линейный коэффициент
            Core/parameter throughput

            Графики измерений близки по значениям к закону Амдала, но все-таки существенно отличается. Имея измерения для 1, 2, 4, 8 ядер, можно рассчитать количество непараллезируемоего кода по формуле
            Amdahl estimation

            Где NP — количество ядер, SU = Throughpt NP core / Throughput 1 core. Согласно закону Амдала это число должно быть постоянным, но во всех измерениях это число падает, хотя и не значительно (91% — 85%).

            График throughput per core не всегда представляет собой непрерывную линию. К примеру, при нехватке памяти или при работе GC отклонения в throughput могут быть очень значительными.

            Значительные колебания throughput при Full GC
            Core/throughput with Full GC


            Поведенческий тест


            Throughput

            При измерениях нагрузки многопользовательских систем мы ввели определение Throughput = NumberOfConcurrentUsers / AverageTimeResponse. Для интерпретации результатов Throughput — это пропускная способность системы, какое количество пользователей система может обслужить в момент времени, и это определение тесно связано с теорией массового обслуживания. Сложность измерения throughput заключается в том, что значение зависит от входного потока. К примеру, в системах массового обслуживания, предполагается, что время ожидания ответа не зависит от того, сколько заявок находится в очереди. В простой программной реализации, без очереди заявок, время между всеми потоками будет делиться и соответственно система будет деградировать. Важно заметить, что не стоит доверять JMeter измерениям throughput, было замечено, что Jmeter усредняет throughput между всеми шагами теста, что является не правильным.

            Рассмотрим, следующий случай: при нагрузке с 1 пользователем, система выдает Throughput = 10, при 2-х — Throughput=5. Такая ситуация вполне возможна, так как типичный график Throughput/User — эта функция которая имеет один локальный (и глобальный максимум).
            Следовательно, при входящем потоке 1 пользователь каждые 125мс, система будет обрабатывать 8 пользователей в секунду (входной throughput).
            При входящем потоке 2 пользователя каждые 125мс система начнет коллапсировать, так как 8 (входной throughput) > 5 (возможного throughput).

            Коллапсирующая система

            Рассмотрим пример коллапсирующей системы подробнее. После проведения теста Throughput/Users у нас есть следующие результаты.
            Throughput measurements

            Users — количество пользователей одновременных в системе, Progress per user — какое количество работы в процентах пользователь выполняет за одну секунду. Мысленно сэмулируем ситуацию, что каждую секунду приходит 10 пользователей и начинают выполнять одну и ту же операцию, вопрос, сможет ли система обслуживать данный поток.
            System progress

            За 1 секунду 10 пользователей в среднем выполнят только 20% своей работы, исходя из предположения, что в среднем они выполняют всю за 5. На 2-й секунде в системе уже будет 20 пользователей и они будут разделять ресурсы между 20 потоками, что еще уменьшит процент выполняемой работы. Продолжим ряд до того, момент когда первые 10 пользователей закончат работу (теоретически они ее должны закончить так как ряд 1/2 + 1/3 + 1/4… расходящийся).
            Collapse evolution

            Достаточно очевидно, что система сколлапсирует, так как через 80 секунд в системе будет 800 пользователей, а в этом момент смогут закончить только первые 10 пользователей.

            Данный тест показывает, что при любом распределении входящего потока, если входящий throughput (математическое ожидание) больше максимального
            измеряемого throughput для системы, система начнет деградировать и при постоянной нагрузке упадет. Но обратное неверно, в 1-м примере максимальный измеряемый throughput (=10) > входящего (8), но система также не сможет справиться.

            Система в стационарном режиме

            Интересным случаем является работоспособная система. Взяв за основу наши измерения, проведем тест, что каждые 1 секунду приходят 2 новых пользователя. Так как минимальное время ответа превышает секунду, то поначалу количество пользователей будет накапливаться.
            Stabilized system

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

            Из этого можно сделать вывод, что график Throughput/Users с одной стороны представляет количество обрабатываемых пользователей в секунду (throughput) и количество пользователей в системе (users). Падения графика справа от этой точки характеризует только стабильность системы в стрессовых ситуациях и зависимость от характера входящего распределения. В любом случае, проводя тесты Throughput/Users, будет совсем не лишним провести behavioral test с приблизительным характеристиками.


            Удивительное распределение


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

            Самой простой статистикой является среднее, но по указанным выше причинам она не совсем стабильна, особенно для малого количества измерений. Для определения квантилей удобно воспользоваться графиком функции распределения. Благодаря замечательному JMeter плагину у нас есть такая возможность. После первых 10-15 измерений обычно картина недостаточно ясная, поэтому для детального изучения функции потребуется от 100 измерений.
            Первые измерения
            First measurements cum distribution

            Final measurements cum distribution

            Получить N-квантиль из данного графика очень просто, достаточно взять значение функции в данной точки. Функция показывает достаточно странно поведение вокруг минимума, но дальше растет вполне стабильно и только возле 95% квантиля начинается резкий подъем.

            Распределение?

            Является ли данное распределение аналитическим или известным? Для этого можно построить график плотности распределения и попытаться посмотреть известные функции, к счастью их не так много.
            Final measurements distribution

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

            Минимум и экспоненциальное распределение

            Важно отметить, что область значений нашей случайной величины отнюдь не [0, +∞ [, а некоторое [Min, +∞[. Мы не можем ожидать, что программа может выполниться быстрее, чем теоретический минимум. Если предположить, что измеряемый минимум сходится к теоретическому и вычесть это число из всех статистик, то можно наблютать достаточно интересную закономерность.
            Table results

            Оказывается Minimum + StdDev = Mean (Average), причем это характерно для всех измерений. Есть одно известное распределение у которого, математические ожидание совпадает с дисперсией (variance), это экспоненциальное распределение. Хотя график плотности распределения отличается в начале области определения, основные квантили вполне совпадают. Вполне возможно случайная величина является суммой экспоненциального распределения и нормального, что вполне объясняет колебания вокруг точки теоретического минимума.

            Дисперсия и среднее

            К сожалению, мне не удалось найти теоретического обоснования, почему результаты тестов удовлетворяют экспоненциальному распределению. Чаще всего экспоненциальное распределение фигурирует в задачах времени отказа устройств и даже времени жизни человека. Неясно так же, является ли это спецификой платформы (Windows) или Java GC или каких-то физических процессов, происходящих в компьютере.

            Однако, учитывая, что каждое экспоненциальное распределение задается 2 параметрами (дисперсией и математическим ожиданием) и функция распределения performance test экспоненциальная, можно считать, что для peformance теста, нам необходимо и достаточно только 2 показателей. Среднее — время выполнения теста, дисперсия — отклонение от этого времени. Естественно, чем меньше дисперсия, тем лучше, но однозначно сказать, что лучше уменьшить среднее или дисперсию, нельзя.

            Если у кого-то есть теория, откуда берется дисперсия и как влияет тот или иной алгоритм на ее значение, прошу поделиться. От себя хочу заметить, что зависимости между временем выполнения теста и дисперсии, я не нашел. 2 теста выполняющиеся в среднем одинаковое время (без sleep), могут иметь разные порядки дисперсии.

            Комментарии (0)

              Let's block ads! (Why?)