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

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

увы, аврал ещё не окончен. искренне сожалею, но со временем (_|_) и без того

jtootf ★★★★★
()

Видимо не дождемся мы решения от mv :)

Т.к. вариант абсурда на мой взгляд не совсем lispy, могу предложить такой proof of concept, который решает задачу несколько отличную от задачи ТП, но который можно будет допилить до пригодного к этому состояния. (Хотя на мой субъективный взгляд у меня получилось лучше :))

(defun make-object ()
  (let ((hash (make-hash-table)))
    (lambda (field &optional value)
      (if value
	  (progn
	      (setf (gethash field hash) value)
	      ;(format t "~a~%" (list field value))
	      )
	  (case field
	    (:fields (loop
		       for h-key being the hash-key in hash using (hash-value h-value)
		       collect (list h-key h-value)))
	    (t (gethash field hash)))))))


(defmacro defobject (name  parents &rest properties)
  `(progn
     (setf (symbol-function ',name) (make-object))
     (dolist (parent ',parents)
       (mapcar #'(lambda (x)
		   (apply #',name x)) (funcall parent :fields)))
     (mapcar #'(lambda (x)
		 (apply #',name (list (car x) (eval (cadr x)))))
	     ',properties)
     ',name))

;; very dirty and quick macro :)
(defmacro showobject (objects predicate)
  `(remove-if-not  #'(lambda (x)
		       (macrolet ((?x (&rest args)
				     `(funcall x ,@args)))
			 ,predicate))
		   ',objects))

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

(defun test2 ()
  (defobject a ()
    (:value (get-universal-time)))

  (defobject b ()
    (:value (a :value)))

  (defobject c (b)
    (:value (* (+ (/ 1000.0 500.) (* 1 (+ 1 1)))
	       (+ (sqrt (+ (sqrt
			    (+ 56
			       (* 2 (+ 50 50))))
			   9))
		  2))))

  (a :value2 (sqrt (get-universal-time)))

  (defobject d (a))
  
  (a :value2)
  (c :value)
  (b :value)
  (d :value))

(defun test ()
  (loop for n from  1 to 1000000 do
       (test2)))

Собственно думаю из функции тест видно, как и что определяется и какой используется mini-dsl, если не понятно - могу прокомментировать. ИМХО, это даже больше, чем просил ТП, потому как эти самые объекты можно использовать в любых выражения, а не только которые жестко указаны в задаче, можно использовать любые типы данных (можно при желании один объект засунуть в другой), также для show можно использовать вообще любые предикаты и выражения - какие захочешь. 

По поводу производительности. Для второго теста 

lester: ~5c

./task test2.txt
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;
Time: 4.940000

Запускалось несколько раз, средний ~5c

мой: ~40c

CL-USER> (time (test))
Evaluation took:
  43.433 seconds of real time
  40.262517 seconds of total run time (35.898244 user, 4.364273 system)
  [ Run times consist of 2.728 seconds GC time, and 37.535 seconds non-GC time. ]
  92.70% CPU
  26,000,000 forms interpreted
  87,856,023,877 processor cycles
  81 page faults
  3,175,994,448 bytes consed

Конечно, мой недоделанный до тз вариант (хотя я, конечно же, бы лучше оставил его так :)) не корректно сравнивать, но все-равно. Проигрыш в производительности в 8 раз - это небольшая цена для более гибкого и мощного на мой взгляд решения. Ну и кроме 1827/34 = 58.

PS. Код не оптимизирован, не документирован, не проверялся на неправильные данные и вообще сделан на скорую руку.

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

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

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

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

вместо List - Lisp, видно пальцы слово Lisp не хотят запоминать :)

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

> П.С. хоть я абсолютно не знаю Lisp, но таки в общем смысл в том, чтоб представить текст теста в виде кода List?

Ага. Но еще смысл в том, что построенная абстракция (объекты) является частью языка и с ней можно творить, что душе угодно. Например, трудно ли будет тебе доделать свою программу, чтобы она в show воспринимала любые логические конструкции (show (value > 10) || (value < 100) && circle)?

> если да - можно также сделать для С - и думаю быстрее решения уж точно не будет( за вычетом компиляции конечно )

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

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

> Например, трудно ли будет тебе доделать свою программу, чтобы она в show воспринимала любые логические конструкции (show (value > 10) || (value < 100) && circle)?

думаю 10-15 мин, зато у меня есть возможности ускорить мой вариант( например большая часть времени как я уже говорил уходит на аллокацию/деаллокацию памяти, что решается умным пулом или отказом от stl в коде для выполнения запросов )

> что макросы в си небезопасны и не шибко удобны


зачем макросы - все просто и банально:

...
С_value = time();
D_value = 100 + A_value;
D_value2 = C_value * D_value;

printf( "%d", D_value2 );

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

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

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

Согласен. Lisp для этого хорошо подходит.

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

> чего с ручным парсингом и ручным разбором выражений достичь тяжело.
> Согласен. Lisp для этого хорошо подходит.


вы просто переложили роль парсера на конечного пользователя ;)

да и взять хотя бы такое выражение:
(:value (* (+ (/ 1000.0 500.) (* 1 (+ 1 1)))
(+ (sqrt (+ (sqrt
(+ 56
(* 2 (+ 50 50))))
9))
2))))

и трудно в записи и не читабельно

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

> думаю 10-15 мин, зато у меня есть возможности ускорить мой вариант( например большая часть времени как я уже говорил уходит на аллокацию/деаллокацию памяти, что решается умным пулом или отказом от stl в коде для выполнения запросов )

У меня тоже есть возможность. Я же даже без (declaim (optimize (speed 3)) тестил. Сейчас попробую оптимизировать - может чего выйдет.


> зачем макросы - все просто и банально:
...
С_value = time();
D_value = 100 + A_value;
D_value2 = C_value * D_value;
printf( "%d", D_value2 );

Не, а где синтаксис для наследования? А где возможность увидеть объекты с заданными свойствами? Кстати, в моей проге это все есть, и лисповый dsl-код сделан как можно "ближе" к оригиналу тестов.

> т.е. просто выставить нужный порядок вычисления "свойств", хотя конечно и тут есть проблемы - например то же деление на 0 и корень от отрицательного числа( которые у меня проверяются ), но в принципе не проблема разложить выражение на части( что уже сделано ) и добавить проверки в С код

Корень из отрицательного числа - это не ошибка :)

CL-USER> (sqrt -10.0)
#C(0.0 3.1622777)


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

точно также можно предложить сразу писать код на С в стиле:

...
С_value = time();

// Object D
D_value = 100 + A_value;
D_value2 = C_value * D_value;

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

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

> вы просто переложили роль парсера на конечного пользователя ;) (:value (* (+ (/ 1000.0 500.) (* 1 (+ 1 1))) (+ (sqrt (+ (sqrt (+ 56 (* 2 (+ 50 50)))) 9)) 2)))) и трудно в записи и не читабельно

Оно и в инфиксной записи тяжело читается - я минуту распарсивал :) В таких случаях здорово помогает форматирование.

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

> точно также можно предложить сразу писать код на С в стиле: ... С_value = time(); // Object D D_value = 100 + A_value; D_value2 = C_value * D_value;

Ага, еще раз прочитай мое предпредыдущее письмо - как с таким синтаксисом сделать человеческое наследование объектов? - вручную? Как сделать show - вручную?

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

> Не, а где синтаксис для наследования? А где возможность увидеть объекты с заданными свойствами? Кстати, в моей проге это все есть, и лисповый dsl-код сделан как можно "ближе" к оригиналу тестов.

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

vector<string> circle;
circle.push_back( "A" );
...
map<string, vector<string>> pmap;
pmap[ "circle" ] = circle;
...

> Корень из отрицательного числа - это не ошибка :)


не проблема ;)

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

> как с таким синтаксисом сделать человеческое наследование объектов? - вручную? Как сделать show - вручную?

для сгенеренного варианта так:
map<string, vector<string>>::iterator it = pmap.find( "circle" );
if( it != pmap.end )
{
vector<string>& list = it.second;
size_t count = list.size();
for( size_t i = 0 ; i < count ; ++i )
printf( list[ i ] );
}

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

#include <smart.h>

DECLARE_CLASS( A )
ADD_PROPERTY( "circle" )

DECLARE_CLASS( B )
ADD_PARENTS( C )
ADD_EXPRESSION( value = 1 + 1; )

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

> для ручного пишется один раз несколько макросов( что вы вроде и предложили ) и все будет просто:

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

> #include <smart.h>

DECLARE_CLASS( A )
ADD_PROPERTY( "circle" )

DECLARE_CLASS( B )
ADD_PARENTS( C )
ADD_EXPRESSION( value = 1 + 1; )

Тем более все-равно это очень многословный синтаксис. Хотелось бы чего-нибудь простого, что вроде 

DECLARE_OBJECT (A : C, B; value = C_value * 5; circle; )

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

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

> Если это просто - можно увидеть реально работающий код,

будет просто, когда макросы уже будут написаны :) вкратце:

#define ADD_PROPERTY( value ) pmap[ value ].push_back( gCurrentObject ); objmap[ gCurrentObject ].AddProperty( value );
#define ADD_PARENTS AddParentToLastObject
void AddParentToLastObject( size_t count, ... )
{
...
тут через va_list получаем имена родителей, от них берем список свойств и добавляем в текущий объект
}

и т.д., полностью написать - надо время, но думаю смысл понятен

> Тем более все-равно это очень многословный синтаксис. Хотелось бы чего-нибудь простого, что вроде

> DECLARE_OBJECT (A : C, B; value = C_value * 5; circle; )


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

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

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

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

> будет просто, когда макросы уже будут написаны :) вкратце:


#define ADD_PROPERTY( value ) pmap[ value ].push_back( gCurrentObject ); objmap[ gCurrentObject ].AddProperty( value );
#define ADD_PARENTS AddParentToLastObject
void AddParentToLastObject( size_t count, ... )
{
...
тут через va_list получаем имена родителей, от них берем список свойств и добавляем в текущий объект
}

Это самые простые и очевидные макросы, самое интересное (DECLARE_OBJECT SHOW) - ты почему-то опускаешь :)) Дьявол, он в деталях, после попытки такое реализовать и где-то использовать - желание заниматься метапрограммированием на си, си++ отпадет. Ну и кроме того, такое решение не предоставит программисту абстракции - точнее предоставит, но текущую изо всех щелей, в отличие от. Ну например, нужно будет в качестве одного из свойств сделать другой объект.

(defobject a ())
(defobject c () :included-object a).  

Решение с A_value сразу же пойдет лесом. 

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

Единственное, с чем я согласен, что инфиксная нотация там была бы кстати :). А так 

DECLARE_CLASS( A )
ADD_PROPERTY( "circle" )

DECLARE_CLASS( B )
ADD_PARENTS( C )
ADD_EXPRESSION( value = 1 + 1; )

явно не проще

(defobject a ()
    :circle t)

(defobject b (c) 
    :value (+ 1 1))

,которая  по простоте близка к оригиналу 

object A {
     circle;
}

object B : C {
     value = 1 + 1;
}
    

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

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

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

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

> Это самые простые и очевидные макросы, самое интересное (DECLARE_OBJECT SHOW) - ты почему-то опускаешь :))

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

> Решение с A_value сразу же пойдет лесом.


это решение будет только для сгенерированного кода( а не написанного макросами )

> которая по простоте близка к оригиналу


но таки уступает ему, кстати в вашем решении выполняется ли условие про правильное наследование свойств с одинаковыми именами, а также про то что описание родителя может быть позже, а также проверяется ли наличие рекурсий, корректность данных и т.п.? Дьявол, он в деталях ;) может код на Lisp очень разрастется, если будет удовлетворять всем условиям?

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

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

А так хотелось увидеть :) Не верю я в метапрограммирование на сишных макросах. 

> это решение будет только для сгенерированного кода( а не написанного макросами )

а как тогда в определениях ссылаться на значения свойств других объектов?

A.value? И как тогда будет осуществляться доступ к ним A.value.color? И как это все будет реализовано?

> которая по простоте близка к оригиналу но таки уступает ему

плата за масштабируемость решения, очень небольшая плата, имхо.

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

да 

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

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

> Дьявол, он в деталях ;) 

Дык, хотя бы это сделайте сишными макросами :) - так чтобы работало.
Только там не какие-то детали - там целая помойка, выбраться из которой не легко.

> может код на Lisp очень разрастется, если будет удовлетворять всем условиям? 

Нет, но то, что станет более медленным совершенно очевидно - streams в лиспе не шустрый. 

И снова, я сразу написал, что это proof of concept, который не решает поставленную в тз задачу, а предлагает другой подход. Хотя при определенном желании переделать можно.  

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

> и как я понял первый тест таки не работает? :)

А что там? Он длинный был - а я хотел спать :) Щаз протестируем.

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

> вы просто переложили роль парсера на конечного пользователя ;)

Аа.. а я просто не понял. Быстро глянул не углубляясь (бо лиспа не знаю), думал у него в тех нескольких строках и парсер и вычисление уместились (еще удивился:-). Тогда да, тогда не интересно. :-)

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

> А так хотелось увидеть :) Не верю я в метапрограммирование на сишных макросах.

метапрограммирование ради метапрограммирования? это неинтересно - надо просто сделать простой способ записи условия в виде кода, и это таки на сишных макросах очень просто делается

> а как тогда в определениях ссылаться на значения свойств других объектов? И как тогда будет осуществляться доступ к ним A.value.color? И как это все будет реализовано?


так и будет: A_value = B_value2 + 1;

у нас есть один экземпляр объекта с уникальными свойствами, не вижу причины почему A.value нельзя заменить на A_value, полный список свойств будет вычисляться заранее( уже реализовано ) - так что сортируем выражения в правильном порядке и просто шмалим в исходный код

> плата за масштабируемость решения, очень небольшая плата, имхо.


потому-что ваше решение не полное, когда оно будет полным - "плата" станет гораздо больше

> нет, используется несколько другой подход - и это тоже плата за гибкость


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

> Дык, хотя бы это сделайте сишными макросами :) - так чтобы работало.


зачем? :)

> Нет, но то, что станет более медленным совершенно очевидно



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

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

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

Есть смысл - какой я уже написал.

> потому-что ваше решение не полное, когда оно будет полным - "плата" станет гораздо больше

Да, я посмотрел на первый тест - действительно, то, что предложил я на ней работать принципиально не сможет. И кода действительно будет больше. На сколько это повлияет на производительность сложно сказать.

> за это будет платить конечный пользователь - оно ему надо руками сортировать объекты, писать выражения в постфиксной записи и т.п.?

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

paranonymous
()

Вот я тут набыдлокодил на лиспе.

http://ifolder.ru/13173301

Первый тест выполняется чуть меньше двух минут. Второй -- 12 секунд.

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