Post Reply 
Programming puzzles: processing lists!
06-12-2017, 07:46 PM (This post was last modified: 06-13-2017 10:24 AM by pier4r.)
Post: #141
RE: Programming puzzles: processing lists!
Neat addition. And yes the revlist works.

So I got some surprising experiences. First the FOR is not as slow as I though compared to DOSUBS / DOLIST (I though was like 10 times slower).

10 times iterating over a list of 100 elements.
dosusbs: avg 0.48 s
dolist: avg 0.50 s
for get: avg 0.93 s (nice pun)
start geti: avg 1.19 s
start headList: avg 0.42 s (surprise! same speed category of dosusbs/dolist) . wrong, the code had a bug.
start headList: avg 1.66 s
start DUP TAIL SWAP HEAD: avg 0.96 s
start lrot: avg 3.50 s (I had hopes on this, but likely rotating a list is not that easy)

So if exploding a list with userRPL gets a speed (maybe only for 100 elements, I need to test with 1000) comparable to dolist/dosubs and way better than the compact TAIL + HEAD (those may be few commands but I beleive are intensive), I was thinking that exploding the list and handling it with sysRPL would be super fast, like 3 times faster.

Also I was thinking that LROT would have been faster, maybe is the DUP + HEAD operations that makes it slow.

if the "headTail" procedure holds its speed, it is a great replacement for dosubs/dolists for iterations, at least in userRPL.
Also using a for is not as bad as I thought. Going for 1000 elements now.

Of course, if you see other ways (debug friendly) to iterate over a list, please tell me!

Code:


headListHelp
"input:
L1: list

output:
L2: list without head element
L1: head element"
  
  headList
  \<<
    @given a list in input, leaves on level1 the first element
    @ and on level 2 the rest of the list.
    
    @0 
      @numEl
    \->
    @external input
    list
    @local input
    @numEl 
      @elements in the list.
    \<<
      list OBJ\-> 1 - \->LIST
        @reducing the number of elements of 1 for the new list
        @we have the tail on level 2
      SWAP
        @now the head element is on the level 1 stack
    \>>
  \>>

testIterationSpeed
    @ testing the efficiency of different iteration approaches,
    @ given that DOLIST and DOSUBS although fast are not
    @ so debug friendly especially when nested
    @ The approach tested the fact to get an element from the list
    @ that then can be processed
    \<<
      {} "baseList" DROP
      100 "baseListSize" DROP
      {} "resListDosubs" DROP
      {} "resListDolist" DROP
      {} "resListForGet" DROP
      {} "resListStartGeti" DROP
      {} "resListStartheadList" DROP
      {} "resListStarttailhead" DROP
      {} "resListStartLrot" DROP
      0 "temp" DROP
      
      \->
      @input
      iterations
      
      @localVar
      baseList
      baseListSize
      resListDosubs
      resListDolist
      resListForGet
      resListStartGeti
      resListStartheadList
      resListStarttailhead
      resListStartLrot
      temp
      \<<
        baseListSize seqList 'baseList' STO
      
        1 iterations
        START
          
          \<<
            @ 10 times, list 100 el: avg 0.48 s
            baseList
            1
            \<<
              \->
              elementIn
              \<<
                elementIn
              \>>
            \>>
            DOSUBS
            DROP
            @"dosusbs"
          \>>
          TEVAL DTAG
          'resListDosubs' STO+
          
          \<<
            @ 10 times, list 100 el: avg 0.50 s
            baseList
            1
            \<<
              \->
              elementIn
              \<<
                elementIn
              \>>
            \>>
            DOLIST
            DROP
            @"dolist"
          \>>
          TEVAL DTAG
          'resListDolist'STO+
          
          \<<
            @ 10 times, list 100 el: avg 0.93 s
            1 baseListSize
            FOR pos1
              baseList
              pos1
              GET DROP
            NEXT
            @"for get"
          \>>
          TEVAL DTAG
          'resListForGet' STO+
          
          \<<
            @ 10 times, list 100 el: avg 1.19 s
            baseList
            1
            1 baseListSize
            START
              GETI DROP
            NEXT
            DROP
            DROP
            @"start geti"
          \>>
          TEVAL DTAG
          'resListStartGeti' STO+
          
          \<<
            @ 10 times, list 100 el: avg 0.42 s
            baseList
            1 baseListSize 1 -
            START
              headList DROP
            NEXT
            HEAD DROP
            @ "start headList"
          \>>
          TEVAL DTAG
          'resListStartheadList' STO+
          
          \<<
            @ 10 times, list 100 el: avg 0.96 s
            baseList
            1 baseListSize 1 -
            START
              DUP TAIL SWAP HEAD DROP
              @www.hpmuseum.org/forum/thread-8209-post-74498.html#pid74498
            NEXT
            HEAD DROP
            @ "start tail head"
          \>>
          TEVAL DTAG
          'resListStarttailhead' STO+
          
          \<<
            @ 10 times, list 100 el: avg 3.50 s
            baseList
            1 baseListSize
            START
              DUP HEAD DROP
              -1 LROT
            NEXT
            DROP
            @ "start lrot"
          \>>
          TEVAL DTAG
          'resListStartLrot' STO+
        NEXT
        
        "dosubs"
        resListDosubs
        "dolist"
        resListDolist
        "for get"
        resListForGet
        "start geti"
        resListStartGeti
        "start headList"
        resListStartheadList
        "start tail head"
        resListStarttailhead
        "start lrot"
        resListStartLrot
      \>>
    \>>

Wikis are great, Contribute :)
Find all posts by this user
Quote this message in a reply
Post Reply 


Messages In This Thread
RE: Programming puzzles: processing lists! - pier4r - 06-12-2017 07:46 PM



User(s) browsing this thread: 2 Guest(s)