Comments 28
раз пять перечитал и не понял о чём статья
Автор же написал, что гуманитарий. Так и должно быть.
Думаю вся соль здесь:
Многим техническим текстам этого не хватает и они напоминают сухари с изюмом вместо сдобных булочек с изюмом.
А дальше, простите, я допил холодный чай, который простоял на столе 2 часа, утёр свисающую соплю и нажал Enter, так я запустил свой только что откомпилированный код и, конечно же, откинулся на спинку стула, приготовившись ждать минут пять, когда моё чудо сгенерирует все перестановки для n = 10
Многим техническим текстам этого не хватает и они напоминают сухари с изюмом вместо сдобных булочек с изюмом.
О том, что лирик всех физиков победил и переписал алгоритм в 5 раз быстрее, чем в учебнике.
Си, амиго, — это фантастика! )
С рекурсией в разных языках (и реализциях их) не всегда всё так однозначно и некоторый Форт, например, может опередить некоторый Си (например на тесте поиска чисел Фибоначи) в силу более «присособенности» для рекурсивных алгоритмов.
P.S. Неплохая подборка примеров рекурсивных алгоритмов на разных языках на rosettacode.org
P.S. Неплохая подборка примеров рекурсивных алгоритмов на разных языках на rosettacode.org
Может быть подразумевался некоторый «посыл» схожий с первым сообщением такой темы из Форт форума
Форт — игра?
P.S. Некоторым Форт программистам не чужды и литературные таланты, а каким то «гуманитариям» и Форт программирование,
вплоть до «экспериментов» в лингвистической области.
Форт — игра?
P.S. Некоторым Форт программистам не чужды и литературные таланты, а каким то «гуманитариям» и Форт программирование,
вплоть до «экспериментов» в лингвистической области.
Чего только не напишешь, чтобы из песочницы выйти. Простите, но это моё мнение. Полезной информации статья не несёт. Примерно с тем же успехом могу описать свой сегодняшний поход в продуктовый магазин.
У меня на десяти знаках программа не заканчивает свою работу ни через минуту, ни через десять.
Я сумел протестировать только на одной машине, в разных ОС — WIN7 64x и Llinux (Gentoo) 64x.
Я вам скажу, что под WINDOWS генерация намного дольше.
Есть еще момент, который я забыл оговорить в статье: подозреваю, что конструкция второго цикла не совсем верная.
Честно скажу, я не знаю, можно ли так писать в Си a[i] > a[i-1], так как при i=0 i-1 в массиве нет.
Я вам скажу, что под WINDOWS генерация намного дольше.
Есть еще момент, который я забыл оговорить в статье: подозреваю, что конструкция второго цикла не совсем верная.
Честно скажу, я не знаю, можно ли так писать в Си a[i] > a[i-1], так как при i=0 i-1 в массиве нет.
>можно ли так писать
Выход за пределы массива, конечно, приводят к плачевным результатам. Не делайте так.
>под WINDOWS генерация намного дольше
расскажите лучше, чем компилировали под линукс и виндовс и с какими настройками.
Выход за пределы массива, конечно, приводят к плачевным результатам. Не делайте так.
>под WINDOWS генерация намного дольше
расскажите лучше, чем компилировали под линукс и виндовс и с какими настройками.
> Выход за пределы массива, конечно, приводят к плачевным результатам.
Подозревал, но очень не хотелось добавлять проверок.
Под Linux компилировал gcc (версия 4.6.3 p1.13) в командной строке указывал только входной и выходной файл
gcc -dumpmachine (если понимаю верно, то целевая архитектура) выводит:
x86_64-pc-linux-gnu
В make.conf
CFLAGS="-march=k8 -O2 -pipe"
CXXFLAGS="${CFLAGS}"
MAKEOPTS="-j6"
В use флагах ничего с процессором связанного вроде бы нет, хотя вроде это никак и не должно влиять.
А под Windows — это был Dev C++, чуть позже напишу версию
Подозревал, но очень не хотелось добавлять проверок.
Под Linux компилировал gcc (версия 4.6.3 p1.13) в командной строке указывал только входной и выходной файл
gcc -dumpmachine (если понимаю верно, то целевая архитектура) выводит:
x86_64-pc-linux-gnu
В make.conf
CFLAGS="-march=k8 -O2 -pipe"
CXXFLAGS="${CFLAGS}"
MAKEOPTS="-j6"
В use флагах ничего с процессором связанного вроде бы нет, хотя вроде это никак и не должно влиять.
А под Windows — это был Dev C++, чуть позже напишу версию
В общем под Windows Dev C++ 4.9.9.2
Параметры компилятора — Default compiler, а это видимо gcc, т.к. он стоит первым в списке в программах.
Оптимизации, видимо, нет.
Параметры компилятора — Default compiler, а это видимо gcc, т.к. он стоит первым в списке в программах.
Оптимизации, видимо, нет.
Немного поэкспериментировал, добавил funroll-loops, почитав вот эту статью:
https://habrahabr.ru/company/intel/blog/167417/
Не знаю, насколько актуальны там рекомендации ( + еще пару опций относящиеся к циклам ).
Результат для n=10
real 0m8.963s
user 0m1.210s
sys 0m2.850s
https://habrahabr.ru/company/intel/blog/167417/
Не знаю, насколько актуальны там рекомендации ( + еще пару опций относящиеся к циклам ).
Результат для n=10
real 0m8.963s
user 0m1.210s
sys 0m2.850s
Вообще массив и отрицательный, тут в самом конце интересно
http://stackoverflow.com/questions/3473675/are-negative-array-indexes-allowed-in-c/3473684#3473684
Надо будет повникать еще
http://unixforum.org/index.php?showtopic=135153&st=0&p=1244250&#entry1244250
http://stackoverflow.com/questions/3473675/are-negative-array-indexes-allowed-in-c/3473684#3473684
Надо будет повникать еще
http://unixforum.org/index.php?showtopic=135153&st=0&p=1244250&#entry1244250
Валидна арифметика с указателями. т.е. адрес элемента будет посчитан корректно, но это вовсе не значит что он действительно на что-то валидное указывает.
>char a[strlen(argv[1])];
>j=0;
>while(a[j] < a[i])
В вашем случае массив объявлен прямо тут на стеке и значит ничего перед a[0] нет. Значит вы будете читать из «чужой» памяти. А какое там значение будет — хрен знает. Может вообще упасть с ошибкой.
А вот такое, например, будет работать:
int a[10];
int * b = &a[5];
ASSERT(b[-1] == a[4], «Значения у них одни и те же»);
ASSERT(&b[-1] == &a[4], «Да и адреса тоже»);
ОДНАКО, я не уверен, что ПО СТАНДАРТУ будет работать отрицательный индекс. Потому что надо понимать, что (a — b) и (a + (-b)) — это не одно и то же. В первом случае чисто unsigned арифметика, а во втором signed. И надо убедиться, что оператор [] может принимать signed аргументы. Если на платформе используется дополнительный код, то с большой вероятностью это будет работать корректно, однако это не значит, что сработает на другой.
>char a[strlen(argv[1])];
>j=0;
>while(a[j] < a[i])
В вашем случае массив объявлен прямо тут на стеке и значит ничего перед a[0] нет. Значит вы будете читать из «чужой» памяти. А какое там значение будет — хрен знает. Может вообще упасть с ошибкой.
А вот такое, например, будет работать:
int a[10];
int * b = &a[5];
ASSERT(b[-1] == a[4], «Значения у них одни и те же»);
ASSERT(&b[-1] == &a[4], «Да и адреса тоже»);
ОДНАКО, я не уверен, что ПО СТАНДАРТУ будет работать отрицательный индекс. Потому что надо понимать, что (a — b) и (a + (-b)) — это не одно и то же. В первом случае чисто unsigned арифметика, а во втором signed. И надо убедиться, что оператор [] может принимать signed аргументы. Если на платформе используется дополнительный код, то с большой вероятностью это будет работать корректно, однако это не значит, что сработает на другой.
Да, спасибо. Интересно. Нашел что-то похожее.
Сейчас еще раз посмотрел в алгоритм и подумал, что, возможно, проблема решается очень просто — перед этим циклом установить i=1. Сейчас только проверю не сбивается ли алгоритм.
Сейчас еще раз посмотрел в алгоритм и подумал, что, возможно, проблема решается очень просто — перед этим циклом установить i=1. Сейчас только проверю не сбивается ли алгоритм.
Да, все верно, i =0 можно махнуть на 1 и тогда i-1 в крайнем случае будет указывать на 0 индекс, сейчас отредактирую код.
Автору: функция revstring (да и любая другая) может перевернуть строку с любым именем, если тип тот же самый.
Да, да. Спасибо. Я про функции еще буду перечитывать, так как не все осело. Я когда тренировался, видимо, где-то ошибся, получил не тот результат и чтобы сильно не мучить учебник в тот момент просто продублировал функции. Тем более что первая выполняется один раз.
Там по идее и в первом цикле сравнение строк можно заменить предпосчитанным факториалом.
Там по идее и в первом цикле сравнение строк можно заменить предпосчитанным факториалом.
Под Windows медленнее, так как там тормозит вывод на консоль.
Неожиданно ваша правда.
Если убрать вывод, то для 12-ти символов время работы 2 минуты 38 секунд под Windows.
И без вывода под Linux: real 3m30.775s.
Если убрать вывод, то для 12-ти символов время работы 2 минуты 38 секунд под Windows.
И без вывода под Linux: real 3m30.775s.
Но есть и приятный момент по поводу тестов.
Простейшая рекурсивная реализация на python, которую в комментариях к предыдущим заметкам мне привел тов. Shashkov
оказалась медленнее: для n=11
Real time: 4m30.566s
Простейшая рекурсивная реализация на python, которую в комментариях к предыдущим заметкам мне привел тов. Shashkov
оказалась медленнее: для n=11
Real time: 4m30.566s
Код
def perm_gen(n):
if n == 1:
yield [1]
else:
for row in perm_gen(n - 1):
for i in range(n):
yield row[:i] + [n] + row[i:]
for perm in perm_gen(4):
print(' '.join(map(str, perm)))
Sign up to leave a comment.
Программирование глазами (и руками ) гуманитария. Личный опыт. Немного философии