LINUX.ORG.RU

Task 1


0

1

На тот случай, если заданий никто не даст, пишу, что придумал с утра( по большей части, чтоб не забыть, а также, чтоб учесть все недостатки ).

Пусть будет текстовый файл такого формата:

object A
{
	color = "red";
	value = 100!;
	circle;
}

object B : A, C
{
	color = "green";
	circle;
}

object C
{
	value = time();
	square;
}

object D
{
	color = "blue";
	value = 100 + A.value;
	value2 = C.value * value;
}

show circle;
show A.value;
show value > 100!;

думаю задача очевидна, но конечно же поподробней:

object A
{
	color = "red";
	value = 100!;
	circle;
}

это описание объекта( не типа, а именно объекта ), у него есть поля, которые бывают трех типов:

circle - признак, не имеет значения, просто означает, что A это круг

color = «red» - текстовое поле со значением «red»

value = 100!; - числовое поле( о нем будет дальше )

Смотрим дальше:

object B : A, C
{
	color = "green";
	circle;
}

это наследование, тут все просто - все поля из A, C теперь есть и в B, если есть одинаковые поля, то приоритетность - B, С, А( по убыванию ), т.е. у B color = «green», а value = time()

Про чиcловые поля - они задаются в виде выражений, допустимые операции +-*/ и !( факториал ), естественно присутствуют скобки (), в качестве операндов любые целые числа( в десятичной системе ), также time() ( то же, что и в С ) - чтоб разнообразить результаты на итерациях, а также любое числовое значение из этого/другого объекта( A.value etc. ), в случае рекурсии в выражениях - возвращать 0

Последняя часть:

show circle;
show A.value;
show value > 100!;

тут все просто - выводит на экран объекты удовлетворяющие условию или их свойства show circle - у которых есть поле circle show A.value - выводит значение любого выражения, например A.value + B.value * 2 show value > 100!; - состоит из «имя поля» + «операция сравнения» + «аргумент»( любое выражение ), ищет все объекты по условию

имена объектов и свойств состоят только из a..A, z..Z, 0..9, имена регистрозависимые

текстовые значения могут быть длинной до 65535 символов

П.С. наверняка что-то упустил так как пишу все с головы, жду критики, вопросов, уточнений условия и т.п.

П.П.С. хотелось бы, чтоб mv тоже попробовал после утверждения задания( если таки будет оно, а не другое ) решить его на Lisp( задание вроде под Lisp подходит ) - заодно и скорость работы программ можно будет сравнить

П.П.П.С. думаю полезно в текстовый файл добавить два параметра:

iterations = 100000

log = off

★★★★
Ответ на: комментарий от jtootf

> anyway, одного дня от текущего момента уж точно достаточно

значит завтра в 22.00( по ЛОР-му времени ) выкладываем архивы с решением и тестами

lester ★★★★
() автор топика

тестирование будет двух вариантов - парсер + отработка show и просто отработка show, итого в файле есть три вероятных ключа:

iterations = 100000; - кол-во итераций
log = on/off; - вкл./выкл. вывода результатов show на экран( чтоб получить чистое время )
test = all/show; - что будет тестироваться, то ли 100000 раз распарсить и сделать поиск, либо один раз распарсить и 100000 раз сделать поиск( вычислить выражение )

lester ★★★★
() автор топика

>это наследование, тут все просто - все поля из A, C теперь есть и в B, если есть одинаковые поля, то приоритетность - B, С, А( по убыванию ), т.е. у B color = "green", а value = time()

у B есть свойство circle, у C - square. это ошибочная ситуация, или объект может иметь более одного свойства?

jtootf ★★★★★
()
Ответ на: комментарий от jtootf

> у B есть свойство circle, у C - square. это ошибочная ситуация, или объект может иметь более одного свойства?

больше одного - просто неудачный пример

lester ★★★★
() автор топика

>имена объектов и свойств состоят только из a..A, z..Z, 0..9, имена регистрозависимые

набор свойств неограничен, т.е. свойство может иметь любое имя, удовлетворяющее этому условию?

