Сравнительное исследование дефектов показывает превосходство стека TCP/IP Linux

Correction: Скедьюлинга

ARia

По ходу дела, такой низкоуровневой оптимизацией за меня занимается бакенд - Quick C--. ;)

ARia

2 MrBool :))))))))))

> Нюню, без тулзов запаришся дескрипторы к ej beans писать.

Ну да :))) А что смотри: :))))

1. С ленцой так это почитать 3-5K стр. на ночь
2. С еще большей ленцой с утречка просмотреть 5-7K практики
3. Ну, а для работы слегка заинстоллить Ora 9i AS (самый чуток).

А чего? Лень - двигатель прогресса :))))). Ты помнишь анекдот про спор трех котов о том, кто из них ленивее? :)))

(..на этом месте неудержимый смех обуял автора и он не в состоянии продолжить..)

P.S.
Извиняюсь за злостный офтопик. :))))))

ignite (*) (2003-02-19 10:22:15.393):
> ...логика железная - выдает не то что нужно, а что нужно - не знаю.
Сравни с тем, что написано у меня:

> ...результат ОТЛИЧНЫЙ от того, что дает алгоритм eugine_kosenko...
> ...А что требовалось ... лень разбираться.
Последняя фраза IMHO очевидна, но для любителей логики поясняю:
мне лень разбираться ("а что нужно - не знаю"), какую математическую конструкцию
реализует описанный на псевдокоде алгоритм
eugine_kosenko (*) (2003-02-17 23:44:34.18).

Поднапряги то, что тебе заменяет логику, и постарайся осознать, что твой
алгоритм делает не то же самое, что eugine_kosenko (*) (2003-02-17 23:44:34.18).

Я не утверждаю, что алгоритм eugine_kosenko (*) (2003-02-17 23:44:34.18)
НЕЛЬЗЯ реализовать без goto (мне лень разбираться), - я утверждаю, что ты
это сделал неверно, поскольку я тупо прогнал обе программы и получил разные
результаты (разумеется, исходные данные я брал одни и те же).

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

А в остальном я смеюсь до слёз... Вы, похоже, сходили на amazon.com и прочитали оглавление книги. Но изобразить из себя осведомлённого человека всё равно плохо получается. Скажите, милейший, причём сдесь Optimization For Memory Hierarchy, Guide To Assembly Languages, Representation of sets...???

Если Вы бы зашли на researchindex и набрали бы там Steven S Muchnik, Вы бы сразу поняли, что он специалист по методам анализа потоков данных, естественно, занимающийся и другими вопросами.

2 Die-Hard

ignite (*) (2003-02-19 10:22:15.393):
> ...логика железная - выдает не то что нужно, а что нужно - не знаю.
Сравни с тем, что написано у меня:

> ...результат ОТЛИЧНЫЙ от того, что дает алгоритм eugine_kosenko...
> ...А что требовалось ... лень разбираться.
Последняя фраза IMHO очевидна, но для любителей логики поясняю:
мне лень разбираться ("а что нужно - не знаю"), какую математическую
конструкцию реализует описанный на псевдокоде алгоритм
eugine_kosenko (*) (2003-02-17 23:44:34.18).

Поднапряги то, что тебе заменяет логику, и постарайся осознать, что
твой алгоритм делает не то же самое, что eugine_kosenko (*) (2003-02-17 23:44:34.18).

Я не утверждаю, что алгоритм eugine_kosenko (*) (2003-02-17 23:44:34.18) 
НЕЛЬЗЯ реализовать без goto (мне лень разбираться), - я утверждаю,
что ты это сделал неверно, поскольку я тупо прогнал обе программы и
получил разные результаты (разумеется, исходные данные я брал одни
и те же).


+++ ------------------------------------------- +++


Хм, простой вопрос - алгоритм eugine_kosenko ты прямо так на псевдокоде и проганял ? Алгоритм ты конечно не понял, с goto это довольно непросто, но полученные результаты сравнить тупо можно же было...
 
Показываю:


#include <stdio.h>

void print_vec(int *v, int n){
	int i ;
	for( i = 0; i < n; i++) printf("%d ", v[i]);
	printf("\n");
}

#define n 3
int main(int argc, char *argv[]){
	int N[n] = {3, 4, 2};
	int j[n] = {1, 1, 1};
	int k;

print_tuple:
	print_vec(j, n);
	k = n - 1;

	do{
		j[k] = j[k] + 1;
		if( j[k] <= N[k] )
			goto print_tuple;
		j[k] = 1;
		k = k - 1;
	}while( k >= 0 );
	
	return 0;	
}

