Антон
Ну, зависит от того, как nub определено. Но свёртка вообще за линейное время работать будет
A64m
а это не будет что ли?
A64m
нуб определен так, что константное кол-во уникальных элементов ищет за линейное время
A64m
потому что N * C = N
Alexander
линейная там сложность
Aleksey
> O(n^2). The nub function removes duplicate elements from a list. In particular, it keeps only the first occurrence of each element. (The name nub means `essence'.) It is a special case of nubBy, which allows the programmer to supply their own equality test.
Alexander
и?
Aleksey
> 2) нафига сюда nub с квадратичной сложностью?
Aleksey
у нее действительно квадратичная сложность
Alexander
нет
Vladimir
Не будет там квадратичной.
Alexander
у нее линейная сложность
Aleksey
а какая?
Aleksey
это как?
Alexander
у того, что написал клапауций
Aleksey
если в доке квадратичная
Alexander
ленивость ftw
Vladimir
На списке из равных элементов будет линейная. А при взятии двух элементов -- тоже линейная.
Alexander
константа там хуже чем у свертки
Vladimir
В доке -- наихудший случай.
Alexander
в доке случай для полного вычисления
Alexander
но функция итеративная, а не монолитная
Alexander
а для любого конечного подписка она линейная
Alexander
хотя константа ожидает делать лучшего
Alexander
k* (k-1) для списка размера k
Alexander
но это константа
Alexander
от n не зависит
Vladimir
Для бесконечных списков оно не работает. Совсем)
Vladimir
К счастью.
Alexander
очевидно, что это утверждение неверно
Alexander
для бесконечного списка оно сразу же вернёт бесконечный список
Alexander
и любой подписок можно достать
Vladimir
length . nub . repeat?
Alexander
и?
Aleksey
Prelude Data.List> take 2 $ nub $ replicate 1000000000000 1
[1^CInterrupted.
Alexander
это явно не попадает под "совсем не работает"
Aleksey
там элементы гарантированно разные в списке?
Alexander
@s9gf4ult там линено
Aleksey
что линейно?
Alexander
при всех одинаковых оно делает то же что свертка
Vladimir
Окай, а на каких бесконечных списках работает nub?
Alexander
сверяет со всеми возвращенными которых 1
Alexander
и возвращает бесконечный список
Vladimir
Чо?
Alexander
ну блин ну хватит тупить уже
Aleksey
дайте линк на код который тут у вас линейный
Aleksey
потому что take 2 . nub не линейно в худжем случае
Alexander
length . take 2 . nub
Vladimir
take 10 $ nub $ [1..]
Alexander
линейно
Aleksey
в худшем случае - да
Aleksey
попробуй запустить в ghci
Aleksey
take 2 $ nub $ replicate 1000000000000 1
Alexander
в любом случае линейная сложность
Aleksey
запусти
Alexander
с тебя сок если я докажу что линейно
Aleksey
линейная относительно длинны списка, или аргумента take ?
Alexander
Окей?
Alexander
относительно длины списка конечно
Alexander
это нормально, тут неочевидное место
Aleksey
а если take 3 ?
Aleksey
слабо линейно сделать?
Aleksey
take 3 . nub
Aleksey
короче понятно, посмотрел в исходник
Aleksey
первый элемент возвращается сразу
Vladimir
Получается, что nub упадёт в дно только если подсунуть бесконечный список из конечного числа элементов и попросить + 1.
Aleksey
бесконечный список из конечного числа элементов
Aleksey
круто
Vladimir
ну cycle [1..7], например
Алексей
repeat x
Aleksey
не, take 2 $ nub $ repeat 1 должно упасть
Aleksey
ghci повис
Alexander
конечно должно упасть
Alexander
сложность О(n)
Vladimir
Ну это и есть дно, чо)