jtootf ★★★★★
()
Ответ на: комментарий от jtootf

> набор свойств неограничен, т.е. свойство может иметь любое имя, удовлетворяющее этому условию?

первый символ не цифра, в остальном - любое, лишь бы не повторялись в рамках одного объекта

lester ★★★★
() автор топика
Ответ на: комментарий от lester

>> anyway, одного дня от текущего момента уж точно достаточно

>значит завтра в 22.00( по ЛОР-му времени ) выкладываем архивы с решением и тестами

Я завтра отдыхаю. Если на лиспе решения не будет, придется делать мне но в воскресенье. Лисп знаю более чем посредственно.

Absurd ★★★
()
Ответ на: комментарий от Absurd

>Я завтра отдыхаю

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

>Если на лиспе решения не будет, придется делать мне

будет крайне интересно посмотреть, кстати говоря

jtootf ★★★★★
()
Ответ на: комментарий от jtootf

> будет крайне интересно посмотреть, кстати говоря

Я уже написал. Правда не на лиспе, а на Ruby. Потестирую еще немного и выложу.

smh ★★★
()
Ответ на: комментарий от jtootf

>будет крайне интересно посмотреть, кстати говоря

Лисповый вариант будет. только вот посплю чуток и допишу.

Sectoid ★★★★★
()
Ответ на: комментарий от Sectoid

>Лисповый вариант будет. только вот посплю чуток и допишу.

вследствие желания сделать всё как положено (а не как обычно), я упёрся в странное поведение buildExpressionParser; в ожидании ответа от коллективного разума тоже потопал спать

jtootf ★★★★★
()
Ответ на: комментарий от lester

>всем рабочим коллективом решаете

естественно! все дела заброшены, проекты остановлены, полный аврал - lester задачу поставил, надо выполнять

jtootf ★★★★★
()

предлагаю по четыре теста выложить( 10 - таки многовато ), 2 рабочих и 2 со специальной ошибкой, согласен?

lester ★★★★
() автор топика
Ответ на: комментарий от lester

> доделал, jtootf, успеваешь к 21:00 по киевскому времени сделать?

А куда выкладывать? Могу, конечно, прямо сюда, бо оно ~120 строк занимает.

Я, кстати, параметры iterations, log, test с командной строки беру. Как-то логичнее.

smh ★★★
()
Ответ на: комментарий от smh

> А куда выкладывать? Могу, конечно, прямо сюда, бо оно ~120 строк занимает.

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

lester ★★★★
() автор топика
Ответ на: комментарий от lester

>доделал, jtootf, успеваешь к 21:00 по киевскому времени сделать?

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

jtootf ★★★★★
()
Ответ на: комментарий от lester

>я не хочу пока выкладывать тесты, чтоб он вдруг не нашел у себя ошибку и быстро не исправил

3.14здец. ты правда веришь в то, что пишешь?

jtootf ★★★★★
()
Ответ на: комментарий от jtootf

> у тебя принципиально установка на крысиные бега?

когда я тебя прямо спросил сколько времени надо - ты сам сказал, что день более чем достаточно, называй необходимое кол-во дней и постарайся не превратить простую задачу( учись у smh ) в долгострой

П.С. про справки я уже молчу

lester ★★★★
() автор топика
Ответ на: комментарий от jtootf

> 3.14здец. ты правда веришь в то, что пишешь?

я верю, что ты редкий балабол

lester ★★★★
() автор топика
Ответ на: комментарий от lester

суммарно на задачу на данный момент я потратил пять часов, из них два - на изучение неиспользованых ранее возможностей Parsec'а; оставшуюся часть я оцениваю минут в полчаса (плюс-минус десять минут), но заниматься ею сейчас времени (и желания) у меня нет. играть на время я не собирался и не собираюсь, тешь своё ЧСВ сколько угодно. впрочем, без решения зрителей этого цирка я не оставлю

>про справки я уже молчу

правильно. молчи. тебе полезно

jtootf ★★★★★
()
Ответ на: комментарий от jtootf

