На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! Правила раздела:
1. Название темы - краткое описание кто/что против кого/чего
2. В первом сообщении - список параметров, по которым идет сравнение.
3. Старайтесь аргументировать свои высказывания. Фразы типа "Венда/Слюникс - ацтой" считаются флудом.
4. Давайте жить дружно и не доводить обсуждение до маразма и личных оскорблений.
Модераторы: Модераторы, Комодераторы
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> C++ vs функциональщина , Вброс от самого Бьёрна (и немного от Кармака)
    http://www.linux.org.ru/forum/development/9525806

    С++-ники наверняка скажу, что просто теперь С++ стал еще фичастей, но мы-то с вами знаем.
    Сообщение отредактировано: korvin -
      Ну, если наша скука зашла так далеко, что мы уже ЛОР обсуждаем, то следует сказать, что stevejobs - тролль неважнецкий. Его интерпретация действительности крайне выборочна, он передёргивает факты. И делает это вполне осознанно, в чём и признаётся. Хотя считает, что это всё для благой цели избавления мира от C++, но на деле он просто неосилятор. А его предыдущий топик о C++ - просто смесь бреда с непониманием.

      По теме:
      1. Кармак - не авторитет.
      2. Яхз что там Бьярн пилит, но язык уже давно не его.
      3. Сопоставление с образцом в ОО языке нужно постольку поскольку... а возможно, что и вообще не нужно.
      4. Нужны мультиметоды - а их Бьярн со товарищи уже запилили, жаль не приняли предложение.
      Сообщение отредактировано: MyNameIsIgor -
        Блин, я-то ведь их тоже запилил как либу. Когда ж руки-то дойдут опубликовать, два года почти прошло...
          korvin, там по-моему С++ vs функциональщина ни при чем...

          Может пару тезисов вбросишь лучше на эту тему? А то там обсуждать-то и нечего.
            Кармак на Плюсах и не писал-то особо. Он Сишечник. Вот Вальвовцы - те да. Вроде бы. По крайней мере где-то внутрях их .EXEх или .DLLек на boost::filesystem я натыкался.
              Наткнулся я тут на форуме Sql.ru на давний зачотный срач вокруг C++. Там некий Ксеноцефал и в хвост, и в гриву чихвостил С++. Среди прочего наткнулся я вот на какую картинку:
              Прикреплённая картинка
              Прикреплённая картинка

              И тут меня стукнуло - ведь пример кода в правой части делает совсем не то, что пример кода в левой части. К тому же, он не на C++, а на C. Ну и в итоге решил прикинуть, как бы выглядел на C++11 код, эквивалетный хаскельному. Получилось вот что. Ведь при всём своём изяществе Haskell, проповедуя парадигму чистых функций, всякий раз возвращает копию отсортированного списка...

              Это сообщение было перенесено сюда или объединено из темы "D vs C++"
                Introduction/Direct Translation
                Цитата
                The quicksort quoted in Introduction isn't the "real" quicksort and doesn't scale for longer lists like the c code does.

                http://programming.reddit.com/info/5yutf/comments/

                Here are some points to how the "real" quicksort would look in haskell.

                Lennart Augustsson has a quicksort entry on his blog which is pure (no unsafe):

                http://augustss.blogspot.com/2007/08/quick...icksort-is.html

                Another version (uses System.IO.Unsafe), is below.

                There is also a "parallel" quicksort at

                http://www.macs.hw.ac.uk/~dsg/gph/nofib/

                roconnor claims that in haskell the "real" quicksort is really a treesort:

                http://programming.reddit.com/info/2h0j2/comments

                Unfortunately none of the above "real" quicksorts seems to compile as given, when copy/pasted into ghci. Can someone fix? The "parallel" quicksort gave error "unknown package concurrent" when I ran make in quicksort/gransim.

                Has anyone got a functioning "real" quicksort that works on copy/paste?

                The program below is working very very slowly. It's probably slowsort... :o)

                ExpandedWrap disabled
                  import Control.Monad (when)
                  import Control.Monad.ST
                  import Data.Array.ST
                  import Data.Array.IArray
                  import Data.Array.MArray
                   
                  qsort :: (IArray a e, Ix i, Enum i, Ord e) => a i e -> a i e
                  qsort arr = processArray quickSort arr
                   
                  processArray :: (IArray a e, IArray b e, Ix i)
                               => (forall s. (STArray s) i e -> ST s ()) -> a i e -> b i e
                  processArray f (arr :: a i e) = runST $ do
                      arr' <- thaw arr :: ST s (STArray s i e)
                      f arr'
                      unsafeFreeze arr'
                   
                  quickSort :: (MArray a e m, Ix i, Enum i, Ord e) => a i e -> m ()
                  quickSort arr = qsort' =<< getBounds arr
                    where
                      qsort' (lo, hi) | lo >= hi  = return ()
                                      | otherwise = do
                          p <- readArray arr hi
                          l <- mainLoop p lo hi
                          swap l hi
                          qsort' (lo, pred l)
                          qsort' (succ l, hi)
                   
                      mainLoop p l h  | l >= h    = return l
                                      | otherwise = do
                          l' <- doTil (\l' b -> l' < h  && b <= p) succ l
                          h' <- doTil (\h' b -> h' > l' && b >= p) pred h
                          when (l' < h') $ do
                              swap l' h'
                          mainLoop p l' h'
                   
                      doTil p op ix = do
                          b <- readArray arr ix
                          if p ix b then doTil p op (op ix) else return ix
                   
                      swap xi yi = do
                          x <- readArray arr xi
                          readArray arr yi >>= writeArray arr xi
                          writeArray arr yi x

                This uses various extensions to make the types ridiculously general, but the actual algorithm (quickSort) is plain Haskell.

                A more specific/direct translation (neither this nor the C version is polymorphic) is offered by Daniel Fischer, who reports that this version runs within 2x of the C version:

                ExpandedWrap disabled
                  import Data.Array.Base (unsafeRead, unsafeWrite)
                  import Data.Array.ST
                  import Control.Monad.ST
                   
                  myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
                  myqsort a lo hi
                     | lo < hi   = do
                         let lscan p h i
                                 | i < h = do
                                     v <- unsafeRead a i
                                     if p < v then return i else lscan p h (i+1)
                                 | otherwise = return i
                             rscan p l i
                                 | l < i = do
                                     v <- unsafeRead a i
                                     if v < p then return i else rscan p l (i-1)
                                 | otherwise = return i
                             swap i j = do
                                 v <- unsafeRead a i
                                 unsafeRead a j >>= unsafeWrite a i
                                 unsafeWrite a j v
                             sloop p l h
                                 | l < h = do
                                     l1 <- lscan p h l
                                     h1 <- rscan p l1 h
                                     if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1
                                 | otherwise = return l
                         piv <- unsafeRead a hi
                         i <- sloop piv lo hi
                         swap i hi
                         myqsort a lo (i-1)
                         myqsort a (i+1) hi
                     | otherwise = return ()

                  D_KEY, я это хотел запостить! >:( :'(
                    OMFG! :wacko: :wacko: :wacko:

                    Добавлено
                    А вот что будет, если не стремиться повторить логику хаскеля.
                      Цитата Flex Ferrum @
                      А вот что будет, если не стремиться повторить логику хаскеля.

                      Гмм... У меня получилось так
                      ExpandedWrap disabled
                        template<class ForwardIt>
                        void quick_sort(ForwardIt first, ForwardIt last)
                        {
                            if(first == last) return;
                            auto pivot_index = partition(first, last, [pivot = *first](const auto& value) { return value < pivot; });
                            quick_sort(first, pivot_index);
                            quick_sort(++pivot_index, last);
                        }

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

                      Совсем другое дело - где много лет назад обещанные оптимизации для функциональных языков, которые должны реализовывать подобные вещи императивно, оставляя для программиста функциональную семантику?
                        Цитата MyNameIsIgor @
                        Гмм... У меня получилось так

                        Я тоже так пробовал. Но... Это не совсем верная реализация. partition гарантирует только то, что после до и после pivot_index значения будут разделены согласно предикату. Но вот порядок их следования partition не гарантирует. Таким образом, по pivot_index может оказаться совсем не pivot. Отсюда и некоторые приседания в моём коде.
                        Чтобы твой алгоритм работал, требуется stable_partition вместо partition.

                        Добавлено
                        Цитата MyNameIsIgor @
                        Но вообще это всё чушь - и в изначальном примере видно, что преимущество хаскеля в использовании генератора списков вместо явно написанной функции разбиения. Понятно, что если она уже есть, то всё будет "не так однозначно".

                        Угу. Именно так.
                        Сообщение отредактировано: Flex Ferrum -
                          Цитата MyNameIsIgor @
                          Совсем другое дело - где много лет назад обещанные оптимизации для функциональных языков, которые должны реализовывать подобные вещи императивно, оставляя для программиста функциональную семантику?

                          В первый раз такое слышу. И каким образом должен быть "оптимизирован" тот "функциональный" недо-quicksort?
                          Сообщение отредактировано: korvin -
                            Цитата korvin @
                            И каким образом должен быть "оптимизирован" тот "функциональный" недо-quicksort?

                            Анализом потока управления. Списки, генерируемые внутри функции сортировки, алиасов не имеют, потому мы можем их изменять - программист об этом не узнает. А на основе генератора списка мы можем узнать как именно его менять, не генерируя новый. Это сложно, но обещалось уже давненько.
                              Цитата MyNameIsIgor @
                              Анализом потока управления. Списки, генерируемые внутри функции сортировки, алиасов не имеют, потому мы можем их изменять - программист об этом не узнает. А на основе генератора списка мы можем узнать как именно его менять, не генерируя новый. Это сложно, но обещалось уже давненько.

                              Но зачем? Для того, чтобы поменять два элемента, придется бегать по списку от головы, кроме того, это входит в конфликт с другой обещалкой -- автоматическим распараллеливанием.
                                Цитата korvin @
                                Но зачем?

                                Да чтобы памяти столько не жрать :)
                                Цитата korvin @
                                Для того, чтобы поменять два элемента, придется бегать по списку от головы

                                Так не обязательно, можно запускать два итератора - место вставки и искомый элемент. Да и реализация списка может быть какой угодно, не обязательно односвязный список.
                                Цитата korvin @
                                кроме того, это входит в конфликт с другой обещалкой -- автоматическим распараллеливанием

                                Так вроде не должно быть сложностей - от'map'ить список по кускам на потоки, для каждого куска разделить список по "меньше" и "не меньше", и с'reduce'ить разделённые части.
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0739 ]   [ 18 queries used ]   [ Generated: 29.03.24, 02:19 GMT ]