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

[bandures.livejournal.com]

Глупое сравнение. Java для маленьких задач неудобен, это и так известно.

[aruslan.livejournal.com]

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

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

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

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

Но почему тогда (негениальным) студентам платят >1,500 USD в бизнес-проектах?..

[glebedev.livejournal.com]

можешь глянуть, я там в c-style отстрелялся на шарпе. наверняка куча ошибок, но все тесты проходит. исходник в оригинальном треде.

[aruslan.livejournal.com]

А отчего ты не захотел рекурсивной классики, если не секрет?
Вот типа как Пушыстый напейсал (правда у него на одну строчку больше чем нужно) или как Objective Caml или, не побоюсь этого слова, как Python?

[glebedev.livejournal.com]

Ну типа по-честному решал %)

[bandures.livejournal.com]

Если они работу выполняют, почему бы и не платить ?

[aruslan.livejournal.com]

Потому что их требуется загнать в жёсткие формализованные рамки.
Чтобы "работа" была "выполнена".

А там, где рамки - там всегда потеря правильных opportunities.
То есть вместе с люлькой и т.д.

В сумме пока получается таки дешевле иметь нормальных специалистов плюс вменяемых учеников.

[bandures.livejournal.com]

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

[aruslan.livejournal.com]

Вот именно в игровых проектах меня серость и пугает...

[copperfeet.livejournal.com]

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

[ilya666.livejournal.com]

1500 это много или мало?

Индусы, блин.

[http://users.livejournal.com/_winnie/]

bool match(const char *word, char const *pattern)
{
    if (!*pattern) return !*word;
    if (*word == *pattern || *pattern == '?') return match(word+1, pattern+1);
    if (*pattern != '*') return false;
    while (*word)  if (match(word++, pattern+1)) return true;
    return match(word, pattern+1);
}

Re: Индусы, блин.

[aruslan.livejournal.com]

Ну, стандартное (читай - классическое) рекурсивное решение выглядит несколько иначе ;)

Re: Индусы, блин.

[http://users.livejournal.com/_winnie/]

в каком смысле?

Re: Индусы, блин.

[aruslan.livejournal.com]

Тебе ответили в твоей ветке ;)

[ex-alexeych.livejournal.com]

Хм. Некий студен прифигевает от того как круто он написал некий треш всего в n строк? И в чём собстно поинт?

Не сочтите меня снобом и занудой, но попробую сказануть своё мнение.

Во-первых, я дико несогласен с приведённой в начале цитатой 'неизвестного'. А также возгласами аля про пушки и воробьёв. Поинт в том что OO-языки эффективны толко при активно переиспользовании кода и расширяемой в смысле OO и OCP архитектуры. Иначе, это как дрова бензопилой колоть. А построить аппликацию в таком 'правильном' ракурсе - это вам не кубики катать, этому учиться надо.

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

P.S.
Понравился вариант пушистого. Стильно и мощно ;)

[aruslan.livejournal.com]

Алексей, я ж не о сравнении языков, не поймите меня правильно.
Мне прёт от реакции народа (и даже в этой ветке ;) ).
И от того, насколько ж чёрт возьми разнятся мозги.
Я ж сделал ссылку на TDM+TL, неужто не очевидно, что меня заинтересовало?

А вариант Пушыстого - это самый мощный вариант, как и варианты на Python и Objective Caml.
У него есть маааленькая проблемка (скорость), но именно его я ждал от кандидатов как наиболее простого и буквального, когда давал на собеседовании именно этот алгоритмический вопрос.

[ex-alexeych.livejournal.com]

>Алексей, я ж не о сравнении языков, не поймите меня правильно...
По первых строках письма... вобщем я пока ещё в единственм числе.

Оторвавшись от студии, я действительно не подумал о чём это ты ;) Я просто прочитал исходный топик о сравнении язков и выразил своё имхо именно на эту тему.

Да, а о чём ты, кстати? Постой, попробую догадаться.
Неужели ты о подходе к решению проблем? К ограниченности в выборе исполниетелями или о стоимости последствий таких решений. Может быть о непонимании того, что язык лишь узкий ящик в который приходться втискивать свои идеи, но не то что создаёт тру вэй решения задачи? Что опять не угадал? Нда, вот блин какой я недогадливый ;) ничего, что бы не было бы известно и банально, придумать не могу. ;)) Но, последняя попытка, может быть просто для фану?

>Я ж сделал ссылку на TDM+TL, неужто не очевидно, что меня заинтересовало?
Не поверишь ;) я это не читал.

З.Ы.
Никогда не мог понять, в чём сложность рекурсии и композиции чистых функций. Это же лишь вариант абстракции. Способ формализации задачи.

[aruslan.livejournal.com]

Лёш, али я тебя обидел чем? :)

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

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

> Никогда не мог понять, в чём сложность рекурсии и композиции чистых функций.
Вот и я этого не могу понять.
И при чём тут прокрустово ложе языка - тоже.
И почему на простую задачку пишется треш в N строк - тоже...

P.S. http://portal.acm.org/citation.cfm?id=74625&dl=ACM&coll=portal

[ex-alexeych.livejournal.com]

>Лёш, али я тебя обидел чем? :)

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

>Но когда от этого данного конкретного программиста в конечном итоге будет зависеть качество конечного продукта...

Как там Морфиус говорил? - Добро пожаловать в реальный мир...
Матрица имеет нас, Руслан. ;) Тем интереснее становиться жить. Организовать эту разношёрстую компанию ЛыцАрей клавиатуры и направить по нужному тебе путь, задача посерёзнее чем забабахать крутой алгоритм.