[ivan@onix ivan]$ vi dec.c
[ivan@onix ivan]$ gcc -o dec dec.c
[ivan@onix ivan]$ ./dec
1 1 1
1 1 2
1 2 1
1 2 2
1 3 1
1 3 2
1 4 1
1 4 2
2 1 1
2 1 2
2 2 1
2 2 2
2 3 1
2 3 2
2 4 1
2 4 2
3 1 1
3 1 2
3 2 1
3 2 2
3 3 1
3 3 2
3 4 1
3 4 2
[ivan@onix ivan]$

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

2 All
Блин, ну откуда такое ламьё берётся ?

Кстати, по поводу исходной задачи, для тех кто не понял причем здесь декартово произведение. Напомню первоначальную формулировку:

------------------------------------------------------------------

Дано целое n и вектор целых чисел N[n]. Необходимо найти декартово произведение множеств

A[i] = {j| 1 <= j <= N[i]}, где 1<=i<=n

-------------------------------------------------------------------

Понимать это следует так: n - это количество множеств, то есть искать будем декартово произведение n множеств. Значения элементов множнств в данной задаче неважны, поэтому множества представлены своими кардинальными числами (количество элементов). То есть N[i] - это количество элементов в i множестве. Можно считать, что i-e множествo состоит из целых цисел от 1 до N[i]. Далее, декартово произведение n множеств это множество кортежей размерности n (полное определение давать не буду, да и забыл, в смысле трудно кратко сформулировать).

Вывод программы: 1 1 1 1 1 2 1 2 1 .... Это и есть декартово произведение, если его прочитать так: { (a1, b1, c1), (a1, b1, c2), (a1, b2, c1), .... }, как это принято в математике.

Надеюсь теперь всем понятно - причем здесь декартово произведение.

2ignite:
> Теперь попробуй только скажи, что это не неализация алгоритма
> eugine_kosenko,
Верно, уел. Это я с индексом прогнал (делать мне не хрена, кроме как
хрен знает что отлаживать?).

> Блин, ну откуда такое ламьё берётся ?
Че, нельзя было просто носом ткнуть, обязательно под2.72бнуть надо?
Я тебе отвечал всего лишь по поводу твоей "железной" логики.

2 замечания.

1. Читабельность:
continue в
do{...if() continue; else ...}while()
по сути то же самое goto. Оператор разрыва с точки зрения Дейкстры
есть единственно правильно, но continue в цикле под ифом ...
С точки зрения читабельности IMHO не лучше goto, с точки зрения Дейкстры
- нет такого. И, вообще, пюлювать мне на Дейкстру, если я на Це пишу.

2. Эффективность:
Твой алгоритм по времени стабильно сливает варианту с goto.

Кстати, ни у кого под рукой нет примера Кнута? Помнится, он приводил пример кода, невозможного без goto.

2 Die-Hard: Кнут не мог приводить пример кода _невозможного_ без goto - т.к. доказано, что без него можно обойтись _всегда_...

он показывал, если мне память не изменяет, три случая, когда использование goto _оправдано_. т.е. где данный оператор позволяет снять кучу геммороя с программиста.

PTO (*) (2003-02-19 18:52:11.557):

Ессно! Последовательность, развилка и любой цикл позволяют сделать все. Вопрос в эффективности.

Дык, кто знает ссылку? Лень искать. Вечером поищу, если никто не кинет.

2 Die-Hard

> Теперь попробуй только скажи, что это не неализация алгоритма
> eugine_kosenko,
Верно, уел. Это я с индексом прогнал (делать мне не хрена, кроме как
хрен знает что отлаживать?).

> Блин, ну откуда такое ламьё берётся ?
Че, нельзя было просто носом ткнуть, обязательно под2.72бнуть надо?
Я тебе отвечал всего лишь по поводу твоей "железной" логики.

----------------------------------------------------------------

Скажем так нечего было провоцировать - ниже цитата, а так да,
погорячился... :)

Поднапряги то, что тебе заменяет логику, и постарайся осознать, что
твой алгоритм делает не то же самое, что eugine_kosenko (*) (2003-02-17 23:44:34.18).

----------------------------------------------------------------


2 замечания.