обойдемся без тебя, сейчас полчаса-час профайлером программу погоняю + попробую ускорить ее и выложу

lester ★★★★
() автор топика
Ответ на: комментарий от lester

>обойдемся без тебя, сейчас полчаса-час профайлером программу погоняю + попробую ускорить ее и выложу

ура! ура!

jtootf ★★★★★
()
Ответ на: комментарий от jtootf

> ура! ура!

я и не сомневался, что ты так отреагируешь

lester ★★★★
() автор топика

Погонялось на старом P4 3.0

Время не окончательное

Test1 - 1.08сек

iterations = 10000000;
log = off;

object A
{
   circle;
   color = "red";
   value = sqrt(100);
}

object B : A, C, D
{
   circle;
   color = "green";
}

object C : D
{
   value = time();
   square;
}

object D
{
   color = "blue";
   value = 235 + A.value + sqrt( 100 );
   value2 = C.value * value + value4;
   value3 = value2 * time();
   value4 = 20;
}

object E : B {}
object F : B {}
object G : B {}
object H : B {}
object I : B {}
object J : B {}

show B.color;
show circle;
show D.value;
show D.value4;
show sqrt( sqrt( J.value ) );


Test2 - 8.17сек

iterations = 1000000;
log = off;

object A { value = time(); value2 = sqrt( time() ) - C.value; }
object B { value = A.value; }
object C : B { value = ( 1000 / 500 + 1 * ( 1 + 1 ) ) * ( sqrt( sqrt( ( 50 + 50 ) * 2 + 56 ) + 9 ) + 2 ); }
object D : A {}

show A.value2;
show C.value;
show B.value;
show D.value;


исходники выложу уже завтра - после доведения до ума, должно стать весомо быстрее

lester ★★★★
() автор топика
Ответ на: комментарий от lester

>то что должно вывестись на экран

На экран должен выводиться текст или нужно рисовать красный круг и т.д.?

mky ★★★★★
()
Ответ на: комментарий от mky

> На экран должен выводиться текст или нужно рисовать красный круг и т.д.?

просто текст, хотя идея с рисованием интересная

lester ★★★★
() автор топика
Ответ на: комментарий от lester

ха, 1.08 сек и 8.17 сек это vc2008, винт "удачно" накрылся - при доступе к некоторым разделам( один из них корневой убунты ) он начинает стучать и комп периодично висит( на неделе поеду покупать новый системник на Q9550 ) - потому поставил andLinux, скомпилил и запустил в нем - 0.89 сек и 7.4 сек( никаких изменений не делал ), по идее на родном Linux скорость должна быть еще выше

таки залил архив( смысл допиливать и вычищать код - если больше вариантов не будет ):
http://letitbit.net/download/6925.6a6fafd58c245f8e51cb28432/Task.7z.html

собирается одной строкой:

g++ -O3 ./App.cpp ./Expression.cpp ./ExpressionParser.cpp ./Parser.cpp ./Storage.cpp ./Utils.cpp ./VObject.cpp ./VProperty.cpp ./VQuery.cpp -o ./task

lester ★★★★
() автор топика
Ответ на: комментарий от lester

Хе-хе. У меня оно считало этот 2-ой тест 4 минуты. :-)) Хотя, сейчас скачаю jruby - никогда его не пробовал. Должно быть чуть-чуть получше. Но все равно ожидать чего-то сильно лучшего, я думаю, не стоит. С другой стороны даже просто пустой цикл в 10000000 в Ruby несколько секунд крутится.

smh ★★★
()
Ответ на: комментарий от smh

> Хе-хе. У меня оно считало этот 2-ой тест 4 минуты. :-))

как для интерпретатора очень таки пристойно, можно плз посмотреть код( заинтересовали - по свободе начну осваивать Ruby )

lester ★★★★
() автор топика
Ответ на: комментарий от lester

> как для интерпретатора очень таки пристойно, можно плз посмотреть код( заинтересовали - по свободе начну осваивать Ruby )

