Продуктивные программисты

Не секрет, в сфере программирования работает много особей мужского пола. И также не секрет, что настоящие программисты обожают померяться п… знаниями, а конкретно, в плане чья программа круче! Лично я не являюсь крутанским мега крутаном в плане алгоритмов, и мне далеко до бойцов высшей лиги TopCoder’а, Google Code Jam’а и т.д., но алгоритмы люблю и ими интересуюсь.

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

Далее есть спецы по различным API – например, им не надо глядеть в man каждый раз при вызове socket (7), чтобы вспомнить, как там правильно подавить появление сигнала SIGPIPE и т.д.

Дальше идут знатоки проектирования. Всякие темы типа ООП, например, когда именно лучше применять агрегирование, а когда композицию и т.д.

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

Может, есть и еще категории (если кто знает, прошу делиться).

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

У нас контора весьма крупная. Количество программистов более нескольких сотен. Есть из кого выбирать для интервьюирования. Многие не любят учувствовать в этом, но лично я люблю. По нескольким причинам. Во-первых, постоянно есть возможность глядеть на себя со стороны, так как если человек по телефону как орехи разделал все твои вопросы или поставил тебя в тупик встречным вопросом, то может ты как-то уже профессионально «засахарился»? Или если большинство коллег дали совершенно противоположную твоей оценку, может ты спрашиваешь какую-то ерунду и думаешь, что это важно? А во-вторых, есть появляется возможность быть в курсе, что вообще сейчас на рынке труда.

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

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

Веселые перестановки

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

Вопрос: как на месте преобразовать первую последовательность во вторую, если в плане перемещения/копирования элементов есть только одна функция - обмен двух соседних элементов. Произвольный доступ к одиночным элементам есть только на чтение. Для перезаписи/изменения элементов надо пользоваться данной функцией обмена.

Конечно, интересно иметь и оценку сложности.

Мой ответ, если кому интересно, будет завтра.

Добавление элементов в std::vector

На собеседованиях по С++ задают много вопросов про контейнеры STL. И самый безобидный из них, как думал, std::vector. Но вот и по нему попался интересный вопрос.

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

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

Как я полагаю, в среднем ожидается, что отвечать стоит практически сразу.

На всякий случай: мой ответ будет завтра.

А сейчас мини эксперимент с реальным std::vector (компилятор, и сообразно STL — Sun C++ 5.9 SunOS_sparc) для выяснения реальной стратегии роста буфера в векторе:

#include <vector>
#include <iostream>
#include <iomanip>
#include <cstdlib>

int main() {
  int last = -1;
  std::vector<int> a;
  std::cout << std::setw(12) << "Capacity" << " " 
            << std::setw(12) << "Size"
            << std::setw(12) << "Ratio" << std::endl
            << std::setw(12) << std::setfill('-') << "-" << " " 
            << std::setw(12) << "-" << " "
            << std::setw(12) << "-" << std::endl;

  std::cout << std::setfill(' ') << std::fixed;
  while (1) {
    if (a.capacity() != last) {
      last = a.capacity();
      std::cout << std::setw(12) << a.capacity() << " "
                << std::setw(12) << a.size() << " "
                << std::setw(12) << std::setprecision(6)
                << (float)a.capacity() / a.size() << std::endl;
    }
    a.push_back(std::rand());
  }
  return 0;
}

А вот и результат:

    Capacity         Size       Ratio
------------ ------------ ------------
           0            0          NaN
          32            1    32.000000
          64           33     1.939394
         103           65     1.584615
         166          104     1.596154
         268          167     1.604790
         433          269     1.609665
         700          434     1.612903
        1132          701     1.614836
        1831         1133     1.616064
        2962         1832     1.616812
        4792         2963     1.617280
        7753         4793     1.617567
       12544         7754     1.617746
       20296        12545     1.617856
       32838        20297     1.617875
       53131        32839     1.617924
       85965        53132     1.617952
      139091        85966     1.617977
      225049       139092     1.617987
      364129       225050     1.617992
      589160       364130     1.617994
      953260       589161     1.617996
     1542374       953261     1.617998
     2495561      1542375     1.617999
     4037817      2495562     1.617999
     6533187      4037818     1.617999
    10570696      6533188     1.618000
    17103386     10570697     1.618000
    27673278     17103387     1.618000
    44775363     27673279     1.618000
    72446537     44775364     1.618000
   117218496     72446538     1.618000
   189659526    117218497     1.618000
   306869113    189659527     1.618000

