?

Log in

No account? Create an account
The Software Unfactory | Averages - II - Valse oubliée [entries|archive|friends|userinfo]
aruslan

[ userinfo | livejournal userinfo ]
[ archive | journal archive ]
[ delicious | aruslan's delicious ]

Links
[Links:| Tags Profile Friends FG1 PP gamedev XNA FF Entries Comments Memories ]

The Software Unfactory | Averages - II [May. 8th, 2006|08:01 pm]
aruslan
[Tags|]

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).

Страшно.
LinkReply

Comments:
[User Picture]From: justy_tylor
2006-05-08 04:49 pm (UTC)
Помнится, пару лет назад надо мне было поиск по маске в нашем редакторе прикрутить.

Обычный алгоритм был откинут из-за дороговизны *, но в сознании было что-то про оптимизацию регэкспов через битовый след, так что было сделано именно так, не более тридцати двух *, но без повышения вычислительной сложности. Около 30 грязных строк на C++ (на экран помещалось всё), часа 3 с отладкой, наверное... Вот только что забавно - алгоритм писался на C++, а в голове была какая-то страшная смесь функциональщины и ассемблера.
(Reply) (Thread)
[User Picture]From: aruslan
2006-05-08 05:08 pm (UTC)
Ну, есть еще такой вариант ((ц) 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++;
    }
  }

(Reply) (Parent) (Thread)
[User Picture]From: justy_tylor
2006-05-08 05:39 pm (UTC)
По памяти, с битовым следом оно примерно так (проверять влом):

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;
}

(Reply) (Parent) (Thread)
[User Picture]From: aruslan
2006-05-08 06:05 pm (UTC)
Ага, я такое где-то видел.
То есть обычная рекурсия + битовый след для как ограниченная память.

Впрочем, всё равно по экспоненте пойдёт, нет? ;)
(Reply) (Parent) (Thread)
[User Picture]From: justy_tylor
2006-05-08 07:24 pm (UTC)
То, что я привёл выше - вообще не обязательно работает, потому что после "первого дня на роликах" совершенно не хочется переключаться на "некрасивые" задачи и включать мозг. :)

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

(Reply) (Parent) (Thread)
[User Picture]From: bandures
2006-05-08 05:23 pm (UTC)
Глупое сравнение. Java для маленьких задач неудобен, это и так известно.
(Reply) (Thread)
[User Picture]From: aruslan
2006-05-08 05:38 pm (UTC)
Ну, я неуверен, что он удобен и для бОльших задач, но это имхо не по делу.
В данном случае меня намного больше заинтересовал "gap" между различными решениями.

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

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

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

Но почему тогда (негениальным) студентам платят >1,500 USD в бизнес-проектах?..
(Reply) (Parent) (Thread)
[User Picture]From: glebedev
2006-05-08 05:54 pm (UTC)
можешь глянуть, я там в c-style отстрелялся на шарпе. наверняка куча ошибок, но все тесты проходит. исходник в оригинальном треде.
(Reply) (Parent) (Thread)
[User Picture]From: aruslan
2006-05-08 06:03 pm (UTC)
А отчего ты не захотел рекурсивной классики, если не секрет?
Вот типа как Пушыстый напейсал (правда у него на одну строчку больше чем нужно) или как Objective Caml или, не побоюсь этого слова, как Python?
(Reply) (Parent) (Thread)
[User Picture]From: glebedev
2006-05-09 03:54 am (UTC)
Ну типа по-честному решал %)
(Reply) (Parent) (Thread)
[User Picture]From: bandures
2006-05-08 07:35 pm (UTC)
Если они работу выполняют, почему бы и не платить ?
(Reply) (Parent) (Thread)
[User Picture]From: aruslan
2006-05-08 08:11 pm (UTC)
Потому что их требуется загнать в жёсткие формализованные рамки.
Чтобы "работа" была "выполнена".

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

В сумме пока получается таки дешевле иметь нормальных специалистов плюс вменяемых учеников.
(Reply) (Parent) (Thread)
[User Picture]From: bandures
2006-05-08 08:57 pm (UTC)
Негениальные-студенты лишь увеличивают нагрузку на верхнее звено. В бизнес-проектах, где задания чётко формализованы, гениальность отдельно взятого программиста не требуется, за него подумает архитектор, а старший программист поставит задачу. Мало того, даже некоторые игровые конторы умудряются так работать ...
(Reply) (Parent) (Thread)
[User Picture]From: aruslan
2006-05-08 10:16 pm (UTC)
Вот именно в игровых проектах меня серость и пугает...
(Reply) (Parent) (Thread)
[User Picture]From: copperfeet
2006-05-18 09:32 am (UTC)
Судя по тексту, пацан немного знает паскаль и не шарит в java. Программист из него вообще нулевой. Короче - не показатель.
(Reply) (Parent) (Thread)
[User Picture]From: ilya666
2006-05-10 04:27 am (UTC)
1500 это много или мало?
(Reply) (Parent) (Thread)
[User Picture]From: _winnie
2006-05-08 05:25 pm (UTC)

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

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);
}
(Reply) (Thread)
[User Picture]From: aruslan
2006-05-08 05:39 pm (UTC)

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

Ну, стандартное (читай - классическое) рекурсивное решение выглядит несколько иначе ;)
(Reply) (Parent) (Thread)
[User Picture]From: _winnie
2006-05-08 08:38 pm (UTC)

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

в каком смысле?
(Reply) (Parent) (Thread)
[User Picture]From: aruslan
2006-05-09 02:48 pm (UTC)

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

Тебе ответили в твоей ветке ;)
(Reply) (Parent) (Thread)
From: ex_alexeych
2006-05-09 11:48 am (UTC)
Хм. Некий студен прифигевает от того как круто он написал некий треш всего в n строк? И в чём собстно поинт?

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

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

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

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

(Reply) (Thread)
[User Picture]From: aruslan
2006-05-09 01:07 pm (UTC)
Алексей, я ж не о сравнении языков, не поймите меня правильно.
Мне прёт от реакции народа (и даже в этой ветке ;) ).
И от того, насколько ж чёрт возьми разнятся мозги.
Я ж сделал ссылку на TDM+TL, неужто не очевидно, что меня заинтересовало?

А вариант Пушыстого - это самый мощный вариант, как и варианты на Python и Objective Caml.
У него есть маааленькая проблемка (скорость), но именно его я ждал от кандидатов как наиболее простого и буквального, когда давал на собеседовании именно этот алгоритмический вопрос.
(Reply) (Parent) (Thread)
From: ex_alexeych
2006-05-09 02:01 pm (UTC)
>Алексей, я ж не о сравнении языков, не поймите меня правильно...
По первых строках письма... вобщем я пока ещё в единственм числе.

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

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

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

З.Ы.
Никогда не мог понять, в чём сложность рекурсии и композиции чистых функций. Это же лишь вариант абстракции. Способ формализации задачи.
(Reply) (Parent) (Thread)
[User Picture]From: aruslan
2006-05-09 02:36 pm (UTC)
Лёш, али я тебя обидел чем? :)

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

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

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

P.S. http://portal.acm.org/citation.cfm?id=74625&dl=ACM&coll=portal
(Reply) (Parent) (Thread)
From: ex_alexeych
2006-05-09 03:50 pm (UTC)
>Лёш, али я тебя обидел чем? :)

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

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

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