Мой скромной опыт программирования привел меня к мысли, что этот род деятельности может быть ценным сам по себе и не иметь конкретных практических целей. Безусловно программирование может приносить творческое удовлетворение и, может быть, кому-то своеобразное эстетическое наслаждение; в конце концов, в любой сфере люди жаждут видеть собственную гармонию. Я, когда-то давно, когда еще едва был знаком с программированием и даже плохо понимал значение слова функция применительно к написанию кода, пошутил, сказав, что программирование это искусство. Это была просто брошенная фраза за дружеским чайным столом. Кто-то подыграл мне, спросив, как я это могу доказать. Я ответил что-то вроде: «не зря же Дональд Кнут свою антологию назвал искусством программирования». А ведь он знает толк в этом.
В то время я относился к программированию, как к сухой трудно понятной мне науке, считая её смесью лингвистики и математики. Конечно, тогда я уже имел представление об HTML, но коды программ я видел только издалека и предпочитал держаться от всего этого подальше. Компьютер — это печатная машинка, энциклопедия, переводчик, иногда игрушка — вот, что такое компьютер для гуманитария, лет так 10-15 назад. Конечно, сюда еще можно включить работу с почтой, может быть, еще пару вещей, но основное назначение компьютера для гуманитария — быть печатной машинкой.
Однако все меняется, когда появляется потребность сделать сайт. Я не знаю, сколько гуманитариев трудится в сфере информационных технологий и сколько из них занимается программированием, но я точно уверен, — нашего брата к написанию кода приводит именно WEB. По крайне мере так было еще совсем недавно. Одного молодого филолога-php-программиста из Сибири я недавно встретил на форуме dapf.ru, и он такой, скорее всего, не единственный. Если копнуть глубже, то можно вспомнить, что создатель языка Perl Ларри Уолл, — у которого 27 сентября день рождения, — лингвист по образованию. Но вернусь к теме искусства.
Своё отношение к уже множество раз упомянутой деятельности в этой заметке я изменил после того, как чисто умозрительно попытался провести параллели между написанием кода и игрой в шахматы (или решением шахматных задач), а также теми эффектами, которые они приносят субъекту действия.
На мой взгляд, общего очень много. К программированию вполне возможно относиться как к своего рода игре, в которой есть место и хитрости, и психологии, и присущей только этой сфере магии. Возможно, о примерах этой магии и говорят опытные программисты, когда рассказывают о том, как получили в наследство код, который почти невозможно поддерживать, но он каким-то чудом работает?!
На мой взгляд, отношение к программированию как к игре, вероятно, может помочь преодолеть ряд психологических барьеров тем людям, которые считают написание кода уделом выпускников и студентов спецвузов. Новому поколению, правда, уже, наверное, не понять того, как наши родители еще лет 20 назад боялись нажать лишний раз не то сочетание клавиш. Теперь многое доступно, нет особенных страхов повредить домашний стационарный ПК, ибо у кого-то в запасе еще есть ноутбук, может быть, два, а под подушкой спрятан планшет. Одним словом — программировать можно не стесняясь…
Поскольку существенные этапы развития программирования прошли мимо меня, а мне всегда хотелось немножко заглянуть в эту сферу — отчасти из любопытства, отчасти в силу некоторых историко-научных интересов, — то я решил, пользуясь свободным временем, немножечко почитать учебник по языку Си Денниса Ритчи и что-нибудь закодировать, что-нибудь потестировать и что-нибудь с чем-нибудь сравнить, чтобы было веселее. Простите, что не буду оригинальным, так как я решил воспроизвести — с использованием стандартных библиотек Си — тот самый алгоритм перестановок, о котором уже писал ранее.
Код получился очень громоздким, так как я старался побольше функций реализовать самостоятельно. Собственно, написание данного кода и было для меня своего рода игрой, так сказать, наслаждением для разума.
Должен добавить, что я бы не стал тревожить сообщество Хабра своим «гуманитарным кодом», а просто опубликовал бы эту заметку без кода и вообще упоминания каких-либо алгоритмов, если бы не один довольно интересный момент: мой длиннющий код с достаточным количеством функций и циклов после компиляции на Linux-системе оказался крайне шустрым. Я даже полез по старым ссылкам, чтобы найти наиболее быстрые реализации на других языках.
По данной ссылке, в самом низу, рекурсивный алгоритм перестановок на awk, который помечен автором как наиболее быстрый.
Я решил сравнить скорость со своим учебным примером и, честно говоря, результаты меня удивили. Для n = 10 awk выдал вот такой результат: real time 1m16.770s (на всякий случай, машина: AMD Phenom T1100 6x)
То, что произошло дальше, с моей гуманитарной колокольни достойно литературного описания… А дальше, простите, я допил холодный чай, который простоял на столе 2 часа, утёр свисающую соплю и нажал Enter, так я запустил свой только что откомпилированный код и, конечно же, откинулся на спинку стула, приготовившись ждать минут пять, когда моё чудо сгенерирует все перестановки для n = 10. Но не тут-то было, скажу вам, моя спина к спинке прислониться только и успела, может быть, я еще успел почесать затылок, в общем, терминал выдал мне: real time 0m13.411s
Си, амиго, — это фантастика!
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
//This reverse x. Переворачиваем х
char revstring(char * x) {
int i = strlen(x);
int k=0;
char c;
while( i > k ) {
i--;
c=x[k];
x[k]=x[i];
x[i]=c;
k++;
}
}
//This cut x
char subb (char * x, int i) {
x[i]='\0';
}
//This cut y
char subb2 (char * y, int i) {
int k = 0;
while (k != strlen(y)+1) {
y[k]=y[i];
i++;
k++;
}
}
//It gets an argumet like 1234 or abcd. All symbols must be uniqe
int main (int argc, char *argv[]) {
if (argc < 2) {
printf("Enter an argument. Example 1234");
return 0;
}
char b[strlen(argv[1])];
char a[strlen(argv[1])];
int ij=0;
while (ij!=strlen(argv[1])) {
a[ij]=argv[1][ij];
b[ij]=argv[1][ij];
ij++;
}
a[ij]='\0';
b[ij]='\0';
revstring(a);
printf("%s\n", a);
int i;
int j;
char c;
while (strcmp (a, b) !=0 ) {
i=1;
while(a[i] > a[i-1]) {
i++;
}
j=0;
while(a[j] < a[i]) {
j++;
}
c=a[j];
a[j]=a[i];
a[i]=c;
char x[strlen(a)+1];
char y[strlen(a)+1];
strcpy(x,a);
strcpy(y,a);
subb(x, i);
revstring(x);
subb2(y, i);
sprintf(a, "%s%s", x,y);
printf("%s\n", a);
}
}
Update:
Код исправлен, сравнение с i-1 больше не приводит к выходу за пределы массива.
Также приятно сознавать, что данная реализация работает по времени сопоставимо (приемлемо, а может, и быстрее для малых n) с рекурсивным алгоритмом на том же Си.
Сравнение проводилось с кодом по следующей ссылке.
Рекурсивный алгоритм выдал время работы для n=11:
real 2m9.213s
user 0m2.920s
sys 0m26.290s
Алгоритм из этой заметки выдал для n=11:
real 2m15.510s
user 0m19.750s
sys 0m34.300s
Для n=10
Рекурсивный:
real 0m11.919s
user 0m0.340s
sys 0m2.390s
Из этой заметки:
real 0m12.128s
user 0m1.490s
sys 0m3.040s
Комментарии (27)
Yuriandryu
21.09.2016 12:14+2Чего только не напишешь, чтобы из песочницы выйти. Простите, но это моё мнение. Полезной информации статья не несёт. Примерно с тем же успехом могу описать свой сегодняшний поход в продуктовый магазин.
fishca
21.09.2016 13:07+1так вроде не из песочницы?
Yuriandryu
21.09.2016 13:18Не заметил, но сути не меняет. Я думаю статья ориентировалась вот на эту статью, которая более полезная.
UA3MQJ
21.09.2016 13:27У меня на десяти знаках программа не заканчивает свою работу ни через минуту, ни через десять.
dcc0
21.09.2016 13:39Я сумел протестировать только на одной машине, в разных ОС — WIN7 64x и Llinux (Gentoo) 64x.
Я вам скажу, что под WINDOWS генерация намного дольше.
Есть еще момент, который я забыл оговорить в статье: подозреваю, что конструкция второго цикла не совсем верная.
Честно скажу, я не знаю, можно ли так писать в Си a[i] > a[i-1], так как при i=0 i-1 в массиве нет.
kosmos89
21.09.2016 17:26+1>можно ли так писать
Выход за пределы массива, конечно, приводят к плачевным результатам. Не делайте так.
>под WINDOWS генерация намного дольше
расскажите лучше, чем компилировали под линукс и виндовс и с какими настройками.dcc0
21.09.2016 17:55> Выход за пределы массива, конечно, приводят к плачевным результатам.
Подозревал, но очень не хотелось добавлять проверок.
Под 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
21.09.2016 19:05В общем под Windows Dev C++ 4.9.9.2
Параметры компилятора — Default compiler, а это видимо gcc, т.к. он стоит первым в списке в программах.
Оптимизации, видимо, нет.
dcc0
21.09.2016 19:32Немного поэкспериментировал, добавил funroll-loops, почитав вот эту статью:
https://habrahabr.ru/company/intel/blog/167417/
Не знаю, насколько актуальны там рекомендации ( + еще пару опций относящиеся к циклам ).
Результат для n=10
real 0m8.963s
user 0m1.210s
sys 0m2.850s
dcc0
21.09.2016 23:49Вообще массив и отрицательный, тут в самом конце интересно
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&#entry1244250kosmos89
22.09.2016 00:07Валидна арифметика с указателями. т.е. адрес элемента будет посчитан корректно, но это вовсе не значит что он действительно на что-то валидное указывает.
>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
22.09.2016 01:10Да, спасибо. Интересно. Нашел что-то похожее.
Сейчас еще раз посмотрел в алгоритм и подумал, что, возможно, проблема решается очень просто — перед этим циклом установить i=1. Сейчас только проверю не сбивается ли алгоритм.
dcc0
22.09.2016 01:19Да, все верно, i =0 можно махнуть на 1 и тогда i-1 в крайнем случае будет указывать на 0 индекс, сейчас отредактирую код.
vlad9486
21.09.2016 17:59+1Автору: функция revstring (да и любая другая) может перевернуть строку с любым именем, если тип тот же самый.
dcc0
21.09.2016 18:08Да, да. Спасибо. Я про функции еще буду перечитывать, так как не все осело. Я когда тренировался, видимо, где-то ошибся, получил не тот результат и чтобы сильно не мучить учебник в тот момент просто продублировал функции. Тем более что первая выполняется один раз.
Там по идее и в первом цикле сравнение строк можно заменить предпосчитанным факториалом.
hd_keeper
22.09.2016 22:01+1Под Windows медленнее, так как там тормозит вывод на консоль.
dcc0
22.09.2016 23:28Неожиданно ваша правда.
Если убрать вывод, то для 12-ти символов время работы 2 минуты 38 секунд под Windows.
И без вывода под Linux: real 3m30.775s.
dcc0
23.09.2016 00:05Но есть и приятный момент по поводу тестов.
Простейшая рекурсивная реализация на 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)))
VGrabko
раз пять перечитал и не понял о чём статья
ripatti
Автор же написал, что гуманитарий. Так и должно быть.
fishca
Думаю вся соль здесь:
Многим техническим текстам этого не хватает и они напоминают сухари с изюмом вместо сдобных булочек с изюмом.
azsx
О том, что лирик всех физиков победил и переписал алгоритм в 5 раз быстрее, чем в учебнике.
S_A
Я так понял о том, что код на С быстрее рекурсии на awk.
KyHTEP
Си, амиго, — это фантастика! )
FForth
С рекурсией в разных языках (и реализциях их) не всегда всё так однозначно и некоторый Форт, например, может опередить некоторый Си (например на тесте поиска чисел Фибоначи) в силу более «присособенности» для рекурсивных алгоритмов.
P.S. Неплохая подборка примеров рекурсивных алгоритмов на разных языках на rosettacode.org
FForth
Может быть подразумевался некоторый «посыл» схожий с первым сообщением такой темы из Форт форума
Форт — игра?
P.S. Некоторым Форт программистам не чужды и литературные таланты, а каким то «гуманитариям» и Форт программирование,
вплоть до «экспериментов» в лингвистической области.