2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Задача по ссылке от Munin
Сообщение28.02.2013, 23:55 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Да, видимо во входном файле есть перевод строки в конце. Просто обрабатывайте '\n' так же, как пробел

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение01.03.2013, 00:04 


05/09/12
2587
Спасибо, наконец-то он прожевал мой код :-) Просто я не подозревал что в корректной входной строке будут ещё '\r' и '\n'....

ЗЫ странно, по времени победил лидера, а по памяти нет.... Сейчас ещё уберу лишний массив...
Не помогло :-) Вообще интересно, как он считает используемую память?
Скачал код лидера (фактически он на С, там навскиду никаких С++ особенностей не встречается) - взглянул пару секунд и закрыл - такая лаконичность и красота (по первому впечатлению), что не хотел разбираться в нем раньше того, как сам ещё подумаю над оптимальным алгоритмом :-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение01.03.2013, 04:41 


05/09/12
2587
После нескольких безуспешных попыток улучшить количественные оценки кода - скорость и память, возникают вопросы: а как они, собственно, считаются?

Время выполнения - я понимаю как количество тактов процессора при данной частоте. На каждую операцию однозначное количество тактов (в EEPROM не пишем). Судя по АВР отладчику я заметно уменьшил такты, а время не изменилось.

Память - вообще непонятно. Какая память считается? Флеш где лежит сам код, его объем? Или использование ОЗУ + стек? Я в последней редакции максимально ужался - использую всего один массив 158 байт (при этом корректно обрабатывается максимальная входная строка в 80 символов!) и несколько переменных, никаких рекурсий и нарастания стека. У меня этот алгоритм влезет со свистом в самый маленький по ОЗУ микроконтроллер. Откуда взялась цифра 214 Кб?

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

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение01.03.2013, 07:37 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота
_Ivana в сообщении #689384 писал(а):
После нескольких безуспешных попыток улучшить количественные оценки кода - скорость и память, возникают вопросы: а как они, собственно, считаются?
Я думаю, этот вопрос надо владельцу/админу сайта задавать, вряд ли кто-то здесь ответит.
Я, кстати, тоже пытался сдать свою задачу (только другую, про палиндромы, и на паскале), у меня на компе все работает, а там - нет. Плюнул и пошел спать.

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение01.03.2013, 08:29 


05/09/12
2587

(Оффтоп)

Админу сайта я написал, но что-то подсказывает мне что я могу не дождаться ответа и тем более каких то комментариев. Я думал просто обсудить этот момент, а еще может вдруг у кого есть возможность как-нибудь протестировать код на скорость\память, я бы дал свой и тот который скачал оттуда, получили бы более адекватные цифры... Хотя, кому это надо?... Просто если мотивация опередить другие алгоритмы, соревновательный момент, зарубается вот так на корню из-за непонятной и сомнительной системы распределения мест, то пропадает всякое желание и энтузиазм. Буду соревноваться в других областях - в скоростном беге на коньках, например :-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение01.03.2013, 09:33 
Заслуженный участник


06/07/11
5627
кран.набрать.грамота

(Оффтоп)

_Ivana в сообщении #689406 писал(а):
Буду соревноваться в других областях - в скоростном беге на коньках, например :-)
Я в прошлые выходные участвовал в альпинистском двоеборье - лыжная гонка 15 км и скалолазание. Я вам так скажу: если хотите побеждать - лучше программируйте...

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение01.03.2013, 15:08 


05/09/12
2587
Задача про максимальный палиндром имхо вообще для школьников. Непонятно, за что там давать 15 баллов, когда за сабжевую задачу топика дают 10. Вот мой код, который работает на http://liveworkspace.org и по традиции не работает на сайте с задачами :-) Конечно, для гарантии хорошо быть вставить пару проверок - невыходы за границы массива.
код: [ скачать ] [ спрятать ]
Используется синтаксис C++
#include <iostream>

int main(void)
{
   char in_str[100001];
        int len=0, max_len=0;
        char *p_in, *p_l, *p_r, *p_res;
       
        std::cin >> in_str;
        p_in = in_str; p_res = in_str;
        while (*p_in) {
                p_l = p_in; p_r = p_in + 1; len = 0;
                while (*p_l-- == *p_r++) {len++;} len = len<<1;
                if (len > max_len) {max_len = len; p_res = p_l+2;}

                p_l = p_in - 1; p_r = p_in + 1; len = 0;
                while (*p_l-- == *p_r++) {len++;} len = (len<<1)+1;
                if (len > max_len) {max_len = len; p_res = p_l+2;}

                p_in++;
        };     
        for (len=0;len<max_len;len++) {std::cout << *p_res++;}
   
   return 0;
}
 
