Рассуждения о том, что паскаль мёртв и как надо сдавать ЕГЭ

#41

У начинающего падавана.

#42

Ну, это не программирование. В интернете много такого - задачки с подвохом. Это другой жанр.

#43

Без компьютера сложновато будет решать. Но и без мозгов тоже не выйдет.

Во-первых, если n делится на m, то 2n делится на 2m, то есть если удвоить делитель половины числа, то получится чётный делитель всего числа. Кроме того, если p делится на k и k чётное, то и p тоже чётное и кроме того p/2 делится на k/2. То есть, вопрос сводится к тому, сколько существует чисел от 22500000 до 25000000 у которых ровно 28 делителей (включая 1 и само число).

Само число 28 можно представить в виде произведения вот такими способами: 28=28=2*14=4*7=2*2*7, соответственно нужные числа должны иметь одну из форм, где p, q и r — простые числа:

  • p^27, хотя таких в нужном интервале нет, потому что даже 2^27 уже больше чем 25 млн;
  • p*q^13, такие числа уже есть, причём q может быть только 2, так как для q=3 единственное подходящее в интервал 15 не является простым, под эту форму подходит всего 37 чисел, так как между 2747 и 3051 (22.5 и 25 млн соотвественно делить на 2¹³) всего 37 простых;
  • p^3*q^6, здесь опять q может быть только 2, так как при q=3 в нужном интервале нет ни одного простого, значит всего два числа этой формы: 22906304 и 24897088;
  • p*q*r^6, а здесь r не может быть больше 17, но подходящие числа есть только для r=11 (24801854 = 2 * 7 * 11⁶) и меньше, но как раз для этого случая всё равно придётся писать программу, которая находит числа, имеющие ровно два простых делителя не равных r на интервалах вида [2.25e7/r⁶; 2.5e7/r⁶] для каждого r из {2, 3, 5, 7, 11}.

В общем тут проще просто перебрать всё подряд, перебор занимает 5 минут на моём компьютере. Это долго, но для экзамена приемлемо, так как пока идёт перебор, никто не запрещает решать следующие задачи:

$ time ./even_divisors
final countdown: 7352

real	5m12.506s
user	5m9.888s
sys	0m0.346s

Код такой:

Program even_divisors;
var i, j, r, c, cc: longint;
begin
	cc:=0;
	for i:=22500000 to 25000000 do begin
		r:=trunc(sqrt(i));
		if r*r=i then
			c := -1
		else
			c := 0;
		for j:=1 to r do begin
			if (i mod j) = 0 then
				c := c+2
		end;
		if c = 28 then begin
			{writeln(i*2);}
			cc := cc + 1
		end
	end;
	writeln('final countdown: ', cc)
end.

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

#44

Я не понял, задание 5 минут выполнялось?

#45

Что тут не понятно? Я же вывод команды time привёл. Программа выдаёт результат через 5 минут 12 секунд после запуска.

#46

Ага… а .NET по-Вашему дольше будет работать?

изображение
изображение657×663 42.4 KB

В общем, если и дальше будете глупости писать, “отберу у Вас и погремушку, и соску” (с)

#47

У вас компьютер намного быстрее, чем у меня, так что сравнение по общему времени выполнения программы вообще ни о чём. К тому же, я сказал “этот же код”, а у вас другой код. Так что дважды ни о чём.

#48

Ну запустите у себя этот код. Сверьтесь по времени.

## uses School;
var o := new StopWatch;
o.Start;
(45000000..50000000)
  .Select(t -> t.Divisors)
  .Where(t -> t.Where(u -> u.IsEven).Count = 28)
  .Count
  .Println;
o.Stop;
Print(o.Elapsed)

Неужели непонятно, что никогда код на FPC не обгонит код LINQ уже хотя бы потому, что LINQ использует глубоко оптимизированные C++ библиотеки?

#50

Запустил в PascalABC.net IDE. Получилось 22 минуты и две секунды. Но это уже другой компьютер, так что другой код тоже надо заново измерять.

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

#51

Что? 22 минуты? Вы что, на виртуальной машине запускали с 1 Мб памяти?