Выходит, что для моей STL - это какой-то магический коэффициент 1.618.

Update: В комментариях подсказали хорошую ссылку на тему стратегии управления размером вектора.

Update 2: Лично мой ответ на тему вычислительной сложности последовательного добавления элементов в вектор, если вектор будет удваивать размер буфера при переполнении.

Так как мы добавляем k элементов, то это как минимум O(k). А так как по условию вектор удваивает буфер каждый раз, когда нет места, то произойдет log2(k) раз (так как по условию элементы поступают последовательно).

Получаем в этоге: O(k*log2(k)).

Update 3: В комментариях меня поправили: O(k + log2(k)) или просто O(k)

EcoDisc

Пришел недавно очередной выпуск "Linux Format". Как всегда в нем был DVD диск. Но в этот раз меня сильно удивил диск как таковой. Поглядите, что можно с ним делать без минимального ему вреда и без каких-либо усилий:







Называется "EcoDisc".

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

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

Модель процессора с одной командой

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

В середине 90-x, в эхо-конференции Фидо RU.HACKER, небезысвестный Solar Designer (он же Alexander Peslyak, автор таких вещей как John The Ripper и Openwall Linux), опубликовал интересную программу собственного сочинения, и предлагал попробовать ее взломать, угадав пароль, который она запрашивает и проверяет.

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

У этой виртуальной машины память линейна и стоит из 16-х битных слов. Данные и исполняемый код могут перемешиваться. Каждая инструкция состоит из трех слов - адресов операндов. Исполнение инструкции - это в чтении из памяти двух слов, адреса которых лежат в первых двух операндах, проведения между ними операции NOR и записи результата по адресу, заданному в третьем операнде. После выполнения инструкции указатель команд увеличивается на 3 (чтобы указывать на следующую инструкцию), и все повторяется сначала.

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

cld
emCPU:
mov  si,emIP
lodsw
xchg ax,di
mov  di,[di]
lodsw
xchg ax,bx
or   di,[bx]
lodsw
xchg ax,di
not  ax
mov  emIP,si
stosw
jmp  short emCPU

Но ни что не мешает перенести его в мир, например, Питона (тут вместо NOR используется NAND):

def nand(a, b):
  return ~(a & b) & 0xFFFF

def norcpu():
  while 1:
    i = mem[IP];
    a = mem[i + 0]
    b = mem[i + 1]
    r = mem[i + 2]
    mem[IP] = i + 3
    f = nand(mem[a], mem[b])
    mem[r] = f

Почему именно NOR? Из теории булевой алгебры известно, что любую из 14-ти логических функций (например, NOT, AND, OR, XOR и т.д., всего их 16) двух одно битовых аргументов можно выразить через функции NOR и NAND. Например:

NOT(a) = NAND(a, a)
AND(a, b) = NAND(NAND(a, b), NAND(b, a))
OR(a, b) = NAND(NAND(a, a), NAND(b, b))
XOR(a, b) = OR(AND(a, NOT(b)), AND(NOT(a), b)))

Пересылка данных MOVE(src, dst) может быть сделана через OR:

mem[dst] = OR(mem[src], mem[src])

Условный переход также реализуется через булеву логику. Если cond равно 0xFFFF (истина), то осуществляется переход на адрес addr, а если cond равно 0x0000, то выполнение продолжается линейно:

mem[IP] = OR(AND(addr, cond), AND(mem[IP], cond))

или в нотации интерпретатора:

AND addr, cond, @t1
AND IP, cond, @t2
OR @t1, @t2, IP

