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

У каждого, наверное, есть какая-то своя излюбленная тема в IT, помимо повседневной практической работы, приносящей порой лишь хлеб насущный. Может быть, кто-то в свободное время делает мультфильмы или работает над какой-нибудь игрой, может быть, участвует в разработке какого-нибудь социального проекта или просто изучает что-то новое без особенной на то практической нужды, одним словом — делает что-то для себя, так сказать, для души.

Мой скромной опыт программирования привел меня к мысли, что этот род деятельности может быть ценным сам по себе и не иметь конкретных практических целей. Безусловно программирование может приносить творческое удовлетворение и, может быть, кому-то своеобразное эстетическое наслаждение; в конце концов, в любой сфере люди жаждут видеть собственную гармонию. Я, когда-то давно, когда еще едва был знаком с программированием и даже плохо понимал значение слова функция применительно к написанию кода, пошутил, сказав, что программирование это искусство. Это была просто брошенная фраза за дружеским чайным столом. Кто-то подыграл мне, спросив, как я это могу доказать. Я ответил что-то вроде: «не зря же Дональд Кнут свою антологию назвал искусством программирования». А ведь он знает толк в этом.

В то время я относился к программированию, как к сухой трудно понятной мне науке, считая её смесью лингвистики и математики. Конечно, тогда я уже имел представление об 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
Поделиться публикацией
Реклама помогает поддерживать и развивать наши сервисы

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

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

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

                  >под WINDOWS генерация намного дольше
                  расскажите лучше, чем компилировали под линукс и виндовс и с какими настройками.
                  • 0
                    > Выход за пределы массива, конечно, приводят к плачевным результатам.
                    Подозревал, но очень не хотелось добавлять проверок.

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

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

                        • 0
                          Вообще массив и отрицательный, тут в самом конце интересно
                          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
                          • 0
                            Валидна арифметика с указателями. т.е. адрес элемента будет посчитан корректно, но это вовсе не значит что он действительно на что-то валидное указывает.

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

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

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

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