Re: [racket-users] Does match against list traverse the whole list?
Thanks everyone. I guess I misread the docs. Great to hear re: caching. Guess I wasn't screwing things up as I momentarily feared. :) Sam Tobin-Hochstadt writes: > Here are some quick numbers on the traditional Racket VM: > > ``` >> (define v (build-list 1000 values)) >> (time (list? v)) > cpu time: 47 real time: 47 gc time: 0 > #t >> (time (list? v)) > cpu time: 31 real time: 31 gc time: 0 > #t >> (time (list? v)) > cpu time: 13 real time: 13 gc time: 0 > #t >> (time (list? v)) > cpu time: 15 real time: 16 gc time: 0 > #t >> (time (list? v)) > cpu time: 4 real time: 4 gc time: 0 > #t >> (time (list? v)) > cpu time: 1 real time: 1 gc time: 0 > #t >> (time (list? v)) > cpu time: 2 real time: 2 gc time: 0 > #t >> (time (list? v)) > cpu time: 1 real time: 1 gc time: 0 > #t >> (time (list? v)) > cpu time: 1 real time: 0 gc time: 0 > #t >> (time (list? v)) > cpu time: 1 real time: 0 gc time: 0 > #t >> (time (list? v)) > cpu time: 1 real time: 0 gc time: 0 > #t >> (define v2 (drop v (/ 1000 2) )) >> (time (list? v2)) > cpu time: 0 real time: 0 gc time: 0 > #t > ``` > Here's some RacketCS numbers, which are a little different: > > ``` > [samth@huor:~/.../extra-pkgs/typed-racket/typed-racket-test (master) > plt] racketcs > Welcome to Racket v7.5.0.4 [cs]. >> (define v (build-list 1000 values)) >> (time (list? v)) > cpu time: 77 real time: 77 gc time: 0 > #t >> (time (list? v)) > cpu time: 73 real time: 73 gc time: 0 > #t >> (time (list? v)) > cpu time: 53 real time: 53 gc time: 0 > #t >> (time (list? v)) > cpu time: 37 real time: 37 gc time: 0 > #t >> (time (list? v)) > cpu time: 25 real time: 25 gc time: 0 > #t >> (time (list? v)) > cpu time: 12 real time: 13 gc time: 0 > #t >> (time (list? v)) > cpu time: 2 real time: 2 gc time: 0 > #t >> (time (list? v)) > cpu time: 3 real time: 3 gc time: 0 > #t >> (time (list? v)) > cpu time: 1 real time: 1 gc time: 0 > #t >> (time (list? v)) > cpu time: 0 real time: 0 gc time: 0 > #t >> (define v2 (drop v (/ 1000 2) )) >> (time (list? v2)) > cpu time: 61 real time: 61 gc time: 0 > #t >> (time (list? v2)) > cpu time: 50 real time: 50 gc time: 0 > #t >> (time (list? v2)) > cpu time: 15 real time: 15 gc time: 0 > #t >> (time (list? v2)) > cpu time: 25 real time: 25 gc time: 0 > #t >> (time (list? v2)) > cpu time: 22 real time: 22 gc time: 0 > #t >> (time (list? v2)) > cpu time: 3 real time: 3 gc time: 0 > #t >> (time (list? v2)) > cpu time: 0 real time: 0 gc time: 0 > #t > ``` > > If you want to make that match pattern faster, use `cons` or `list-rest`. > > Sam > > On Tue, Oct 29, 2019 at 2:18 PM Alexis King wrote: >> >> > On Oct 29, 2019, at 12:41, Christopher Lemmer Webber >> > wrote: >> > >> > But the documentation says that the `list?` predicate is O(n). >> >> I’m not sure where you’re seeing that, but the documentation actually says >> just the opposite. Specifically, it says this: >> >> > This procedure effectively takes constant time due to internal caching (so >> > that any necessary traversals of pairs can in principle count as an extra >> > cost of allocating the pairs). >> >> In other words, `list?` is amortized constant time. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Racket Users" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to racket-users+unsubscr...@googlegroups.com. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/racket-users/4E904F54-3605-4964-AC19-EB6617A5D9F7%40gmail.com. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/87k18nxv8c.fsf%40dustycloud.org.
Re: [racket-users] Does match against list traverse the whole list?
Here are some quick numbers on the traditional Racket VM: ``` > (define v (build-list 1000 values)) > (time (list? v)) cpu time: 47 real time: 47 gc time: 0 #t > (time (list? v)) cpu time: 31 real time: 31 gc time: 0 #t > (time (list? v)) cpu time: 13 real time: 13 gc time: 0 #t > (time (list? v)) cpu time: 15 real time: 16 gc time: 0 #t > (time (list? v)) cpu time: 4 real time: 4 gc time: 0 #t > (time (list? v)) cpu time: 1 real time: 1 gc time: 0 #t > (time (list? v)) cpu time: 2 real time: 2 gc time: 0 #t > (time (list? v)) cpu time: 1 real time: 1 gc time: 0 #t > (time (list? v)) cpu time: 1 real time: 0 gc time: 0 #t > (time (list? v)) cpu time: 1 real time: 0 gc time: 0 #t > (time (list? v)) cpu time: 1 real time: 0 gc time: 0 #t > (define v2 (drop v (/ 1000 2) )) > (time (list? v2)) cpu time: 0 real time: 0 gc time: 0 #t ``` Here's some RacketCS numbers, which are a little different: ``` [samth@huor:~/.../extra-pkgs/typed-racket/typed-racket-test (master) plt] racketcs Welcome to Racket v7.5.0.4 [cs]. > (define v (build-list 1000 values)) > (time (list? v)) cpu time: 77 real time: 77 gc time: 0 #t > (time (list? v)) cpu time: 73 real time: 73 gc time: 0 #t > (time (list? v)) cpu time: 53 real time: 53 gc time: 0 #t > (time (list? v)) cpu time: 37 real time: 37 gc time: 0 #t > (time (list? v)) cpu time: 25 real time: 25 gc time: 0 #t > (time (list? v)) cpu time: 12 real time: 13 gc time: 0 #t > (time (list? v)) cpu time: 2 real time: 2 gc time: 0 #t > (time (list? v)) cpu time: 3 real time: 3 gc time: 0 #t > (time (list? v)) cpu time: 1 real time: 1 gc time: 0 #t > (time (list? v)) cpu time: 0 real time: 0 gc time: 0 #t > (define v2 (drop v (/ 1000 2) )) > (time (list? v2)) cpu time: 61 real time: 61 gc time: 0 #t > (time (list? v2)) cpu time: 50 real time: 50 gc time: 0 #t > (time (list? v2)) cpu time: 15 real time: 15 gc time: 0 #t > (time (list? v2)) cpu time: 25 real time: 25 gc time: 0 #t > (time (list? v2)) cpu time: 22 real time: 22 gc time: 0 #t > (time (list? v2)) cpu time: 3 real time: 3 gc time: 0 #t > (time (list? v2)) cpu time: 0 real time: 0 gc time: 0 #t ``` If you want to make that match pattern faster, use `cons` or `list-rest`. Sam On Tue, Oct 29, 2019 at 2:18 PM Alexis King wrote: > > > On Oct 29, 2019, at 12:41, Christopher Lemmer Webber > > wrote: > > > > But the documentation says that the `list?` predicate is O(n). > > I’m not sure where you’re seeing that, but the documentation actually says > just the opposite. Specifically, it says this: > > > This procedure effectively takes constant time due to internal caching (so > > that any necessary traversals of pairs can in principle count as an extra > > cost of allocating the pairs). > > In other words, `list?` is amortized constant time. > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/racket-users/4E904F54-3605-4964-AC19-EB6617A5D9F7%40gmail.com. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAK%3DHD%2BZsYFDbK3A8z74A0vd4bMcakDgSYUtXQvKhPm18SNHicg%40mail.gmail.com.
Re: [racket-users] Does match against list traverse the whole list?
>From the expansion result, match does check whether the inspected value is a list using list?. But at least for the current version of Racket (and the C VM), list? is handled specially and ``effectively takes constant time due to internal caching.'' (quoted from: https://docs.racket-lang.org/reference/pairs.html?q#(def._((quote._~23~25kernel)._list~3f)) ) On Tue, Oct 29, 2019 at 12:41 PM Christopher Lemmer Webber wrote: > > Imagine the following code: > > (let lp ([items '(1 2 3 4 5)]) > (match items > [(list head rest ...) > (cons (* head 2) >(lp rest))])) > > My gut feeling is "oh, this is just O(n) because it's pulling the top > off the list quite efficient." > > But then I realized that: > > (match '(1 2 3 4 . 5) > [(list head rest ...) >(* head 2)]) > > throws an exception because it's a dotted list. > > But the documentation says that the `list?` predicate is O(n). I'm > suddenly fearing, have I been writing O(n^2) code this whole time? Does > match against list actually check the whole list every time? > > -- > You received this message because you are subscribed to the Google Groups > "Racket Users" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to racket-users+unsubscr...@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/racket-users/87lft3xxdo.fsf%40dustycloud.org. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CAMTzy%2BZ6z6EETExv-5QaDdKy-nG%3DVF%2BC3N4w0VoMNwLL%3D0gikA%40mail.gmail.com.
Re: [racket-users] Does match against list traverse the whole list?
> On Oct 29, 2019, at 12:41, Christopher Lemmer Webber > wrote: > > But the documentation says that the `list?` predicate is O(n). I’m not sure where you’re seeing that, but the documentation actually says just the opposite. Specifically, it says this: > This procedure effectively takes constant time due to internal caching (so > that any necessary traversals of pairs can in principle count as an extra > cost of allocating the pairs). In other words, `list?` is amortized constant time. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/4E904F54-3605-4964-AC19-EB6617A5D9F7%40gmail.com.
[racket-users] Does match against list traverse the whole list?
Imagine the following code: (let lp ([items '(1 2 3 4 5)]) (match items [(list head rest ...) (cons (* head 2) (lp rest))])) My gut feeling is "oh, this is just O(n) because it's pulling the top off the list quite efficient." But then I realized that: (match '(1 2 3 4 . 5) [(list head rest ...) (* head 2)]) throws an exception because it's a dotted list. But the documentation says that the `list?` predicate is O(n). I'm suddenly fearing, have I been writing O(n^2) code this whole time? Does match against list actually check the whole list every time? -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/87lft3xxdo.fsf%40dustycloud.org.
