10 вещей, которые я страстно ненавижу в работе

В порядке убывания приоритета:

1. Аргумент в защиту неаккуратного кода "Ну так работает же!!!"
2. Пробел перед запятой
3. Использование мыши, если сделать клавиатурой можно в десять раз быстрее
4. Проекты, которые нельзя собрать, просто набрав "make"
5. Смесь табуляций и пробелов как разделителей в одном исходнике
6. Однопанельные файловые менеджеры
7. Советы типа "кликнуть там-сям, перетащить мышкой сюда, потом снова кликнуть..." если можно написать скрипт
8. Неумение пользоваться повтором в командной строке и перебивание каждый раз заново
9. Префикс "my" в именовании переменных, "MyClass" например, и автоматическое именование типа TButton1, TButton2, которое ручками не исправлено на нормальные имена ("Ну так работает же!!!")
10. Двоичные исходные файлы в проекте

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

Задача с интервью одного очень крупного инвестиционного банка

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

Как результат надо вывести начальный и конечный индексы этого интервала.

Подразумевается решение O(n).

Динамическая линковка C++ на AIX

AIX мне всегда нравился своим особо изощренным отношением к линковке.

Итак, рассмотрим пример (система AIX 5.3).

Файл "alib.cpp" компилируем как динамическую библиотеку.

struct A {
  A() {
    value_ = 123;
  }
  int value_;
};

A a = A();

extern "C"
int value() {
  return a.value_;
}

В этой библиотеке создается статический объект класса А, и значение его поля возвращается функцией "value()".

Компилируем:

xlC -o alib.so -qrtti=all -qmkshrobj=-100 -G -brtl -bnolibpath alib.cpp

"xlC" - это компилятор С++ на AIX.

Далее, файл "main.c". Это головной модуль на С, который вызывает функцию "value()".

extern int value();

int main() {
  return value();
}

Этот модуль вызывает "value()", и значение становится кодом возврата процесса.

Компилируем:

xlc -c -o main.o main.c

"xlc" (маленькая "с" на конце) - это компилятор С на AIX.

Линкуем, используя компилятор "С", запускаем и печатаем код возврата ($?):

xlc -o main main.o alib.so && LIBPATH=.:$LIBPATH ./main ; echo $?

Результат на экране:

0

Интересно?! Почему не ожидаемое 123?

Теперь линкуем, используя компилятор "С++", запускаем и печатаем код возврата:

xlC -o main main.o alib.so && LIBPATH=.:$LIBPATH ./main ; echo $?

Результат на экране:

123

Мораль: на AIX, при динамической линковке библиотек, чтобы правильно работала статическая инициализация на С++, надо принудительно линковать конечный бинарь в режиме С++ (как бы это странно не звучало). Иначе конструкторы статических объектов вызваны не будут, и их инициализация будет произведена не ДО функции "main()", а непонятно когда.

Можно принудительно заставить таки систему вызвать конструкторы статических объектов, написав что-то вроде:

#include <dlfcn.h>

static int module_initialised = 0;
static void ManualInitilizationForStatics() {
  if (module_initialised) return;
  dlopen("blah.so", RTLD_NOW);
  module_initialised = 1;
}

Но это не программирование, а ерзанье.

Интересное за неделю

EKOPath 4 Compiler Suite

EKOPath вроде как собирается выпустить в open-source их супер-пупер оптимизирующий компилятор C++.

Как пишут в пресс-релизе:

The PathScale EKOPath Compiler Suite has the world's most advanced optimization infrastructure and can fully exploit the potentials of many-core architectures.

---

Вам хочется рисовать диаграммы и блок-схемы по-настоящему, в vi'e, роняя скупую слезу юниксоида, взгляните на это ASCII Flow.

Как говориться, почему рулит plain-text? А потому, что его можно поместить под контроль версий (1) и делать diff (2).

---

Google выложил в open-source Address Sanitizer.

Address Sanitizer - это аналог Valgrind, но не совсем. Например, эта штука умеет ловить buffer over-/underrun не только на куче, но и на стеке. Работает только на Linux Intel 32 и 64 бит.

Должен ли быть стандарт кодирования жестким?

Например, вот такой кусок кода:

void f (  int a , char *p  )
{
   int   whattodo ;

   whattodo = a < 1 ? 2 : 0;

   switch ( whattodo )
   {
   case 2:
             printf("THIS\n"); break;
   case 1:
             printf("THAT\n");
             break;
   }
   if ( a !=  * p  ) {
             a = 1111111 ;

   } else
             a = 2222222;


}

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