И второе. Для чего мне заведомо худший код запускать у себя? Чтобы посмотреть, как РАВС моделирует FPC? Так понятно, что моделирование всегда хуже оригинала. Но совместимость сделана не для того, чтобы в РАВС работать вместо FPC, а чтобы при необходимости перенести программу в РАВС и переписать ее архаичный код на современный.

Ну да ладно. Попробовал Ваш код.

final countdown: 7352
00:00:25.1055818

Дольше в два с лишним раза.

#52

Ну как для чего. Вот предствьте, что вы хотите сравнить насколько быстрее или медленней выполняется программа, собранная с -O2 или -O3, чем без оптимизаций, вы что будете разный код сравнивать? Сравнение имеет смысл только если запускается один и тот же код, в одних и тех же условиях, за исключением ровно одного параметра (например разные компиляторы). А если сравнивать на разных компьютерах в разных ОС, разных компиляторах одновременно, то сравнение становится вообще бессмысленным.

Кстати пока вы спорили, мой оригинальный код в PascalABC.net IDE (добавил только код таймера скопированный из вашего примера) завершился за 7 минут и 40.453 секунд, то есть в три раза быстрее чем этот ваш LINQ.

Сейчас ещё в fpc на том же компе надо проверить.

#53

У меня есть сравнение результатов на моем компьютере и я его привел. Что там у Вас получается и на каких вёдрах Вы код запускаете - мне неинтересно.

#54

Ну увидели. А выводы какие?

Ну вот у меня почему-то обгоняет, причём почти в три раза. Правда у меня наверное версия .NET другая.

Почему заведомо худший? Даже в PascalABC.net мой код показал лучший результат чем ваш на моём компьютере. Ну, может, я где-то ошибся с измерениями, поэтому сейчас перепроверил. В первый раз я несколько раз в фоне запускал разные программы, сейчас пробую закрыть всё кроме консоли с этой программой и не трогать компьютер, пока идёт измерение. Сейчас получилось 21:55 для вашего кода (код с таймером закомментирован, измерение времени производилось с помощью внешней утилиты timeit)

Это просто самый обычный код на паскале. Никто ничего не моделирует.

Ну, кстати, оказалось, что для данной конкретной программы не настолько хуже, как я ожидал. На ABC 7:36, на FPC 7:28, на этот раз код один и тот же, измерение внешней утилитой. Хотя, надо перепроверить с другими опциями оптимизации. Кстати у pabcclear есть какие-нибудь опции оптимизации?

Хорошо. А как вы объясните, что на моём компьютере LINQ стабильно медленнее нормального кода?

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

#55

Когда я вижу Ваше значение 22 минуты вместо моих 12 секунд, т.е. замедление в 110 раз, я понимаю, что говорить тут не о чем.

#56

А вы чего от компа 20-летней давности ожидали, который и в своё время был не самым топовым?

Хотя, могу предположить, что этот ваш LINQ, видимо, умеет автоматически распараллеливаться на несколько потоков, иначе такой разницы в скорости даже с учётом вышесказанного не должно быть. Современные компы может и быстрее 20-летних, но не настолько же.

#57

Вот именно поэтому я не вижу смысла ориентироваться на железо 20-летней давности.

#58

Вот как сами думаете, на ЕГЭ будет у школьника современный топовый комп или всё-таки что-то больше похожее на мою тестовую машину?

Как видим, хоть LINQ и умеет распараллеливаться, но производительность его в рамках каждого отдельного потока так себе. А вы можете для более объективного сравнения сделать так, чтобы версия программы с LINQ занимало только один поток? Тогда наверное и на вашем компе мой код окажется раза в 2-3 быстрее.

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

#59

А Вы запускаете по shift-F9 с выключенным Debug?

Для сравнения производительности может быть интересной статья

#60

изображение
изображение1277×50 9.27 KB

#61

При первом замере нажимал на зелёный треугольник на панели инструментов и использовал код для таймера из фрагмента выше, при втором убрал этот код из обоих версий и компилировал в консоли через pabcclear с единственной опцией с указанием файла с исходником, а время измерял через timeit. Все замеры делались на ноутбуке 20-летней давности с Windows XP.

Так зачем эта задача была задана в итоге? Ну я показал, что её вполне можно решить, пользуясь только fpc на Windows. Или цель была какая-то другая?