1. Читабельность:
continue в
do{...if() continue; else ...}while()
по сути то же самое goto. Оператор разрыва с точки зрения Дейкстры
есть единственно правильно, но continue в цикле под ифом ...
С точки зрения читабельности IMHO не лучше goto, с точки зрения Дейкстры
- нет такого. И, вообще, пюлювать мне на Дейкстру, если я на Це пишу.

--------------------------------------------------------------

Ну, читабельность дело такое - кто что привык читать. Но вариант
без goto читабельнее хотя бы просто потому, что прочитав continue, сразу знаешь куда собственно переход - к началу цикла. Более важный аргумент - другой: в моем варианте есть ОДИН цикл, внутри которого
ОДИН условный оператор с двумя ветками. Все. Вот и вся структура.
В варианте с goto фактически есть еще один цикл: от метки - до goto. Вместе с основным циклом repeat они образуют нечто вроде сцепленых колец. Нужно объяснять что это плохо ?
Еще одно, continue, в принципе здесь и не нужен, убрав его получим
корректный алгоритм. Добавил я его (вначале был вариант без) только
чтобы избежать упреков в лишних проверках на к=0 в первой ветке.
То есть принципиально структуру программы continue не меняет, это
только оптимизация, соответственно читабельность заметно ухудшить не может.

----------------------------------------------------------


2. Эффективность:
Твой алгоритм по времени стабильно сливает варианту с goto.

---------------------------------------------------------

И где же это интересно ?


С goto - 

1 print
2 k = n
3 j[k] = j[k] + 1
4 if j[k] <= N[k] goto 1
5 j[k] = 1
6 k = k - 1
7 if k <> 0 goto 3


Без - 

1 j[k] = j[k] + 1
2 if j[k] > N[k] goto 6
3 print
4 k = n - 1
5 goto 1
6 j[k] = 1
7 k = k - 1
8 if k < 0 goto 1 

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

ignite (*) (2003-02-19 19:27:27.309):
> ...как там оно процессором будет соптимизировано, и сколько там на самом 
> деле будет переходов хз.
Да я просто прогнал в цикле по 100000 раз оба варианта на разных 
компилерах/архитектурах с разными уровнями оптимизации - вариант без 
goto сливает 3-7 %. 

> В варианте с goto фактически есть еще один цикл: от метки - до goto.
С точки зрения Дейкстры, continue -  тоже еще один вложенный цикл.

Впрочем, ты меня убедил ( заставил-таки в алгоритме разобраться;) ), 
и этот пример - совсем не тот случай, чтобы goto лепить. Это, фактически,
цикл Дейкстры с лишним if'ом (без if( j[k] <= N[k] ) был бы классический 
цикл Дейкстры):

for(;;){
     j[k] ++;
     if( j[k] <= N[k] ){
         print;
         k = n - 1;
     }else{
         j[k] = 1;
         if(k<1)
            break;
         k--;
     }
}

2AVL:гики превращаю
> верить можно богу. а насчет остального надо думать, мой маленький
> сотворитель кумиров...
Вещал не я, а вы, неудавшийся кандидат в кумирчики местного масштаба. Не нравится слово "верить", возьми "доверять", "cоглашаться". После чего утрись и осознай, что код не делается нечитаемым лишь потому, что некий ниспровергатель авторитетов AVL2 об этом громко возвестил миру.

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

> А что, трудно догадаться, что пересечения конструкций без правил и
> лот заранее разобраные логические конструкции (главное,
> циклы) в неоптимизируемую кашу? Все аргументы про дробление на блоки
> уже звучали.
Или в пылу священной страсти забыли, что спор крутится об оправданности применения goto там, где это _упрощает_ код или оправдано для большей эффективности. Вы же логоворились до обвинения противников в злонамеренном втыкании goto направо и налево, с нуждой или без. Мелкое такое передёргивание. Из пламенного борца за тотальное искоренение goto вы этак элегантно перескочили в лагерь борцов на чистоту кода, что не есть одно и то же.

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

> а разбираться с экстренным выходом из того же цикла и одновременным > влетом в середину другого уже не будем?
А зачем? В поисках заявленной вами pipeline stall?