Но я пока не планирую глубоко разбираться в С++ и особенностях класса string, а на С там компилятора нет, поэтому придется или искать другой сайт подобного рода, который принимает С код, или обувать таки коньки :lol: Если только вдруг Munin не даст задачку с аналогичного С-шного сайта :-)

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение01.03.2013, 23:56 


05/09/12
2587
Вести с полей :-)
Путем насилия упомянутого сайта удалось выяснить:
- время выполнения включает время ввода-вывода и зависит от организации и библиотеки последнего.
- количество Кб памяти - объем слинкованного файла вместе с подгружаемыми библиотеками.
- можно использовать тамошний С++ компилятор, но подсовывать ему чистый С код, со своей библиотекой stdio - это уменьшает объем, но увеличивает время.
- на ОЗУ и время выполнения к каждой задаче даются свои ограничения (выше условия), но они там имхо более чем щедрые - например, зря я уложился в 200 Байт - мог бы использовать все
Цитата:
Ограничение памяти: 65536КБ
- это никак не влияет на ранжирование результата :lol:

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение02.03.2013, 13:50 


05/09/12
2587

(Оффтоп)

Провел тест - специально сделал ошибку в тексте скачанной программы лидера (только не приводящую к ошибке компиляции, а только к неправильному ответу) - и отправил его от своего имени на сайт :-) Казалось бы, зачем? У меня возникли сомнения, и я их подтвердил. Код с ошибочным результатом не помещается в список решений, зато помимо сообщения об ошибке выдается и время выполнения и размер файла. Так вот, сейчас код лидера имеет показатели: время 0.0014 сек, память 218 КБ. А на момент когда этот код занял первое место (01.03.2011), было: 0.0016 сек / 122 КБ. В коде стоит
Код:
#include <iostream>
#include <string>
Я полагаю, что с того времени обновилась и существенно выросла одна или обе библиотеки и немножко убыстрилось железо сервера. Получается, что если сейчас использовать стандартные библиотеки, то нереально превзойти лидера в принципе. Кстати, лучший мой код имеет показатели 0.0013 сек / 214 КБ (видно на странице статистики по задаче), и капельку, но превосходит настоящие (на текущий момент) лидерские.

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

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение02.03.2013, 13:55 
Заслуженный участник
Аватара пользователя


30/01/06
72407

(Оффтоп)

Можете написать всё это админу...

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение02.03.2013, 14:18 


05/09/12
2587

(Оффтоп)

Админ или не получает или игнорирует мои письма, так что пусть и дальше пребывает в благоденствии. Если будет интерес, я сделаю себе короткую библиотеку ввода/вывода и пошлю с ней. И вообще, раз тема про алгоритмы - я придумал алгоритм потеснения лидера:
1) пишем любое, самое неоптимальное, но верное решение задачи
2) отправляем его, получаем возможность скачать код лидера
3) перерабатываем его немного, чтобы не выглядел плагиатом, и отправляем с короткими и быстрыми процедурами ввода/вывода - получаем код меньше и быстрее лидерского

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение03.03.2013, 14:11 
Заслуженный участник


28/04/09
1933
Xaositect
Xaositect в сообщении #688915 писал(а):
У EtCetera какой-то из диалектов пролога. Сначала классифицируем все символы на скобки, идендификаторы и операторы, потом для списка таких токенов строим синтаксическое дерево (задаваемое типом Operation). Для этого рассматриваем список слева направо как последовательность, разделенную операторами малого приоритета (+-), каждый элемент этой последовательности как последовательность, разделенную операторами */, а на нижнем уровне операнд - либо идентификатор, либо аналогичное выражение в скобках.
Удивительно точное описание!
Остается только добавить, что используемый вариант пролога $\text{---}$ Visual Prolog (для компиляции применялась одноименная среда старенькой, кажется, 5-ой, версии).

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение03.03.2013, 14:17 


05/09/12
2587
Меня Xaositect в этой теме вообще поражает способностью быстро и точно разбираться в чужих кодах на самых разнообразных языках :shock:

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение03.03.2013, 19:35 
Заслуженный участник


11/05/08
32166
Такой тупой-тупой вариант. Конечно, никто так не пишет, это даже и неприлично, тем не менее: безо всяких деревьев и рекурсий. Ловля ошибок -- неполная: допускает записи типа A*B(+C), интерпретируя их как A*(B+C).