где @t1 и @t2 - некоторые вспомогательные переменные. Команды AND и OR также раскрываются в последовательность элементарных NOR, как было показано ранее.

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

Вот тут в оригинальной программе Александра был трюк, с помощью которого можно было вызывать native код x86. Так как код самого интерпретатора на ассемблере x86 также находился в адресном пространстве виртуальной машины, то в нужный момент в начало интерпретатора командой MOVE подставлялась двухбайтовая команда перехода x86 (то есть интерпретатор сам себя модифицировал), по адресу перехода которой находился нужный native код x86. После его выполнения восстанавливались оригинальные первые два байты интерпретатора, интерпретация продолжалась в обычном режиме.

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

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

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

Лирическое отступление. Я всегда интересовался reverse engineering'ом (даже сейчас не прочь покопаться IDA'ой в каком-нибудь экзешнике), и в частности различными идеями защиты от отладки. А данная идея интерпретатора одной команды тут подходит как нельзя лучше. Так как все реализовано через одну элементарную функцию, то при анализе и дизассемблировании сложно понять, где границы высокоуровневых команд. Как одну из идей, я переделал свой простейший Форт-интерпретатор с прямым шитым кодом (который сам по себе затруднен для анализа) под использование NOR интерпретатора для реализации всех низкоуровневых Форт-примитивов.

Недавно я вернулся к теме NOR-интерпретатора. Интересно было написать это на Питоне. Также пришла мысль, как можно модифицировать интерпретатор, чтобы на нем можно было бы реализоваться и полноценное сложение.

Я ввел одну дополнительную команду в него — циклический сдвиг результата каждой операции и сохранение значения в специальной ячейке-регистре:

def norcpu():
  while 1:
    i = mem[IP];
    a = mem[i + 0]
    b = mem[i + 1]
    r = mem[i + 2]
    mem[IP] = i + 3
    f = nand(mem[a], mem[b])
    mem[r] = f
    mem[S] = ((f >> 31) & 1) | ((f & 0x7FFF) << 1)

То есть теперь есть две особые ячейки: IP (instruction pointer) и S (значение последней операции, циклически сдвинутое влево).

Попробуем реализовать полное суммирование 16-х слов с переносом. Я буду писать на некотором элементарном макро-ассемблере.

Итак, полный однобитный сумматор в нотации булевой алгебры:

sum = (a ^ b) ^ carry
carry = (a & b) | (carry & (a ^ b))

Теперь на языке NOR(NAND)-процессора:

; Вход:
;  mask  - битовая маска рабочего бита (0x0001, 0x0002, 0x0004, 0x0008 и т.д.)
;  carry - перенос от предыдущего бита (бит определяется маской mask)
;  a, b  - адреса аргументов
;  r     - адрес результата
; Выход:
;  r     - результат
;  carry - перенос для следующего разряда (по отношению к mask уже сдвинут на 1 бит влево)
;  mask  - маска, сдвинутая слево на 1 бит
;
; Переменные с префиксом '@' - локальные для этого макроса.
;
!macro FADD mask, carry, a, b, r
  AND a, mask, @bit_a        ; Уберем в "a" все биты, кроме нужного.
  AND b, mask, @bit_b        ; Уберем в "b" все биты, кроме нужного.
  AND carry, mask, carry     ; Уберем в переносе все биты, кроме нужного.
  XOR a, b, @t1              ; Формула: sum = (a ^ b) ^ carry.
  XOR @t1, carry, @bit_r     ; 
  AND @bit_r, mask, @bit_r   ; Уберем из @bit_r все биты, кроме текущего 
                             ; по маске.
  OR @bit_r, r, r            ; Наложим текущий сложенный бит на результат: 
                             ; r |= sum
  AND a, b, @t2              ; Формула: carry = (a & b) | (carry & (a ^ b))
  AND carry, @t1, @t1        ;
  OR @t2, @t1, carry         ; Перенос получил новое значение. Регистр S
                             ; равен ему же, но сдвинутому влево на 1 бит. 
  MOVE S, carry              ; Теперь перенос равен себе же, но со сдвигом
                             ; влево на 1 (для суммирования в следующем бите).
  MOVE mask, mask, mask      ; Пустое присваивание mask самой себе, чтобы
                             ; получить сдвинутое значение в S.
  MOVE S, mask               ; Маска сдвинута влево на 1 бит для суммирования
                             ; следующего бита: mask = S = mask << 1