Но:

• абсолютная неаккуратность и непоследовательность использования пробелов и пустых строк
• бессмысленное имя переменной "whattodo"
• непоследовательность в стиле расположения "{" и "break"

Вывод - это не код, а помойка.

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

Какой текст приятнее и понятнее читать?

Так:

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

Или так:

кОМИьютерная сеть       Международного    валютного
    фонда  подверглась хакерской атаке   . Официального
объявления          об этом пока не сделано , однако сотрудникам о
   вторжении сообщили ЕЩе в СрЕдУ.
ПредстАвитель   МВФ отказался сООбщить  какую-  либо информацию об
инциденте , заверив  журналистов        , что организация работает в
обычном         реЖиме  .

На многих это производит эффект.

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

Еще пару мыслей. Есть определенные приемы в форматировании кода, которые призваны облегчить copy-paste.

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

A::A() :
  a(1)
  , b(1)
  , c(1)
{
...
}

Лично я не против copy-paste, когда ради его удобства уродуют текст - это уже слишком. Я резко против таких приемов.

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

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

Алгоритмы в прикладном программировании

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

Первое, что приходит в голову – задача выдачи денег в банкомате.

Клиент хочет сумму X, и в банкомате есть купюры нескольких номиналов. Если выбранная целевая функция – минимизировать количество выдаваемых купюр, то задача сводится к распространённой задаче выдачи сдачи и решается за O(N^2).

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

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

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

И увы, мой список на этом заканчивается.

А какие прикольные алгоритмы приходилось в реальной работе использовать вам?

Кто быстрее: string::find, strstr или КМП?

Я как-то пребывал в убеждении, что библиотечные функции поиска строки в подстроке обычно реализуют какой-нибудь "правильный" алгоритм: Кнута — Морриса — Пратта (КМП), например, или Бойера — Мура. Это было бы логично.

Ниже очередная пузомерка сферического коня в попугаях.

В забеге учавствуют:

• std::string::find()
• std::strstr()
• рукодельный naive_strstr() со сложностью O(N^2)
• рукодельный КМП (kmp_strstr()) без особых изысков

Данные для поиска сделаны в виде "наихудщего случая", когда сравнивать надо все до победного, и совпадение будет только с самом конце. Это должно вызвать явное квадратичное время у naive_strstr().

#include <iostream>
#include <vector>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <ctime>

int naive_strstr(const char* str, const char* needle) {
  int str_sz = std::strlen(str);
  int needle_sz = std::strlen(needle);
  for (int i = 0; i < str_sz - needle_sz + 1; ++i) {
    int j;
    for (j = 0; j < needle_sz; ++j)
      if (str[i + j] != needle[j])
        break;
    if (j == needle_sz)
      return i;
  }
  return -1;
}

int kmp_strstr(const char* str, const char* needle) {
  int str_sz = std::strlen(str);
  int needle_sz = std::strlen(needle);

  std::vector<int> prefix(needle_sz, 0);
  for (int i = 1; i < needle_sz; ++i) {
    int j = prefix[i - 1];
    while (j > 0 && needle[j] != needle[i])
      j = prefix[j - 1];
    if (needle[j] == needle[i])
      j += 1;
    prefix[i] = j;
  }

  int j = 0;
  for (int i = 0; i < str_sz; ++i) {
    while (j > 0 && needle[j] != str[i])
      j = prefix[j - 1];
    if (needle[j] == str[i])
      j += 1;
    if (j == needle_sz)
      return i - j + 1;
  }

  return -1;
}

int main(int argc, char* argv[]) {
  int N = argc > 1 ? std::atoi(argv[1]) : 10*1000*1000;
  int M = argc > 2 ? std::atoi(argv[2]) : 1000;

  std::string str(N, 'a');
  std::string needle(M, 'a');

  // Our needle is the last M characters of the string.
  str[str.length() - 1] += 1;
  needle[needle.length() - 1] += 1;

  std::cout << "N = " << N << ", M = " << M << std::endl;

  size_t correct_position = str.length() - needle.length();
  std::cout << "Correct position: " << correct_position << std::endl;

  const char* str_p = str.c_str();
  assert(std::strlen(str_p) == str.length());

  const char* needle_p = needle.c_str();
  assert(std::strlen(needle_p) == needle.length());

  time_t started, duration;
  size_t i;

  started = std::time(0);
  i = str.find(needle);
  duration = std::time(0)- started;
  std::cout << "string::find(): " << i << ", time " << duration << std::endl;
  assert(i == correct_position);

  started = std::time(0);
  const char* p = std::strstr(str_p, needle_p);
  duration = std::time(0)- started;
  assert(p != NULL);
  i = p - str_p;
  std::cout << "strstr()      : " << i << ", time " << duration << std::endl;
  assert(i == correct_position);

  started = std::time(0);
  i = naive_strstr(str_p, needle_p);
  duration = std::time(0)- started;
  std::cout << "naive_strstr(): " << i << ", time " << duration << std::endl;
  assert(i == correct_position);

  started = std::time(0);
  i = kmp_strstr(str_p, needle_p);
  duration = std::time(0)- started;
  std::cout << "kmp_strstr()  : " << i << ", time " << duration << std::endl;
  assert(i == correct_position);

  return 0;
}

