Delphi Challenge: Первые протесты участников

← →
Style (2003-05-30 08:56) [0]

http://www.delphichallenge.ru
Не успели мы выложить оценки судейства по 1-вым двум заданиям как Sandman25 прислал свой протест!
В общем страсти накаляются.. Смотрите инфу на сайте!

По итогам первого тура будем извелакать уроки и лишь тогда начнем второй тур!

← →
Palladin (2003-05-30 09:34) [1]

Ребята, вы чего там устроили, при чем тут cpp?
Вы бы еще морковь и желуди сравнили бы...
непонимаю, это delphi или винегрет?

← →
Style (2003-05-30 09:43) [2]

Ну человек прислал решения на CPP почему бы и нет.. :)

Тем более если алгоритм не правильный то на CPP ты пишешь или на Delphi разницы нет :)

← →
Palladin (2003-05-30 09:52) [3]

я бы даже и delphi туда не вводил, чистый паскаль и ничего более..
а решения на других ЯП рассматривал в отдельной категории...

← →
Sandman25 (2003-05-30 10:36) [4]

Я подозреваю, что при компиляции Delphi программ не был убран флажок Range Checking из настроек компилятора. В результате происходили ненужные проверки на правильность индексов массива, отсутствующие на C.

← →
Доброжелатель (2003-05-30 10:41) [5]

Вообще, если такие мероприятия проводятся, то тестироваться все должно на одной системе, на одной программе. Для всех - одинаковые условия. А тот, кто писал на cpp, мог бы и в Delphi переложить, раз уж он так крут...

← →
Style (2003-05-30 10:48) [6]

Sandman25 ©>> Ответ судейства не получили??

Результаты еще не зафиксированы.. т.е. вы еще можете поспорить

← →
Sha (2003-05-30 10:51) [7]

Sandman25 © (30.05.03 10:36)
Скорее всего.

← →
han_malign (2003-05-30 10:57) [8]

http://www. delphi challenge.ru
- уже конкретно обозначает среду, и это документ, пресекающий любые споры насчет CPP! К тому-же чужих исходников на CPP, в сети, на порядок больше, чем на OP....

← →
Sha (2003-05-30 11:00) [9]

Sandman25 © (30.05.03 10:36)
Кроме того, т.к. различие в скорости составляет несколько процентов, оно вполне может объясняться различным выравниванием кода. Вряд ли уважаемому судейству хватило времени тестировать работу процедур всех участников при 32 различных вариантах выравнивания основного цикла.

← →
Style (2003-05-30 11:02) [10]

Т.е. вы предлагаете не принимать решения на C++

Наверное если будут решения на C++ то проводить отдельный конкурс.. Или если такое одно то просто его опубликовать..

← →
Sha (2003-05-30 11:07) [11]

Принимать при наличии штатного переводчика :). А пока такая должность вакантна, обязать переводить на OP самих участников.

При небольшом различии в скорости либо присуждать одинаковое место, либо тестировать детальнее, см. Sha © (30.05.03 11:00)

← →
Sandman25 (2003-05-30 11:14) [12]

2 Style
Нет, ответа не получал. Я вчера послал еще одну аппеляцию - по поводу второго задания. Возможно, она тоже потерялась. А сегодня послал вот такой вариант второго задания.
function Middle(const Data: array of word): Extended; var i: integer; AllElemCount: integer; Arr: array of word; begin SetLength(Arr, High(word)); ZeroMemory(@Arr[0], SizeOf(Word)*(High(Word)+1)); for i := High(Data) downto 0 do inc(Arr[Data[i]]); Result := 0; AllElemCount := 0; for i := High(Arr) downto 0 do if Arr[i] in [3..5] then begin AllElemCount := AllElemCount + Arr[i]; Result := Result + Arr[i] * i; end; if AllElemCount <> 0 then Result := Result / AllElemCount; end;
Работает быстрее Quicksort, памяти требует меньше, чем Quicksort требует для копии массива. Ну а то, что тип элементов изменился на Word, никто и не заметит :)