> Остальное подсказывает, что основным оптимизирующим моментом по
> твоей логике является смена компьютера. :(
Да нет, мозги программиста. Где уж вам догадаться...

to anonymous (*) (2003-02-19 15:09:54.042)
По этим страницам, судя по амозону находятся две части 
по flow analysis.

ФКшф

to anonymous (*) (2003-02-19 15:09:54.042

Я не занимаюсь компилляторами - я занимаюсь высокоуровневой оптимизацией, как то aggressive unboxing, partial evaluation 
и, в особенности, CST и hole abstraction transformation.
Боюсь, что вам это ничего не говорит.

ARia

2 Die-Hard & all

ignite (*) (2003-02-19 19:27:27.309):
> ...как там оно процессором будет соптимизировано, и сколько там на самом 
> деле будет переходов хз.
Да я просто прогнал в цикле по 100000 раз оба варианта на разных 
компилерах/архитектурах с разными уровнями оптимизации - вариант без 
goto сливает 3-7 %. 

> В варианте с goto фактически есть еще один цикл: от метки - до goto.
С точки зрения Дейкстры, continue -  тоже еще один вложенный цикл.

Впрочем, ты меня убедил ( заставил-таки в алгоритме разобраться;) ), 
и этот пример - совсем не тот случай, чтобы goto лепить. Это, фактически,
цикл Дейкстры с лишним if'ом (без if( j[k] <= N[k] ) был бы классический 
цикл Дейкстры):

for(;;){
     j[k] ++;
     if( j[k] <= N[k] ){
         print;
         k = n - 1;
     }else{
         j[k] = 1;
         if(k<1)
            break;
         k--;
     }
}

-------------------------------------------------------

ОК, как говорил классик - практика критерий истины :)
Окончательный эксперимент, который расставляет все точки над i.

Итак, три реализации алгоритма - мой с continue, eugine_kosenko
c goto, Дейкстры с break. Реализация алгоритма Дейксты ниже, 
все остальные были модифицированы аналогично (печать
закомментирована, массив из трех 1000, добавлен вывод времени счета).


#include <stdio.h>
#include <time.h>

void print_vec(int *v, int n){
//	int i;
//	for(i = 0 ; i < n ; i++) printf("%d ", v[i]);
//	printf("\n");
}

#define n 3

int main(){
	int N[n] = {1000, 1000, 1000};
	int j[n] = {1,1,0};
	int k = n - 1;

	time_t start = time(NULL);
		
	for(;;){
		j[k] = j[k] + 1;		
		if( j[k] <= N[k] ){
			print_vec(j, n);
			k = n - 1;
		}else{
			j[k] = 1;
			k = k - 1;
			if( k < 0 ) break;
		}
	}

	printf("Time: %f\n", difftime(time(NULL), start));
	return 0;
}

Результат (повторяется от запуска к запуску - влияние операционки
минимально):

1 continue - 30 c
2 goto     - 28 c
3 break    - 25 c

По моему впечатляюще. Интерпретация результатов: проигрыш 
continue по сравнению с goto - лишний переход. Проигрыш goto
break-у ничем иным, как лучшей оптимизацией процессором мне
объяснить не удается.

Вот так-то вот.

По-моему следуют два вывода: 1) классики правы - любой алгоритм
можно реализовать без goto 2) попытка с помощью goto оптимизировать
алгоритм может привести к обратному эффекту на современных 
процессорах и компиляторах.

to ignite :

>Вот так-то вот.

Кстати, выкинь print_vec(j, n); и еще раз прогони проги, plz

2 MrBool

Без вызова функции время выполнение уменьшилось до 13-14 с, чтобы
получить более достоверный результат изменил входные данные:
int N[n] = {3000, 1000, 1000}

1. goto     - 42 c
2. continue - 42 c
3. break    - 40 c

Тенденция, однако...

2РТО

2 Die-Hard: Кнут не мог приводить пример кода _невозможного_ без goto - т.к. доказано, что без него можно обойтись _всегда_...

_всегда_ - наверное очень сильное утверждение, всегда нужно

указывать язык/архитектуру где это справедливо.

На ассемблере давно ничего не писали ? Как там обойтись без

всяких условных/безусловных jump или в фортране 4 ?

Саныч

2Саныч: на счет фортрана - ну если язык хреново спроектирован, то ему ничего не поможет, это да :) Правда не стоит забывать что фортран и алгол60 были первыми высокоуровневыми языками програмирования.
На счет асемблера - для современных процов на асме пишут только законченные крентины...:) Это _возможно_, _иногда_, в очень ограниченных объемах, допустимо для embedded systems... И просьба не поминать пики и мсц51 в суе...:)

2 Саныч

Не занимайтесь подменой понятий. Доказано, что любой алгоритм можно записать без АБСТРАКТНОЙ АЛГОРИТМИЧЕСКОЙ КОНСТРУКЦИИ ПЕРЕХОДА.