код: [ скачать ] [ спрятать ]
Используется синтаксис Pascal
var  prg: string;                        { Исходое выражение            }
     wrk: string;                        { Поток накопленных фрагментов }
     af:  array[#128..#255] of byte;     { Адреса фрагментов в потоке   }
     lastc:  char;                       { Код последнего фрагмента     }
     lev: string;                        { Уровни вложенности           }

{-------------------------------------------------------------------}
procedure stop(i: integer);
begin    writeln('!!!  Error  ', i, '  !!!');    readln;    Halt;    end;
{-------------------------------------------------------------------}
{-------------------------------------------------------------------}
function getfrg(c: char): string;
{ Извлекает из потока  wrk  фрагмент с кодом  c }
var  i,k: integer;
begin
  i:=af[c];                      k:=ord(wrk[i]);
  getfrg:=Copy(wrk, i+1, k);     Delete(wrk, i, k+1);
  for c:=#128 to #255 do
    if af[c]>i  then dec(af[c], k+1);
end;
{-------------------------------------------------------------------}
procedure insfrg(frg: string);
{ Добавляет в конец потока  prg  фрагмент  frg  с кодом  lastc+1 }
var  i: integer;
begin
  inc(lastc);    af[lastc]:=length(wrk)+1;
  wrk:=wrk + frg[0] + frg;
  end;
{-------------------------------------------------------------------}
function findop(currlev: integer; op: char): boolean;
{ Находит на текущем уровне первую операцию с приоритетом op ('*' / '+') }
{ Заносит в поток  wrk  фрагмент выходного кода для этой операции        }
{ Удаляет из потока фрагмент, на которые ссылались операнды              }
{ Заменяет в исходной  prg  операцию с операндами на код её фрагмента    }
var  i: integer;    s1,s2: string;     c: char;
begin
  findop:=false;
  for i:=1 to length(prg) do begin
    if currlev<>ord(lev[i]) then continue;
    c:=prg[i];
    if (op='*') and (c<>'*') and (c<>'/')  then continue;
    if (op='+') and (c<>'+') and (c<>'-')  then continue;
    if (i=1) or (i=length(prg)) then stop(2);
    if prg[i-1] in ['a'..'z', 'A'..'Z']   then s1:=prg[i-1]
      else if prg[i-1]>=#128   then s1:=getfrg(prg[i-1])
      else stop(2);
    if prg[i+1] in ['a'..'z', 'A'..'Z']   then s2:=prg[i+1]
      else if prg[i+1]>=#128   then s2:=getfrg(prg[i+1])
      else stop(2);
    s2:='(' + s1 + ',' + s2 + ')';
    case c of
      '*':  s1:='MUL';     '/':  s1:='DIV';
      '+':  s1:='ADD';     '-':  s1:='SUB';
      else;   end;
    insfrg(s1 + s2);
    Delete(prg, i, 2);    prg[i-1]:=lastc;
    Delete(lev, i, 2);
    findop:=true;    break;
  end;
end;
{-------------------------------------------------------------------}

var  inp,out: string;
     i,k: integer;
     maxlev: integer;

begin

  inp:='y-(a*s/t-(h+A/f*r/c))*((((b-m))))';

  {---------- Определяем уровни вложенности: ----------}
  k:=0;        maxlev:=0;
  prg:=inp;    lev:=inp;
  for i:=1 to length(prg) do begin
    if prg[i]='(' then inc(k);
    if prg[i]=')' then dec(k);
    if k<0 then stop(1);
    if maxlev<k then maxlev:=k;
    lev[i]:=char(k);
  end;
  {---------- Удаляем скобки - они больше не нужны: ----------}
  i:=1;
  while i<=length(prg) do
    if (prg[i]='(') or (prg[i]=')')
      then begin    Delete(prg, i, 1);    Delete(lev, i, 1);    end
      else inc(i);
  {---------- Собственно парсинг: }
  lastc:=#127;
  wrk:='';
  for k:=maxlev downto 0 do begin
    while findop(k, '*') do;
    while findop(k, '+') do;
  end;
  if prg<>lastc then stop(3);
  out:=getfrg(lastc);

  writeln(#177, inp, #177);
  writeln(#177, out, #177);
  readln;
end.

 

 Профиль  
                  
 
 Re: Задача по ссылке от Munin
Сообщение03.03.2013, 19:59 
Заблокирован
Аватара пользователя


07/08/06

3474
Это задача на знание "обратной польской записи", по-моему. По крайней мере, я бы решал только так :-)

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 89 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group