2 Sha
Спасибо за поддержку.

← →
Sandman25 (2003-05-30 11:27) [13]

2Style
Почту получил. Я не ожидал, что Вы мне ответите на другой адрес.

← →
Style (2003-05-30 11:47) [14]

Смотри все письма в новостях!

← →
Mystic (2003-05-30 12:30) [15]

По поводу вопроса насчет C++, то исходный код был переведен мною на Delphi.

> Sandman25 © (30.05.03 11:14)

Тесты заметят :) При генерации тестовых данных встречаются значения, превышающие 65535.

← →
Sandman25 (2003-05-30 12:45) [16]

Mystic

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

← →
Anatoly Podgoretsky (2003-05-30 13:37) [17]

А вот это лишнее, не надо указывать наборы, надо указывать ограничения на данные. Известная ошибка подгонка под тестовую задачу, иногда и тестовые задачи подгоняются под нужный результат, если надо доказать, что какой то продукт лучше.

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

Sandman25 © (30.05.03 12:45)
Ну а что говорить о приведенном тобой решении, его следует отнести к неработающим, Mystic © (30.05.03 12:30) указал причину. В условии указан тип данных const Data: array of Integer

← →
han_malign (2003-05-30 13:51) [18]

> const Data: array of Integer
>Sandman25 ©
- а массив на 4Гб, до выхода 64-битных Windows - увы и ах..., да и просто сканирование 4...(сколько там) значений довольно длительная операция...

← →
Sandman25 (2003-05-30 14:42) [19]

Anatoly Podgoretsky © (30.05.03 13:37)

Ограничения на данные указаны не были.
И кто сказал, что писать надо на Delphi6? Может у меня версия Object Pascal, на которой Integer является Signed 16-bit и может принимать значения -32768..32767. Вон в хелпе Delphi3 об этом написано. Тогда я смело могу заменить word на integer, и после небольшой модификации данная версия будет работать.

han_malign © (30.05.03 13:51)
Так и я о том же. Я совершенно наивно полагал, что тестироваться будут небольшие массивы, а оказывается речь шла о массивах из сотен тысяч элементов. Тогда давайте уже протестируем еще бОльший массив, чтобы при копировании массива происходила ошибка памяти или свопинг на диск. Тогда и временнОе ранжирование решений будет совсем другое.

← →
Anatoly Podgoretsky (2003-05-30 14:56) [20]

han_malign © (30.05.03 13:51)
Ты не прав, это больше 4 gb * 4 (-MaxInt..Maxint) * SizeOf(Integer)

Sandman25 © (30.05.03 14:42)
Версии компилятора, на которых будет тестироваться указать надо и также опции компиляции - естественно надо указать, иначе будут получаться разные данные, а вот набор данных, который будет использоваться для тестирования указываться не должен, во избежание подсройки под данные, функциЯ должна работать на любых размерах массива. Более того надо протестировать как минимум на трех разных массивах, разных по размеру, например: 1000, 10000, 100000 и 1000000 элементов, тогда будут видны недостатки алгоритма. Для исключения влияния дисков, массив должен предварительно располагаться в оперативной памяти - 4 мегабайта это же не много. Цель тестирования не измерение производительности дисковой подсистемы, а алгоритма.

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

← →
Sandman25 (2003-05-30 15:14) [21]

Anatoly Podgoretsky © (30.05.03 14:56)

>1000, 10000, 100000 и 1000000 элементов

Причем предлагаю начать с 100 или даже с 10.

>Я бы посоветовал авторам {...} сказать, что тестирование будет проводиться на таких то таких массивах

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

Насчет компиляторов. Существует ли опасность, что участник заоптимизирует свою программу под какую-то конкретную версию компилятора, которой не окажется у членов жюри? Я подозреваю, что все компиляторы даже в пределах "семьи" (скажем D3 или D6) не совсем одинаковы.

← →
Style (2003-05-30 15:40) [22]