И теперь сам макрос полного суммирования:

; Вход:
;  a, b  - аргументы
;  carry - перенос (0 или 1 в младшем разряде)
; Выход:
;  r     - результат
;  carry - перенос (0 или 1 в младшем разряде)
;
; Переменные с префиксом '@' - локальные для этого макроса.
; const_1 - специальная ячейка, в которой содержится 0x0001.
;
!macro ADC a, b, carry, r
  XOR r, r, r                     ; Запишем 0 в r.
  MOVE const_1, @mask             ; Начальное значение маски: 0x0001
  *16 FADD @mask, carry, a, b, r  ; Повторяем FADD 16 раз (просто линейно в
                                  ; памяти, никаких циклов).
  AND carry, const_1, carry       ; Почистим перенос от мусора в старших
                                  ; разрядах.

Что происходить в ADC? При каждом повторении FADD происходит суммирование текущего бита, маска которого задана в mask. Просуммированный бит добавляется (через OR) в результат. Кроме этого mask автоматически сдвигается влево на 1 бит, чтобы указывать на следующей бит (0x0001 -> 0x0002 -> 0x0004 и т.д.). Также в каждом вызове FADD перенос после суммирования тоже сдвигается влево на 1 бит, чтобы быть готовым для суммирования на следующей итерации. После суммирования последнего 16-го бита перенос уйдет снова в самый младший разряд (так как интерпретатор делает циклический сдвиг), и это значение и будет результирующим переносом после всего суммирования.

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

Итак, что мы имеем в сухом остатке после муторных битовых баталий? Некую битовую виртуальную машину, на которой можно делать любые вычисления.

Машина крайне проста, но из-за этого программный код, состоящий из примитивных NOR'ов (или NAND'ов) может быть большим.

Для чего? Первое и главное: академический интерес. Прикольно же получить полноценную вычислительную среду на базе единственной операции NOR или NAND. Второе: изначально все это задумывалось как вариант защиты, например, от копирования. На данной виртуальной машине можно реализовать хитрую крипто-функцию и ей проверять валидность ключа. Таким образом к крипто-защите еще и добавится трудный анализа кода.

Но на дворе время opensource, то что повторюсь - академический интерес!

Посты по теме:

• Обмен двух переменных через XOR

Обмен двух переменных через XOR

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

a += b;
b = a - b;
a -= b;

Интересно разве что с академической точки зрения. Но есть способ интереснее:

a ^= b ^= a ^= b;

который также меняет местами значения этих переменных.

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

Решето Эратосфена - кто быстрее: Go, C или C++?

Go очень интересный язык. Компиляция в native-code (никаких виртуальных машин, JIT-компиляций и т.д.), при этом автоматическая сборка мусора и встроенная поддержка многопоточности, объектно-ориентированная модель, и в довершение всего - очень быстрая компиляция.

Лично я обычно на новых для меня языках люблю писать Решето Эратосфена в качестве "Hello, world!".

Моя версия на Go выгдядит так:

Файл erato-go-bool.go:

package main

import "fmt"
import "math"
import "flag"

func main() {
    var N int
    flag.IntVar(&N, "N", 100, "")
    flag.Parse()

    fmt.Printf("%d\n", N)

    seive := make([]bool, N)
   
    limit := int(math.Sqrt(float64(N))) + 1

    for i := 2; i < limit; i++ {
        if !seive[i] {
            for j := i * i; j < N; j += i  {
                seive[j] = true
            }
        }
    }

    count := 0
    for i := 2; i < N; i++ {
        if !seive[i] {
            count++
        }
    }
    fmt.Printf("%d\n", count)
}

