- 01
- 02
- 03
- 04
- 05
- 06
- 07
- 08
- 09
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
program Project42;
{$APPTYPE CONSOLE}
uses
SysUtils, Math;
const
Radix = 10;
function čòũʼnť(N: Integer): Integer;
begin
Result := 0;
while N > 0 do
begin
N := N div Radix;
Inc(Result);
end;
end;
function count(N: Integer): Integer;
begin
// Result := Ceil(LogN(Radix, N)); { slow! }
Result := Ceil(Log10(N));
end;
function rdtsc: Int64;
asm
rdtsc
end;
var
I: Integer;
t0: Int64;
const
N = 100500;
begin
try
Assert((count(42) = čòũʼnť(42)) and (count(100500) = čòũʼnť(100500)));
t0 := rdtsc;
for I := 1 to N do
čòũʼnť(Random(MaxInt + 1));
Writeln('naïve: ', rdtsc - t0, ' ticks');
t0 := rdtsc;
for I := 1 to N do
count(Random(MaxInt + 1));
Writeln('prőper: ', rdtsc - t0, ' ticks');
Writeln(StringOfChar('-', 42));
except
on E: Exception do
Writeln(E.ClassName, ': ', E.Message);
end;
if DebugHook <> 0 then
begin
Write('any big key to exit...');
Readln;
end;
end.
{ http://imgs.xkcd.com/comics/haiku_proof.png :-P }
Follow us!
WTF?
К тому же, во-первых, не O(N), а O(log(N)) (можно сделать и O(log(log(N)))), во-вторых, иногда таки O(1) > O(log(N)).
по копрометрической шкале Шайзе-Каковского в код попугайчик насрал, как минимум
здесь N -- кол-во [десятичных] разрядов, не абсолютная величина, чтобы не морочить себе голову с основанием логарифма
Потому что константное время лучше, чем время, зависящее от данных.
Для 64 бит логарифм может просто не работать.
ORLY? После минимума правки оба варианта будут работать с 19 десятичными разрядами. Что значит "может"?
(как известно, дельфи прибит гвоздями к интелу)
У log10 в сигнатуре real, double или extended (или как оно там обзываются)? Потеря точности тут.
Только что заметил грубую ошибку -- count(9)=1.
Extended, естественно, так что в мантиссу влезет
~1100 тактов занимает 19 раз 2^63-1 поделить на 10
else if пишется на одной строке.
Не ёлочка, а баобаб. ;) Почти сбалансированное дерево.
if( n < 1000)return 3
else if(n < 10000)return 4
else return 5;
else if - это как в других языка готовая конструкция elsif!
почему Random(MaxInt + 1)? давайте, чтоб было одинаково.
вот именно, ч.т.д. :-)
не понял, где неодинаково? +1 чтобы покрыть весь диапазон неотрицательных целых [0,MaxInt], а не [0,MaxInt)
в первом случае могут одни попасться, во втором — другие.
P.S Посмотрел щас, здесь 100500 вариантов, так что может и не надо.
Да, мне этого в Дельфях не хватает иногда...
можно пруф?
Только там не в 15, а в 16 раз.
Вообще, хороший пример - ТеХ, автор которого, в отличие от Билли сам ПЛАТИЛ пользователям за обнаруженные ошибки.
Да да да, я знаю, это всё упоротые пасквилянты по ссылке развлекаются.
студентом, который пишет для журнала "хакер"?
я совершенно не паскалефоб (из всех языков я только VB и php нелюблю, может javascript еще), просто при таком количестве кода и написанных на нем операционках -- си смешно хоронить)
да и прикладная разработка (которая безусловно уходит от си) идет явно не к дельфи))
Но вообще лучше бы си не рождался - его распространение связано скорее с интеллектуальным онанизмом (зацените, на каком крутом языке я прогу написал), чем с практической полезностью.
паскаль более жесток в типизации, а следовательно налажать в нем в сложнее.
распостранение си связано с тем, что на нем написаны самые популярные оси))
По надёжности уберСи сливает недоПаскалю, и ничего с этим не сделать.
Говноёбы вот вообще паскаль не осилили (у них до сих пор его упоминание вызывает боль), они любят си ебать. Логично.
стройность и логичность паскаля дает ему плюсы при обучении (не даром он считается лучшим языком для обучения), но на практике эта стройность может быть и не нужна (Вам же не нужен GC). Человек, который 15 лет писал на сях скорее всего будет на них нормально писать, даже несмотря на все изъяны).
> и опасная тенденция: распространение C-образных языков.
Ахаха, автора, автора на сцену!
у него сегодня 5 уроков.
зы: хакер -- это правильный журнал для чтения конечно
Верить серьёзному аналитическому журналу? Да, конечно, там ведь не обманывают своих малолетних читателей.
а паскаль -- что бы паскалефобов позлить?
Пока N махонькое -- O(N) может быть даже быстрее O(1). Потом N вырастет и сюрприз-сюрприз. Ваш КО.
логарифм медленнее чем X делений, найти X, заморока же
я имел ввиду не ванильный паскаль, а тот, что делал борланд и называл его турбо паскалем (или борланд, в более полной версии).
>> В Паскале нет модулей — они взяты из языка Модула
погодите, в классическом паскале нет модулей? Тоесть вся программа -- один модуль?
зы: я имел ввиду -- зачем багминот свой пример именно на паскале написал
Нету там ничего, кроме Program. Получается, что одна программа — один модуль.
В Турбо Паскале до четвёртой версии не было модулей (но, кажется, можно было прилинковывать обжи), зато можно было получать ортодоксальный com-файл. А для TP 4.0, в котором появились-таки модули, энтузиасты уже написали TPU2OBJ.
а как же мне код реюзать?
иклудить его в момент компиляции и компилировать каждый раз?
и никакого аналога runtime lib нет?
а всякие writeln откуда берутся?
типа того
writeln и проч. встроены в язык. Это у Си такое новшество было -- что все стандартные функции вынесены в библиотеки.
мне казалось что линковка -- святое дело в любом языке
оказывается -- нет)))
спасибо.
про стуктуры и алгоритмы
собственно Вирт и создал паскаль, и как бээ логично, что в своих книгах, он его юзает пропагандирует
== - обыкновенная халтура языка Си, которой нет среди математических обозначений и которая призвана что-то придумать для оператора сравнения, когда = уже занято.
и словить варнинг
нет?
А если мне действительно надо написать if (i=j)?
Отрубать предупреждения?
Вот если я напишу if (i:=j) то тут всё понятно.
Нефиг такое писать в if'е. А если и требуется присваивание, то и сравнение какое-то присутствует. Например:
То есть (i:=j) уже имеет булев типа.
> Нефиг такое писать в if'е.
Давно бы запретили.
Тогда добавить явную булеву константу:
Вот тут уже ==true как бы и не ГК, как в большинстве случаев.
здраствуй похупэ со его $a === true
Не нравится ==true ? напиши >false :)
Читайте как делаются компиляторы.
= и ==
==============
Первый схалтурил, вторые — нет.
Офигенная разница.
:= означает «присвоить», как и в Паскале.
= означает «решить уравнение», как в функциональных языках. Да, в метафонте есть специальное значение переменной «не определено», относительно такой переменной уравнение и решается.
У меня логарифм оказался быстрее деления, в полтора раза.
ага, примерно так и есть (сильно зависит от твиков при сборке, но добро матан всегда побеждает)
для семизнаков быстрее деление, для восьмизнаков - логарифм.
кстати, для отрицательных чисел и 0 не работает, но, видимо, оно и не требуется.
А ещё рандом тоже время неплохо кушает.
Всё ждал, заметит ли кто.
Логарифм в 2-5 раз медленнее при полной оптимизации. Если вычесть время на рандом -- вообще на порядок.
хехе