Сорри, немного увлекся JRuby :-). В общем, практически одинаково. Простой Ruby даже похоже что лучше. Скомпилировал в джавовский class. Запустил. Разницы никакой. :-)

Cейчас немного приведу в порядок код и вышлю.

smh ★★★
()
Ответ на: комментарий от Absurd

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

Где решение на лиспе? :-) Интересно ж...

smh ★★★
()
Ответ на: комментарий от smh

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

>Где решение на лиспе? :-) Интересно ж...

Я тут уже BNF на макрах изобрел. Какой интересный оказывается язык - а раньше я знал его чисто концептуально. Постараюсь однако сконцентрироваться на результате.

Absurd ★★★
()
Ответ на: комментарий от Absurd

В общем, если я правильно понял, дерево можно построить примерно так если делать "в лоб". Поправьте если я ошибаюсь. Вместо печати "Unexpected" наверно надо кидать исключения, но я их еще не ковырял.

(defun make-tokenizer(stream seps)
  (let ((seps-hash (make-hash-table))
	(fetch-new-line T)
	(line nil))
    (defun tokenizer()
      (if fetch-new-line
	  (progn
	    (setf line (read-line stream nil nil))
	    (setf fetch-new-line nil)))
      (if line
	  (if (> (length line) 0)
	      (let
		  ((p (position-if #'(lambda(c) (gethash c seps-hash)) line))
		   (line0 line))
		(if p
		    (if (> p 0)
			(progn
			  (setf line (subseq line p))
			  (cons 'word (subseq line0 0 p)))
			(progn
			  (setf line (subseq line 1))
			  (cons 'separator (elt line0 0))))
		    (progn
		      (setf line "")
		      (cons 'word line0))))
	      (progn
		(setf fetch-new-line T)
		(cons 'separator #\Newline)))
	  (progn
	    (close stream)
	    nil)))
      (if stream
	  (progn
	    (mapcar #'(lambda(sep) (setf (gethash sep seps-hash) T)) seps)
	    #'tokenizer)
	  nil)))

(defun make-filter-tokenizer(tokenizer skip-seps)
  (let ((skip-seps-hash (make-hash-table)))
    (defun tokenizer0 ()
      (let ((token nil))
	(loop for token0 = (funcall tokenizer)
	   while (and (setf token token0)
		      (eq (car token0) 'separator)
		      (gethash (cdr token0) skip-seps-hash))) 
	token))
    (mapcar #'(lambda (sep)(setf (gethash sep skip-seps-hash) T)) skip-seps)
    #'tokenizer0))

(defun token-equal(token term)
  (if token
      (if term
	  (if (eq (car token) (car term))
	      (if (eq (car term) 'separator)
		  (char= (cdr term) (cdr token))
		  (string-equal (cdr term) (cdr token)))
	      nil)
      nil)
  nil))

(defmacro token-is(token token-type)
  `(eq (car ,token) ,token-type))

(defun bt-read-word(tokenizer)
   (let ((token (funcall tokenizer)))
     (if (token-is token 'word)
	 (cdr token)
	 (print "Unexpected"))))

(defun bt-read-separator(tokenizer)
  (let ((token (funcall tokenizer)))
     (if (token-is token 'separator)
	 (cdr token)
	 (print "Unexpected"))))

(defun bt-read-sequence(tokenizer separator delimiter)
  (defun bt-read-sequence0(seq)
    (let ((token (funcall tokenizer)))
      (if (not (token-is token 'separator))
	  (let ((element0 (cdr token))
		(separator0 (bt-read-separator tokenizer)))
	    (cond ((char= separator0 separator) (cons element0 (bt-read-sequence0 seq)))
		  ((char= separator0 delimiter) (cons element0 nil))
		  (T (print "Unexpected"))))
	  (print "Unexpected"))))
  (bt-read-sequence0 nil))

(defun build-expression(tokenizer)
  (let ((expr nil))
    (loop for token0 = (funcall tokenizer)
       while (and token0
		  (not (token-equal token0 '(separator . #\;))))
       do (push token0 expr))
    (reverse expr)))

(defun build-attribute(tokenizer)
  (let ((token (funcall tokenizer)))
    (cond ((token-is token 'word)
	   (let ((sep (bt-read-separator tokenizer)))
	     (cond ((char= sep #\;)
		    (list 'flavour (list 'name (cdr token))))
		   ((char= sep #\=)
		    (list 'property (list 'name (cdr token))
			  (list 'value (build-expression tokenizer))))
		   (T (print "Unexpected")))))
	  ((char= (cdr token) #\}) nil)
	  (T (print "Unexpected")))))

(defun build-object-inheritance-list(tokenizer)
  (let ((sep (bt-read-separator tokenizer)))
    (cond ((char= sep #\:) (bt-read-sequence tokenizer #\, #\{))
	  ((char= sep #\{) nil)
	  (T (print "Unexpected")))))

(defun build-object-attribute-list(tokenizer)
  (let ((attribute-list nil))
    (loop for attribute0 = (build-attribute tokenizer)
       while attribute0
       do (push attribute0 attribute-list))
    (reverse attribute-list)))

(defun build-object (tokenizer)
  (list (list 'name (bt-read-word tokenizer))
	(list 'inheritance-list (build-object-inheritance-list tokenizer))
 	(list 'attribute-list (build-object-attribute-list tokenizer))))

(defun build-show (tokenizer)
  (list (list 'show
	      (build-expression tokenizer))))

(defun build-tree (tokenizer)
  (let ((tree nil))
     (loop for token = (funcall tokenizer)
        while token do
 	 (cond ((token-equal token '(word . "object")) (push (build-object tokenizer) tree))
 	       ((token-equal token '(word . "show")) (push (build-show tokenizer) tree))
 	       (T (print "unexpected"))))
     (reverse tree)))

(let ((tokenizer
      (make-filter-tokenizer (make-tokenizer
			      (open "./test1.txt" :if-does-not-exist nil)
			      '(#\Space #\{ #\} #\: #\; #\( #\) #\. #\, #\= #\+ #\* #\" #\< #\< #\!))
			     '(#\Space #\Newline))))


  (print (build-tree tokenizer)))

Absurd ★★★
()
Ответ на: комментарий от lester

А что оно вообще должно делать? Я только подобие AST-дерева строю для этого файла, еще надо по идее выражение в show отинтерпретировать. Что за второй тест?

Absurd ★★★
()
Ответ на: комментарий от lester

>а делать должно то, что в show указано - вывести значение выражения или все "объекты" по условию

А что означают "итерации"? По несколько тысяч раз чтоли выводить?

Absurd ★★★
()
Ответ на: комментарий от Absurd

> А что означают "итерации"? По несколько тысяч раз чтоли выводить?

Да. Столько раз, сколько указано. Сам вывод можно отключать. Интересует сколько времени тратится на вычисление выражений.

smh ★★★
()

Ну... момент с iterations - просто глупость.

Если в си еще можно расчитывать, что компилятор не оптиимизирует и будет считать это все 100000 раз, то с Хаскель я совершенно не уверен.

Waterlaz ★★★★★
()

Да и вопрос. Что по скорости меряем? В принципе, что-бы распарсить входной файл надо много больше времени, чем что-бы ответить на запрос.

Waterlaz ★★★★★
()
Ответ на: комментарий от Waterlaz

> Ну... момент с iterations - просто глупость.
> Если в си еще можно расчитывать, что компилятор не оптиимизирует и будет считать это все 100000 раз, то с Хаскель я совершенно не уверен.


глупость было не заметить time() в выражениях ;)

lester ★★★★
() автор топика
Ответ на: комментарий от Waterlaz

> Да и вопрос. Что по скорости меряем?

я мерял запросы, если кому надо - померяю парсер

lester ★★★★
() автор топика
Ответ на: комментарий от mipt_student

круто - не ожидал, что столько вариантов на разных языках будет :)

П.С. jtootf не потратишь "полчаса", чтоб доделать свой вариант?

lester ★★★★
() автор топика
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.