Это утверждение никак не зависит ни от языков программирования, ни от аппаратных архитектур, это понятия из разных плоскостей. Это МАТЕМАТИКА, а не технология (языки программирования - технология).

Если в С нет объектов, это не значит, что на нем нельзя писать объектно-ориентированные программы. Если в ассемблере нет других (кроме перехода) алгоритмических конструкций, то это не значит, что нельзя писать в структурном стиле. Вы спрашиваете как ? Моделируя алгоритмические конструкции, например:

while expr loop: expr jne end op1 op1 ... ... end jmp loop end:

if expr expr: expr jne else op1 op1 ... ... jmp end else else: op2 op2 ... ... end end:

И так далее. И не используя jmp ВО ВСЕХ ДРУГИХ СЛУЧАЯХ. Я думаю это должно быть достаточно понятно.

блин, ну когда запомню, что нужно формат внизу выбирать :)

2 Саныч 

Не занимайтесь подменой понятий. Доказано, что любой алгоритм
можно записать без АБСТРАКТНОЙ АЛГОРИТМИЧЕСКОЙ КОНСТРУКЦИИ ПЕРЕХОДА.

Это утверждение никак не зависит ни от языков программирования,
ни от аппаратных архитектур, это понятия из разных плоскостей.
Это МАТЕМАТИКА, а не технология (языки программирования - технология).

Если в С нет объектов, это не значит, что на нем нельзя писать
объектно-ориентированные программы. Если в ассемблере нет других
(кроме перехода) алгоритмических конструкций, то это не значит,
что нельзя писать в структурном стиле. Вы спрашиваете как ?
Моделируя алгоритмические конструкции, например:

while expr    loop: expr
                    jne end
    op1             op1 
    ...             ...
end                 jmp loop
              end:


if expr       expr: expr
                    jne else
    op1             op1
    ...             ...
                    jmp end 
else          else:
    op2             op2
    ...             ... 
end           end: 

И так далее. И не используя jmp ВО ВСЕХ ДРУГИХ СЛУЧАЯХ.
Я думаю это должно быть достаточно понятно.

to ignite :

>Тенденция, однако...

Интересно было бы (для меня во всяком случае ;) на чем
компилил, с какими ключами, где пущал (железо/ось) ?

Есть подозрение что при хорошей оптимизации break еще
больше оставит goto позади :)

2 ignite

Внимательно читаем пост

"_всегда_ - наверное очень сильное утверждение, всегда нужно

указывать язык/архитектуру где это справедливо."

>Это утверждение никак не зависит ни от языков программирования, ни от аппаратных архитектур, это понятия из разных плоскостей. Это МАТЕМАТИКА

Если Вы уж аппелируете к математике, то следует понимать, что нет

некоторой универсальной МАТЕМАТИКИ, которая верна всегда.

Каждая мат. теория имеет свою область применения и ограничения.

Геометрия Евклида тоже не всегда страведлива и параллельные

прямые пересекаются.

>Это утверждение никак не зависит ни от языков программирования, ни от аппаратных архитектур

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

времени способны сказать в каком состоянии она находится и все

процессы в ней детерминированы.

Для абстрактного квантового компьютера, боюсь что нет.

И алгоритмы там будут другие и теоремы и вся математика.

Так что не надо говорить "всегда".

>while expr loop: expr jne end op1 op1 ... ... end jmp loop end:

if expr expr: expr jne else op1 op1 ... ... jmp end else else: op2 op2 ... ... end end:

Ну и что ? Вон сколько jmp.

Саныч

2 Irsi >На счет асемблера - для современных процов на асме пишут только законченные крентины

Ну не знаю.

Посмотрите сколько в линуксе кода на асме, не думаю

что его написали кретины :)

Саныч

2 Саныч:

Вы физик? занимались изучением программирования как математической дисциплины? или вся сила на тензоры и спиноры потрачена?

Советую почитать Бома и Джакопини, которые еще в 1965 году ДОКАЗАЛИ математически, что ЛЮБАЯ программа может быть построена с использованием трех блоков/конструкций:

1. Линейная последовательность действий - функциональный блок
2. Цикл с проверкой в начале - обобщенный цикл
3. Условный переход - двоичное решение

Заметьте - все сие без относительно от платформы/языка и т.п.

Дональт Кнут показал, что есть случаи, когда использование готу целесообразно и допустимо в своей статье
Structured Programming with go to Statements за 1974 год
http://portal.acm.org/citation.cfm?doid=356635.356640

