Re: [racket-users] Fast way to map over a list many times, changing ONE element each time?
Is there a split-at-reverse anywhere, equivalent to split-at except that the first return value is reversed? If not, should that be added somewhere like srfi/1? I’m asking because wanted to be able to write functions like: (define ((drop-lens n) lst) (define-values [fst-lst rst-lst] (split-at-reverse lst n)) (values rst-lst (λ (x) (append-reverse fst-lst x (define ((list-ref-lens i) lst) (match-define-values [fst-lst val:rst-lst] (split-at-reverse lst i)) (match-define (cons val rst-lst) val:rst-lst) (values val (λ (x) (append-reverse fst-lst (cons x rst-lst) These are lenses as used in this package: https://github.com/jackfirth/lenses I wrote my own version of split-at-reverse, but I’m wondering if it should be put in something like srfi/1 as a companion to append-reverse, or if it perhaps already is in some other library. Alex Knauth On Jun 19, 2015, at 4:28 PM, Jens Axel Søgaard jensa...@soegaard.net wrote: A more efficient version using append-reverse from srfi/1. #lang racket (require (only-in srfi/1 append-reverse)) (define (list-splits xs) (define (loop ys zs) ; xs = (append (reverse ys) yz) (match zs ['() '()] [(cons z zs*) (cons (list ys zs) (loop (cons z ys) zs*))])) (loop '() xs)) (define (map-once f xs) (for/list ([ys+zs (list-splits xs)]) (match ys+zs [(list ys '()) '()] [(list ys (cons z zs)) (append-reverse ys (cons (f z) zs))]))) (list-splits '(1 2 3)) (map-once sqr '(1 2 3)) 2015-06-19 22:07 GMT+02:00 Jens Axel Søgaard jensa...@soegaard.net: #lang racket (define (list-splits xs) (define (loop ys zs) ; xs = (append (reverse ys) yz) (match zs ['() '()] [(cons z zs*) (cons (list ys zs) (loop (cons z ys) zs*))])) (loop '() xs)) (define (map-once f xs) (for/list ([ys+zs (list-splits xs)]) (match ys+zs [(list ys '()) '()] [(list ys (cons z zs)) (append (reverse ys) (cons (f z) zs))]))) (list-splits '(1 2 3)) (map-once sqr '(1 2 3)) 2015-06-19 22:05 GMT+02:00 Jon Zeppieri zeppi...@gmail.com: It's unlikely that an implementation using continuations would be faster than one that does not. An idiomatic solution might look like: (define (map-once fn xs) (for/list ([i (in-range (length xs))]) (for/list ([(x j) (in-indexed (in-list xs))]) (cond [(= i j) (fn x)] [else x] But it's not terribly fast. If you're willing to use vectors instead of lists, then maybe: (define (map-once fn xs) (build-vector (vector-length xs) (λ (i) (define v (vector-copy xs)) (vector-set! v i (fn (vector-ref v i))) v))) On Fri, Jun 19, 2015 at 3:24 PM, Luke Miles rashreportl...@gmail.com wrote: Say I have a list ls and I want to produce a list of lists where the i'th list has the i'th element of ls tripled, but all other elements are the same. e.g. '(3 5 7) = '((9 5 7) (3 15 7) (3 5 21)) What is a fast way to do this? I could do a loop with appending. (define (map-once f ls) (let M ([sooner null] [later ls]) (if (null? later) null (cons (append sooner (list (f (car later))) (cdr later)) (M (append sooner (list (car later))) (cdr later)) - (map-once sqr '(4 5 6)) '((16 5 6) (4 25 6) (4 5 36)) Unfortunately, this is very slow messy. I have to do 2 big appends for every element is the return list. Here is a cleaner-looking, but still slow way: (define (list-set ls i new-val) (let-values ([(sooner later) (split-at ls i)]) (append sooner (list new-val) (cdr later (define (map-once f ls) (for/list ([i (in-naturals)] [elm (in-list ls)]) (list-set ls i (f elm I'm thinking a good implementation might use continuations somehow? Maybe of vector-set (without the exclamation point) existed, I could use it? -- 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. For more options, visit https://groups.google.com/d/optout. -- 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. For more options, visit https://groups.google.com/d/optout. -- -- Jens Axel Søgaard -- -- Jens Axel Søgaard -- 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. For more options, visit
Re: [racket-users] Fast way to map over a list many times, changing ONE element each time?
As it turns out, this is a perfect application for my persistent vectors library. I used the following test harness, matching your examples and using the more “elegant” style of tackling the problem using for loops. I think the performance speaks for itself. #lang racket/base (require alexis/collection alexis/pvector) (define (map-once f ls) (extend (pvector) (for/sequence ([i (in-naturals)] [elm (in ls)]) (set-nth ls i (f elm) (define (sqr x) (* x x)) (define num-test-cases 1) (define num-runs-per-f 3) (define v (extend (pvector) (take num-test-cases (randoms (displayln pvector method:) (for ([__ (in-range num-runs-per-f)]) (time (void (map-once sqr v ; OUTPUT ; ; pvector method: ; cpu time: 228 real time: 227 gc time: 64 ; cpu time: 163 real time: 163 gc time: 71 ; cpu time: 122 real time: 121 gc time: 31 Alexis -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Fast way to map over a list many times, changing ONE element each time?
On 19/06/2015 21:24, Luke Miles wrote: Say I have a list ls and I want to produce a list of lists where the i'th list has the i'th element of ls tripled, but all other elements are the same. e.g. '(3 5 7) = '((9 5 7) (3 15 7) (3 5 21)) What is a fast way to do this? I could do a loop with appending. (define (map-once f ls) (let M ([sooner null] [later ls]) (if (null? later) null (cons (append sooner (list (f (car later))) (cdr later)) (M (append sooner (list (car later))) (cdr later)) - (map-once sqr '(4 5 6)) '((16 5 6) (4 25 6) (4 5 36)) Unfortunately, this is very slow messy. I have to do 2 big appends for every element is the return list. Here is a cleaner-looking, but still slow way: (define (list-set ls i new-val) (let-values ([(sooner later) (split-at ls i)]) (append sooner (list new-val) (cdr later (define (map-once f ls) (for/list ([i (in-naturals)] [elm (in-list ls)]) (list-set ls i (f elm I'm thinking a good implementation might use continuations somehow? I would start out with i lists in a vector of length i and construct them according to their index and the index of the current element in the source list. The key expressions would be (make-vector i '()) (when (= vector-idx list-idx) (f ... (vector-list ... This way you should be able recurse or iterate with an inner definition. Is it better to use single linked lists or double linked lists as the internal data graph of the text edit buffer? I think with 64bit pointers and up to 90.000 lines as a sane soft maximum single linked lists with a register holding the number of the current line on screen would perform better and are generally easier to handle. Oops, that was not meant to end up here ... -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Fast way to map over a list many times, changing ONE element each time?
A more efficient version using append-reverse from srfi/1. #lang racket (require (only-in srfi/1 append-reverse)) (define (list-splits xs) (define (loop ys zs) ; xs = (append (reverse ys) yz) (match zs ['() '()] [(cons z zs*) (cons (list ys zs) (loop (cons z ys) zs*))])) (loop '() xs)) (define (map-once f xs) (for/list ([ys+zs (list-splits xs)]) (match ys+zs [(list ys '()) '()] [(list ys (cons z zs)) (append-reverse ys (cons (f z) zs))]))) (list-splits '(1 2 3)) (map-once sqr '(1 2 3)) 2015-06-19 22:07 GMT+02:00 Jens Axel Søgaard jensa...@soegaard.net: #lang racket (define (list-splits xs) (define (loop ys zs) ; xs = (append (reverse ys) yz) (match zs ['() '()] [(cons z zs*) (cons (list ys zs) (loop (cons z ys) zs*))])) (loop '() xs)) (define (map-once f xs) (for/list ([ys+zs (list-splits xs)]) (match ys+zs [(list ys '()) '()] [(list ys (cons z zs)) (append (reverse ys) (cons (f z) zs))]))) (list-splits '(1 2 3)) (map-once sqr '(1 2 3)) 2015-06-19 22:05 GMT+02:00 Jon Zeppieri zeppi...@gmail.com: It's unlikely that an implementation using continuations would be faster than one that does not. An idiomatic solution might look like: (define (map-once fn xs) (for/list ([i (in-range (length xs))]) (for/list ([(x j) (in-indexed (in-list xs))]) (cond [(= i j) (fn x)] [else x] But it's not terribly fast. If you're willing to use vectors instead of lists, then maybe: (define (map-once fn xs) (build-vector (vector-length xs) (λ (i) (define v (vector-copy xs)) (vector-set! v i (fn (vector-ref v i))) v))) On Fri, Jun 19, 2015 at 3:24 PM, Luke Miles rashreportl...@gmail.com wrote: Say I have a list ls and I want to produce a list of lists where the i'th list has the i'th element of ls tripled, but all other elements are the same. e.g. '(3 5 7) = '((9 5 7) (3 15 7) (3 5 21)) What is a fast way to do this? I could do a loop with appending. (define (map-once f ls) (let M ([sooner null] [later ls]) (if (null? later) null (cons (append sooner (list (f (car later))) (cdr later)) (M (append sooner (list (car later))) (cdr later)) - (map-once sqr '(4 5 6)) '((16 5 6) (4 25 6) (4 5 36)) Unfortunately, this is very slow messy. I have to do 2 big appends for every element is the return list. Here is a cleaner-looking, but still slow way: (define (list-set ls i new-val) (let-values ([(sooner later) (split-at ls i)]) (append sooner (list new-val) (cdr later (define (map-once f ls) (for/list ([i (in-naturals)] [elm (in-list ls)]) (list-set ls i (f elm I'm thinking a good implementation might use continuations somehow? Maybe of vector-set (without the exclamation point) existed, I could use it? -- 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. For more options, visit https://groups.google.com/d/optout. -- 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. For more options, visit https://groups.google.com/d/optout. -- -- Jens Axel Søgaard -- -- Jens Axel Søgaard -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Fast way to map over a list many times, changing ONE element each time?
It's unlikely that an implementation using continuations would be faster than one that does not. An idiomatic solution might look like: (define (map-once fn xs) (for/list ([i (in-range (length xs))]) (for/list ([(x j) (in-indexed (in-list xs))]) (cond [(= i j) (fn x)] [else x] But it's not terribly fast. If you're willing to use vectors instead of lists, then maybe: (define (map-once fn xs) (build-vector (vector-length xs) (λ (i) (define v (vector-copy xs)) (vector-set! v i (fn (vector-ref v i))) v))) On Fri, Jun 19, 2015 at 3:24 PM, Luke Miles rashreportl...@gmail.com wrote: Say I have a list ls and I want to produce a list of lists where the i'th list has the i'th element of ls tripled, but all other elements are the same. e.g. '(3 5 7) = '((9 5 7) (3 15 7) (3 5 21)) What is a fast way to do this? I could do a loop with appending. (define (map-once f ls) (let M ([sooner null] [later ls]) (if (null? later) null (cons (append sooner (list (f (car later))) (cdr later)) (M (append sooner (list (car later))) (cdr later)) - (map-once sqr '(4 5 6)) '((16 5 6) (4 25 6) (4 5 36)) Unfortunately, this is very slow messy. I have to do 2 big appends for every element is the return list. Here is a cleaner-looking, but still slow way: (define (list-set ls i new-val) (let-values ([(sooner later) (split-at ls i)]) (append sooner (list new-val) (cdr later (define (map-once f ls) (for/list ([i (in-naturals)] [elm (in-list ls)]) (list-set ls i (f elm I'm thinking a good implementation might use continuations somehow? Maybe of vector-set (without the exclamation point) existed, I could use it? -- 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. For more options, visit https://groups.google.com/d/optout. -- 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. For more options, visit https://groups.google.com/d/optout.
Re: [racket-users] Fast way to map over a list many times, changing ONE element each time?
#lang racket (define (list-splits xs) (define (loop ys zs) ; xs = (append (reverse ys) yz) (match zs ['() '()] [(cons z zs*) (cons (list ys zs) (loop (cons z ys) zs*))])) (loop '() xs)) (define (map-once f xs) (for/list ([ys+zs (list-splits xs)]) (match ys+zs [(list ys '()) '()] [(list ys (cons z zs)) (append (reverse ys) (cons (f z) zs))]))) (list-splits '(1 2 3)) (map-once sqr '(1 2 3)) 2015-06-19 22:05 GMT+02:00 Jon Zeppieri zeppi...@gmail.com: It's unlikely that an implementation using continuations would be faster than one that does not. An idiomatic solution might look like: (define (map-once fn xs) (for/list ([i (in-range (length xs))]) (for/list ([(x j) (in-indexed (in-list xs))]) (cond [(= i j) (fn x)] [else x] But it's not terribly fast. If you're willing to use vectors instead of lists, then maybe: (define (map-once fn xs) (build-vector (vector-length xs) (λ (i) (define v (vector-copy xs)) (vector-set! v i (fn (vector-ref v i))) v))) On Fri, Jun 19, 2015 at 3:24 PM, Luke Miles rashreportl...@gmail.com wrote: Say I have a list ls and I want to produce a list of lists where the i'th list has the i'th element of ls tripled, but all other elements are the same. e.g. '(3 5 7) = '((9 5 7) (3 15 7) (3 5 21)) What is a fast way to do this? I could do a loop with appending. (define (map-once f ls) (let M ([sooner null] [later ls]) (if (null? later) null (cons (append sooner (list (f (car later))) (cdr later)) (M (append sooner (list (car later))) (cdr later)) - (map-once sqr '(4 5 6)) '((16 5 6) (4 25 6) (4 5 36)) Unfortunately, this is very slow messy. I have to do 2 big appends for every element is the return list. Here is a cleaner-looking, but still slow way: (define (list-set ls i new-val) (let-values ([(sooner later) (split-at ls i)]) (append sooner (list new-val) (cdr later (define (map-once f ls) (for/list ([i (in-naturals)] [elm (in-list ls)]) (list-set ls i (f elm I'm thinking a good implementation might use continuations somehow? Maybe of vector-set (without the exclamation point) existed, I could use it? -- 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. For more options, visit https://groups.google.com/d/optout. -- 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. For more options, visit https://groups.google.com/d/optout. -- -- Jens Axel Søgaard -- 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. For more options, visit https://groups.google.com/d/optout.
[racket-users] Fast way to map over a list many times, changing ONE element each time?
Say I have a list ls and I want to produce a list of lists where the i'th list has the i'th element of ls tripled, but all other elements are the same. e.g. '(3 5 7) = '((9 5 7) (3 15 7) (3 5 21)) What is a fast way to do this? I could do a loop with appending. (define (map-once f ls) (let M ([sooner null] [later ls]) (if (null? later) null (cons (append sooner (list (f (car later))) (cdr later)) (M (append sooner (list (car later))) (cdr later)) - (map-once sqr '(4 5 6)) '((16 5 6) (4 25 6) (4 5 36)) Unfortunately, this is very slow messy. I have to do 2 big appends for every element is the return list. Here is a cleaner-looking, but still slow way: (define (list-set ls i new-val) (let-values ([(sooner later) (split-at ls i)]) (append sooner (list new-val) (cdr later (define (map-once f ls) (for/list ([i (in-naturals)] [elm (in-list ls)]) (list-set ls i (f elm I'm thinking a good implementation might use continuations somehow? Maybe of vector-set (without the exclamation point) existed, I could use it? -- 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. For more options, visit https://groups.google.com/d/optout.
