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

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

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

Клиент хочет сумму 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++ и Java

Не побоюсь повториться -- две совершенно волшебные, на мой взгяд, ссылки на реализации множества алгоритмов на C++ и Java.

• http://e-maxx.ru/algo/ - алгоримты на С++ с минимумом теории
• http://sites.google.com/site/indy256/ - алгоритмы на Java и С++

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

Умножение вручную на бумажке по-китайски

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

Поиск подстроки в строке: алгоритм Кнута-Морриса-Пратта

Мне понравилась идея недели борьбы с велосипедизмом, посему внесу свою лепту.

Один из частых вопросов, которые задают у нас в Блумберге на интервью в плане так называемого coding exercise (это когда надо на бумаге или на доске написать почти реальный кусок кода) - это поиск строки в подстроке. Это абсолютно жизненная задача.

Подавляющее число людей пишут первое, что приходит в голову - это два вложенных цикла, когда искомая строка последовательно "прикладывается" с каждой позиции исходной строки. Такой подход дает сложность O(M*N), и, очевидно, что в жизни он нереален, если строки более менее длинные. Хотя все при этом знают, что любой hex-вьювер спокойно ищет в огромных файлах за явно линейное время.

Итак, для эффективного поиска строки в подстроке есть алгоритм Кнута-Морриса-Пратта, который решает проблему не за O(N*M), а за O(N+M).

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

P.S. Сразу скажу, у нас никто не просит по памяти писать КМП. И если человек после написания простого O(N^2) решения также скажет, что есть метод быстрее, и сможет описать его идею - этого вполне достаточно.

Лекции из MIT

На сайте MITа лежит множество лекций из различных разделов науки. Например, раздел Computer science.

В частности, курс Introduction to Algorithms.

Все сделано максимально удобно: в добавок к видео (некоторые идут сразу с субтитрами) еще есть и транскрипт каждой лекции.

Я еще рекомендую заценить примеры экзаменационных задач.

Честно говоря, берет зависть, насколько там все удобно сделано для учебы.

Немного об алгоритмах

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

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

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

Обнаружил просто мега-сайт - e-maxx.ru/algo. Справочник по алгоритмам и их реализациями на С++. Все на русском языке. Как мне тут сказали, что, в принципе, освоив большинство из них, можно показывать неплохие результаты на программистских соревнованиях.

В разделе книг там также отличная подборка.

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



и



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

Кстати, заметил интересный факт. Лично я не люблю язык Паскаль. Мое субъективное мнение. Многословный и эстетически некрасивый синтаксис. Но Российская школа программирования уважает Паскаль и Дельфи (спасибо вечному Турбо Паскалю 7.0), и поэтому программы в этих книгах написаны на Паскале, а не на С++. И заставляя себя вчитываться в паскалевские куски кода, еще и изуродованные форматированием для печати в книге, получаешь более полное понимание алгоритма. Как говорят: умение читать код может быть даже важнее для программиста, чем писать его.

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

Алгоритмы - это очень интересно.

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

• Фундаментальные алгоритмы
• Судоку для программистов или олимпиадные задачи

Смесь двоичной и десятичной арифметики

Многие знают, что происходит при выполнении присваивания "n &= (n - 1);" просто потому, что это весьма распространенный шаблон, и для чего может понадобиться выполнение его в цикле, пока n не станет нулем.

Интересно другое: четкое математическое (и/или алгоритмическое) объяснение, почему это работает именно так, строгое доказательство.


Update:

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

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

С точки зрения битового представления любого числа, есть только два случая:

1. Если число нечетное, на конце будет единица: "xx...xx1". Вычитание из такого числа даст: "хх...хх0". Поэтому "(xx...xx1) & (xx...xx0)" даст "(xx...xx0)". Фактически, мы убрали младший бит.

2. Если число четное, на конце будет ноль (или несколько нулей): "xx...xx100...00". Видно, что вычитание единицы из такого числа однозначно не изменит разряды "xx...xx", стоящие слева после первой единицы. Более того, результат вычитания единицы однозначно предсказуем: "xx...xx011...11". Теперь точно видно, что будет после операции "and": ("xx...xx100...00") & ("xx...xx011...11") даст ""xx...xx000...00". То есть мы убрали единицу из самого младшего ненулевого разряда.

Теперь ясно видно, что именно проиходит в присваивании "n &= (n - 1);". А именно, обнуление самого младшего ненулевого разряда.

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