2Саныч: ну и зря не думаете - думать полезно...;)))

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

2 MrBool

Тестовая машина - Celeron 666/128M
OS, compiler:

[ivan@onix ivan]$ gcc -v
Reading specs from /usr/lib/gcc-lib/i386-redhat-linux/3.2/specs
Configured with: ../configure --prefix=/usr --mandir=/usr/share/man --infodir=/usr/share/info --enable-shared --enable-threads=posix --disable-checking --host=i386-redhat-linux --with-system-zlib --enable-__cxa_atexit
Thread model: posix
gcc version 3.2 20020903 (Red Hat Linux 8.0 3.2-7)
[ivan@onix ivan]$

Все предыдущие тесты проводились без оптимизации:
gcc -o dec dec.c

Результаты с оптимизацией:

-O
1. goto     - 28 c
2. continue - 38 c
3. break    - 28 c

-O1
1. goto     - 28 c
2. continue - 38 c
3. break    - 28 c

-O2
1. goto     - 28 c
2. continue - 23 c
3. break    - 28 c

А вот и сюрприз:

-O3
1. goto     - 19 c
2. continue - 23 c
3. break    - 28 c

Еще сюрприз, компиляция с -O3 -mcpu=i686 для goto показала время
28 с, в то время как для двух других время не изменилось.

Все, интерпретировать результаты не берусь :)

Комментарии ?

to PTO :

>Дональт Кнут показал, что есть случаи, когда
>использование готу целесообразно и допустимо

Именно по причине полезности в 1% случаев goto присутствует в языке Ada :)

2 РТО

Здрасте, здрасте ! Вот Вы где, а я уж думал уехали целину поднимать

в регионах.

Нести, так сказать, нетленные идеи МС в массы.

>2 Саныч:

>Вы физик? занимались изучением программирования как математической дисциплины? или вся сила на тензоры и спиноры потрачена?

Нет, я не проф. физик, в ПТУ учусь, сами же сказали.

Про кван. компьютинг прочел в "Компьютерре", стало очень интересно.

>Советую почитать Бома и Джакопини, которые еще в 1965 году ДОКАЗАЛИ математически, что ЛЮБАЯ программа может быть построена с использованием трех блоков/конструкций:

1. Линейная последовательность действий - функциональный блок 2. Цикл с проверкой в начале - обобщенный цикл 3. Условный переход - двоичное решение

Помните, по моему - Лаплас, сказал: "Дайте мне импульсы и нач.

координаты частиц во вселенной и я предскажу будущее"

С точки зрения матем./физики того времени - утверждение было

бесспорно, но с современной точки зрения оно ложно.

Теорема Бома и Джакопини

безусловно справедлива, для детерминированного вычислителя

со счетным множеством состояний, понятно, что природа вычис. может

быть любой. Важно, что он детерминирован - в любой момент времени Вы

можете абсолютно

точно сказать в каком состоянии этот выч. находится и предсказать

будущее его поведение с вероятностью 1.

В случае кван. вычислителя Вы не можете рализовать тот же условный

переход, поскольку не знаете его состояние, а если попытаетесь узнать,

то это состояние разрушите.

Так что математика и алгоритмы должны отличаться.

Так что давайте не будем говорить "никогда".

Зы В 1965 году Бома и Джакопини наверное еще не знали про квантовый

компьютинг :)

Саныч

to ignite :

>Все, интерпретировать результаты не берусь :)
>Комментарии ?

Блин, ну ты и прооптимизировал ;)

-O3 -mcpu=i386 -fomit-frame-pointer -fexpensive-optimizations
-O3 -mcpu=i686 -fomit-frame-pointer -fexpensive-optimizations
-O6 -mcpu=i686 -fomit-frame-pointer -fexpensive-optimizations


Кто бы еще и на AMD прогнал :)

Да, нашел Кнута, thanks to PTO (*) (2003-02-20 14:30:51.145).

Массив A[m] с разными чиселками. На входе - некое число x. Требуется
поискать его в A; если нет, то добавить в конец. И еще есть массив B, 
который содержит счетчики: B[i] = сколько раз искали A[i].

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

for(i=0;i<m;i++) 
   if(A[i] == x) goto found;
i=m;m=i+1;A[i]=x;B[i]=0;
found: B[i] ++;

2 Саныч:

