LINUX.ORG.RU
решено Форум — Development  

Помогите пройти тест по Haskell

 ,


1

2 
Отметьте функции, которые не могут привести к расходимости ни на каком корректном наборе аргументов.

foo a = a

bar = const foo

baz x = const True

quux = let x = x in x

corge = 10

grault x 0 = x
grault x y = x

garply = grault 'q'

waldo = foo

Я нашел, только baz и corge. Но это не правильный ответ.

 ← 1 2 3 →
Ответ на: комментарий от trupanka

на моей машине мой qsort сортирует список из миллиона элементов типа инт примерно 20 секунд. замена фильтра на партитион ускоряет его примерно на 5%. делал всего 2 замера.

MyTrooName, попробую стандартный хаскелевый сейчас

AndreyKl ★★★★★
()
Последнее исправление: AndreyKl (всего исправлений: 1)
Ответ на: комментарий от MyTrooName 
part :: (a → Bool) → [a] → ([a], [a])
part f [] = ([], [])
part f (x:xs) = if f(x) then (x:left, right)
                        else (left, x:right)
  where (left, right) = part f xs

qsort :: Ord a ⇒ [a] → [a]
qsort [] = []
qsort [x] = [x]
qsort (x:xs) = qsort left ++ x : qsort right
  where (left, right) = part (<x) xs
MyTrooName ★★★★★
()
Ответ на: комментарий от AndreyKl

мой qsort сортирует список из миллиона элементов типа инт примерно 20 секунд

При этом стандартный сорт из Data.List сортирует за 5 секунд. И памяти есть в 4 раза меньше.

нормальный qsort должен сортировать список in-place без лишних затрат памяти, но это haskell. может, отсюда и замедление растет.

разница по времени в 4 раза - в пределах погрешности. покажи, как именно мерял.

MyTrooName ★★★★★
()
Ответ на: комментарий от MyTrooName

да, я нашёл, спасибо.

мерджсорт на 5 миллионах элементах обгоняет мой код уже не в 5 раз а чуть более чем вдвое. вероятно мой квиксорт действительно обгонит мердж когда нибудь. но тест занимает уже две минуты. может завтра на 15 миллионов запущу на поглядеть.

AndreyKl ★★★★★
()
Ответ на: комментарий от MyTrooName

разница по времени в 4 раза - в пределах погрешности. покажи, как именно мерял.

*Списки> let l = take 5000000 $ randomList 42 :: [Int]
(0.00 secs, 0 bytes)
*Списки> let l1 = qsort' l
(0.00 secs, 0 bytes)
*Списки> let l2 = qsort l
(0.00 secs, 0 bytes)
*Списки> let l3 = Data.List.sort l
(0.00 secs, 0 bytes)
*Списки> drop 4999999 l1
[9223371674832527611]
(120.37 secs, 38,466,246,728 bytes)
*Списки> drop 4999999 l2
[9223371674832527611]
(118.79 secs, 17,860,522,760 bytes)
*Списки> drop 4999999 l3
[9223371674832527611]
(55.86 secs, 7,841,731,272 bytes)

нормальный qsort должен сортировать список in-place без лишних затрат памяти, но это haskell. может, отсюда и замедление растет.

вероятно, да

AndreyKl ★★★★★
()
Последнее исправление: AndreyKl (всего исправлений: 1)
13 февраля 2017 г.
Ответ на: комментарий от iVS

то заработал ты его нечестным путем

По честному живут только лохи и терпилы.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.
 ← 1 2 3 →
Development