И первый вопрос, который приходит в голову - а насколько это быстро работает?

Некоторое время назад я уже писал, как использовал решето для тестирования STL'евского контейнера std::vector на разных компиляторах.

Сейчас я провел похожее сравнение между Go, C++ и C.

Итак, первый кандитат - версия на Go с использованием типа bool (см. выше). Второй - тоже на Go, но с использованием типа int.

Файл erato-go-int.go:

package main

import "fmt"
import "math"
import "flag"

func main() {
    var N int
    flag.IntVar(&N, "N", 100, "")
    flag.Parse()

    fmt.Printf("%d\n", N)

    seive := make([]int, N)
   
    limit := int(math.Sqrt(float64(N))) + 1

    for i := 2; i < limit; i++ {
        if seive[i] == 0 {
            for j := i * i; j < N; j += i  {
                seive[j] = 1
            }
        }
    }

    count := 0
    for i := 2; i < N; i++ {
        if seive[i] == 0 {
            count++
        }
    }
    fmt.Printf("%d\n", count)
}

Далее идет версия на С++. Макрос TYPE позволяет переключать программу для нужно типа в контейнере (int или bool):

Файл erato-cxx.cpp:

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cmath>

int main(int argc, char* argv[]) {
  int n = argc > 1 ? std::atoi(argv[1]) : 100;

  std::cout << n << std::endl;

  int sqrt_n = static_cast<int>(std::sqrt(static_cast<double>(n))) + 1;

  std::vector<TYPE> S(n, true);

  for (int i = 2; i < sqrt_n; ++i)
    if (S[i])
      for (int j = i*i; j < n; j+=i)
        S[j] = false;

  int count = 0;
  for (int i = 2; i < n; ++i)
    if (S[i])
      count++;

  std::cout << count << std::endl;

  return 0;
}

Ну и для полноты картины версия на С:

Файл erator-c-int.c:

#include <stdio.h>
#include <stdlib.h>
#include <memory.h>
#include <math.h>

int main(int argc, char* argv[]) {
  int n = argc > 1 ? atoi(argv[1]) : 100;
  int* S;
  int count;
  int sz = n * sizeof(*S);
  int i, j;

  printf("%d\n", n);

  long sqrt_n = sqrt(n) + 1;

  S = malloc(sz);
  memset(S, 0, sz);

  for (i = 2; i < sqrt_n; ++i)
    if (S[i] == 0)
      for (j = i*i; j < n; j+=i)
        S[j] = 1;

  count = 0;
  for (i = 2; i < n; ++i)
    if (S[i] == 0)
      count++;

  printf("%d\n", count);

  free(S);
  return 0;
}

Ну и Makefile для удобного запуска.

Файл Makefile:

.SILENT: 

all: 
        $(MAKE) run 2>&1 | tee log
        $(MAKE) parse-log

run: go-bool go-int cxx-int cxx-bool c-int

N ?= 100000000

go-bool:
        echo $@
        6g erato-$@.go
        6l -o erato-$@ erato-$@.6
        time -p -f %e ./erato-$@ -N=$(N)

go-int: 
        echo $@
        6g erato-$@.go
        6l -o erato-$@ erato-$@.6
        time -p -f %e ./erato-$@ -N=$(N)

cxx-bool:
        echo $@
        g++ -o erato-$@ \
                -O3 -funroll-all-loops -fomit-frame-pointer \
                -DTYPE=bool erato-cxx.cpp 
        time -p -f %e ./erato-$@ $(N)

cxx-int:
        echo $@
        g++ -o erato-$@ \
                -O3 -funroll-all-loops -fomit-frame-pointer \
                -DTYPE=int erato-cxx.cpp 
        time -p -f %e ./erato-$@ $(N)

c-int:
        echo $@
        gcc -o erato-$@ -lm \
                 -O3 -funroll-all-loops -fomit-frame-pointer erato-$@.c
        time -p -f %e ./erato-$@ $(N)