как узнал что я был в Целинограде то бишь Астане? у шайтан!
Тока я там не в массы нес знания, а в очень-очень ограниченный круг энтерпрайз заказчиков... типа элита ИТ сообщества Казахстана

Понятно - ПТУшники не изучают теорию алгоритмов и программирование как математическую дисциплину. понятие программы и алгоритма им неведомо... они в высоких сферах летают... пыхнут и летают...

Наркотики очень вредны для молодого организма - особливо на мозг

2 Die-Hard: ну пора уже коллекционировать "спасибо" в свой адрес.

2Irsi

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

А это смотря какие задачки решать :)

This article is to introduce the reader into the fun land of

exploiting a routing device made by Cisco Systems.

For a string overflow scenario like this one, the recommended way for

small code is to use self-modification.

--- bootstrap.s --- .globl _start _start: | Remove write protection for NVRAM. | Protection is Bit 1 in BR7 for 0x0E000000 move.l #0x0FF010C2,%a1 lsr (%a1)

| fix the brance opcode | 'bne decode_loop' is OP code 0x6600 and this is bad lea broken_branch+0x101(%pc),%a3 sub.a #0x0101,%a3 lsr (%a3) ........

--- end bootstrap.s ---

You may assemble the code into an object file using:

linux# m68k-aout-as -m68360 -pic --pcrel -o bootstrap.o bootstrap.s

А теперь покажите мне

self-modification code в реализации на С, Java, или Васик

Саныч

2 РТО

>как узнал что я был в Целинограде то бишь Астане? у шайтан! Тока я там не в массы нес знания, а в очень-очень ограниченный круг энтерпрайз заказчиков... типа элита ИТ сообщества Казахстана

А я теперь все про Вас знаю, следим за элитой ИТ сообщества России :)

>Понятно - ПТУшники не изучают теорию алгоритмов и программирование как математическую дисциплину. понятие программы и алгоритма им неведомо... они в высоких сферах летают... пыхнут и летают...

Да, Вы правы, систематически, в рамках академических курсов не изучал.

Вот накоплю денег и куплю себе Кнута, небось когда Вы учились

он раз в десять дешевле стоил.

Но "знание некоторых общих принципов, позволяет избежать знания

массы деталей".

Вот возьмите мозг, даже не человека, а насекомого, тоже ведь

вычислитель в своем роде. Можете описать в терминах теории

"алгоритмов и программирование" как он работает ?

Без привлечения биофизики, биохимии, бионики и еще десятка смежных

дисциплин.

>Наркотики очень вредны для молодого организма - особливо на мозг

Не, это не про меня, я веду практически здоровый образ жизни, даже

физкультурой занимаюсь.

Саныч

2 MrBool

>Все, интерпретировать результаты не берусь :)
>Комментарии ?

Блин, ну ты и прооптимизировал ;)

-O3 -mcpu=i386 -fomit-frame-pointer -fexpensive-optimizations
-O3 -mcpu=i686 -fomit-frame-pointer -fexpensive-optimizations
-O6 -mcpu=i686 -fomit-frame-pointer -fexpensive-optimizations


Кто бы еще и на AMD прогнал :)

--------------------------------------------

Результат абсолютно одинаков с просто -О3

2 Саныч 

Ясно, школьник.
Спорить с тобой смысла нет. Абсолютно неинтересно доказывать
азбучные истины. Подучись немного, потом вернемся к этому вопросу.
:)

Абсолютно не хочу обидеть. Сам таким был. Пока не докажут не верил.
Просто кто-то это обязан делать (преподаватели), а я нет. Лень-с :)

to ignite :

>Результат абсолютно одинаков с просто -О3

Хм, странно. Если не влом пришли все 3 варианта сорцов на
mr.bool@rambler.ru

Че-то мне не верится... :)

2 ignite

>2 Саныч

Ясно, школьник. Спорить с тобой смысла нет. Абсолютно неинтересно доказывать азбучные истины. Подучись немного, потом вернемся к этому вопросу. :)

Какие азбучные истины Вы тут доказали ?

Спросил как прогр. на асме без jmp а

Вы привели кучу кода именно с jmp.

Или Вы доказали, что теорема Бома и Джакопини справедлива ВСЕГДА ?

Во все времена, на веки вечные и при любых условиях ?

Мировая константа, истина в последней инстанции ?

Саныч

2 MrBool :

>>Результат абсолютно одинаков с просто -О3

>Хм, странно. Если не влом пришли все 3 варианта сорцов на
>mr.bool@rambler.ru

