[racket-users] Predictable random...so to say
Hi, is there a racket function, which shuffles a list of items based on a seed value...that is: Same seed value results in same shuffle results? Cheers Meino -- 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] Syntax for hash contracts
On Thu, Dec 1, 2016 at 7:29 PM, David Storrs wrote: > I'm having trouble understanding the docs on hash contracts ( > https://docs.racket-lang.org/reference/data-structure- > contracts.html#%28def._%28%28lib._racket%2Fcontract% > 2Fprivate%2Fhash..rkt%29._hash%2Fc%29%29) > > What I'm trying to express is: > > - This function returns #t because it is a simple test function intended > to get the hang of hash contracts... > - This function takes one argument... > - Which is a hash... > - Which has keys 'success, 'file-id, 'scratchdir-path, and 'chunk-hash... > - All of which are symbols... > - The values will be, respectively: > success boolean? > 1. Like Alexis says, `hash/dc` lets you specify a relationship between keys and values **but** the same relationship needs to hold for every key/value pair. Here's an example: #lang racket (require rackunit) (define my-hash/c (hash/dc [k char?] [v (k) (=/c (char->integer k))])) (contract my-hash/c (make-hash '((#\A . 65) (#\B . 66))) '+ '-) ;; good hash (contract my-hash/c (make-hash '((#\A . 66))) 'pos 'neg) ;; bad hash 2. And here's a funny way to check the property you care about (define special-list/c (list/c (cons/c 'chunk-hash string?) (cons/c 'file-id (or/c #f exact-positive-integer?)) (cons/c 'scratchdir-path path-string?) (cons/c 'success boolean?))) (define (special-hash/c h) (special-list/c (sort (hash->list h) symbolhttps://groups.google.com/d/optout.
Re: [racket-users] Predictable random...so to say
I think something like this works: ;; shuffle/seed : list? integer -> list? (define (shuffle/seed lst seed) (random-seed seed) (shuffle lst)) > (define a-list (list 1 2 3 4 5 6 7 8 9 10)) > (shuffle/seed a-list 0) '(3 4 9 8 5 1 10 7 6 2) > (shuffle/seed a-list 0) '(3 4 9 8 5 1 10 7 6 2) > (shuffle/seed a-list 1) '(3 2 1 8 5 10 4 7 6 9) > (shuffle/seed a-list 1) '(3 2 1 8 5 10 4 7 6 9) On Fri, Dec 2, 2016 at 2:05 AM, wrote: > Hi, > > is there a racket function, which shuffles a list of items > based on a seed value...that is: Same seed value results in > same shuffle results? > > Cheers > Meino > > -- > 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] Predictable random...so to say
Daniel Feltey [16-12-02 09:28]: > I think something like this works: > > ;; shuffle/seed : list? integer -> list? > (define (shuffle/seed lst seed) > (random-seed seed) > (shuffle lst)) > > > (define a-list (list 1 2 3 4 5 6 7 8 9 10)) > > (shuffle/seed a-list 0) > '(3 4 9 8 5 1 10 7 6 2) > > (shuffle/seed a-list 0) > '(3 4 9 8 5 1 10 7 6 2) > > (shuffle/seed a-list 1) > '(3 2 1 8 5 10 4 7 6 9) > > (shuffle/seed a-list 1) > '(3 2 1 8 5 10 4 7 6 9) > > > > On Fri, Dec 2, 2016 at 2:05 AM, wrote: > > > Hi, > > > > is there a racket function, which shuffles a list of items > > based on a seed value...that is: Same seed value results in > > same shuffle results? > > > > Cheers > > Meino > > > > -- > > 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. HI Daniel, thanks a lot...exactly for what I have searched for! Cheers Meino -- 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] Re: Methods for least squares
In case you get interested in implementing fitting for non-linear problems as well, consider taking a look at this survey: "Methods for non-linear least squares problems" by K. Madsen, H.B. Nielsen, O. Tingleff. http://www2.imm.dtu.dk/pubdb/views/edoc_download.php/3215/pdf/imm3215.pdf The first section is on descent algorithms. /Jens Axel 2016-12-02 7:52 GMT+01:00 'John Clements' via Racket Users < racket-users@googlegroups.com>: > > > On Dec 1, 2016, at 12:07, Bradley Lucier wrote: > > > > On 12/01/2016 02:04 PM, John Clements wrote: > >> > >> Would it be all right with you if I shared your mail with the mailing > list? A brief reading of this paper shows me the relationship between > solving this problem and approximation of gaussian elimination, and I’d > like to ask Jens Axel Soegaard and Neil Toronto how this relates to the > general algorithms for matrix solution. > > > > Yes, you can share it. > > > > The Conjugate Gradient method is applicable to solving $Ax=b$ when $A$ > is a symmetric, positive definite matrix. It's not applicable to the > problem with general $A$. > > > > So, in fact, it's applicable to solving $A^*Ax=A^*b$, the normal > equations for least squares, since $A^*A$ is symmetric and positive > definite. The brilliance of the method is that it doesn't actually compute > $A^*A$, but only $Ay$ and $A^*y$ for various vectors $y$. > > > > The method is particularly useful when the linear system $Ax=b$ has > inherent error in $A$ and $b$, and so one requires only an approximation to > the solution $x$. > > Okay, I’ve taken a crack at implementing this… well, I have a toy > implementation, that doesn’t do any checking and only works for a > particular matrix shape. > > Short version: yep, it works! > > Now, a few questions. > > 1) What should one use as the initial estimate, x_0 ? The method appears > to work fine for an initial estimate that is uniformly zero. Is there any > reason not to use this? > > 2) When does one stop? I have not read the paper carefully, but it appears > that it’s intended to “halt” in approximately ’n’ steps, where ’n’ is the … > number of rows? In the one case I tried, my “direction” vector p_i quickly > dropped to something on the order of [1e-16, 1e-16], and in fact it became > perfectly stable, in that successive iterations produced precisely the same > values for the three iteration variables. However, it wouldn’t surprise me > to discover that there were cases on which the answer oscillated between > two minutely different values. Can you shed any light on when it’s safe to > stop in the general case? > > 3) Do you have any idea how this technique compares to any described in > Numerical Recipes or implemented in LAPACK ? > > John > > > > -- > 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.
Re: [racket-users] Predictable random...so to say
I suggest to use the current-pseudo-random-generator, because otherwise the shuffle/seed will change globally the random sequence of all the program. For example: ;--- #lang racket ;; shuffle/seed : list? integer -> list? (define (shuffle/seed lst seed) (random-seed seed) (shuffle lst)) (define a-list (list 1 2 3 4 5 6 7 8 9 10)) (shuffle/seed a-list 0) ;=> '(3 4 9 8 5 1 10 7 6 2) (random) ;=> 0.5029567011201275 (shuffle/seed a-list 0) ;=> '(3 4 9 8 5 1 10 7 6 2) (random) ;=> 0.5029567011201275 (shuffle/seed a-list 1) ;=> '(3 2 1 8 5 10 4 7 6 9) (random) ;=> 0.1591727701267079 (shuffle/seed a-list 1) ;=> '(3 2 1 8 5 10 4 7 6 9) (random) ;=> 0.1591727701267079 (define (shuffle/temp/seed lst seed) (parameterize ([current-pseudo-random-generator (make-pseudo-random-generator)]) (random-seed seed) (shuffle lst))) (shuffle/temp/seed a-list 0) ;=> '(3 4 9 8 5 1 10 7 6 2) (random) ;=> 0.9636171831359096 (may change) (shuffle/temp/seed a-list 0) ;=> '(3 4 9 8 5 1 10 7 6 2) (random) ;=> 0.6541579154005383 (may change) (shuffle/temp/seed a-list 1) ;=> '(3 2 1 8 5 10 4 7 6 9) (random) ;=> 0.679958229286436 (may change) (shuffle/temp/seed a-list 1) ;=> '(3 2 1 8 5 10 4 7 6 9) (random) ;=> 0.22302974490220356 (may change) ;--- [Note: shuffle/temp/seed is a horrible name. I used a different name to avoid confusion.] Gustavo On Fri, Dec 2, 2016 at 5:37 AM, wrote: > Daniel Feltey [16-12-02 09:28]: > > I think something like this works: > > > > ;; shuffle/seed : list? integer -> list? > > (define (shuffle/seed lst seed) > > (random-seed seed) > > (shuffle lst)) > > > > > (define a-list (list 1 2 3 4 5 6 7 8 9 10)) > > > (shuffle/seed a-list 0) > > '(3 4 9 8 5 1 10 7 6 2) > > > (shuffle/seed a-list 0) > > '(3 4 9 8 5 1 10 7 6 2) > > > (shuffle/seed a-list 1) > > '(3 2 1 8 5 10 4 7 6 9) > > > (shuffle/seed a-list 1) > > '(3 2 1 8 5 10 4 7 6 9) > > > > > > > > On Fri, Dec 2, 2016 at 2:05 AM, wrote: > > > > > Hi, > > > > > > is there a racket function, which shuffles a list of items > > > based on a seed value...that is: Same seed value results in > > > same shuffle results? > > > > > > Cheers > > > Meino > > > > > > -- > > > 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. > > HI Daniel, > > thanks a lot...exactly for what I have searched for! > > Cheers > Meino > > > -- > 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.
[racket-users] Cleanest way to locate contiguous sequences? (as part of reuniting segments of a file)
This is a more business-logic as opposed to syntax/technique question than usually shows up on this list, but hopefully folks won't mind. I started off to ask "what's the best way to find contiguous sequences of numbers in a list?" and then realized that maybe I should answer the "What are you trying to achieve?" question first. Short version: Tactical problem: Given a list of sorted numbers, how best to identify contiguous sequences within the list? Strategic problem: How best to put a chunked-up file back together given a (possibly incomplete) set of chunks and the index number of those chunks? Long version: I have a file that's been broken up into chunks of roughly standard size and I want to put the file back together. I have the chunk number for each chunk so I know what order they should be concatenated in. I may not have all the chunks, but I don't want to wait for all of them to arrive before starting the assembly, so I'll need to be able to be able to generate intermediate products and add to them later when the assembly process is re-run. My database has filepath and chunk-number data for all chunks (even the ones that haven't arrived yet; the filepaths are predictable), so I know where the chunks will be and what order to assemble them in. My first thought is to get the sorted list of chunk numbers for all the chunks that I currently have, locate contiguous sub-sequences, and assemble those sub sequences, then assemble the sub-sequences once they become contiguous. Something like this: Available chunk nums: '(1 2 3 5 7 200 201 202 203) Group them by contiguous: '( (1 2 3) (5) (7) (200 201 202 203)) Generate superchunks: 1-3, 200-203 Later... Available chunk nums: '(1-3 4 5 7 190 193 200-203) Group them by contiguous: '( (1-3 4 5) (7) (190) (193) (200-203)) Merge 4 and 5 into 1-3, rename 1-3 as 1-5. ...etc I realized I don't actually know a simple way to identify contiguous sub-sequences. I came up with the following, but it feels clumsy. (define-values (n final) (for/fold ((prev (car nums)) (acc '()) ) ((n (cdr nums))) (values n (if (= n (add1 prev)) (cons n acc) (begin (set! result (cons (reverse acc) result)) (list n )) (cons (reverse final) result) Given this: '(1 2 3 5 7 200 201 202 203) It yields this: '((200 201 202 203) (7) (5) (2 3)) Which is fine -- I don't care about the order of the sublists within the overall list, as long as each sublist is itself sorted ascending. Does anyone have any advice to offer, on either the tactical or strategic problem? -- 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] Re: Methods for least squares
For the benefit of people on the Racket Users list, we're discussing the Conjugate Gradient (CG) method applied to Least Squares problems, as described in the original paper by Hestenes and Stiefel: http://www.math.purdue.edu/~lucier/jresv49n6p409_A1b.pdf The formulas to use are (10:2) on page 16 of the file (page 424 in the original). (I get only the Racket Users digest, and that information wasn't included there.) On 12/02/2016 01:52 AM, John Clements wrote: Okay, I’ve taken a crack at implementing this… well, I have a toy implementation, that doesn’t do any checking and only works for a particular matrix shape. Short version: yep, it works! Now, a few questions. 1) What should one use as the initial estimate, x_0 ? The method appears to work fine for an initial estimate that is uniformly zero. Is there any reason not to use this? x_0=0 works fine. 2) When does one stop? In exact arithmetic, the algorithm stops when $A^*r_k$, where $r_k$ is the residual at the $k$th step, is the zero vector. In exact arithmetic, this is guaranteed to happen when $k$ is less than or equal to the number of columns of $A$. In floating-point arithmetic, it is not guaranteed that $A^*r_k$ is ever the zero vector. I have not read the paper carefully, but it appears that it’s intended to “halt” in approximately ’n’ steps, where ’n’ is the … number of rows? The number of columns. In the one case I tried, my “direction” vector p_i quickly dropped to something on the order of [1e-16, 1e-16], and in fact it became perfectly stable, in that successive iterations produced precisely the same values for the three iteration variables. However, it wouldn’t surprise me to discover that there were cases on which the answer oscillated between two minutely different values. Can you shed any light on when it’s safe to stop in the general case? If the columns of $A$ are normalized to all have size about 1, then I would stop when $\|A^*r_k\|$ is about round-off size, or when $k$ hits the number of columns, whichever is earlier. In statistical data analysis, many people compute only a few steps, think of the the search direction vectors $p_k$ as "factors" and derive some information from this. With only one RHS vector $b$ this is the same as Partial Least Squares (PLS). 3) Do you have any idea how this technique compares to any described in Numerical Recipes or implemented in LAPACK ? I'm not an expert in numerical linear algebra or least squares problems. It appears that LAPACK uses a so-called $QR$ factorization of $A$ to solve linear least squares problems. I don't know how to compare them. Matlab probably has its own methods. There is an iterative method called LSQR described here: https://web.stanford.edu/class/cme324/paige-saunders2.pdf It is in some sense a more stable version of CG (in exact arithmetic they generate the same sequence of approximations $x_k$), and it is compared to CG in section 7 of that paper. I'm not saying that CG is a particularly good method to solve this problem, just that forming and solving $A^* Ax=A^* b$ is a particularly *bad* method. Brad -- 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] Reducing Program Startup Time
I have a GUI program (located here, for reference: https://github.com/lehitoskin/ivy.git ) I'm working on and I've found that the time it takes to go from clicking on the binary (or calling from CLI) to getting a fully loaded window takes about 2.5 ~ 3 seconds. What I would like is to get it down to 1 ~ 1.5 seconds. Now, I've done some more obvious things like using racket/base and racket/gui/base and calling require on every specific package I use, but it seems that isn't enough to get the startup times where I want them. Are there any other obvious or generalized steps I could do that might help? Perhaps moving some code into expansion instead of runtime (not exactly sure what or how to do that, though)? -- 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] Cleanest way to locate contiguous sequences? (as part of reuniting segments of a file)
Perhaps this is a more elegant approach to the tactical problem: simultaneously iterating over displaced versions of the original list. E.g. _x '(1 1 2 3 5 7 200 201 202) ; shifted right x '(1 2 3 5 7 200 201 202 203) ; original list x_ '(2 3 5 7 200 201 202 203 203) ; shifted left When (= (+ _x 1) x (- x_ 1)) we are mid-run. Otherwise we're at the start or end of a run. Code below. A further displacement is needed to deal with extended runs: x__ to skip elements in long runs. #lang racket ; Given a strictly ascending list of numbers, summarise runs ; (... b b+1 ... b+n c ...) -> (... a b - b+n c ...) (define (runify xs) (define MIN (first xs)) (define MAX (last xs)) (for/list ([_x (cons MIN xs)] [x xs] [x_ (append (rest xs) (list MAX))] [x__ (append (drop xs 2) (list MAX MAX))] #:unless (= (+ _x 2) x_ (- x__ 1))) (if (= (+ _x 1) x (- x_ 1)) '- x))) ; Replace runify-ed lists with lists of lists ; E.g. '(1 - 3 8 12 15 - 100) -> '((1 3) (8) (12) (15 100)) ; (define (chunkify xs [acc null]) (cond [(null? xs) acc] [(equal? (first xs) '-) (chunkify (drop xs 2) (cons (list (caar acc) (second xs)) (rest acc)))] [else (chunkify (rest xs) (cons (list (first xs)) acc))])) (define xs '(1 2 3 5 7 200 201 202 203)) (runify xs) ; '(1 - 3 5 7 200 - 203) (reverse (chunkify (runify xs))) ; '((1 3) (5) (7) (200 203)) * * * Racket question: How do I define a sequence generator (in-shifted-list xs shift) to make runify work in true single pass fashion? I would like to be able to write the following version of runify, without generating auxiliary lists: (define (runify-efficient xs) (for/list ([_x (in-shifted-list xs -1)] [x xs] [x_ (in-shifted-list xs 1)] [x__ (in-shifted-list xs 2)] #:unless (= (+ _x 2) x_ (- x__ 1))) (if (= (+ _x 1) x (- x_ 1)) '- x))) Dan -- 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] Cleanest way to locate contiguous sequences? (as part of reuniting segments of a file)
Thanks, Dan. Working with shifted lists is an interesting technique that I'll keep in my quiver. I appreciate you taking the time. On Fri, Dec 2, 2016 at 1:56 PM, Daniel Prager wrote: > Perhaps this is a more elegant approach to the tactical problem: > simultaneously iterating over displaced versions of the original list. E.g. > > _x '(1 1 2 3 5 7 200 201 202) ; shifted right > x '(1 2 3 5 7 200 201 202 203) ; original list > x_ '(2 3 5 7 200 201 202 203 203) ; shifted left > > When (= (+ _x 1) x (- x_ 1)) we are mid-run. Otherwise we're at the start > or end of a run. Code below. > > A further displacement is needed to deal with extended runs: x__ to skip > elements in long runs. > > > #lang racket > > ; Given a strictly ascending list of numbers, summarise runs > ; (... b b+1 ... b+n c ...) -> (... a b - b+n c ...) > (define (runify xs) > (define MIN (first xs)) > (define MAX (last xs)) > (for/list ([_x (cons MIN xs)] > [x xs] > [x_ (append (rest xs) (list MAX))] > [x__ (append (drop xs 2) (list MAX MAX))] > #:unless (= (+ _x 2) x_ (- x__ 1))) > (if (= (+ _x 1) x (- x_ 1)) > '- > x))) > > ; Replace runify-ed lists with lists of lists > ; E.g. '(1 - 3 8 12 15 - 100) -> '((1 3) (8) (12) (15 100)) > ; > (define (chunkify xs [acc null]) > (cond [(null? xs) acc] > [(equal? (first xs) '-) > (chunkify (drop xs 2) >(cons (list (caar acc) (second xs)) > (rest acc)))] > [else > (chunkify (rest xs) (cons (list (first xs)) acc))])) > > > (define xs '(1 2 3 5 7 200 201 202 203)) > > (runify xs) ; '(1 - 3 5 7 200 - 203) > > (reverse (chunkify (runify xs))) ; '((1 3) (5) (7) (200 203)) > > > * * * > > Racket question: How do I define a sequence generator (in-shifted-list xs > shift) to make runify work in true single pass fashion? > > I would like to be able to write the following version of runify, without > generating auxiliary lists: > > (define (runify-efficient xs) > (for/list ([_x (in-shifted-list xs -1)] > [x xs] > [x_ (in-shifted-list xs 1)] > [x__ (in-shifted-list xs 2)] > #:unless (= (+ _x 2) x_ (- x__ 1))) > (if (= (+ _x 1) x (- x_ 1)) > '- > x))) > > Dan > > -- > 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] Cleanest way to locate contiguous sequences? (as part of reuniting segments of a file)
You could use an interval tree instead of a list. Before inserting into it, you could check to see if your current chunk number is contiguous with an existing interval in the tree. If so, merge the chunks and expand the existing interval. Otherwise, insert an interval of size 1 into the tree. Stephen Chang's ftree package might be useful here. - Jon On Fri, Dec 2, 2016 at 2:39 PM, David Storrs wrote: > This is a more business-logic as opposed to syntax/technique question than > usually shows up on this list, but hopefully folks won't mind. > > I started off to ask "what's the best way to find contiguous sequences of > numbers in a list?" and then realized that maybe I should answer the "What > are you trying to achieve?" question first. > > Short version: > Tactical problem: Given a list of sorted numbers, how best to identify > contiguous sequences within the list? > Strategic problem: How best to put a chunked-up file back together given > a (possibly incomplete) set of chunks and the index number of those chunks? > > Long version: > I have a file that's been broken up into chunks of roughly standard size > and I want to put the file back together. I have the chunk number for each > chunk so I know what order they should be concatenated in. I may not have > all the chunks, but I don't want to wait for all of them to arrive before > starting the assembly, so I'll need to be able to be able to generate > intermediate products and add to them later when the assembly process is > re-run. > > My database has filepath and chunk-number data for all chunks (even the > ones that haven't arrived yet; the filepaths are predictable), so I know > where the chunks will be and what order to assemble them in. > > My first thought is to get the sorted list of chunk numbers for all the > chunks that I currently have, locate contiguous sub-sequences, and assemble > those sub sequences, then assemble the sub-sequences once they become > contiguous. Something like this: > > Available chunk nums: '(1 2 3 5 7 200 201 202 203) > > Group them by contiguous: '( (1 2 3) (5) (7) (200 201 202 203)) > > Generate superchunks: 1-3, 200-203 > > Later... > > Available chunk nums: '(1-3 4 5 7 190 193 200-203) > > Group them by contiguous: '( (1-3 4 5) (7) (190) (193) (200-203)) > > Merge 4 and 5 into 1-3, rename 1-3 as 1-5. > > ...etc > > I realized I don't actually know a simple way to identify contiguous > sub-sequences. I came up with the following, but it feels clumsy. > > (define-values (n final) > (for/fold ((prev (car nums)) > (acc '()) > ) > ((n (cdr nums))) > (values n > (if (= n (add1 prev)) >(cons n acc) >(begin > (set! result (cons (reverse acc) result)) > (list n > )) > (cons (reverse final) result) > > Given this: '(1 2 3 5 7 200 201 202 203) > It yields this: '((200 201 202 203) (7) (5) (2 3)) > > Which is fine -- I don't care about the order of the sublists within the > overall list, as long as each sublist is itself sorted ascending. > > Does anyone have any advice to offer, on either the tactical or strategic > problem? > > -- > 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] Cleanest way to locate contiguous sequences? (as part of reuniting segments of a file)
Hi Jon, That sounds excellent. Always preferable to find a better algorithm, and I wasn't familiar with interval trees. Thanks for the pointer. Dave On Fri, Dec 2, 2016 at 3:18 PM, Jon Zeppieri wrote: > You could use an interval tree instead of a list. Before inserting into > it, you could check to see if your current chunk number is contiguous with > an existing interval in the tree. If so, merge the chunks and expand the > existing interval. Otherwise, insert an interval of size 1 into the tree. > > Stephen Chang's ftree package might be useful here. > > - Jon > > > > On Fri, Dec 2, 2016 at 2:39 PM, David Storrs > wrote: > >> This is a more business-logic as opposed to syntax/technique question >> than usually shows up on this list, but hopefully folks won't mind. >> >> I started off to ask "what's the best way to find contiguous sequences of >> numbers in a list?" and then realized that maybe I should answer the "What >> are you trying to achieve?" question first. >> >> Short version: >> Tactical problem: Given a list of sorted numbers, how best to identify >> contiguous sequences within the list? >> Strategic problem: How best to put a chunked-up file back together >> given a (possibly incomplete) set of chunks and the index number of those >> chunks? >> >> Long version: >> I have a file that's been broken up into chunks of roughly standard size >> and I want to put the file back together. I have the chunk number for each >> chunk so I know what order they should be concatenated in. I may not have >> all the chunks, but I don't want to wait for all of them to arrive before >> starting the assembly, so I'll need to be able to be able to generate >> intermediate products and add to them later when the assembly process is >> re-run. >> >> My database has filepath and chunk-number data for all chunks (even the >> ones that haven't arrived yet; the filepaths are predictable), so I know >> where the chunks will be and what order to assemble them in. >> >> My first thought is to get the sorted list of chunk numbers for all the >> chunks that I currently have, locate contiguous sub-sequences, and assemble >> those sub sequences, then assemble the sub-sequences once they become >> contiguous. Something like this: >> >> Available chunk nums: '(1 2 3 5 7 200 201 202 203) >> >> Group them by contiguous: '( (1 2 3) (5) (7) (200 201 202 203)) >> >> Generate superchunks: 1-3, 200-203 >> >> Later... >> >> Available chunk nums: '(1-3 4 5 7 190 193 200-203) >> >> Group them by contiguous: '( (1-3 4 5) (7) (190) (193) (200-203)) >> >> Merge 4 and 5 into 1-3, rename 1-3 as 1-5. >> >> ...etc >> >> I realized I don't actually know a simple way to identify contiguous >> sub-sequences. I came up with the following, but it feels clumsy. >> >> (define-values (n final) >> (for/fold ((prev (car nums)) >> (acc '()) >> ) >> ((n (cdr nums))) >> (values n >> (if (= n (add1 prev)) >>(cons n acc) >>(begin >> (set! result (cons (reverse acc) result)) >> (list n >> )) >> (cons (reverse final) result) >> >> Given this: '(1 2 3 5 7 200 201 202 203) >> It yields this: '((200 201 202 203) (7) (5) (2 3)) >> >> Which is fine -- I don't care about the order of the sublists within the >> overall list, as long as each sublist is itself sorted ascending. >> >> Does anyone have any advice to offer, on either the tactical or strategic >> problem? >> >> -- >> 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] Predictable random...so to say
Hi Gustavo, oh YEAH - WHOW...what a *MACHINE* ! :) 8) Thanks a lot! Cheers Meino Gustavo Massaccesi [16-12-03 03:18]: > I suggest to use the current-pseudo-random-generator, because otherwise the > shuffle/seed will change globally the random sequence of all the program. > For example: > > ;--- > #lang racket > > ;; shuffle/seed : list? integer -> list? > (define (shuffle/seed lst seed) > (random-seed seed) > (shuffle lst)) > > (define a-list (list 1 2 3 4 5 6 7 8 9 10)) > > (shuffle/seed a-list 0) ;=> '(3 4 9 8 5 1 10 7 6 2) > (random) ;=> 0.5029567011201275 > (shuffle/seed a-list 0) ;=> '(3 4 9 8 5 1 10 7 6 2) > (random) ;=> 0.5029567011201275 > (shuffle/seed a-list 1) ;=> '(3 2 1 8 5 10 4 7 6 9) > (random) ;=> 0.1591727701267079 > (shuffle/seed a-list 1) ;=> '(3 2 1 8 5 10 4 7 6 9) > (random) ;=> 0.1591727701267079 > > (define (shuffle/temp/seed lst seed) > (parameterize ([current-pseudo-random-generator > (make-pseudo-random-generator)]) > (random-seed seed) > (shuffle lst))) > > (shuffle/temp/seed a-list 0) ;=> '(3 4 9 8 5 1 10 7 6 2) > (random) ;=> 0.9636171831359096 (may change) > (shuffle/temp/seed a-list 0) ;=> '(3 4 9 8 5 1 10 7 6 2) > (random) ;=> 0.6541579154005383 (may change) > (shuffle/temp/seed a-list 1) ;=> '(3 2 1 8 5 10 4 7 6 9) > (random) ;=> 0.679958229286436 (may change) > (shuffle/temp/seed a-list 1) ;=> '(3 2 1 8 5 10 4 7 6 9) > (random) ;=> 0.22302974490220356 (may change) > ;--- > > [Note: shuffle/temp/seed is a horrible name. I used a different name to > avoid confusion.] > > Gustavo > > > > On Fri, Dec 2, 2016 at 5:37 AM, wrote: > > > Daniel Feltey [16-12-02 09:28]: > > > I think something like this works: > > > > > > ;; shuffle/seed : list? integer -> list? > > > (define (shuffle/seed lst seed) > > > (random-seed seed) > > > (shuffle lst)) > > > > > > > (define a-list (list 1 2 3 4 5 6 7 8 9 10)) > > > > (shuffle/seed a-list 0) > > > '(3 4 9 8 5 1 10 7 6 2) > > > > (shuffle/seed a-list 0) > > > '(3 4 9 8 5 1 10 7 6 2) > > > > (shuffle/seed a-list 1) > > > '(3 2 1 8 5 10 4 7 6 9) > > > > (shuffle/seed a-list 1) > > > '(3 2 1 8 5 10 4 7 6 9) > > > > > > > > > > > > On Fri, Dec 2, 2016 at 2:05 AM, wrote: > > > > > > > Hi, > > > > > > > > is there a racket function, which shuffles a list of items > > > > based on a seed value...that is: Same seed value results in > > > > same shuffle results? > > > > > > > > Cheers > > > > Meino > > > > > > > > -- > > > > 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. > > > > HI Daniel, > > > > thanks a lot...exactly for what I have searched for! > > > > Cheers > > Meino > > > > > > -- > > 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. -- 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.
