The Software Unfactory | Averages - II

[aruslan]

Java и традиционные языки: производительность программиста

Результаты интересные, конечно.
Только не Java vs Pascal и уж тем более не Java vs Python и Java vs Objective Caml.

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

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

Подвиг 1984-1987 годов Tom DeMarco with Tim Lister ("Software Development: State of the Art vs State of the Practice") повторить не удалось, но разлёт - налицо.
Сразу вспоминается vitaly_b и Движок За Миллион (tm).

Страшно.

Comments

[justy-tylor.livejournal.com]

По памяти, с битовым следом оно примерно так (проверять влом):

bool maskcmp(const char* mask, const char* str, uint32* temp, uint32 l, int i)
{
  while(*mask && *str)
  {
    if(*mask=='?' || *mask==*str)
    {
      ++mask;
      ++str;
      ++i;
      continue;
    }
    if(*mask=='*')
    {
      const char* t = str;
      int j = i;
      for(; *t; ++t, ++j)
      {
        if(temp[j]&l)
          return false;
        if(maskcmp(mask+1, t, temp, l<<1, j))
          return true;
        temp[j] |= l;
      }
      return false;
    }
    return false;
  }
  return !*mask && !*str;
}

[aruslan.livejournal.com]

Ага, я такое где-то видел.
То есть обычная рекурсия + битовый след для как ограниченная память.

Впрочем, всё равно по экспоненте пойдёт, нет? ;)

[justy-tylor.livejournal.com]

То, что я привёл выше - вообще не обязательно работает, потому что после "первого дня на роликах" совершенно не хочется переключаться на "некрасивые" задачи и включать мозг. :)

В рабочем варианте - худшим вариантом (для особо дурных сочетаний маска-строка) было O(m*n), где m - длина маски, а n - длина строки. Либо экспонента, но вроде таки нет, хотя вспоминается сейчас плохо.