Программирование глазами (и руками ) гуманитария. Личный опыт. Немного философии

[VGrabko]

раз пять перечитал и не понял о чём статья

[ripatti]

Автор же написал, что гуманитарий. Так и должно быть.

[fishca]

Думаю вся соль здесь:

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

Многим техническим текстам этого не хватает и они напоминают сухари с изюмом вместо сдобных булочек с изюмом.

[azsx]

О том, что лирик всех физиков победил и переписал алгоритм в 5 раз быстрее, чем в учебнике.

[S_A]

Я так понял о том, что код на С быстрее рекурсии на awk.

[KyHTEP]

Си, амиго, — это фантастика! )

[FForth]

С рекурсией в разных языках (и реализциях их) не всегда всё так однозначно и некоторый Форт, например, может опередить некоторый Си (например на тесте поиска чисел Фибоначи) в силу более «присособенности» для рекурсивных алгоритмов.

P.S. Неплохая подборка примеров рекурсивных алгоритмов на разных языках на rosettacode.org

[FForth]

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

P.S. Некоторым Форт программистам не чужды и литературные таланты, а каким то «гуманитариям» и Форт программирование,
вплоть до «экспериментов» в лингвистической области.

[dcc0]

Спасибо. Прочитал. Да, наверное, Си — это коллективная игра.

[Yuriandryu]

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

[fishca]

так вроде не из песочницы?

[Yuriandryu]

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

[Yuriandryu]

https://m.habrahabr.ru/post/151091/

[UA3MQJ]

У меня на десяти знаках программа не заканчивает свою работу ни через минуту, ни через десять.

[dcc0]

Я сумел протестировать только на одной машине, в разных ОС — WIN7 64x и Llinux (Gentoo) 64x.
Я вам скажу, что под WINDOWS генерация намного дольше.
Есть еще момент, который я забыл оговорить в статье: подозреваю, что конструкция второго цикла не совсем верная.
Честно скажу, я не знаю, можно ли так писать в Си a[i] > a[i-1], так как при i=0 i-1 в массиве нет.

[kosmos89]

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

>под WINDOWS генерация намного дольше
расскажите лучше, чем компилировали под линукс и виндовс и с какими настройками.

[dcc0]

> Выход за пределы массива, конечно, приводят к плачевным результатам.
Подозревал, но очень не хотелось добавлять проверок.

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

[dcc0]

В общем под Windows Dev C++ 4.9.9.2
Параметры компилятора — Default compiler, а это видимо gcc, т.к. он стоит первым в списке в программах.
Оптимизации, видимо, нет.

[dcc0]

Немного поэкспериментировал, добавил funroll-loops, почитав вот эту статью:
https://habrahabr.ru/company/intel/blog/167417/
Не знаю, насколько актуальны там рекомендации ( + еще пару опций относящиеся к циклам ).
Результат для n=10
real 0m8.963s
user 0m1.210s
sys 0m2.850s

[dcc0]

Вообще массив и отрицательный, тут в самом конце интересно
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

[kosmos89]

Валидна арифметика с указателями. т.е. адрес элемента будет посчитан корректно, но это вовсе не значит что он действительно на что-то валидное указывает.

>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 аргументы. Если на платформе используется дополнительный код, то с большой вероятностью это будет работать корректно, однако это не значит, что сработает на другой.

[dcc0]

Да, спасибо. Интересно. Нашел что-то похожее.
Сейчас еще раз посмотрел в алгоритм и подумал, что, возможно, проблема решается очень просто — перед этим циклом установить i=1. Сейчас только проверю не сбивается ли алгоритм.

[dcc0]

Да, все верно, i =0 можно махнуть на 1 и тогда i-1 в крайнем случае будет указывать на 0 индекс, сейчас отредактирую код.

[vlad9486]

Автору: функция revstring (да и любая другая) может перевернуть строку с любым именем, если тип тот же самый.

[dcc0]

Да, да. Спасибо. Я про функции еще буду перечитывать, так как не все осело. Я когда тренировался, видимо, где-то ошибся, получил не тот результат и чтобы сильно не мучить учебник в тот момент просто продублировал функции. Тем более что первая выполняется один раз.
Там по идее и в первом цикле сравнение строк можно заменить предпосчитанным факториалом.

[hd_keeper]

Под Windows медленнее, так как там тормозит вывод на консоль.

[dcc0]

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

[dcc0]

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