1. C++ / Говнокод #12412

    +3

    1. 01
    2. 02
    3. 03
    4. 04
    5. 05
    6. 06
    7. 07
    8. 08
    9. 09
    10. 10
    11. 11
    12. 12
    13. 13
    14. 14
    15. 15
    16. 16
    17. 17
    18. 18
    19. 19
    20. 20
    21. 21
    22. 22
    23. 23
    24. 24
    25. 25
    26. 26
    27. 27
    28. 28
    29. 29
    30. 30
    31. 31
    32. 32
    33. 33
    34. 34
    35. 35
    36. 36
    37. 37
    38. 38
    #include <stdio.h>
    #include <string.h>
    #include <stdlib.h>
    #include <iostream>
    }
    void main (){
    int prog=0,n;
    
    printf ("Which programm?  ");
    scanf ("%d",&prog);
    
    if (prog==1){
    int glas=0,sogl=0,j=0,k=0;
     char *s,*l,*m;
     s=(char*)calloc(20,sizeof(char));
     l=(char*)calloc(20,sizeof(char));
     m=(char*)calloc(20,sizeof(char));
     flushall();
     printf ("\nEnter text:  ");
     gets(s);
     n=strlen(s);
     /*Разбиваем на два массива исходную строку*/
     for (int i=0;i<n;i++){
    if(s[i]=='a'||s[i]=='q'||s[i]=='e'||s[i]=='y'||s[i]=='u'||s[i]=='i'||s[i]=='o'||s[i]=='j'){ l[j]=s[i]; glas++;j++;}
    if(s[i]=='g'||s[i]=='f'||s[i]=='d'||s[i]=='s'||s[i]=='p'||s[i]=='t'||s[i]=='r'||s[i]=='w'||s[i]=='h'||s[i]=='k'||s[i]=='l'||s[i]=='z'||s[i]=='x'||s[i]=='c'||s[i]=='v'||s[i]=='b'||s[i]=='b'||s[i]=='n'||s[i]=='m'){ m[k]=s[i];sogl++;k++;}
       }
        printf ("\nDivided:\n");
     puts(l);puts(m);
    /*Сортируем каждый массив*/
     char c=51,d=11;
     for(j=0;j<sogl;j++) {for (int i=0;i<sogl;i++){if (m[i]>m[i+1] && (i+1)<sogl){d=m[i+1];  m[i+1]=l[i];  m[i]=d;}}}
     for(j=0;j<glas;j++){ for (int i=0;i<glas;i++){if (l[i]>l[i+1] && (i+1)<glas){c=l[i+1];  l[i+1]=l[i];  l[i]=c;}}}
     
      printf ("\nFinal:\n");
     puts(l);
     flushall();
     puts(m);
     }

    Источник: http://otvety.google.ru/otvety/thread?tid=78a81d7ac11a8804&table=/otvety/topics?clk=lftpn&tab=wtmtosb
    Цитата: "Задача: Написать программу для обработки строки следующим образом: вначале должны идти гласные буквы, упорядоченные по возрастанию (aaeeiioo), затем согласные, упорядоченные по убыванию.
    Написал программу, она нормально сортирует гласные, но когда переходит к согласным - совершенно не работает."

    Запостил: 10a10b1s, 12 Января 2013

    Комментарии (171) RSS

    • В первой итерации :) Можно лучше
      (defun vow-cons-sort (str)
      	(let ( (vow nil) (!vow nil) )
      		(map nil 
      			#'(lambda (c)
      				(if (member c '(#\A #\E #\O #\I #\a #\e #\i #\o)) (push c vow) (push c !vow)) 
      			) str)
      		(concatenate 'string (sort vow #'char<) (sort !vow #'char>))
      	)
      )
      
      (vow-cons-sort "i hate this fucking world i dont wanna live on this planet anymore")
      Ответить
      • Так вот ты какое, функциональное программирование!
        Ответить
        • Нет. Это игра в скобочки.
          Ответить
        • Все функцианально ебанулись чтоле? Еще лет 5 назад читал древнюю статью о вреде такого подхода:
          http://lukeplant.me.uk/blog/posts/why-learning-haskell-python-makes-you-a-worse-programmer
          Ответить
          • Мой мозг анально окупирован функциональным программированием.
            Ответить
          • Не нашел наездов на функциональщину. Кратко суть треда: В том бложике с древовидными комментариями сказали, что С#/JavaGovno, так как не может в функциональный код и превращает его в нечитаемую кашу, при этом размер кода также не уменьшается.
            Ну и рассказал кулстори про терки с каллегами из-за того, что автор стал везде пихать функциональный код в нефункциональном языке.

            К слову C# сейчас стал более функциональным, будь то var или лямбды без необходимости писать delegate в каждой. Да и каллеги стали попрошаренее.
            Ответить
      • (defun classify-and-sort (string)
          (loop with wovels =
               (loop with table = (make-hash-table)
                  for c across "AEIOUaeiou" do
                    (setf (gethash c table) t)
                  finally (return table))
             for char across string
             if (gethash char wovels)
             collect char into beginning
             else collect char into ending
             finally
               (return
                 (concatenate 'string
                              (sort beginning #'char<)
                              (sort ending #'char<)))))

        Без создания ненужных лямбд + более быстрая классификация, нормальное форматирование. Если не делать супер-портабельным, то хеш-таблицу можно записать буквально, вместо того, чтобы создавать динамически, но это так на так получится. Можно использовать case вместо таблицы, но зависит от конкретного Лиспа. Многие оптимизируют case лучше, чем таблицу, но некоторые тупо перебором сделают.
        Ответить
        • Я думал сделать на loop, но это не так функционально. case еще хуже.

          P.S. Форматирование не трожь! Оригинальный tirinox-style, на зло всем. ;-)
          Ответить
        • И кстати!
          CL-USER> (time (dotimes (i 10000) (classify-and-sort "i hate this fucking world i dont wanna live on this planet anymore")))
          Evaluation took:
            0.212 seconds of real time
            0.211638 seconds of total run time (0.211298 user, 0.000340 system)
            100.00% CPU
            665,417,790 processor cycles
            25,262,880 bytes consed
            
          NIL
          
          CL-USER> (time (dotimes (i 10000) (vow-cons-sort "i hate this fucking world i dont wanna live on this planet anymore")))
          Evaluation took:
            0.178 seconds of real time
            0.177834 seconds of total run time (0.177650 user, 0.000184 system)
            100.00% CPU
            559,571,853 processor cycles
            14,895,616 bytes consed
          Ответить
          • А кому это вообще уперлось, функционально или нет?
            Макросы нужно компилировать, чтобы они хорошо работали. Ну и тест сделаный на основании одной тестовой строки? Да и кроме того, у вас не все гласные перечислены?..
            Ответить
            • Мне тут на Хабре доказывали, что оно и так всегда компилируется. Так что незачет :)
              Про гласные, да, я внизу поправил.
              Про тестовые условия, ну, я ж строку не подбирал, чтобы она у меня быстрее работала.. и как-то лениво было всеобъемлющее исследование проводить ради комментов в говнокоде )
              Ответить
              • А Рабинович вам ничего по телефону не сообщал? Или на хабре начали писать компиляторы для всех Лиспов?
                И что, что вы строку не подбирали? А то, что в ней нет прописных букв вообще? А то, что в ней есть символы из (возможно) недопустимого диапазона? Тест левый вообще и ни к чему не обязывает.
                Ответить
                • Будь проще и люди к тебе понятнутся.
                  P.S. У меня SBCL, а убеджал человек, которому я склонен верить...
                  Ответить
                  • Так все таки Рабинович?
                    Есть стандарт, который описывает как код должен работать, стандарт нигде не предписывает как компилятор должен инлайнить чего-то, или как он должен оптимизировать код полученый из макросов, и т.п. Все остальное - вымысел или, в лучшем случае - домысел. Даже если указать в декларации, что функцию нужно заинлайнить - это только рекоммендация, и если компилятор не умеет, или посчитает лишним - то и не сделает.
                    Ответить
          • Премного извиняюсь, забыл в своей реализации гласную u. Впрочем, это не сильно усугубило.
            CL-USER> (time (dotimes (i 10000) (vow-cons-sort "i hate this fucking world i dont wanna live on this planet anymore")))
            Evaluation took:
              0.180 seconds of real time
              0.180826 seconds of total run time (0.179112 user, 0.001714 system)
              100.56% CPU
              568,781,049 processor cycles
              14,895,440 bytes consed
              
            NIL
            Ответить
            • Лисп, лисп...
              classifyAndSort s =
                  let (v, r) = partition (`elem` "aeiou") $ filter (`elem` ['a'..'z']) s in
                      sort v ++ (reverse $ sort r)
              Наглядно, кратко, и работает быстрее этих ваших лиспов даже в ghci, я молчу про то, как оно будет работать при нормальной компиляции с -O2.

              "aaaaaeeeeiiiiiioooouywwvtttttssrrpnnnnn nnmlllkhhhgfddc"
              (0.01 secs, 2959140 bytes)
              Ответить
              • Ну только в строке предположительно есть и прописные буквы, и тестировать на одном примере, который еще не известно является ли легальным для этой функции или нет? - и к какому выводу можно прийти сравнивая такие результаты?
                Ответить
                • > и к какому выводу можно прийти сравнивая такие результаты
                  Да собственно ни к какому, так же как и по вашему коду, и коду trinox.

                  Я просто пришел и насрал в уютном клубе лисперов, которые, между прочим, первые начали мериться таймингами кода, даже не зафиксировав условия задачи перед тем как ее решать.
                  Ответить
                • P.S. Если уж мериться - то самым шустрым решением будет массив счетчиков. На первой фазе читаем входной поток и считаем сколько каких символов. На второй фазе выводим гласные в нужном количестве, на третьей согласные.
                  Ответить
                • P.P.S. И куда засунуть эти прописные буквы? В конец (aaaeeeAAAEEE)? В начало (AAAEEEaaaeee)? Наравне со строчными (AAAaaaEEEeee)? Каждый понял задачу по-своему, и решил ее согласно своему пониманию. Давайте закроем этот бессмысленный спор.

                  > в строке предположительно есть и прописные буквы
                  А еще там предположительно есть пробелы.
                  Ответить
                  • (defun classify-and-sort-do (string)
                      (declare (type simple-string string)
                               (optimize (debug 0) (speed 3)))
                      (do* ((vowels "AEIOUaeiou")
                            (len (length string))
                            (step-size 10 10)
                            (minlen 9)
                            (i 0 (1+ i))
                            (offset 0 0)
                            (found 1 1)
                            (char #\Space)
                            beginning ending)
                           ((= i len)
                            (concatenate 'string
                                         (sort beginning #'char<)
                                         (sort ending #'char<)))
                        (declare (type fixnum offset step-size minlen found i len)
                                 (type list beginning ending)
                                 (type simple-string vowels)
                                 (type character char)
                                 (disable-package-locks common-lisp:* common-lisp:+))
                        (setq char (aref string i))
                        (loop while (and (/= found 0) (> step-size 0)) do
                             (let ((half (round step-size 2)))
                               (declare (type fixnum half)
                                        (ftype (function (fixnum fixnum) fixnum)
                                               common-lisp:* common-lisp:+))
                               (setq step-size half
                                     offset (min (+ offset (common-lisp:* half found)) minlen)
                                     found 
                                     (cond
                                       ((char= char (aref vowels offset)) 0)
                                       ((char< char (aref vowels offset)) -1)
                                       (t 1)))))
                        (if (= 0 found)
                            (push char beginning)
                            (push char ending))))

                    Но идея была неплохая... :)
                    Ответить
                    • Да ты упоротый. На хаскель программу посмотри и на это монструозное уёбище.
                      Ответить
                    • > classify-and-sort-do
                      Новое боевое искусство!
                      Ответить
                    • Почему так раздуто?
                      Ответить
                      • "Раздуто" предполагает, что можно было написать короче. Я не вижу, как можно было записать короче, если только не экономить на именах переменных.
                        Нужно вдумчиво прочитать код, для того, чтобы понять, почему его больше, чем в других примерах.
                        Ответить
                    • Да нахрена тогда ваще лисп? Я затеял функциональный тред для коротких и красивых решений....
                      Ответить
                      • Потому что первое решение на Лиспе было нубским (т.е. даже не наивным), я предложил более вменяемый вариант. Последнее решение - это принципиальное описание того, как можно было бы сделать (и как, скорее всего получается в случае, если использовать case на хорошо оптимизирующих компиляторах).
                        Я к сожалению не смог добиться от Питона хорошей оптимизации кейса. Возможно есть смысл посмотреть в сторону Алегро или CCL. Или попробовать допилить Питон специально под этот случай (но это очень много работы).
                        Ответить
                        • А чё, в лиспе хештаблицы нет? Не верю.
                          Ответить
                          • http://govnokod.ru/12412#comment166570

                            Но из этого явно не следует, что решение с использованием хеш-таблицы будет обязательно лучше, т.как реализация таблицы - скорее всего бинарное дерево, и бинарный поиск по упорядоченому массиву эквивалентен поиску по такой хеш-таблице.
                            Ответить
                            • > реализация таблицы - скорее всего бинарное дерево
                              Хеш-таблица на то и хеш-таблица, чтобы состоять из хеш-функции и массива. Время поиска складывается из времени хеширования значения и 1 или нескольких выборок из таблицы. При низком к-те заполнения и хорошей функции выборка будет всего лишь одна.

                              P.S. Если в библиотеке лиспа бинарное дерево назвали хэш-таблицей, то впизду такие лживые библиотеки.
                              Ответить
                            • >реализация хеш-таблицы - скорее всего бинарное дерево
                              Я вспоминаю треды, где wvxvw разглагольствовал о правильности парадигм на основе своего незыблемого опыта и тут вдруг такой вброс.
                              Ответить
                              • http://stackoverflow.com/questions/4846468/hash-table-vs-balanced-binary-tree

                                Not all hash tables use a linked-list as a bucket. A popular alternative is to use a "better" bucket, for example a binary tree, or another hash table (with another hash function), ...
                                Ответить
                                • Ну на первом то уровне всегда хеш функция и таблица ;) какая разница чем там дальше разруливают коллизии.
                                  Ответить
                                  • По-моему много ума не надо, чтобы догадаться о чем я говорил...
                                    Ответить
                                • Ну и какое отношение это имеет к повышению сложности? Правильно используемая хештаблица дает O(1).
                                  Ответить
                                  • И константа рядом с О растет в зависимости от количества элементов в таблице. Кроме того, за исключением самых тривиальных случаев, когда очень просто придумать хорошую хеширующую функцию, промахов будет достаточно много для того, чтобы время стало сравнимым. (В Явовских хеш-таблицах при достаточной ловкости рук можно добиться чистого O(n), например).
                                    Мне когда-то попадалась статья про trie где были результаты тестов и сколько времени занимают какие операции в хеш-таблице по сравнению с ним и с бинарным деревом. И для данных, которыми могут оперировать ПК с типичными на сегодня объемом памяти - разница между хеш-таблицей и бинарным деревом практически никакая (удаление из хеш-таблицы правда, дороже).
                                    Ответить
                                    • > И константа рядом с О растет в зависимости от количества элементов в таблице
                                      Ну неправда. Если бы так было - сложность бы записывали к примеру как O(log(n)), зачем себя обманывать?

                                      Для реализации со списками:
                                      Трудоёмкость операций в хеш-таблице зависит не от числа элементов n, содержащихся в ней, а от коэффициента заполнения α. Оценку трудоёмкости можно записать, как O(1+α/2) А большие load-factor'ы никто никогда не ставит, разве что недалекие люди, которые думают, что так сэкономят память.
                                      Ответить
                          • Есть конечно, выше wvxvw кидал код с ее использованием.
                            Ответить
                  • И, еще раз, про пробелы и какие либо другие символы (а может там строка не Юникод? А может там самодельная кодировка? А может там Юнкод с багами?) Зачем придумывать ситуации не описанные в задаче? Никто не говорил, что в вводе могут быть символы, которые не относятся ни к одной из груп, задачу отфильтровать неподходящие символы никто не просил решать.
                    Ответить
                    • Ну в таком случае мой код выше полностью решает задачу, т.к. про заглавные буквы тоже нигде не упоминается.
                      Ответить
                      • Выберите из этих двух букв одну, которая не гласная: "А" и "а"?
                        Ответить
                        • Ок, сдаюсь. Ну тогда меняем sort на sortBy (\x y -> toLower x `compare` toLower y) и добавляем заглавные буквы в соотв. списки, чтобы получить результат в котором одноименные строчные и заглавные стоят рядом (АааАааЕееЕЕЕоОоооо). Смысла в дальшейшем упорядочении прописных и строчных внутри каждой группы я не вижу.
                          Ответить
              • Блин, а я вот забыл как partition называется, хотя искал его и среди span и split* и break и group* и др...
                Ответить
              • http://liveworkspace.org/code/1176Eq$1
                import Data.Char
                import Data.List
                classifyAndSort s =
                    let (v, r) = partition (`elem` "UAEOIuaeoi") $ filter isLetter s in
                        sort v ++ (reverse $ sort r)
                        
                main = print $ classifyAndSort "i hate this fucking world and i want go to immutable world now!"
                GovnoEdition
                По краткости лучше не получается
                Ответить
          • Например так, конкретно в SBCL будет быстрее, но не факт, что на любых платформах:
            (defun classify-and-sort-iterate (string)
              (iter:iter
               (iter:for char in-string string)
               (case char
                 ((#\a #\e #\i #\o #\u #\A #\E #\I #\O #\U)
                  (iter:collect char into beginning at start))
                 (otherwise (iter:collect char into ending at start)))
               (iter:finally
                (return
                     (concatenate 'string
                                  (sort beginning #'char<)
                                  (sort ending #'char<))))))

            Как, и будет ли это быстрее, например в CCL на ARM? - хз. Разница между тестами маргинальная, но есть какие-то общеизвестные трудности при реализации чего-то. SBCL смог хорошо заинлайнить лямбду, а какой-нибудь друой лисп не смог бы этого сделать, и получили бы штраф за вызов функции, и т.п.
            Ответить
            • Прежде чем писькомериться инлайнами не поленились бы пофиксить очевидные баги - в вывод пролезают символы, не являющиеся буквами, согласные сортируются не в том порядке.
              Ответить
            • (let ((table (loop with table = (make-hash-table)
                              for c across "AEIOUaeiou" do
                                (setf (gethash c table) t)
                              finally (return table))))
                (defun char-vowel< (a b)
                  (let ((a-v (gethash a table))
                        (b-v (gethash b table)))
                    (cond
                      ((or (and a-v b-v) (and (not a-v) (not b-v)))
                       (char< a b))
                      (a-v t)
                      (t nil)))))
              (sort "some string data" #'char-vowel<)

              Интерестно, что это будет даже медленнее работать, чем если тут же заменить хеш-таблицу на список. Вариант со списком будет работать примерно так же, как и предыдущие (но экономнее расходует память).
              (let ((table '(#\A #\E #\O #\I #\U #\a #\e #\i #\o #\u)))
                (defun char-list-vowel< (a b)
                  (let ((a-v (member a table))
                        (b-v (member b table)))
                    (cond
                      ((or (and a-v b-v) (and (not a-v) (not b-v)))
                       (char< a b))
                      (a-v t)
                      (t nil)))))
              Ответить
        • wvxvw
          tirinox
          Могли бы и не делать такую глупую ошибку. Вы забыли удалить лишние символы из строки, например знаки припинания, так как они не относятся ни к гласным ни согласным.
          http://liveworkspace.org/code/2jTjqt$24
          import Data.List
          import Data.Char
          isSoglasnaya ch = ch `elem` "UAEOIuaeoi"
          pr1 src = sort $ filter isSoglasnaya srcFiltred ++ (reverse $ sort $ filter (not.isSoglasnaya) srcFiltred)
             where srcFiltred = filter isLetter src
          main = print $ pr1 "i hate this fucking world and i want go to immutable world now"
          Знаю как написать оптимальнее, но мне лень, пока код не учавствует в бенчах.
          Ответить
          • Блин, я всегда буду обновлять страницу перед отправкой ;)
            Ответить
          • ХЗ. Откуда мне было знать, что в строке есть что-то еще? В описании задачи нет ничего про то, что нужно выбрать только определенные буквы. Так может еще начнем казуистику с алфавитами, и является ли y гласной или нет? А может возьмем Английский алфавит 17-го века? А может 12-го?
            Ответить
          • >stdout: "aaaabcdddeefgghhiiiiiklllmmnnnnooooorrs tttttuuwwww"
            >гласные буквы, упорядоченные по возрастанию (aaeeiioo), затем согласные, упорядоченные по убыванию
            Ответить
            • bormand только что #
              Он скобки забыл
              http://liveworkspace.org/code/2obWBt$1
              Ответить
          • import Data.List
            import Data.Char
            isSoglasnaya ch = ch `elem` "UAEOIuaeoi"
            pr1 src = (sort $ filter isSoglasnaya srcFiltred) ++ (reverse $ sort $ filter (not.isSoglasnaya) srcFiltred)
               where srcFiltred = filter isLetter src
            main = print $ pr1 "i hate this fucking world and i want go to immutable world now"

            А вы ещё на лисперов гоните. Среди хаскелистов одни идиоты.
            Ответить
    • import string #может и перебор подключать модуль ради одной константы, но мне лениво набивать согласные самому
      vowels = frozenset('UAEOIuaeoi')
      consonants = frozenset(string.ascii_letters) - vowels
      #говнострочник - просто интереса для
      transform = lambda s: ''.join(sorted(filter(lambda c:c in vowels,s))) + ''.join(sorted(filter(lambda c:c in consonants,s),reverse=True))
      
      print transform('i hate this fucking world i dont wanna live on this planet anymore')
      Ответить
    • Да, и кроме всего остального.
      Решения, естесственно, можно оценивать с разных позиций. Так вот, изначальное решение на CL, как и все последующие решения на Хаскелле, (возможно, за исключением тех, где используется partition - хотя, я не знаю, как именно оно реализовано, так что может и нет) принципиально выигрывают за счет того, что при маленьком n выполняется "n примерно равно log n примерно равно 1". Естесственно, если мы попытаемся расширить алгоритм и сделать его более универсальным, для последовательностей произвольной длины (например, захотим с его помощью реализовать регулярные выражения для строк в Юникоде). То все эти решения обламаются - потому что, чем болше будет n, тем быстрее будут работать варианты, где классификация делается за n или n log n время, вместо n^2.
      Ответить
      • Классификация тут во всех способах делается за линейное время O(количество_символов_в_строке), откуда тут взяться n^2? Алгоритм, проверяющий является ли буква гласной выполняется за константное время, не зависящее от длины строки. Да, наивный хаскелевский (`elem` "aeiou") безусловно проиграет более шустрым хешу\дереву\массиву\свичу\подставьте_сво е, но ни в коем случае не в асимптотике, а просто на константу.

        Все тормоза в этих алгоритмах будут в сортировке, которая займет O(n*log(n)), где n - количество символов в строке.

        > например, захотим с его помощью реализовать регулярные выражения для строк в Юникоде
        Вы не в ту сторону копаете. Количество букв во всех земных алфавитах вполне конечно, в отличие от длины строки, которая как раз произвольна. Поэтому в асимптотике насрать на то, ищем ли мы китайские иегроглифы состоящие из трех черт, или всего лишь 5 гласных букв. Это влияет только на константу. Захочется уменьшить константу - ок, заменяйте на хеши, мапы, или что там будет быстрее.
        Ответить
        • > Откуда взятся n^2
          тут, в большинстве случаев имеем дело с m * n, где m - количество символов в вводе, и n - количество символов в категории, котоую нужно отфильтровать. В общем случае это n^2. И именно поэтому проигрывает не на константу, а в квадрате.

          > Количество букв вполне конечно
          Вот только когда мы говорим о Юникоде, где символов имеется 0xFFFFFF или что-то в этом духе, то это становится вполне себе соизмеримо со строками, с которыми эта функция будет работать.
          Ответить
          • Браво, маэстро! Как вы красиво O(m*n), где m конечное, хотя, возможно велико, превратили в O(n^2)... ловкость рук и никакого обмана...
            Ответить
            • лол, между m и n разница всего в единичку почти во всех кодировках, можно и приравнять
              Ответить
              • 'm' ^ 2 = 'o'
                'n' ^ 2 = 'p'

                З.ы. таблицы под рукой нет, считал в уме, могу ошибиться...
                Ответить
          • > Вот только когда мы говорим о Юникоде, где символов имеется 0xFFFFFF или что-то в этом духе, то это становится вполне себе соизмеримо со строками, с которыми эта функция будет работать.

            Ок, 0xFFFFFF это примерно 16млн. Значит в наивной реализации константа составит 16млн, в более разумной с деревом или бинарным поиском - всего 24, битмаска же на 16млн элементов даст константу 1 (т.к. в типичном тексте, даже китайском, используется лишь маленькая часть всех символов юникода, то используемый кусок битмаски поместится в кеш, и доступ будет очень шустрым). С константой разобрались, теперь перейдем к O(n^2).

            Видя сложность O(n^2) резонно предположить, что 200 символов будут обрабатываться в 100 раз дольше, чем двадцать. Но... это же не так. 200 символов будут обрабатываться всего в 10 раз дольше чем 20, даже при самой-самой наивной реализации (`elem` многоМногоБукв), с этим то вы спорить не будете? А это и есть сложность O(n).

            P.S. Не разбирались с теорией сложности вычислений - не трогайте ее, это вам не цирк, где можно безнаказанно жонглировать определениями.
            Ответить
            • Эээ... даже в Хаскелле условно бесконечные списки только условно бесконечны. Все конечно, бесконечность - просто удобный способ работать с несоизмеримо большими числами. :|
              А откуда такие предположения сразу о том что именно будет в тексте? А если это не китайский, а японский учебник арабских математических терминов? И вообще, какое это имеет отношение? В общем случае есть последовательность с доменом неопределенного, но возможно очень большого размера. Естесственно, в конкретной задаче об этом не говорится, поэтому, я не настаиваю на том, что более общее решение лучше. Я только говорю, что нужно иметь в виду, что решение предпочтительно только тогда, когда домейн очень ограничен.

              > Но... это же не так.
              Откуда инфа? Есть множество накладных расходов помимо непосредственной задачи. Тета или биг-О задают только верхний предел. А то, что случайно может получится быстрее - ну так повезло.
              Ответить
              • > Откуда инфа?
                Худшее время классификации каждого символа (Tbad) нам известно заранее, оно зависит только от алфавита и от алгоритма выбора категории по символу, и никак не зависит от входной строки. Входная строка (длины n) пробегается ровно 1 раз. Значит худшее время классификации составит Tbad*n. А это и есть O(n). Не нравится? Ну так докажите обратное, что время в худшем случае составит Tbad*n². Докажете - я поверю, что там O(n²). Нет - слив засчитан.
                Ответить
                • Кому заранее известно? Мне не известно. Я же про общий случай говорю, как оно там может быть известно?
                  Ответить
                  • В самом наивном и херовом случае, когда для того, чтобы определить, куда отнести текущий символ, мы используем линейный поиск в пространстве символов (как я это сделал в хаскеле), нам понадобится перебрать все символы. Поэтому Tbad будет равно время_на_проверку_символа * число_символов_в_алфавите. Что тут такого неизвестного?

                    Tbad хоть как-то зависит от длины строки? Нет. Значит вы не имеете права дописать еще одну n к сложности данного алгоритма.
                    Ответить
                    • Это все равно что утверждать, что любой цикл на Си выполняется в константое время, т.как длина массива заранее известна, т.как не может быть больше чем size_t или чего-там. Что уж и говорить про случаи, когда данные описаны в short / byte и т.п. :/
                      Ответить
                      • > Это все равно что утверждать, что любой цикл на Си выполняется в константое время, т.как длина массива заранее известна

                        m - размер алфавита
                        n - количество символов во входной строке
                        for (int i=0; i<n; i++) {
                            for (int i=0; i<m; i++) {
                                // some operation
                            }
                        }
                        Я утверждаю, что внутренний цикл всегда выполняется за время, зависящее только от m, но не от n. При фиксированном m (а во время классификации одной строки оно фиксировано, т.к. никто не меняет категории во время классификации) это время константное.

                        Процитирую вас:
                        > тут, в большинстве случаев имеем дело с m * n, где m - количество символов в вводе, и n - количество символов в категории, котоую нужно отфильтровать.
                        Бесспорно! Здесь я полностью с вами согласен!

                        > В общем случае это n^2.
                        А вот это, простите за выражение, хуйня. Это все равно что утверждать, что вон тот код, который я привел в этом комменте, выполнит m*m итераций, а не m*n.
                        Ответить
                      • P.S. Вот время работы цикла, который я описал комментом выше, составляет m*n*some_operation_time. Безусловно, оно линейно растет как при росте m, так и при росте n. Но было бы глупо утверждать, что это время растет в квадратичной зависимости от m или от n.
                        Ответить
                        • Так какое ж оно фиксированое, если оно не фиксированое? :/ Блин, короче, это уже третий круго того же самого.
                          Ответить
                          • O(m*n) если алгоритм наивный, O(n) если там что-то типа битмаски или m достаточно мало, а n велико. Закончим на этом спор?
                            Ответить
                          • Квадратичная сложность относительно параметра означает что время работы возрастает как квадрат значения параметра при прочих равных.
                            Иными словами, O(m*n) линейно как относительно m (при неизменном n), так и относительно n (при неизменном m).

                            Я правильно понимаю?
                            Ответить
                            • У нас два параметра, а не один. Речь идет об общем случае, а не о частном, когда второй параметр известен и по счастливому стечению обстоятельств гораздо меньше первого.
                              Ответить
                              • А хоть бы и неизвестен. Линейная сложность по каждому из двух параметров =\= квадратичная по обоим.
                                Квадратичная сложность будет только если значения параметров прямо пропорциональны друг другу, что в общем случае совершенно необязательно так.

                                Иначе говоря, O(m*n) = O(n^2) тогда и только тогда, когда m = const*n
                                Ответить
                            • > Квадратичная сложность относительно параметра означает что время работы возрастает как квадрат значения параметра при прочих равных.
                              Все верно.
                              Ответить
              • > Я только говорю, что нужно иметь в виду, что решение предпочтительно только тогда, когда домейн очень ограничен.
                Я не говорю, что наивная реализация через (`elem` "aeiou") предпочтительна, или даже эффективна. Я утверждаю только то, что классификация даже с такой хуевой функцией - O(n), а не O(n^2).

                Да, можно взять двоичный поиск или двоичное дерево, и получить меньшую константу перед O(n).

                Да можно взять битмаску, и получить еще меньшую константу.

                А можно написать код на асме, и выиграть в константе еще в 10 раз, и все равно останется то же самое O(n).

                Поймите, было бы там O(n^2) - время бы росло на 2 порядка на каждый порядок в n. Т.е. при росте строки с 20 до 200 символов время бы выросло в 100 раз. Но это ведь не так. Время растет линейно с ростом длины входной строки.
                Ответить
                • > Я не говорю, что наивная реализация через (`elem` "aeiou") предпочтительна, или даже эффективна.
                  Думаю, что для данного конкретного случая, пока символов не много - этот способ эффективнее хешмапы или любых других сложных структур данных, особенно если бы хаскель умел представлять "aeiou" как массив, а не как список с плохой кешфрендлявостью.
                  Ответить
                  • Ну не быстрее битмаски. А вот в кеш этот список вполне влезет. Он же совсем маленький.
                    Ответить
                    • > Ну не быстрее битмаски.
                      Обращение к большой битмаске потребует загружать новую кешлинию в кеш, замещая старые полезные кешлинии, на каждой итерации цикла. В то время как маленький массив из пары согласных букв не потребует подгружать новую кешлинию, а как ты знаешь, подгрузка кешлиний самая медленная операция у процессора.
                      Ответить
                      • Ну это в теории, в худшем случае. Но ведь как я уже упоминал выше, на практике в реальных текстах будут использоваться далеко не все символы из алфавита, поэтому битмаска будет грузиться не полностью, и ее активные куски вполне влезут в кеш.
                        Ответить
          • >Вот только когда мы говорим о Юникоде, где символов имеется 0xFFFFFF
            А в каком-нибудь языке с большим алфавитом, например в китайском, вообще гласных нет. Как ты тогда свою слишком универсально поставленную задачу будешь решать?
            И подозреваю, что isLetter в хаскеле возвратит true только для символов из установленных в системе локалей.
            Ответить
            • Это я к тому, что вычленять согласные и гласные одновременно из всех языков юникода в данной постановки задачи - глупо.
              Ответить
    • Теперь будешь знать, 10a10b1s, как не приди на говнокод, так обязательно засрут тему лиспоговном или бормондом хаскелябожественным кодом.
      Ответить
    • Внимание: тем временем не в меру упоротое и не до конца тестированное, но очень быстрое решение от Тиринокса:
      (defun ultimate-classify-and-sort (str)
        (declare 
          (type simple-string str)
          (optimize (debug 0) (speed 3)))
        (let (
              (data (make-array '(255) :element-type 'fixnum :initial-element 0))
              (vowels (map 'list #'char-code "aeiouAEIOU")))
             
          (map nil #'(lambda (c) (setf (aref data (char-code c)) (1+ (aref data (char-code c))))) str)
          (loop 
            for i from 65 to 122 
            for c = (aref data i)
            for chr = (code-char i)
            for new-substring = (make-string c :initial-element chr)
            for alpha-flag = (and (<= i 90) (>= i 97))
            if (and (> c 0) alpha-flag (member i vowels)) collect new-substring into beginning
            else if (and (> c 0) alpha-flag) collect new-substring into ending
            finally (return (concatenate 'string (format nil "~{~a~}" beginning) (format nil "~{~a~}" (reverse ending))))
           ; finally (progn (print beginning) (print ending))
          )))


      Дает нам:
      (time (dotimes (i 10000) (ULTIMATE-CLASSIFY-AND-SORT "i hate this fucking world i dont wanna live on this planet anymore")))
      Evaluation took:
        0.029 seconds of real time
        0.029388 seconds of total run time (0.029334 user, 0.000054 system)
        100.00% CPU
        92,393,025 processor cycles
        52,654,816 bytes consed

      В более 6 раз быстрее, чем первое мое :)
      Ответить
      • Попробуйте сократить вашу тестовую строку до одного символа - так еще быстрее будет. А вообще: macroexpand / disassmeble в помощь. Тут еще пилить и пилить на самом деле.
        Ответить
      • О, вот и мою идею со счетчиком реализовали. Из-за отсутствия sort общая сложность кода упала с O(n*log(n)) до O(n).

        > @wvxvw: Попробуйте сократить вашу тестовую строку до одного символа - так еще быстрее будет.
        Ненене, Девид Блейн, пусть он удлинит строку раз в 10. Тогда этот метод начнет обгонять все перечисленные выше. И чем больше будет строка - тем сильнее. Почувствуйте силу асимптотики.
        Ответить
        • Да, только я не учел, что оно вообще результат не выдает. Поспешил и что-то испортил :(
          Но, я думаю, главная идея ясна.
          Ответить
      • (defun partition-and-sort (input)
          (declare 
            (type simple-string input)
            (optimize (debug 0) (speed 3)))
          (loop with vowel-table =
               (make-array 10 :element-type 'fixnum :initial-element 0)
             with consonant-table =
               (make-array 128 :element-type 'fixnum :initial-element 0)
             for i across input
             for char-pos of-type (or fixnum null) = (position i "AEIOUaeiou") do
               (if char-pos
                   ;; Need better `incf' to avoid useless coercion
                   (incf (aref vowel-table char-pos))
                   (incf (aref consonant-table (the fixnum (char-code i)))))
             finally
               (return
                 (loop with result = (make-string (length input))
                    with pointer = 0
                    with i = 0
                    with table = vowel-table
                    for c = (aref table i) do (incf i)
                    when (> c 0) do
                      (loop with filler = 
                           (if (eq table vowel-table)
                               (aref "AEIOUaeiou" (1- i))
                               (code-char (1- i)))
                           with end = (+ c pointer) do
                           (setf (aref result pointer) filler
                                 pointer (1+ pointer))
                           while (> end pointer)) end
                    when (and (= i 10) (eq table vowel-table)) do
                      (setf i 0 table consonant-table) end
                    until (and (eq table consonant-table)
                               (= pointer (length input)))
                    finally (return result)))))

        Это примерно в 4 раза оптимальнее по памяти, и если переписать incf так, чтобы он не прибавлял знаковые целые с fixnum, то по времени будет так же.
        чет я устал как-то совсем :(
        Ответить
        • Оппа, я забыл про incf.
          Респектос, 0.027 seconds of real time на том же тесте.
          Но версия на Си, все равно в 10 раз выигрывает. (Не принимая во внимание, как там что где компилирует или нет).
          Ответить
          • > Но версия на Си, все равно в 10 раз выигрывает.
            Ну не надо сравнивать по скорости Си с функциональными языками. Си всегда выиграет такое соревнование. У ФЯ есть шанс победить в понятности и скорости разработки, да и только.
            Ответить
            • Не факт. Ради интереса, я однажды сравнил решение какой-то чисто математической вычислительной задачи на Лиспе и на С. Результат оказался очень близок (не 10 раз уж). Си-Шарп вообще всрался и програл Лиспу.
              Ответить
              • > Результат оказался очень близок
                С корнями, логарифмами и делениями? Ну так тут и интерпретатор может сравняться по скорости, т.к. эти операции спокойно могут выполняться дольше чем весь управляющий циклом обвес... Но вот обогнать си при одинаковом алгоритме - очень маловероятно.

                > Си-Шарп вообще всрался и програл Лиспу
                Емнип он даже медленнее жабы...
                Ответить
                • Да ежу понятно, что Си быстрее. Но тот же Лисп очень хорош в оптимизации и все эти приблуды ФП сжирают не колоссальное время, а иногда меньшее тех самых мат. действий. Да и асм он генерирует красивый и прозрачный. Какой-нить car там в две команды превращается в идеале, а в хваленых популярных домохозяечных языках схожие операции разворачиваются во вложенные раз 10 вызовы внутренних функции, каждый из которых обрамляется страницей текста на проверки и преобразования, и в конце концов оно еще и выполняется на какой-нить виртуальной машине.

                  И еще. Говоря о Сях(++). Их еще нужно уметь использовать (это справедливо в той или иной степени для всех языков, конечно). Алгоритмы уже реализованные в ф.языках зачастую во много раз быстрее на-коленке-самописных и даже быстрее вроде-бы-отточенных-библиотек. Год назад сравнивал встроенный BigNum в лиспе с одним моим вариантом BigNum и 2-3 разными сторонними либами. И лисп вышел победителем.

                  В сети есть результаты сравнения по скорости решений разных классов задач на разных языках. И функциональные языки там показывают себя весьма достойно.

                  Впрочем вопрос спорный, да.
                  Ответить
                  • > Год назад сравнивал встроенный BigNum в лиспе с одним моим вариантом BigNum и 2-3 разными сторонними либами.
                    В лиспе бингнумы быстрее, чем в GMP?

                    > Алгоритмы уже реализованные в ф.языках зачастую во много раз быстрее на-коленке-самописных
                    Безусловно, а еще они корректнее и отлаженнее чем самописные велосипеды. Поэтому велосипеды - для души, а в продакшене лучше лишнюю либу зацеплю.

                    > все эти приблуды ФП сжирают не колоссальное время
                    Смотря какие... вызов лямбды вполне инлайнится, хаскель тоже так умеет. А вот если эту самую лямбду передать аргументом - то уже не факт, что что-то оптимизнется. Тут надо быть осторожным.
                    Ответить
                    • Нет, GMP вроде почетче будет. Не зря для него врапперы под лисп написаны.
                      До него тогда руки не дошли или плохо гуглил.
                      Ответить
                    • В лиспе, как и в хаскеле GIMP используют.
                      Ответить
                      • > GIMP
                        Чтобы иконку нарисовать? Ну да, ну да, не фотошопом же...
                        Ответить
                        • Очепятка же, ну похоже же же же же.
                          Ответить
                        • > GIMP
                          Извиняй, GIMP каждый день глаза мазолит, а GMP пользуюсь только в составе других языков или библиотек, тк интерфейс у него пrативный.
                          Ответить
                  • Ох уж мне этот функциональный энтузиазм...
                    К сожалению, каждый язык имеет свою область применения. Я хотел бы иметь один удобный везде, но не судьба. Реальность такова, что в большинстве задач вполне хватает "домохозяечных" (это ведь не о C/C++, верно?) императивных языков. Более того, код получается даже проще и быстрее. Да, не хватает некоторых фишек вроде лямбд, но в конечном счёте и без них вполне можно жить. Если хорошенько подумать, всегда можно написать хороший код.

                    А вот если бы я взялся писать компилятор типизированного диалекта lisp под llvm (моя давняя задумка, жаль, руки не доходят), я бы выбрал для этого Haskell, не сомневаясь ни секунды.

                    Очевидно, я не имею ничего против функциональных языков. Я даже обоими руками ЗА. Но примеры CL в этом треде наводят меня на мысль, что уж лучше пусть будет c++.
                    Ответить
                    • True.
                      Ответить
                    • >типизированного диалекта lisp
                      Как ты себе это видишь? Это же вся суть лиспа, что он динамически типизированный. А если нужен статически типизированный лисп - бери хаскель. Помоему выбор очевиден.
                      Ответить
                      • Ну он то динамически типизированный, только вот чтобы задрочить производительность, к функциям приписывают аннотации, в которых указаны типы аргументов. Тогда компилятор лишпа делает более кошерный код...

                        Видимо Роман хочет что-то среднее между хаскелем и лиспом - со скобочками и макро, но при этом с выводом типов.
                        Ответить
                        • > Как ты себе это видишь?
                          Есть прецеденты
                          http://docs.racket-lang.org/ts-guide/

                          > Роман хочет что-то среднее между хаскелем и лиспом
                          Да, именно. Хотелось бы получить лучшее из обоих миров. Изящный лисповый синтаксис и гигиеничные макросы, строгая типизация с выводом типов, функциональные ленивые последовательности, "протоколы" === typeclasses, сопоставления с образцом, иерархическая система модулей... компиляция в натив, автоматическая оптимизация от llvm, годный FFI, примитивы многопоточности и асинхронного программирования. Такой лисп (а не дурацкий CL) завоевал бы моё сердце.
                          Ответить
                          • В CL макросы негигиеничны, обычный макротрешак, в котором разрешили использовать код на лиспе, и теперь тешат чсв и ради этого превозмогают скобки... По сути это ненамного лучше питонского compile/eval, разве что у приличных реализаций CL компиляция поэффективней и не в p-code.

                            Да и вообще сам CL, хоть мне и нравятся его концепции, но он имхо представляет из себя типичную исторически сложившуюся помойку, по стилю напоминающую PHP.

                            В остальном да, интересная идея.
                            Ответить
                            • > CL представляет из себя типичную исторически сложившуюся помойку
                              Так и есть, но есть же Scheme R5RS.

                              Начиная с R6RS они уже начали упарываться по оптимизации, превращая язык в раздутую продакшен конструкцию, хоть и во благо.
                              Ответить
                        • > между хаскелем и лиспом - со скобочками и макро, но при этом с выводом типов.
                          > гигиеничные макросы, строгая типизация с выводом типов, функциональные ленивые последовательности, "протоколы", сопоставления с образцом, иерархическая система модулей... компиляция в натив, автоматическая оптимизация от llvm, примитивы многопоточности и асинхронного программирования.


                          Это вы сейчас так мягко намекаете на Nemerle? Добро.
                          Ответить
                      • Есть, кстати, ещё вот такая штука
                        http://en.wikipedia.org/wiki/Qi_%28programming_language%29
                        Ответить
                    • Где лямбд не хватает?
                      Ответить
                      • В с и java. Да и в c++03 ни намёка на них. Многие ли сейчас используют с++11? Есть Boost.Lambda, но это всё же не совсем то.
                        Ответить
                        • Токмо упрощения кода ради, и устранения копипастной рутины.
                          gccшные nested functions и прочие лямбды с замыканиями удобны чтобы не городить указатель на функцию(С), класс-функтор(С++), анонимный класс (Java).

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

                          >Ох уж мне этот функциональный энтузиазм...
                          Хороший, взвешенный коммент.
                          Ответить
                • На самом деле в хакселе и даже в лиспе программы написанные в императивном стиле мало того что читаются как говно, так ещё и кода становится больше, чем в императивном языке. Особенно в хаскеле.

                  Вон попробуй на хаскеле реализовать задачу, которую мы тут обсуждаем, но не через тормозные списки n log n, а через сортировку подсчеом n. Тут же элегантный хаскель код превратится в уёбищное говно и по количеству кода и читабильности сразу проигрет сишке. Ну и по скорости тоже проиграет чуть-чуть.
                  Ответить
                  • Да думал я уже как ее замутить... ничего кроме вот такого корявого решения с O(log(m)*n), где m размерность алфавита, а n число символов во входной строке, в голову не пришло:
                    countSort list = concatMap (uncurry $ flip replicate) $
                        Map.toList $ foldl (\m e -> Map.insertWith (+) e 1 m) Map.empty list
                    Ответить
                    • P.S. Файлик с метром base64 мусора (соответственно 64 возможных символа) эта тупая реализация countSort сортирует быстрее чем Data.List.sort - 0.78с против 2.74с...
                      Ответить
                      • Я тоже так подумал сделать, но log меня остановил. Чтобы красивый код получился и O(n) с мутабильным массивом - к сожалению в хаскеле это не возможно. К сожалению все эти готовые алгоритмы и функции высшего порядка в императивном коде не сильно помогают. К слову в лиспе тоже будет отвратительно выглядеть.
                        Ответить
                        • Но при любом раскладе для данной задачи O(log(m)*n) лучше чем O(log(n)*n), темболее что сортировка в хаскеле может и в O(n^2) вырождатся
                          Ответить
                          • > O(log(m)*n) лучше чем O(log(n)*n)
                            Безусловно. И vwxwv тут не докопается, ибо даже при огромных алфавитах в 4 гигасимвола log2(m) это всего лишь 32.
                            Ответить
                        • Ну кстати, если искать положительные стороны, то этот код универсальней кода с массивом - тут не надо знать заранее, в каких пределах будут числа. К примеру если из 16млн юникодных символов мы юзаем всего 64к, не стоящих рядом, то на вставки будет уходить в районе 16 итераций, а по памяти оно будет жрать намного меньше, чем массив на 16млн ячеек.

                          Так что не все так ужасно, хотя, согласен, совсем не идеально...

                          P.P.S. В хаске есть мутабельный массив, но тут надо еще подумать, как прикрутить его к фолду.
                          Ответить
                          • > В хаске есть мутабельный массив, но тут надо еще подумать, как прикрутить его к фолду.
                            Да знаю что он есть, но к фолду его не прикрутишь. Он же работает как ввод-вывод в файлмассив на монаде IO.

                            Ну и зачем тут массив? Тут std::deque нужен хотябы по той причине, что ты описал выше. Сомневаюсь что в хаски он есть.
                            Ответить
                            • Можно STArray использовать (а если STU, то будет ещё и быстро). Сделать что-то вроде forM_ list (\c -> readArray a (ord c) >>= \i -> writeArray a (ord c) (i + 1) и получится почти императивный цыкл. А потом завернуть в runSTArray и будет чистая снаружи функция.
                              Ответить
                              • >STU - ST Unboxed? А почему Unboxed быстрее? В чем его особенность? Более строгий strict? Особое представление данных?

                                Это можно вызывать из чистых функций или монаду IO придется протягивать из майна? Это как-то не красиво, да и функциональный код превращается в императивный.
                                Приглашаю поучаствовать в соревнованиях нашей специальной олимпиады. Код вы уже почти написали.
                                Ответить
                                • http://ideone.com/HKFxuH (это сортировка подсчётом). Как можно видеть, сама сортировка — чистая. В IO выполняется IOArray, а STArray — в хитрой монаде ST, в которой можно завернуть мутабельные операции в чистую обёртку, это возможно за счёт полиморфизма второго порядка.
                                  Unboxed быстрее, потому что в нём хранятся сами значения цельным куском, а в обычном — только ссылки на них, по которым нужно ещё пройти. Но это возможно только для некоторых типов (в основном примитивных типа Int и Word разного размера).
                                  Ответить
                                  • import Data.Array.Unboxed
                                    import Data.Array.ST
                                    import Control.Monad
                                    import System.Random
                                     
                                    charRange = (0, 63)
                                     
                                    countSort :: [Int] -> [Int]
                                    countSort list = concatMap (uncurry $ flip replicate) . filter ((/= 0) . snd) . assocs $ runSTUArray $ do
                                        a <- newArray charRange 0
                                        forM_ list $ \c -> do
                                            i <- readArray a c
                                            writeArray a c (i + 1)
                                        return a
                                     
                                    main = replicateM 32 (randomRIO charRange) >>= print . countSort

                                    Гляну...
                                    Ответить
                    • HaskellGovno Только что #
                      http://liveworkspace.org/code/1WGydL$77
                      -- a = maybe [] (:[]) Nothing
                      
                      import Data.Char
                      import Data.Array
                      
                      addToList list (Just value) = value:list
                      addToList list Nothing = list
                      
                      itemToArrayItem valueToOrdinary list item = addToList list $ fmap (flip (,) 1) $ valueToOrdinary item
                      
                      codeOfBeginSuitableLetter = ord 'a'
                      codeOfEndSuitableLetter = ord 'z'
                      
                      isSuitableLetter symbol = 
                         let symbolCode = ord symbol in
                            symbolCode >= codeOfBeginSuitableLetter && symbolCode <= codeOfEndSuitableLetter
                            
                      arrayOfIsGlasnaya = listArray (codeOfBeginSuitableLetter, codeOfEndSuitableLetter) $ map (`elem` (map ord "AEOIUaeoiu")) [codeOfBeginSuitableLetter..codeOfEndSuitableLetter]
                      
                      isGlasnayaCode letterCode = arrayOfIsGlasnaya ! letterCode 
                      
                      isGlasnaya symbol = isSuitableLetter symbol && (isGlasnayaCode $ ord symbol)
                      
                      isSoglasnaya symbol = isSuitableLetter symbol && (not $ isGlasnaya symbol)
                      
                      soglsanayaCharToOrdinary symbol
                         | isSoglasnaya symbol   = Just $ ord symbol
                         | True                  = Nothing
                      
                      glsanayaCharToOrdinary symbol
                         | isGlasnaya symbol     = Just $ ord symbol
                         | True                  = Nothing
                      
                      countSort codeOfBegin codeOfEnd valueToOrdinary text = map chr $ concatMap (uncurry $ flip replicate) $ assocs $ accumArray (+) 0 (codeOfBegin, codeOfEnd) $ foldl valueToOrdinary [] text
                      
                      countSortLetters valueToOrdinary text =  countSort codeOfBeginSuitableLetter codeOfEndSuitableLetter (itemToArrayItem valueToOrdinary) text
                      
                      countSortAndClassify text = (countSortLetters glsanayaCharToOrdinary text) ++ (reverse $ countSortLetters soglsanayaCharToOrdinary text)
                      
                      main = print $ countSortAndClassify "I hate this fucking world and i want go to immutable world now."
                      Ответить
                      • CountSort - императивное питушение в функциональном стиле.
                        Работает только с латинскими lowercase символами в непрерывной упорядоченной кодировке.
                        O(n) - затраты памяти, хотя возможно из-за ленивости они будут O(1). Возможно чтобы получить О(1), код нужно поправить, чтобы хвосты не удерживались.
                        O(n) - алгоритмическая сложность.
                        Вот я правда не знаю, нужно как-то strict добавить, а то стек может начать разрастаться.
                        Ответить
                        • Инстересно, CountSort на хаскеле с применением массива быстрее варианта борманда с мапом?
                          Ответить
                          • С таким массивом возможно и медленнее. У дерева на каждом апдейте обновляется log(m) элементов, в иммутабельном массиве все m.
                            Ответить
                            • А с чего ты взял, что хаскель обновляет ни один элемент в массиве? Грязное нативное нутро хаскеля обновляет массив inplace без копирования, а нашей чистой программе кажется, что все по прежнему чисто.
                              Ответить
                              • С того что на старую копию массива могла остаться ссылка? Портить старый массив он сможет только если догадается при помощи dataflow анализа, что старый массив уже никому никогда не будет доступен.

                                Этож не diff array.
                                Ответить
                                • > Этож не diff array.
                                  А его можно без особых переделок применить в коде сортировки с массивом?
                                  Ответить
                                  • > Since GHC-6.12, DiffArray has been splitted off into separated package due to its "unusably slow".
                                    Надежды нет...
                                    Ответить
                                    • http://liveworkspace.org/code/1tt53n$12
                                      Data.Array.Diff совсем пропал...
                                      Data.Array.Unboxed тоже ничего не получается...
                                      Ответить
                                      • И все же, кто-нибудь знает как использовать Data.Array.Diff хотя бы в целях бенча?
                                        Читал про них на
                                        http://www.haskell.org/haskellwiki/Arrays
                                        но бесполезно. Их идеи не компилируются из-за не найденного модуля.
                                        Ответить
                            • А как написать красиво?
                              filter (\symbol -> isLetter symbol && isLower symbol) text

                              Хотелось бы как-то так:
                              filter (isLetter && isLower) text

                              Может как-то через апликативные функцторы или lift?
                              Ответить
                              • a .&&. b = \c -> a c && b c
                                filter (isLetter .&&. isLower) text
                                Как-то так?
                                Ответить
                                • Так, только есть ли стандартные средства, например через какие-то функции типа lift и тд?
                                  Ответить
                                  • Хочется матанчика?
                                    import Control.Arrow (&&&, >>>)
                                    
                                    both (x, y) = x && y
                                    
                                    filter (isLetter &&& isLower >>> both) text
                                    Так устроит?
                                    Ответить
                                    • Где -то я видел более краткий вариант, без определения дополнительных функций
                                      Ответить
                                    • http://ideone.com/80mhUs
                                      Ответить
                                      • http://ideone.com/dq36L9
                                        [color=gray]Но честно признаюсь, подглядел у Лямбдабота.[/color]
                                        Ответить
                                        • import Data.Char
                                          import Control.Monad
                                          import Control.Monad.Instances
                                           
                                          main = getLine >>= putStrLn . filter (liftM2 (&&) isLetter isLower)
                                          Я так и думал, что с лифтингом это можно сделать без лишних функций!
                                          Ответить
                                          • instance Monad ((->) a) вообще страшная штука. Вот, например, мой друг чисто-функциональный интерпретатор Брейнфака написал: http://gist.github.com/4079778
                                            Ответить
                            • Я взял твой код и планирую устроить ему бенчимарк с кодом на массиве.
                              http://liveworkspace.org/code/1XvuHq$21
                              import Data.Map as Map
                              import Data.Char
                              
                              mapCountSort list = concatMap (uncurry $ flip replicate) $
                                  Map.toList $ Prelude.foldl (\m e -> Map.insertWith (+) e 1 m) Map.empty list
                                  
                              mapCountSortAndClassify text = 
                                 let 
                                    filtredText = Prelude.filter (\symbol -> isLetter symbol && isLower symbol) text
                                    isGlasnaya = (`elem` "AEOIUaeoiu")
                                    glasnieInText = Prelude.filter isGlasnaya filtredText
                                    soglasnieInText = Prelude.filter (not.isGlasnaya) filtredText
                                 in
                                    (mapCountSort glasnieInText) ++ (reverse $ mapCountSort soglasnieInText)
                              
                              main = print $ mapCountSortAndClassify "I hate this fucking world and i want go to immutable world now."

                              Вроде поставил в одинаковые условия. Планирую устроить бенч вида replicate этой строки много раз.
                              Только блин, как убрать у всех функций из прелюдии необходимость вместо
                              foldl писать Prelude.foldl ? Проблема появилась после того, как импортнул Data.Map
                              Ответить
                              • Разобрался с проблемой.
                                http://liveworkspace.org/code/1XvuHq$26
                                import qualified Data.Map as Map
                                import Data.Char
                                
                                mapCountSort list = concatMap (uncurry $ flip replicate) $
                                    Map.toList $ foldl (\m e -> Map.insertWith (+) e 1 m) Map.empty list
                                    
                                mapCountSortAndClassify text = 
                                   let 
                                      filtredText = filter (\symbol -> isLetter symbol && isLower symbol) text
                                      isGlasnaya = (`elem` "AEOIUaeoiu")
                                      glasnieInText = filter isGlasnaya filtredText
                                      soglasnieInText = filter (not.isGlasnaya) filtredText
                                   in
                                      (mapCountSort glasnieInText) ++ (reverse $ mapCountSort soglasnieInText)
                                
                                main = print $ mapCountSortAndClassify "I hate this fucking world and i want go to immutable world now."

                                Со всем согласен? Можно мериться?
                                Ответить
                                • Померил:
                                  http://liveworkspace.org/code/2Vf3lp$5
                                  http://liveworkspace.org/code/1tt53n$10

                                  Способ с мапом привел к стековерфловочке. Способ с массивом на взгляд медленноват, но вроде оверфловочки нет. Видимо действительно получилось О(n^2) из-за копирования массива каждый раз.
                                  Ответить
                                  • Добавил -O2:
                                    http://liveworkspace.org/code/2Vf3lp$6
                                    http://liveworkspace.org/code/1tt53n$11

                                    Но по идее надо поиграться со строгостью, а то он походу ничего не делает пока не дочитает строку до конца.
                                    Ответить
                                    • Блин. От этих массивов в хаскеле больше беды, чем скорости. O(log n) мапа и то быстрее работает. :(
                                      Ответить
    • Ну еще вариант таки на Си:
      http://ideone.com/aTR6o2
      Конечно, хреново тестированный и со скрипом скомпиленный.
      Ответить
      • Мои глаза... Можно постить отдельным тредом. Мне сегодня не спится, поэтому привожу более вменяемую реализацию. Я считал, что заглавные идут непосредственно перед прописными, т.е. A > a, но A < b. Мне это кажется разумным.
        http://ideone.com/JfYGCQ
        Работает в постоянном объёме памяти, не дёргает кучу, жрёт строки до 4Гб, толерантна к нестандартному порядку букв в кодировке. Юникод не ест, простите.
        Ответить
        • Сэр, мы работаем на скорость, сэр.
          Не соизволите ли вы оформить ваш код для бенчмарка?
          З.Ы. В задании ни слова о порядке букв в кодировке.
          З.З.Ы. static unsigned long counts - нехорошо, наверн, глобальной то делать, хотя опять же ни слова в задании.
          З.З.Ы. Память не жрет, потому как срет в stdout. 4 Гб буду высираться до конца следующего калаендаря Майя.
          Ответить
          • > Память не жрет, потому как срет в stdout.
            Вы так говорите, как будто ваша программа жрет память, но не будет срать в stdout.
            Ответить
            • Жрет она, конечно, чуть больше, чем ей положено, но константно.
              Я немного не то имел в виду про stdout, а то, что мол одно зло променяли на другое.
              Ответить
              • > char *output_string = (char *)malloc(strlen(input_string) + 1);
                Хуяссе константно. Это между прочим линейное O(n).

                stdout не зло. Программа в любом случае должна выводить. Ваша тоже выводит. Разве что у Романа она чаще дрючит putchar, что, впрочем, не страшно, т.к. там все равно есть буферизация, и оно будет ненамного медленнее, чем мутить свой буфер.
                Ответить
                • Адин раз она это делает.

                  Да, для одной строки может и линейно, а для 10000 строк достаточно уж выделить один буффер максимальной длины в начале и довольно, как я это и сделал. Другой вопрос, если задача встанет: вот вам ОДНА гигабайтовая строка, дерзайте. Вот Роман с расчетом на это и сделал, видимо. И это согласуется с начальным говнокодом.

                  Но мне уже в треде с лиспом взбрело в голову делать тест на 10000 мелких строк, так я и тут продолжил эту линию, чтобы затем сравнивать в почти одинаковых условиях.

                  В конце концов, все сводится к условиям задачи и критериям оценки. Что вы хотите? Быстро, читабельно, универсально, портабельно, минимум кода, минимум потребления памяти? Не все сразу.
                  Ответить
                  • А это O(max(n)), а не константное. В плане памяти код Романа эффективней. В плане скорости его код можно дополнить выходным буфером небольшого размера. Это пара-тройка строк.
                    Ответить
          • > мы работаем на скорость, сэр
            Тогда качество ваших бенчмарков вызывает ха, хаха.
            Мерить там нечего: один символ строки - один доступ по индексу и инкремент. Ни линейных поисков, не выделений памяти. Быстрее не напишешь, да и не нужно.

            С минимальнымм усилиями по жонглированию входными/выходными буферами можно сделать из этого подпрограмму, но я не вижу в этом смысла.

            > В задании ни слова о порядке букв в кодировке.
            Именно поэтому нужно быть осторожным. Буквы могут идти не по порядку.
            Ответить
            • > Именно поэтому нужно быть осторожным. Буквы могут идти не по порядку.
              Надеюсь, я не доживу до того, когда в ASCII кто-то аглийские буквы начнет переставлять.

              Но вообще, очевидно, можно допилить до универсального в этом плане состояния.
              Ответить
              • >> Буквы могут идти не по порядку.
                > Надеюсь, я не доживу
                http://ru.wikipedia.org/wiki/EBCDIC

                Слава богу уже пережили.
                Ответить
    • суть_треда.jpg
      http://tinyurl.com/b889b4w
      Ответить
    • Вью в сторону вектора. ДиффАррей совсем обсолет. Заремовили ит.
      Ответить
      • ДиффВекторов тоже нет. Вообщем засада. Хаскель не умеет в массивы без монад. Говорят, то DiffArray работает медленее immutable array. Это что нужно было курить, чтобы полностью копируемый каждый раз массив при каждом изменении работал медленее нормального модифицируемого массива.
        Ответить

    Добавить комментарий