Makefile:

all:  do-32 do-64

target = strstr_find

do-32: build-32
    $(target)

do-64: build-64
    $(target)

do-build:
    "%VS100COMNTOOLS%..\..\VC\vcvarsall.bat" $(arch) && cl /O2 /EHsc $(target).cpp

build-32:
    $(MAKE) do-build arch=x86

build-64:
    $(MAKE) do-build arch=amd64

run:
    $(target)

clean:
    -del *.exe *.ilk *.obj *.pdb *.suo

Запускаем на Visual Studio 2010 32-bit:

N = 10000000, M = 1000
Correct position: 9999000
string::find(): 9999000, time 4
strstr()      : 9999000, time 8
naive_strstr(): 9999000, time 8
kmp_strstr()  : 9999000, time 0

Запускаем на Visual Studio 2010 64-bit и получаем странное ускорение у find() и замедление strstr() и naive_strstr():

N = 10000000, M = 1000
Correct position: 9999000
string::find(): 9999000, time 1
strstr()      : 9999000, time 16
naive_strstr(): 9999000, time 10
kmp_strstr()  : 9999000, time 0

КМП в обоих случаях работает быстро.

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

И еще. Так как КМП требует дополнительную память порядка длины искомой строки, то подобное осложнение может не годиться для библиотечной функции широкого применения. Может поэтому strstr() и string::find() и работают "в лоб".

Одно не понятно - почему string::find() быстрее strstr()? Может из-за тотального inline'а.

Разумные и неразумные сокращения в C++

Вот вполне себе реальный код:

const char* a = ::getenv("VAR");
if (a == NULL)
  a = "[NULL]";

Но в каком-то внутреннем стремлении сделать код "немного лучше", можно написать так:

const char* a = (a = ::getenv("VAR"), a ? a : "[NULL]");

Мне внутренне больше нравиться второй вариант. Он как-то выразительнее. Но на code view я, конечно, буду настаивать однозначно на первом, так как не только мне одному этот код потом читать.

Также в С++ считается хорошим тоном объявлять переменную цикла ''for'' прямо в теле оператора:

for (int i = 0; ...

Но вот конструкции типа:

if (int a = foo()) {
  ...
}

или

while (int a = foo()) {
  ...
}

уже немного режут глаз, хотя и являются корректными.

А у вас какие есть прикольные сокращение? пусть даже не для production code?

Ошибка в обработке деструктора временного объекта в компиляторе Sun C++ 5.8

Рассмотрим код:

#include <iostream>
int ct = 1;
struct G {
  ~G() { ct--; }
};
int main() {
  (G());  // (1)
  std::cout << ct << std::endl;
  return 0;
}

Как вы думаете - что напечатает данная программа?

Весь вопрос в том, когда будет вызван деструктор временного объекта, созданного в строке "(1)": сразу после знака ";" в этой же строке или в конце блока на символе "}"?

Если первое, то программа выведет "0", если второе, то "1".

Я проверил на 6 разных компиляторах на разных платформах - везде печатается "0", что соответствует стандарту.

Но на отдельно выделенной версии Sun C++ 5.8 2005/10/13 данная программа печатает "1"!

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

Задача про винты и гнезда

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

Вот одна из них.

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

Требуется расставить все винты по гнездам. Разрешено только одно действие - попытка вставить винт i в гнездо j. В результате такой операции можно выяснить: (1) винт тоньще гнезда - не подходит, (2) винт толще гнезда - не подходит, (3) или винт точно входит в гнездо - подходит.

Сравнивать винты или гнезда между собой нельзя.

Очевидное решение за O(N^2) - попробовать каждый болт последовательно в каждое гнездо до совпадения. Но есть решение быстрее.