Я думаю что участник должен писать алгоритм при default настройках... Что никому не было обидно.

← →
Style (2003-05-30 15:40) [23]

Да и писал ту версию Делфи на которой собственно его и делал!

← →
Sha (2003-05-30 20:29) [24]

Чтобы положить конец спорам.
Я оптимизировал вариант программы, предложенный Sandman25 вплоть до ассемблерных инструкций, изменив порядок просмотра элементов тестового массива. По идее, если дело в алгоритме, то он должен бить оба варианта (и Sandman25, и Dmitro). Однако на на различных тестовых данных побеждает любой их этих трех вариантов программы примерно с одинаковой вероятностью. Так что все эти три решения равноценны.

procedure Solution_2(const Data: array of Integer; var Min, Max: Integer); var pFirst, pTest, pFind: pinteger; MyMin, MyMax, Test: integer; label Start, MainLoop, Small, SmallLoop, Big, BigLoop, Done; begin; MyMin:=High(integer); MyMax:=Low(integer); pFirst:=@Data[0]; pTest:=@Data[High(Data)]; goto Start; Small: pFind:=pFirst; SmallLoop: if pFind^<>Test then begin; inc(pFind); goto SmallLoop; end; if pchar(pFind)<>pchar(pTest) then MyMin:=Test; MainLoop: dec(pTest); Start: if pTest=pFirst then goto Done; Test:=pTest^; if Test<MyMin then goto Small; if Test<=MyMax then goto MainLoop; Big: pFind:=pFirst; BigLoop: if pFind^<>Test then begin; inc(pFind); goto BigLoop; end; if pchar(pFind)<>pchar(pTest) then MyMax:=Test; goto MainLoop; Done: if MyMax<MyMin then raise Exception.Create("Повторяющихся элементов нет!"); Min:=MyMin; Max:=MyMax; end;

← →
panov (2003-05-30 21:21) [25]

Предлагаю остановиться на таких вариантах:
1. Принимается только код на Object Pascal(Естественно, без всяких вставок на ассемблере).
2. Код должен выполняться на Delphi5 и независимо от настроек компилятора.
3. Как тестировать, должно принимать решение жюри(каждый в отдельности).
4. Если условия задания не выполнены, поправки и исправления не принимаются.

← →
Sha (2003-05-31 14:12) [26]

2panov © (30.05.03 21:21)
Может быть, я не совсем ясно выразился...
procedure Solution_2 из моего предыдущего поста - это оптимизированный вариант Sandman25. Его паскальные инструкции транслируются на асм 1 в 1. По идее он должен быть пободителем. Но этого не происходит, т.к. все три варинта решения, по сути одинаковые, по-разному сканируют исходный массив. В результате победитель зависит от исходных данных. На разных массивах длиной 1000000 элементов, сгенерированных GenData, у меня 2 раза победил Dmitro, 3 раза - Sandman25, 4 раза - Sandman25 (опт).

← →
Anatoly Podgoretsky (2003-05-31 15:59) [27]

Оставь это дело жюри.

← →
Sha (2003-05-31 19:51) [28]

Наше дело - дать информацию для размышления жюри, на большее не претендуем :)

← →
Style (2003-06-02 07:42) [29]

← →
panov (2003-06-02 11:43) [30]

>Style © (02.06.03 07:42)

Вообще конечно заранее лучше оговорить какой будет компилятор.

В смысле, имеется ввиду компилятор в Delphi, в котором будет компилироваться программа?

← →
Style (2003-06-02 12:12) [31]

← →
panov (2003-06-02 12:30) [32]

Style © (02.06.03 12:12)

Когда я говорил про D5, я имел ввиду набор реализованных стандартно функций в определенной версии Delphi.

Хочу еще сказать по заданиям.

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

Поэтому хотелось бы видеть задачи не толтько на "чистую математику", но и задания на реализацию различных готовых алгоритмов.

← →
Anatoly Podgoretsky (2003-06-02 12:36) [33]

