Речь о первых стандартах ISO 7185:1983, ANSI/IEEE 770X3.97:1983. ИМХО по контексту понятно, что в этих моих примерах не предполагалось никакого переопределения.
История забавная, но надо учитывать, что она расказана участником, не обладающим полной информацией. М.б. действительно имел место случай тупой бюрократии и вопиющей бесхозяйственности. А может это случай неизбежных потерь, которые всегда будут в больших компаниях, как бы хорошо там не был настроен бизнес. Можно предположить в результате того, что
Их разработчик ушёл без предварительного предупреждения и никому не сообщил о состоянии проекта
концы пришлось искать гораздо дольше, чем предполагалось. Более того всех концов найти не удалось и что-то пришлось делать занаво. М.б. все эти недели велась большая напряженная работа в экстремальных условиях, которую автор не видел. Аналогичная не слишком редкая ситуация, когда заказывают такси, водитель ждет 1 час 20 мин. (и все это время крутится счетчик), а поездка занимает всего 20 мин. Бывает, когда такое оправдано.
read (n);
if n<>0 then
x:=y/n
else
write ('Error: invalid input');
Пример 2:
n := 3.14314;
if n<>0 then
x:=y/n
else
write ('Error: invalid input');
В примере 1 при внимательном пользователе код write ('Error: invalid input') не вызывается, но м.б. вызван, если пользователь промажет по клавише или нарочно введет ноль. В примере 2 код write ('Error: invalid input') не м.б. вызван.
Поэтому он мертвый и должен быть удален:
Я также хотел бы найти баг в первом томе «Фундаментальные алгоритмы». Может, и нашёл бы, но в местной библиотеке по какой-то причине имеются только тома 2, 3 и 4A.
ИМХО автору нужно купить у Кнута 1й том в электронном виде за свои шестнадцатеричные доллары ;)
Интересно: кто как оценивает тенденцию (м.б. своя оценка или оценка из сетки):
количество ЯП, пользующихся спросом в мире и РФ:
1) растет;
2) уменьшается;
3) в среднем стабилизировалось: примерно сколько старых ЯП теряют спрос — столько новых получают.
ИМХО прежде всего забыть ООП, согласно заголовку статьи, не реально, т.к. очень многие IDE имеют графические инструменты для создания GUI, и эти инструменты генерируют ОО код. Такие инструменты не интегрированные в IDE, не генерирующие кода, а только ресурсы, появились до широкого распространения ООП. В частности, ResEdit для классических Macintosh 68K. ООП окзалось очень удобным для генерации кода GUI. Про GUI у автора статьи нет ни слова.
Но ИМХО основная сомнительная посылка статьи:
структура данных определяет необходимый код
Сошлюсь на известную классическую книгу Вирта, не содержащую ООП:
Алгоритмы + структуры данных = программы
Об алгоритмах автор забыл? Умолчал?
Простое преобразование данных превращается в кучу неуклюжих взаимопереплетённых методов, вызывающих друг друга, и причина этого только в догме ООП — инкапсуляции.
Недавно в другом обсуждении писал про виртовкий (не ОО) Паскаль:
Простейшая инкапсуляция уже есть в записях (record). Далее понятие о наследовании приходит в таких простых примерах:
type
TCoord = record // координаты точки
x, y : integer
end;
TRect = record // прямоугольник
leftTop, RBot : TCoord;
end;
Но автор борется с ветряными мельницами — многие ЯП не настаивают на использовании ООП, как не настаивают на использовании записей (record) и IDE. Не хотите использовать визуальное средство разработки — чертите на бумажке окошки вашей программы, меряйте линейкой координаты и записывайте в ресурс в виде текста. Бывают случаи ограниченного использования ООП, из собственного опыта: для игрового бота взял интерпретатор Паскаля (Вирт и др.), написанный не в ООП, и приделал IDE, сделанное в ООП.
Если данные программы, например, хранятся в табличном, ориентированном на обработку данных виде, то можно создать два или более модулей, каждый из которых работает с той же структурой данных, но различным образом. Если данные разбиты на объекты с методами, то это больше невозможно.
Снова сошлюсь на свой опыт: ООП не мешает (а помогает) использовать столь нелюбимые автором графы в различных представлениях.
огромные спагетти-графы объектов, указывающих друг на друга, и методы, получающие огромные списки аргументов.
Давным давно для одного коммерческого проекта делал GUI на упомянутом Macintosh 68K под упомянутым ResEdit. Списки аргументов были гораздо больше, чем м.б. с применением ООП. Чтобы убедится достаточно посмотреть многотомниик Inside Macintosh тех лет — там много примеров.
Сочетание разброса данных по множеству мелких объектов, активное использование косвенности и указателей, отсутствие правильной архитектуры данных приводят к низкой скорости выполнения. Такого обоснования более чем достаточно.
Это не обоснование, а голословное утверждение. Необходимы примеры со сравнением времени выполнения.
Пожалуй единственная мысль, возникшая по прочтении этой статьи, с каковой мыслью согласен: при большом желании можно сделать очень плохой код, как с применением ООП, так и без.
Спасибо автору за хороший язык. Некоторые статьи на эту тему были написаны настолько «своеобразно», что уже боязно стало читать. Оказывается и на эту тему можно говорить нормальным языком.
procedure calc (start : integer);
var
i,j,p : integer;
doit : boolean;
begin
for i := 2 to n do
begin
if lp [i] =0 then
begin
lp [i] := i;
inc (prCount);
pr [prCount] := i;
end;
j:= 0;
repeat
doit := false;
inc (j);
inc (stepAll); // new place ------!!!!!!
if j<= prCount then
begin
p := pr[j];
doit := (p <= lp [i]) and (p*i<=n);
// inc (stepAll);
if doit then
begin
lp [p*i] := p;
inc(step);
end; // if doit
end // if j<= prCount
until not doit;
end;
end; //calc
— Sieve of Eratosthenes Line version 1.0.1d3
N= 1000
Time is 0 sec.
Found 168 primes.
stepAll 1830, step 831, stepAll-step=n-1 TRUE
— Sieve of Eratosthenes Line version 1.0.1d3
N= 10000
Time is 0 sec.
Found 1229 primes.
stepAll 18769, step 8770, stepAll-step=n-1 TRUE
— Sieve of Eratosthenes Line version 1.0.1d3
N= 100000
Time is 0 sec.
Found 9592 primes.
stepAll 190406, step 90407, stepAll-step=n-1 TRUE
— Sieve of Eratosthenes Line version 1.0.1d3
N= 1000000
Time is 0 sec.
Found 78498 primes.
stepAll 1921500, step 921501, stepAll-step=n-1 TRUE
— Sieve of Eratosthenes Line version 1.0.1d3
N= 10000000
Time is 0.108999735675752 sec.
Found 664579 primes.
stepAll 19335419, step 9335420, stepAll-step=n-1 TRUE
— Sieve of Eratosthenes Line version 1.0.1d3
N= 100000000
Time is 1.21899987570941 sec.
Found 5761455 primes.
stepAll 194238543, step 94238544, stepAll-step=n-1 TRUE
—
Кстати, в догонку к вашему комментарию про stepAll: добавьте, пожалуйста, вывод stepAll-step.
вывод stepAll-step
Sieve of Eratosthenes Line version 1.0.1d2
N= 1000
Time is 0 sec.
Found 168 primes.
stepAll 1819, step 831, stepAll-step=n-1 FALSE
— Sieve of Eratosthenes Line version 1.0.1d2
N= 10000
Time is 0 sec.
Found 1229 primes.
stepAll 18744, step 8770, stepAll-step=n-1 FALSE
— Sieve of Eratosthenes Line version 1.0.1d2
N= 100000
Time is 0 sec.
Found 9592 primes.
stepAll 190341, step 90407, stepAll-step=n-1 FALSE
— Sieve of Eratosthenes Line version 1.0.1d2
N= 1000000
Time is 0.0160002149641514 sec.
Found 78498 primes.
stepAll 1921332, step 921501, stepAll-step=n-1 FALSE
— Sieve of Eratosthenes Line version 1.0.1d2
N= 10000000
Time is 0.124999950639904 sec.
Found 664579 primes.
stepAll 19334973, step 9335420, stepAll-step=n-1 FALSE
— Sieve of Eratosthenes Line version 1.0.1d2
N= 100000000
Time is 1.203000289388 sec.
Found 5761455 primes.
stepAll 194237314, step 94238544, stepAll-step=n-1 FALSE
Оно всегда будет n-1
К сожалению, нет.
что еще там не понятно?
В вики не указаны размеры массивов — я сделал просто:
var pr : array [1..N] of integer;
lp : array [2..N] of integer;
К сожалению, у меня не было достаточно времени, чтобы все это обдумать, но т.к. заданы вопросы — отвечу предварительными впечатлениями.
если доказательство, которое я привел в другой ветке — не закончено, то я не знаю уже.
По доказательству произошла путаница в обозначениях: м.б. я сам запутался, а м.б. Вы меня запутали — с мат. точки зрения это не важно, важно, что ни я, ни другие участники обсуждения пока по Вашему доказательству категорически не высказались. Я думал, что может Вы внесете поправки, а Вы м.б. думали, что я сделаю указанные Вами замены:
Формально это не конфликт, но если хотите — в определении графа используйте вместо i, допустим u. И не забудьте, что ребра есть для всех составных u.
Но я перключился с теории на эксперимент. По первому впечатлению, как уже сообщил ранее, моя реализация работает согласно теоретической оценки. Но прежде, чем перейти к более детальному обсуждению, хочу напомнить, что авторитетные математики предостерегают о подводных камнях в практическом применении теории вычислительной сложности. М.б. мы имеем дело именно с таким непростым случаем. Т.к. речь идет о графах, ограничусь ссылкой: А.А. Зыков, Основы теории графов, М.: Вузовская книга, 2004, С. 9-10. В нашем более частном случае проблема состоит в следующем: как считать количество операций в цикле с предусловием:
while cond do something;
Нпр., если из n^2 обращений к этому циклу процедура something выполняется не более n раз? — М.б. считать только n вызовов something. Но, операции для расчета формулы условия cond выполняются n^2 раз.
Моя реализация обсуждаемого алгоритма (переделана из Листинг 2 в статье)
procedure calc (start : integer);
var
i,j,p : integer;
doit : boolean;
begin
for i := 2 to n do
begin
if lp [i] =0 then
begin
lp [i] := i;
inc (prCount);
pr [prCount] := i;
end;
j:= 0;
repeat
doit := false;
inc (j);
if j<= prCount then
begin
p := pr[j];
doit := (p <= lp [i]) and (p*i<=n);
inc (stepAll);
if doit then
begin
lp [p*i] := p;
inc(step);
end; // if doit
end // if j<= prCount
until not doit;
end;
end; //calc
Если смотреть выполнение условий внутреннего цикла, то счетчик step будет меньше n. Действительно по Вашему доказательству — больше n ребер в заданном графе быть не может. Но вот отношение stepAll/n растет следующим образом:
n=1000 stepAll/n=1.819
10000 1.874
100000 1.903
1000000 1.921
10000000 1.933
100000000 1.942,
т.е. с ростом n отношение stepAll/n увеличивается, что внушает сомнение в чисто линейной зависимости. Будет интересно выслушать комментарии, при этом напомню с чего начал — это предварительные впечатления.
Прелесть (кроме ассимтотики) этого алгоритма в том, что помимо простых чисел автоматом получается возможность быстро раскладывать на простые множители все числа до n.
на самом деле можно реализовать решето с помощью дерева
Можно. Реализуйте. А сообщество здесь обсудит, как Вам это удалось ;)
Есть более оптимальный по времени и памяти (не новый алгоритм, а доп. оптимизации). Ссылка
Эту ссылку уже приводили в этом обсуждении — воспользуйтесь поиском по странице.
Есть более оптимальный по асимптотике алгоритм на основе решета, который работает значительно быстрее не оптимизированного решета и примерно также, как оптимизированный + находит для каждого числа его наименьший простой делитель, но требует больше памяти.
И этот алгоритм здесь обсуждали. Работает он медленнеее и по асимптотике доказательство здесь не закончено. Более того эксперимент вызывает сомнения в оценке — я выложу позже результаты.
концы пришлось искать гораздо дольше, чем предполагалось. Более того всех концов найти не удалось и что-то пришлось делать занаво. М.б. все эти недели велась большая напряженная работа в экстремальных условиях, которую автор не видел. Аналогичная не слишком редкая ситуация, когда заказывают такси, водитель ждет 1 час 20 мин. (и все это время крутится счетчик), а поездка занимает всего 20 мин. Бывает, когда такое оправдано.
Пример 1:
Пример 2:
В примере 1 при внимательном пользователе код write ('Error: invalid input') не вызывается, но м.б. вызван, если пользователь промажет по клавише или нарочно введет ноль. В примере 2 код write ('Error: invalid input') не м.б. вызван.
Поэтому он мертвый и должен быть удален:
:)))
количество ЯП, пользующихся спросом в мире и РФ:
1) растет;
2) уменьшается;
3) в среднем стабилизировалось: примерно сколько старых ЯП теряют спрос — столько новых получают.
Но ИМХО основная сомнительная посылка статьи:
Сошлюсь на известную классическую книгу Вирта, не содержащую ООП:
Алгоритмы + структуры данных = программы
Об алгоритмах автор забыл? Умолчал?
Недавно в другом обсуждении писал про виртовкий (не ОО) Паскаль:
Но автор борется с ветряными мельницами — многие ЯП не настаивают на использовании ООП, как не настаивают на использовании записей (record) и IDE. Не хотите использовать визуальное средство разработки — чертите на бумажке окошки вашей программы, меряйте линейкой координаты и записывайте в ресурс в виде текста. Бывают случаи ограниченного использования ООП, из собственного опыта: для игрового бота взял интерпретатор Паскаля (Вирт и др.), написанный не в ООП, и приделал IDE, сделанное в ООП.
Снова сошлюсь на свой опыт: ООП не мешает (а помогает) использовать столь нелюбимые автором графы в различных представлениях.
Давным давно для одного коммерческого проекта делал GUI на упомянутом Macintosh 68K под упомянутым ResEdit. Списки аргументов были гораздо больше, чем м.б. с применением ООП. Чтобы убедится достаточно посмотреть многотомниик Inside Macintosh тех лет — там много примеров.
Это не обоснование, а голословное утверждение. Необходимы примеры со сравнением времени выполнения.
Пожалуй единственная мысль, возникшая по прочтении этой статьи, с каковой мыслью согласен: при большом желании можно сделать очень плохой код, как с применением ООП, так и без.
— Sieve of Eratosthenes Line version 1.0.1d3
N= 1000
Time is 0 sec.
Found 168 primes.
stepAll 1830, step 831, stepAll-step=n-1 TRUE
— Sieve of Eratosthenes Line version 1.0.1d3
N= 10000
Time is 0 sec.
Found 1229 primes.
stepAll 18769, step 8770, stepAll-step=n-1 TRUE
— Sieve of Eratosthenes Line version 1.0.1d3
N= 100000
Time is 0 sec.
Found 9592 primes.
stepAll 190406, step 90407, stepAll-step=n-1 TRUE
— Sieve of Eratosthenes Line version 1.0.1d3
N= 1000000
Time is 0 sec.
Found 78498 primes.
stepAll 1921500, step 921501, stepAll-step=n-1 TRUE
— Sieve of Eratosthenes Line version 1.0.1d3
N= 10000000
Time is 0.108999735675752 sec.
Found 664579 primes.
stepAll 19335419, step 9335420, stepAll-step=n-1 TRUE
— Sieve of Eratosthenes Line version 1.0.1d3
N= 100000000
Time is 1.21899987570941 sec.
Found 5761455 primes.
stepAll 194238543, step 94238544, stepAll-step=n-1 TRUE
—
N= 1000
Time is 0 sec.
Found 168 primes.
stepAll 1819, step 831, stepAll-step=n-1 FALSE
— Sieve of Eratosthenes Line version 1.0.1d2
N= 10000
Time is 0 sec.
Found 1229 primes.
stepAll 18744, step 8770, stepAll-step=n-1 FALSE
— Sieve of Eratosthenes Line version 1.0.1d2
N= 100000
Time is 0 sec.
Found 9592 primes.
stepAll 190341, step 90407, stepAll-step=n-1 FALSE
— Sieve of Eratosthenes Line version 1.0.1d2
N= 1000000
Time is 0.0160002149641514 sec.
Found 78498 primes.
stepAll 1921332, step 921501, stepAll-step=n-1 FALSE
— Sieve of Eratosthenes Line version 1.0.1d2
N= 10000000
Time is 0.124999950639904 sec.
Found 664579 primes.
stepAll 19334973, step 9335420, stepAll-step=n-1 FALSE
— Sieve of Eratosthenes Line version 1.0.1d2
N= 100000000
Time is 1.203000289388 sec.
Found 5761455 primes.
stepAll 194237314, step 94238544, stepAll-step=n-1 FALSE
К сожалению, нет.
В вики не указаны размеры массивов — я сделал просто:
Но можно экономнее.
По доказательству произошла путаница в обозначениях: м.б. я сам запутался, а м.б. Вы меня запутали — с мат. точки зрения это не важно, важно, что ни я, ни другие участники обсуждения пока по Вашему доказательству категорически не высказались. Я думал, что может Вы внесете поправки, а Вы м.б. думали, что я сделаю указанные Вами замены:
Но я перключился с теории на эксперимент. По первому впечатлению, как уже сообщил ранее, моя реализация работает согласно теоретической оценки. Но прежде, чем перейти к более детальному обсуждению, хочу напомнить, что авторитетные математики предостерегают о подводных камнях в практическом применении теории вычислительной сложности. М.б. мы имеем дело именно с таким непростым случаем. Т.к. речь идет о графах, ограничусь ссылкой: А.А. Зыков, Основы теории графов, М.: Вузовская книга, 2004, С. 9-10. В нашем более частном случае проблема состоит в следующем: как считать количество операций в цикле с предусловием:
Нпр., если из n^2 обращений к этому циклу процедура something выполняется не более n раз? — М.б. считать только n вызовов something. Но, операции для расчета формулы условия cond выполняются n^2 раз.
Если смотреть выполнение условий внутреннего цикла, то счетчик step будет меньше n. Действительно по Вашему доказательству — больше n ребер в заданном графе быть не может. Но вот отношение stepAll/n растет следующим образом:
n=1000 stepAll/n=1.819
10000 1.874
100000 1.903
1000000 1.921
10000000 1.933
100000000 1.942,
т.е. с ростом n отношение stepAll/n увеличивается, что внушает сомнение в чисто линейной зависимости. Будет интересно выслушать комментарии, при этом напомню с чего начал — это предварительные впечатления.
С этим полностью согласен.
Эту ссылку уже приводили в этом обсуждении — воспользуйтесь поиском по странице.
И этот алгоритм здесь обсуждали. Работает он медленнеее и по асимптотике доказательство здесь не закончено. Более того эксперимент вызывает сомнения в оценке — я выложу позже результаты.
Спасибо. Код в комменте выше.