Pull to refresh

Comments 28

раз пять перечитал и не понял о чём статья
Автор же написал, что гуманитарий. Так и должно быть.
Думаю вся соль здесь:
А дальше, простите, я допил холодный чай, который простоял на столе 2 часа, утёр свисающую соплю и нажал Enter, так я запустил свой только что откомпилированный код и, конечно же, откинулся на спинку стула, приготовившись ждать минут пять, когда моё чудо сгенерирует все перестановки для n = 10

Многим техническим текстам этого не хватает и они напоминают сухари с изюмом вместо сдобных булочек с изюмом.
О том, что лирик всех физиков победил и переписал алгоритм в 5 раз быстрее, чем в учебнике.
Я так понял о том, что код на С быстрее рекурсии на awk.
Си, амиго, — это фантастика! )
С рекурсией в разных языках (и реализциях их) не всегда всё так однозначно и некоторый Форт, например, может опередить некоторый Си (например на тесте поиска чисел Фибоначи) в силу более «присособенности» для рекурсивных алгоритмов.

P.S. Неплохая подборка примеров рекурсивных алгоритмов на разных языках на rosettacode.org
Может быть подразумевался некоторый «посыл» схожий с первым сообщением такой темы из Форт форума
Форт — игра?

P.S. Некоторым Форт программистам не чужды и литературные таланты, а каким то «гуманитариям» и Форт программирование,
вплоть до «экспериментов» в лингвистической области.
Спасибо. Прочитал. Да, наверное, Си — это коллективная игра.
Чего только не напишешь, чтобы из песочницы выйти. Простите, но это моё мнение. Полезной информации статья не несёт. Примерно с тем же успехом могу описать свой сегодняшний поход в продуктовый магазин.
так вроде не из песочницы?
Не заметил, но сути не меняет. Я думаю статья ориентировалась вот на эту статью, которая более полезная.
У меня на десяти знаках программа не заканчивает свою работу ни через минуту, ни через десять.
Я сумел протестировать только на одной машине, в разных ОС — WIN7 64x и Llinux (Gentoo) 64x.
Я вам скажу, что под WINDOWS генерация намного дольше.
Есть еще момент, который я забыл оговорить в статье: подозреваю, что конструкция второго цикла не совсем верная.
Честно скажу, я не знаю, можно ли так писать в Си a[i] > a[i-1], так как при i=0 i-1 в массиве нет.
>можно ли так писать
Выход за пределы массива, конечно, приводят к плачевным результатам. Не делайте так.

>под 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++, чуть позже напишу версию

В общем под Windows Dev C++ 4.9.9.2
Параметры компилятора — Default compiler, а это видимо gcc, т.к. он стоит первым в списке в программах.
Оптимизации, видимо, нет.
Немного поэкспериментировал, добавил funroll-loops, почитав вот эту статью:
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
Валидна арифметика с указателями. т.е. адрес элемента будет посчитан корректно, но это вовсе не значит что он действительно на что-то валидное указывает.

>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 =0 можно махнуть на 1 и тогда i-1 в крайнем случае будет указывать на 0 индекс, сейчас отредактирую код.
Автору: функция revstring (да и любая другая) может перевернуть строку с любым именем, если тип тот же самый.
Да, да. Спасибо. Я про функции еще буду перечитывать, так как не все осело. Я когда тренировался, видимо, где-то ошибся, получил не тот результат и чтобы сильно не мучить учебник в тот момент просто продублировал функции. Тем более что первая выполняется один раз.
Там по идее и в первом цикле сравнение строк можно заменить предпосчитанным факториалом.

Под Windows медленнее, так как там тормозит вывод на консоль.
Неожиданно ваша правда.
Если убрать вывод, то для 12-ти символов время работы 2 минуты 38 секунд под Windows.
И без вывода под Linux: real 3m30.775s.

Но есть и приятный момент по поводу тестов.
Простейшая рекурсивная реализация на 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.

Articles