Programming puzzles: processing lists!
|
04-25-2017, 06:31 PM
Post: #41
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-25-2017 04:27 PM)DavidM Wrote: @Claudio: does newRPL have a "layer" similar in function to SysRPL? If so, is that how you approach the outer-loop processing of the list commands? No, there's no inner layer per se, but you could think of it as if there is one. Let me clarify that a bit. newRPL basic code is written in C, and presents an API for libraries to use. Those libraries implement the RPL commands basically by doing the dispatch, argument check, then calling the API functions. So you could say that the C code is the inner layer, and the core that presents this API is the "low level". However, there's a huge difference between calling an API and running an RPL loop like in sysRPL. If you want to define the inner layer as having an RPL loop, then there's no inner layer. For the specific case of list processing commands, which need to execute a custom RPL program, there is no other way but to run the RPL loop, so those commands in newRPL are actually implemented in... newRPL (surprise). The outer layer == inner layer in this case. There's no need for an inner layer when the outer layer is quite well optimized. Yes, there's a couple of unnamed (hidden) commands that get most of the job done, and let the loop run for the custom user program, in a sandboxed environment. |
|||
04-25-2017, 08:34 PM
Post: #42
|
|||
|
|||
RE: Programming puzzles: processing lists!
Hold on. As far as my understanding of languages goes, I know that if you code in C, while the source is in C, the result is a binary for the CPU architecture (although with some overhead compared to the same binary produced from assembly code, this due to C being at a higher level than assembly).
Then there are the interpreters, like, say, python. Python should be a programming engine written in C that understand code and to avoid "understanding it again" can produce a sort of compiled version that is a bytecode. So with a C binary the code should run without layers, directly CPU code. With an interpreted language, there would be a first step to convert the program in internal code and then run the internal code using calls that run CPU code. So, userRPL -> sysRPL -> saturn code (emulated) -> ARM code while newRPL -> ARM code python would be: python -> "compiled python" -> ARM code When Claudio says "there is the inner layer of C code" it seems that the C code should be interpreted first, instead of being a binary. Like: newRPL -> C -> ARM code Am I mistaken? Wikis are great, Contribute :) |
|||
04-25-2017, 10:24 PM
(This post was last modified: 04-25-2017 10:30 PM by Vtile.)
Post: #43
|
|||
|
|||
RE: Programming puzzles: processing lists!
I post a good quess, which people that truely knows something can then correct.
I think it goes like this: Userprogram -> newRPL / ARM code Where newRPL is a set of libraries of ARM machine commands written and compiled in C (C->Assembly->Machinecode [as compilers are as far as I know usually done to produce target machines assembly source and then automatically with apropriate assembler compiled to machine binaries]). I mean both the OS and the (interactive) interpreter. .. Now we can wait the real knowledge. |
|||
04-26-2017, 12:59 AM
Post: #44
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-25-2017 08:34 PM)pier4r Wrote: Hold on.... I probably contributed to the confusion when I asked Claudio about an equivalent to a sysRPL "layer". In my own defense, I did use quotes. Seeing the list you made above (with the arrows) leads me to believe that you may have the wrong impression of the relationship of user- and sys-RPL. They're actually just subcategories of commands in the larger set of RPL as a whole. Neither is subordinate to the other, though some might argue that userRPL is actually just a subset of sysRPL that defines a "safer" or "less type-specific" operating model due to the way those commands are implemented. When the 50g kernel is executing a collection of RPL objects (aka a "program"), it doesn't care if the next object in the stream is one in the category of userRPL or sysRPL. It sees them in the same way, and just executes them one after the other in the same fashion. There's no further interpretation. (04-25-2017 08:34 PM)pier4r Wrote: When Claudio says "there is the inner layer of C code" it seems that the C code should be interpreted first, instead of being a binary. I don't want to speak for Claudio, but he was probably using those terms because of the way I asked the question. In my mind the more important part of his answer pertains to how the RPL loop in newRPL is used to process the list commands. It sounds like the newRPL kernel is executing the list-processing commands more like another newRPL subroutine (with their own sandbox to play in) as opposed to API library calls as is apparently done with most other commands. |
|||
04-26-2017, 01:30 AM
Post: #45
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-24-2017 08:27 PM)pier4r Wrote: Please provide also the rest of the challenges otherwise I challenge myself (not bad, but still). Here's my attempt at #6: Code: \<< As before, I focused more on using list processing features than performance. This time I used more appropriate line breaks and added comments, so hopefully it will be more readable. I'll go ahead an include #7 as well. It should look somewhat familiar: Code: \<< |
|||
04-26-2017, 02:49 AM
Post: #46
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-25-2017 08:34 PM)pier4r Wrote: So, userRPL -> sysRPL -> saturn code (emulated) -> ARM code Let's start confirming that C is compiled, and runs native ARM code. Like every modern piece of software, newRPL is organized as a "stack": * One layer of low-level subroutines that deal with bare data and exposes an API to manipulate objects and work with the stack, return stack, etc. * A higher layer of libraries that define the commands, check the arguments, etc. * The top layer is the RPL code from the user, be it loose commands ran from the keyboard or the menus, or programs stored in variables. From this perspective, when David asked "is there an inner layer", the answer is yes, there's layers. However, I think he meant an intermediate language like sysRPL, running on the RPL loop. Then the answer is no, because it's the exact same loop, running the same newRPL commands (for the most part, there's a few hidden commands too, but not enough to define a new language), so list commands run in the same outer layer. Except for the outer layer in RPL, the other 2 are compiled C, hence native ARM code. So it depends on what kind of layers you are talking about, or how you define layers. newRPL -> C command libraries -> C lower-level API |
|||
04-26-2017, 04:49 PM
Post: #47
|
|||
|
|||
RE: Programming puzzles: processing lists!
OK, I've formatted and commented the others that I've attempted so far.
#8. Very similar to #7 in approach (and appearance): Code: \<< #9: Code: \<< #10: Code: \<< #11. Similar approach to others using SUB. Care needed to get the proper indices for even/odd element counts: Code: \<< #12. Decided to do this one with a more robust approach than #2. Slower, but behaves better and isn't assumptive: Code: \<< |
|||
04-26-2017, 06:24 PM
(This post was last modified: 04-26-2017 06:25 PM by pier4r.)
Post: #48
|
|||
|
|||
RE: Programming puzzles: processing lists!
David your new #3, #6, #7, #8 looks like variant C solutions (use whatever you like, not only list operations), am I wrong?
Ah wait there is the sub command, I have to check the Aur. As soon as possible I will compare them to mine. Wikis are great, Contribute :) |
|||
04-26-2017, 06:44 PM
Post: #49
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-26-2017 06:24 PM)pier4r Wrote: David your new #3, #6, #7, #8 looks like variant C solutions (use whatever you like, not only list operations), am I wrong? That wasn't my intent. I was actually trying to force myself to use list commands wherever I could. I consider SUB to be a list command in this context, since I am giving it a list and expecting one in return. I'm not exploding the list and doing anything with the elements. So to me, 3, 7, and 8 are all still variant A. I'm also not sure why you would classify #6 as anything but variant A; the main steps used are SORT, DOSUBS (x2), and ΣLIST. Is there something going on with it that doesn't fit the "A" classification? If I were to approach these as variant C, I would likely use sysRPL instead. It's your challenge, so you get to make the rules as you see fit. I'll happily agree to whatever classification you choose for them. |
|||
04-27-2017, 02:11 PM
Post: #50
|
|||
|
|||
RE: Programming puzzles: processing lists!
I made TI-89 versions of some of these just to be obnoxious. (Well, and also to get some use out of this thing; it's nice to program, even if it's a bit clumsy for basic number crunching.)
Most are implemented as functions, which can return a value. Some are implemented as a program, since you can't use SortA or SortD in a function, even on local variables. Lazy compiler design, I guess. (I implemented quicksort as a function in pure Basic, but it's a lot slower than the built-in operations.) Note that I've used != in place of the "not-equals" character, <= and >= for the inequalities, and -> in place of the "STO" arrow. #1 Code: p1(x) #2 Code: p2(x) #3 Code: p3(x) #4 Code: p4(x) #5 Code: p5(x) #6 Code: p6(x) #7 Code: p7(x) #8 Code: p8(x) #10 Code: p10(x) Might attempt a few more of these later. |
|||
04-27-2017, 02:22 PM
Post: #51
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-25-2017 06:25 PM)DavidM Wrote: I have no direct experience with GoferLists, so I'm not qualified to render any opinions on its performance. My comments were directed at the built-in list processing commands that UserRPL has. I believe GoferLists is SysRPL-based, so I see no reason it wouldn't perform at least as well as the built-in commands. Possibly better if the algorithms are optimized and/or special-cased in areas that the built-in ones aren't. The performance of GoferLists is highly variable to put it mildly. Some functions are very slow, some are quite fast, and some are redundant duplicates of existing RPL functions. Still, I consider GoferLists to be essential for anyone doing list- or text-based programming on the HP 50. John |
|||
04-27-2017, 03:56 PM
Post: #52
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-26-2017 06:44 PM)DavidM Wrote:(04-26-2017 06:24 PM)pier4r Wrote: David your new #3, #6, #7, #8 looks like variant C solutions (use whatever you like, not only list operations), am I wrong? Then it is variant A, my "rotate list" is a routine for lists but internally uses the stack, still I consider it variant A since it takes a list as input and returns a list as output. I quickly skimmed the code and missed it. I hope to find time to compare the result (and learn some technique as well). I still have to do the remaining challenges and also computing a suitable random testing generator for challenge #6 (for that I need to compute the probability that out of a random list, I get one valid for the challenge). Wikis are great, Contribute :) |
|||
04-27-2017, 04:00 PM
Post: #53
|
|||
|
|||
RE: Programming puzzles: processing lists!
@Dave Britten: nice, I may join you since my ti 89 lays unused (but I would also like to find for it a more suitable role. Moreover if I use to many things at once I cannot have time for newRPL, there is a wiki to fill and source code to read).
@John Keith. Thanks for the info. I thought it was always faster or very similar to the basic built in procedures. Wikis are great, Contribute :) |
|||
04-27-2017, 04:37 PM
Post: #54
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-27-2017 03:56 PM)pier4r Wrote: I still have to do the remaining challenges and also computing a suitable random testing generator for challenge #6 (for that I need to compute the probability that out of a random list, I get one valid for the challenge). Is there some reason you need to rely solely on chance for the testing? I simply created some supplemental programs to generate known-valid lists of sufficient size, and then slightly altered a duplicate to invalidate them. |
|||
04-28-2017, 07:16 AM
Post: #55
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-27-2017 04:37 PM)DavidM Wrote: Is there some reason you need to rely solely on chance for the testing? I simply created some supplemental programs to generate known-valid lists of sufficient size, and then slightly altered a duplicate to invalidate them. Yes I do the same for debug. For performance testing slightly random stuff adds fun (plus let me refresh some concepts, you know when the probability is slim one reflects a bit about which corners could be cut for a faster check). Otherwise I can just post my solution and you can test it with your routines. Moreover with random inputs (within the given constraints) I ensure a bit more that my algorithm is correct (it happened more than once to catch errors that I did not catched before). Wikis are great, Contribute :) |
|||
04-28-2017, 03:40 PM
(This post was last modified: 04-28-2017 04:01 PM by pier4r.)
Post: #56
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-26-2017 01:30 AM)DavidM Wrote: Here's my attempt at #6: I have problems with this one (clever function though! I still have to improve a lot to match the ideas). At the end one has \GSLIST that seems not to work when the list to sum is {1. } (I have approximate mode on, and at first I run tests with 10 elements, not 100, to see if I did everything correctly) Could you confirm? In the meanwhile I add a 0 to the result list (but it will add to the execution time) because { 1. 0. } works with \GSLIST . Ok after the fix, your function fails when the entire list is composed by one element (like a 10 element list composed by 10 times 10). The version I'm using is the following Code:
The the input list generator can be found at the link below, it may provide quick debug possibilities. So now I try to check your second attempt at #3 using the SUB command. You #3 is very fast! Recap: Pier#1: avg: 50 lists of 100 elements 0.15 secs DavidM#1 avg: 50 lists of 100 elements 1.94 secs DavidM#2 avg: 50 lists of 100 elements 0.043 secs Side question. The tester function is the following (the complete code is here) Code:
Now in the input functions, like inputListGenC6, I have to use a compiled variable otherwise the value of "listSize" is not recalled as I think. For example in \<< \<-listSize c6listGen \>> the behavior when I use a plain "listSize" (instead of the compiled variable) is the following: listSize is saved as 'listSize' in the variable listSizeV of the c6listGen routine. Then in the routine: \<< n \>> 'n' 1 listSizeV 1 SEQ works. While listSizeV 2 * returns the algebraic object 'listSize*2' I thought that variables were properly seen by subprograms in a program, in this case I mean \<< listSize c6listGen \>> should see the value of the variable. So I thought a compiled variable should not be necessary but so far I don't see a workaround (and I was lucky that so far all the other input functions worked without compiled variables, using only "listSize", that then got changed in compiled variable for challenge 6) Wikis are great, Contribute :) |
|||
04-28-2017, 08:53 PM
Post: #57
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-28-2017 03:40 PM)pier4r Wrote: I have problems with this one [#6]... At the end one has \GSLIST that seems not to work when the list to sum is {1. } (I have approximate mode on, and at first I run tests with 10 elements, not 100, to see if I did everything correctly) I can definitely confirm -- you have provided perfectly legitimate input to the program and the approach I used simply doesn't work for that case. It actually falls apart in two separate ways, and I should have remembered both situations as I have hit upon both of them before. Specifically: 1) DOSUBS normally provides a list as its result, EXCEPT for when that list would be empty. In that situation, it doesn't return anything at all. While I disagree with how it works (I think it should return an empty list instead), this isn't the first time I've hit on this issue and I should have remembered it. Ouch. I need to take another look at how I do that first step to address it. It may also be an issue for some of my other submissions. 2) Yes, ΣLIST needs a list of at least 2 elements. I've run into this one before as well. Like I said, I need more practice with list processing on this platform! I think you've hit on the easiest patch for this (adding a 0). (04-28-2017 03:40 PM)pier4r Wrote: You #3 is very fast! It is, because SUB on a list is very efficient. It really doesn't have to do much. The other challenges that I used SUB for will probably be very fast as well. If I didn't make some other silly mistake! (04-28-2017 03:40 PM)pier4r Wrote: Side question. Haven't spent a lot of time looking at this just yet, but my suspicion is that the issue has to do with which variables are already defined and which aren't when the code is parsed. In your supplied code, you are referencing listSize in the program provided to the local var before the var has actually been created (it is created when the → step is executed). At that point, it is simply assumed to be a var name instead of the var itself (since it hasn't actually been created yet). That's probably why it shows up as 'listSize' instead of listSize when the code is run -- it wasn't a known variable when the code was compiled. |
|||
04-28-2017, 09:51 PM
(This post was last modified: 05-02-2017 06:33 AM by pier4r.)
Post: #58
|
|||
|
|||
RE: Programming puzzles: processing lists!
@DavidM: thanks for the answer, and yes I created this challenge also to force myself to think more in terms of list operations, that seems pretty optimized (at least, avoiding MAP) although, as you said, sometimes seems to return or complain for counterintuitive reasons. The point about the "variable not yet local" makes a lot of sense, but why then it works for the first 5 inputs, maybe it is luck.
I already linked the source file containing the entire code for my solutions, here, the code for single challenges will follow below (but likely will not be as updated as the linked file). Moreover once reminded about SUB, I tried to use it because a bit more practical in some cases than DOSUBS or DOLIST. (STREAM I cannot love it, aside for very simple stuff. Moreover I love the fact that one can just call operations between lists, like 'equal' . great function library from the 50g). Average timings for 50 lists of 100 elements (note that I adapted the output of the DavidM functions to return 1 or 0 for easier comparison. #6 (that is very similar to #10, my bad) Pier: 3.04 seconds (impressive the slow down even using DOSUBS) DavidM: waiting for fix, or using the result for #10 #7 Pier: 0.050 s DavidM: 0.053 s I guess we do mostly the same approach #8 Pier: 0.29 s (thanks David for the double check) DavidM: 0.034 s #9 Pier: 0.26 s DavidM: 1.83 s #10 (like #6) Pier: 1.58 s (impressed that SUB overused is faster than __one__ DOSUBS) DavidM: 2.77 s As usual, results and timings on other platforms are welcomed. #6 input gen Code:
#6 Code:
#7 Code:
#8 input gen Code:
#8 Code:
#9 input gen Code:
#9 Code:
#10 Code:
Wikis are great, Contribute :) |
|||
04-29-2017, 08:28 AM
Post: #59
|
|||
|
|||
RE: Programming puzzles: processing lists!
(04-28-2017 08:53 PM)DavidM Wrote: DOSUBS normally provides a list as its result, EXCEPT for when that list would be empty. In that situation, it doesn't return anything at all. Look here for DOSBS and DOLST programs to replace DOSUBS and DOLIST, without those quirks. Cheers, Werner 41CV†,42S,48GX,49G,DM42,DM41X,17BII,15CE,DM15L,12C,16CE |
|||
04-30-2017, 02:31 PM
(This post was last modified: 04-30-2017 05:09 PM by pier4r.)
Post: #60
|
|||
|
|||
RE: Programming puzzles: processing lists!
New solutions and timings.
#11 50 lists of 100 elements, average time Pier: 0.054 s David: 0.047 s #13 (this is an interesting one) 50 lists of 100 elements, average time Pier: 4.03 s #11 input generator Code:
#11 Code:
#13 input generator and code Code:
added also #16 and #17 as processing list challenges (and the more "list things" I see, the more I will add. Of course I know that I miss a lot of possible challenges that I don't see at the moment, but those are ok) #16 Code:
Wikis are great, Contribute :) |
|||
« Next Oldest | Next Newest »
|
User(s) browsing this thread: 1 Guest(s)