parse-log:
        printf "%10s %10s %8s %5s\n" "Language" N Count Time ; \
        (echo "------------------------------------") ; \
        while read type ; do \
                read N && \
                read count && \
                read time && \
                printf "%10s %10s %8s %5s\n" $$type $$N $$count $$time ; \
        done < log

Запускал я все это под Ubuntu 64-bit. Компилятор C и C++ - gcc 4.4.1. Компилятор Go - последний из официального репозитория.

Запускаем:

make N=100000000

и получаем следующее:

 Language           N    Count  Time
------------------------------------
   go-bool  100000000  5761455  3.96
    go-int  100000000  5761455  6.58
   cxx-int  100000000  5761455  6.76
  cxx-bool  100000000  5761455  2.20
     c-int  100000000  5761455  6.47

Получается, что сделал всех С++ с использованием std::vector<bool> для хранения массива. Затем идет Go тоже с типом bool. А С, С++ с std::vector<int> и Go с int'ом примерно равны.

Update: После экспериментов в комментариях выходит, что и на С, и на С++ можно добиться равного быстродействия, если использовать битовые поля. Просто в С++ это синтаксически проще, но не более того.

Посты по теме:

• Кто быстрее: vector<bool> или vector<int>

Трейдинговые системы для чайников

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

Так как данная сфера деятельности активно развивается в англоязычном мире, то многие термины проще использовать без перевода, чтобы не потерять по дороге смысл.

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

Итак, для начала несколько простых определений.

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

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

Ценная бумага - это объект торговли (в английском языке это называется "security"). Типов ценных бумаг очень много (акции, облигации, валюта и т.д.). Я не буду вдаваться в объяснение их сути (для этого следует обраться к литературе по экономике), так как с точки зрения компьютерной системы каждая ценная бумага - это всего лишь идентификатор. Например, "GOOG US Equity" - это акции Гугла на Нью-Йоркской фондовой бирже, "VOD LN Equity" - это акции Vodafone на Лондонской бирже, "CT2 Govt" - это двухлетние государственные облигации правительства США и т.д. Таких идентификаторов тысячи, и в целом большинство электронных систем торговли стараются соблюдать уникальность данных идентификаторов во избежание путаницы при операции между различными платформами.

Каждая система может иметь (и обычно имеет) внутреннюю систему идентификации ценных бумаг для удобства их учета.

Сделка (или trade) - это факт покупки/продажи ценных бумаг. Сделка обычно имеет несколько базовых характеристик: дата/время, идентификатор ценной бумаги, сумма за единицу и количество купленных/проданных единиц ценной бумаги. Данный квант информации обычно называется tick (или feed). Именно поток таких тиков, получаемых в режиме реального времени с различных торговых платформ, и является основным источником различных сводок, диаграмм, графиков, бегущих строк и т.д., описывающих "состояние фондового рынка", по которым трейдеры принимают решение о том, что покупать или продавать, когда и почем.

Скорость поступления тиков может быть весьма высока (сотни или даже тысячи в секунду). Это объясняет, почему одним из важнейших показателей для трейдинговой системы является быстродействие. Чем быстрее обрабатываются входные данные, тем быстрее трейдер узнает об изменениях на рынке, и тем быстрее может принять решение. А для алгоритмического трейдинга (мы поговорим об это чуть ниже) - это вообще один из основных показателей. Это быстродействие может складывается из многих факторов: быстрота программного обеспечения, скорость информационных каналов (часто используются выделенные линии, а не публичные сети типа интернета), производительность аппаратного обеспечения и т.д.

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

Основные участники рынка ценных бумаг

Sell side (я оставлю этот термин без перевода) - это те, что ориентирован на перепродажу. Трейдеры - это типичные представители sell side. Обычно они не имеют своих активов. У них просто есть немного денег. В начале торгового дня они покупают что-то, а потом в течение дня могут перепродавать, покупать другое и т.д. В конце дня они обычно все стремятся распродать, даже если придется продать в убыток. Sell side обычно зарабатывает на быстрых дневных изменениях курсов, вызванных, например, неожиданными новостями.