Уже


>Че-то мне не верится... :)

Мне тоже - а что делать :)

2 Саныч

Или Вы доказали, что теорема Бома и Джакопини справедлива ВСЕГДА ?

Во все времена, на веки вечные и при любых условиях ?

Мировая константа, истина в последней инстанции ?

----------------------------------------------------------

Любая теорема (доказанная) справедлива (истинна) всегда.
Вообще ВСЕГДА. И вообще ВЕЗДЕ. МИРОВАЯ КОНСТАНТА :)

Потому как теорема - это логическое утверждение в форме
импликации A -> B. Читается "если А то В". Такая импликация ложна
только в том случае, если из истинной посылки следут ложный вывод.

Вернемся к Евклидовой геометрии. Теорема в данном случае 
формулируется примерно так: "если верны утверждения а, б, ... 
(аксиомы евклидовой геометрии), то истинны утверждения x, y, z 
(все стройное здание евклидовой геометрии)". Сие утверждение -
теорема, теория ВЕРНО. Век назад, сейчас и ВЕЧНО.

Если ты применишь теорию к неверным исходным данным и получишь
неверный результат - ТЕОРИЯ ОСТАЕТСЯ ВЕРНОЙ. Она может быть
НЕПРИМЕНИМОЙ в данном конкретном случае, но верной и истинной
останется невечно.

Применительно к goto и теореме о его необязательности.

Теорема звучит так: "если есть алгоритмические конструкции:
последовательность, цикл, альтернатива - то с помощью них
можно записать любой алгоритм".

Ты кричиш - а как же в асме - там же нету ни циклов ни...

Ну и как твой крик соотностися со справедливостью теоремы 
(хинт - вспомни о посылках - "есть...") ???

Разъясню мои примеры с jmp и asm.
Можешь представить себе не просто asm а макро ассемблер ?
Тогда запиши приведенные конструкции в виде макросов while, if
и так далее. Вот теперь ТЕОРЕМА тебе гарантирует, что ты сможешь
реализовать любой алгоритм с помощью только этих макросов, без
всяких jmp.

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

Вдогонку
Про Евклидову геометрию и геометрию Лобачевского.

По Евклиду параллельные прямые не пересекаются, это одна из
аксиом этой теории. То есть теория не отвечает на вопрос, пересекаются
ли параллельные прямые. Она отвечает на вопрос, что следует из
того, что параллельные прямые не пересекаются.

А вот если принять что пересекаются (заменили одну из аксиом), то
получим совсем другую теорию (утверждение) - геометрию Лобачевского.

С точки зрения истинности они никак друг с другом не связаны.


Ну вот, разъяснил таки азбучные истины :)

>Любая теорема (доказанная) справедлива (истинна) всегда. Вообще ВСЕГДА. И вообще ВЕЗДЕ. МИРОВАЯ КОНСТАНТА :)

Нифига, всегда нужно указывать условия в которых эта теорема/теория

справедлива.

А теперь скажи справедливы ли теоремы Евсклида в НЕ Евклидовом

пространстве.

"Пространство не Евклидово, хер знает чье оно..."

Саныч :)

2 Саныч

Все, надоело. Не хочешь понимать - не надо.

Всего хорошего :)

2 Саныч: дык может все-таки лучше снова про абелевы группы, тензоры, спиноры?

2 Саныч: я когда учился Кнута было невозможно купить вообще... только в библиотеке - в читальном зале... приходишь с тетрадочкой и умные мысли в нее переносишь из книг великих гуру... потом идешь на лекцию к преподавателю, который читает таки академический курс по программированию... после этого многие вопросы снимаются - нужен там готу или нет и когда...
Уже потом я смог за бешенные по тем временам деньги (типа месячная зарплата моего папы) купить с рук старый трехтомник чтоб был дома...
потом уже вышло новое издание - я был один из первых, кто разместил заказ в Интернете на эти книжки... да и не так уж и дорого они стоят... для физика-то-ядерщика

to All:

Вы что охренели ?!
Пересекаются параллельные !
Специалисто фиговы.

RTFM - Параллельные прямые по определению не пересекаются.

Евклидова геометрия:
Аксиома параллельности:
Через заданную точку можно провести не более, чем одну прямую,
паралельную данной.

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

Знатоки блин.

ARia

Correction:
Вместо Не-Евклидова геометрия следует читать геометрия Лобачевского

ARia

2 ARia

Согласен, старею :)