Наверно, достаточная мощность, в особых случаях стоит оговаривать, но как бы не было, компиляция должна вестись на одном и том же компьютере с проверкой параметров, не должны использоваться .opt/.cfg файлы или прямое прописывание ключей в проекте. Даже сам проект не должен использоваться, только голый модуль, что обеспечит одинаковость для всех участников. Модуль должен содержать одну единственную функцию в интерфейсной части, польностью совпадающую с прототипом задания.
Если участник желает выйти за эти рамки, то он должен обосновать это отдельно. Тестирование ведется же алгоритмов и красоты коды, а не работы дисковой подсистемы, ОС и прочего.
Зато надо бцдет четко в задании описывать входные/выходные параметры, что бы был чистый черный ящик.

← →
Sha (2003-06-02 12:51) [34]

← →
Anatoly Podgoretsky (2003-06-02 12:59) [35]

Не знаю, это ведомо создателям ресурса. Я же говорю про одинаковые условия и уменьшения протестов, про прозрачность задания.

← →
Style (2003-06-02 13:23) [36]

Mystic тестировал у себя. Но я еще прогоню на всякий случай тест на своей машине.. Потому что результаты действительно могут быть разными...

2 Panov: Я тогда просто не представляю как задания будут выглядеть. У меня есть письма заданий на второй тур, но опять же в большинстве они все алгоритмические. Интересно было бы просто посмотреть..

И еще Mystic говорит что заданий слижком много для одного тура.. Как вы думаете какое же должно быть их кол-во??

← →
Style (2003-06-02 13:24) [37]

← →
Sha (2003-06-02 13:52) [38]

2Style © (02.06.03 13:23)

Тестирование скорости работы алгоритмов - главная проблема. Очень уж хочется сравнивать эффективность. Но тут имеется не один подводный камень. Вот только те, что были в первом туре:
Скорость работы алгоритмов, связанных с сортировкой, в значительной мере зависит от входных данных. Практически для любого алгоритма можно подобрать неудобные данные, на которых он будет менее эффективен. Область применения алгоритма и способ тестирования тоже стоит оговаривать, участники обязаны это знать.
Даже в переборных задачах скорость решения невозможно определить однозначно. Например, скорость работы моего решения задания №6, где много мелких циклов и передач управления, можно изменять в значительных пределах (более, чем 30%), изменяя выравнивание кода вставкой NOP"ов.
Что такое скорость в задачах поиска пути? Не представляю, как жюри будет оценивать скорость работы решений задания №7. Там все известные алгоритмы, показывают примерно одинаковое время при работе без откатов, но при наличии откатов времена будут отличаться на порядки. Проблема состоит в том, что откаты у различных алгоритмов возникают на разных досках, разное количество раз, их глубина задается параметрически и т.д.
Наверное надо в конце каждого задания писать, что именно будет оценивать жюри в данном задании, и кратко описать методику оценки или дать ссылку.

Насчет количества Mystic прав. По-моему трех-четырех (но качественных) заданий различной сложности достаточно. Интересные задания попадаются редко, много неинтересных не заменят одно интересное. Да и свободного времени не так много. Лето опять же...

← →
Style (2003-06-02 14:10) [39]

Sha ©>> Приведите пожалуйста пример того кода которым вы генерили данный для массива и соответсвенно тестувую программу.
Просто интересно сравнить..

← →
Style (2003-06-02 14:16) [40]

2 Panov: Вы не могли бы протестировать решения 4 или 5 задачи что бы как можно быстрее опубликовать результаты.. Я думаю все результат оформлять по схеме Mystic... Можете внести что-нибудь свое.. В любом случае это 1-й тур.. И что из этого всего выдет будем смотреть..

2Sha Ну чета пока не чувствуется лето.. такой дождина..
А летом мозги развивать тоже не повредить. Тем более DelphiChallenge это не значит что ты должен неделю сидеть за компом.. Это просто соревнования для желающих.. Лишний повод пообщаться и порассуждать!

Delphi Challenge: Первые протесты участников Найти похожие ветки