Экономическая причина существования sell side - это, как в случае процессинговых систем, вопрос объема. То есть, нельзя просто так взять, и кому угодно подключиться к фондовой бирже, так как это стоит денег (депозиты, оборудование, сертификация, если потребуется и т.д.). Высокий ценовой ценз сделан для отсечения мелких клиентов (бирже не интересно возиться с клиентами, покупающими одну акцию в год). Последние должны будут пользоваться услугами более крупных трейдинговых фирм, и им уже придется платить комиссию.

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

То есть в течение торгового дня sell side перепродает туда-сюда ценные бумаги от buy side, а к концу дня все снова фактически возвращается к buy side, и sell side имеет свою дневную разницу.

Конечно, такое разделение может быть весьма условным, и многие финансовые институты являются одновременно sell side и buy side. Но понимание этого различия весьма важно.

Рассмотрим некоторые важные части трейдинговой системы.

Мониторинг

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

Про новостные системы стоит сказать особо. Они состоят из нескольких уровней. После получения того или иного факта, на первом уровне новость ужимается в одно предложение из нескольких слов и тут же публикуется. Это позволяет для новостного провайдера выпустить новость очень быстро (буквально несколько минут), а для потребителя новости (например, трейдера), увидев новую строчку в новостной ленте (а не читать целый абзац) уловить суть и, если надо, начать действовать. Например, "ГАЗПРОМ снял генерального директора" или "Сбербанк объявил о банкротстве". Далее новость передается на следующий уровень, где пишется уже абзац или два с более детальным описанием. Тут уже может пройти час или два. Если изначальная новость была бомбой, то многие будут ждать этого описания, а если нет, то возможно никто ее и не станет читать. Ну а затем уже на третьем уровне много позже могут написать детальную аналитику, и, например, включить мнения экспертов на влияние новости на те или иные рынки, ценные бумаги и т.д.

Системы учета позиций и истории сделок

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

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

Системы проведения сделок

Обычно, работа трейдера - это договориться о сделке. Электронно или по телефону - неважно. Проведение сделки обычно происходит после закрытия рынков. И этим занимается middle office. На данном этапе могут также проводиться дополнительные проверки активности трейдера.

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

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

Анонимная торговля

Первым способом торговли может быть, когда трейдер напрямую покупает (или продает) у конкретного контрагента (например, у своего постоянного партнера).

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

Устройство электронного рынка для анонимной торговли

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

   Bid       Offer
---------+----------
Ц1 х К1  | Ц5 х К5
---------+----------
Ц2 х К2  | Ц6 х К6
---------+----------
Ц3 х К3  | Ц7 х К7
---------+----------
        ...
---------+----------
Ц4 х К4  | Ц8 х К8
---------+----------

Колонка Bid - это цены и объемы того, что люди хотят купить (список текущего спроса). Эта колонка отсортирована по убыванию цены:

Ц1 > Ц2 > Ц3 > ... > Ц4

То есть физический смысл этой колонки - это показать лучшие (= наибольшие) с точки зрения потенциального продавца цены (и возможные объемы) по данной ценной бумаге.

Допустим, ячейки "Ц1 х К1" пока нет, а на вершине колонки Bid находится "Ц2 х К2". Я, как участник рынка, говорю «я хочу купить ценную бумагу N по цене "Ц1" в количестве "К1"». Так как моя цена больше цены "Ц2", то моя заявка становится на вершину колонки.

Колонка "Offer" (или иногда ее называют "Ask") - это цены и объем того, что люди хотят купить (список текущих предложений). Эта колонка отсортирована по возрастанию цены:

Ц5 < Ц6 < Ц7 < ... < Ц8

Физический смысл этой колонки - это показать лучшие (= наименьшие) с точки зрения потенциального покупатели цены (и объемы) по данной ценной бумаге.

