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]

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

Обычный алгоритм был откинут из-за дороговизны *, но в сознании было что-то про оптимизацию регэкспов через битовый след, так что было сделано именно так, не более тридцати двух *, но без повышения вычислительной сложности. Около 30 грязных строк на C++ (на экран помещалось всё), часа 3 с отладкой, наверное... Вот только что забавно - алгоритм писался на C++, а в голове была какая-то страшная смесь функциональщины и ассемблера.

[aruslan.livejournal.com]

Ну, есть еще такой вариант ((ц) dxsky):

  template<typename T>
  inline bool mask_compare( const T* mask, const T* s )
  {
    const T *cp=0, *mp=0;
    for (; *s&&*mask!='*'; mask++,s++) 
      if (*mask!=*s&&*mask!='?') 
        return false;
    for (;;) {
      if (!*s) { while (*mask=='*') mask++; return !*mask; }
      if (*mask=='*') { 
        if (!*++mask) return true; 
        mp=mask; cp=s+1; continue; 
      }
      if (*mask==*s||*mask=='?') { mask++, s++; continue; }
      mask=mp; s=cp++;
    }
  }

[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 - длина строки. Либо экспонента, но вроде таки нет, хотя вспоминается сейчас плохо.