Далее начинается самое интересное. Как известно, спрос удовлетворяет предложение и наоборот. Так вот данная таблица и является механизмом сопоставления спроса и предложения.

Если я прихожу на рынок и говорю «я хочу купить ценную бумагу N по цене "Ц1" и количестве "К1"», система берет таблицу "Market depth" для ценной бумаги N и просматривает колонку "Offer".

Если какая-то цена совпадает с моей (например, "Ц6"), то система автоматически удовлетворяет мою заявку и продает мне нужное количество ценных бумаг N по цене "Ц1" (= "Ц6") и в количестве "К1". И ячейка "Ц1 х К1" не появляется в колонке спроса "Bid", так как мой спрос удовлетворен. Если мое запрошенное количество "К1" равно "К6", то строка "Ц6 х К6" удаляется из колонки предложений "Offer". Если мое количество "К1" меньше "К6", то строка "Ц6 х К6" остается в колонке, но из "К6" просто вычитается "К1". Ну а если же мое количество "К1" больше "К6", то строка "Ц6 х К6" удаляется из колонки "Offer" (это предложение полностью удовлетворено), а в колонке "Bid" появляется моя строка "Ц1 х К1", где "K1" отображается за вычетом "K6", то есть "Ц1 х K1-K6".

Аналогично, для продажи. Если я прихожу на рынок и говорю «я хочу продать ценную бумагу N по цене "Ц6" и количестве "К6"», система берет таблицу "Market depth" для ценной бумаги N и просматривает колонку "Bid".

Если какая-то цена совпадает с моей (например, "Ц2"), то система автоматически удовлетворяет мою заявку и покупает у меня нужное количество ценных бумаг N по цене "Ц6" (= "Ц2") и в количестве "К6". И ячейка "Ц6 х К6" не появляется в колонке спроса "Offer", так как моё предложение удовлетворено. Если мое запрошенное количество "К6" равно "К2", то строка "Ц2 х К2" удаляется из колонки предложений "Bid". Если мое количество "К6" меньше "К2", то строка "Ц2 х К2" остается в колонке, но из "К2" просто вычитается "К6". Ну а если же мое количество "К6" больше "К2", то строка "Ц2 х К2" удаляется из колонки "Bid" (этот спрос полностью удовлетворен), а в колонке "Offer" появляется строка "Ц6 х К6", где "K6" отображается за вычетом "K2", то есть "Ц6 х K6-K2".

По сути, таблица "Market Depth" отображает список пока еще неудовлетворенных спросов и предложений. Как только находится для спроса парное предложение или наоборот - между ними производится сделка (trade), и эта пара удаляется из таблицы (одна из сторон может после сделки таки остаться в таблице "Market Depth", если, как описано выше, не было полного совпадения по количеству).

Обычно "Market depth" отображает в среднем от 10 до 100 уровней цен по спросу и предложению. Больше нет особого смысла нет.

Кроме того, каждая ячейка данной таблицы может раскрываться списком заявок по цене. Что это значит? Например, ячейка "Ц1 х K2" может быть агрегированным по цене показателем, то есть количество "К1" является предложением не единственного покупателя, а многих (несколько покупателей могут хотеть купить по цене "Ц1"), но так как для продавца неважно, кому именно продавать (цена то все равно одна и та же, и система в целом анонимна), по умолчанию эта детализация может не отображаться.

Механизм сопоставления спроса и предложения по таблице "Market Depth" лежит в основе анонимного трейдинга, и так называемый алгоритмический трейдинг может быть построен на программировании логики автоматизированной торговли, основанной на анализе данных таблицы "Market Depth".

Для алгоритмического трейдинга система предоставляет программный интерфейс (API), который может быть, как вариант, скриптовым языком, например, Lua, с набором функций для просмотра таблиц "Market Depth" и для помещения в систему заявок на покупку или продажу. Логика же программируется автором скрипта.

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

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

Посты по теме:

• 10 распространенных заблуждений про пластиковые карты
• Формат представления сумм "32nd"