Loading ...
Sorry, an error occurred while loading the content.

Re: Fast list code in NetLogo 4.0

Expand Messages
  • Nick
    Seth, It was my report that triggered the discussion; I definitely appreciate the level of responsiveness, and the very complete explanation of the list
    Message 1 of 6 , Jun 30, 2007
    • 0 Attachment
      Seth,

      It was my report that triggered the discussion; I definitely appreciate the level of responsiveness, and the very complete explanation of the list implementation changes.

      I've been rewriting some of my list-based models (particularly a few showing different approaches to implementing Prim's algorithm for finding the minimum spanning tree of a network) for v4, modifying list grow/shrink operations to use fput and but-first as much as possible, and using first & but-first instead of maintaining and advancing an index into sorted lists (e.g. graph adjacency lists) & using item to retrieve the values.

      One thing that concerns me, from the point of view of teaching people how to use lists in NetLogo v4, is the implication of using singly-linked lists, with regard to the significant performance difference between fput/but-first and lput/but-last. Most of the people I teach are either gifted high-school students or middle- and high-school teachers; very few of those teachers have a computer science background. Thus, a trick (building a list with fput and using reverse to put it in the proper order) familiar to those of us with early exposure to Lisp or Logo might inspire more confusion than anything else.

      Obviously, these sorts of implementation decisions are of most concern only when the amount of list processing in models is relatively high. However, given that you and the others in the CCL development team have concluded (justifiably) that a linked list-based implementation is preferable to an array-based implementation, I would suggest (for what it's worth) that a doubly-linked list (e.g. the java.util.LinkedList class) might be preferable to a singly-linked list, to avoid confusing disparity between the performance of head-of-list operations and that of tail-of-list operations.

      Another suggestion on the upcoming v4 release (as well as the eventual 3D release): it would be great if the registry entries created when installing on Windows could be fixed. At least on XP, NetLogo v3.1.x, v4 beta 1, and 3D Preview 4 are all associated with the application name "LaunchAnywhere" (i.e. the installer name), rather than the correct application names. Thus, when a user with multiple versions of NetLogo installed right-clicks on a NetLogo model file, and selects Open With... to choose the desired version of NetLogo, all of the installed NetLogo applications simply show up as "LaunchAnywhere" in the list. Of course, each of the duplicated names is mapped to a specific NetLogo executable, so if the user can guess correctly, the desired version of NetLogo will indeed launch and open the selected model file. But it would be nice if the user didn't have to guess. ;)
    • Jim Lyons
      ... Seth, The tips about using lists in NL4 are very useful, thanks. Using your advice, I was able to improve my implementation of hashes very much over using
      Message 2 of 6 , Jul 2, 2007
      • 0 Attachment
        On Jun 29, 2007, at 1:16 PM, Seth Tisue wrote:

        > The following may be of interest to modelers wanting to use lists
        > efficiently in NetLogo 4.0.
        > ....

        Seth,
        The tips about using lists in NL4 are very useful, thanks. Using your
        advice, I was able to improve my implementation of hashes very much
        over using two lists and POSITION - ITEM. Could this code be improved
        any more? (I would like to see hashes added to NL, but this serves my
        modest needs for now.)
        TIA,
        Jim Lyons
        -----
        breed [ hashes hash ] hashes-own [ pairs ]

        to-report new-hash
        let me nobody
        create-hashes 1 [ set hidden? true set pairs [] set me self ]
        report me
        end

        to put [ #key #value ] ; hash -- put key/value pair, overwrite if key
        exists
        set pairs fput list #key #value filter [first ? != #key] pairs
        end

        to-report get [ #key ] ; hash -- report value for given key
        foreach pairs [ if first ? = #key [ report item 1 ? ] ]
        report false ; key not found
        end

        to delete [ #key ] ; hash -- remove the pair with given key
        set pairs filter [first ? != #key] pairs
        end

        to-report keys ; hash -- report list of keys
        report map [first ?] pairs
        end

        to test
        clear-all
        let h new-hash
        ;
        reset-timer
        foreach n-values 1000 [?] [ ask h [ put ? "xxx" ] ]
        print word "Put: " timer
        ;
        reset-timer
        foreach n-values 1000 [?] [ let x [get ?] of h ]
        print word "Get: " timer
        ;
        end
        -------
      • Jose M. Vidal
        ... Yes, please! pretty please?! Jose
        Message 3 of 6 , Jul 2, 2007
        • 0 Attachment
          On 6/29/07, Seth Tisue <seth@...> wrote:
          > Admittedly, not all algorithms can be rewritten this way. We're looking
          > into perhaps supporting true arrays (and/or hash tables) in the final
          > NetLogo 4.0 release, perhaps via a bundled extension or extensions.
          >

          Yes, please!

          pretty please?!

          Jose
        • Seth Tisue
          ... Jim Seth, The tips about using lists in NL4 are very useful, Jim thanks. Using your advice, I was able to improve my implementation Jim of hashes very
          Message 4 of 6 , Jul 3, 2007
          • 0 Attachment
            >>>>> "Jim" == Jim Lyons <teacherjim42@...> writes:

            Jim> Seth, The tips about using lists in NL4 are very useful,
            Jim> thanks. Using your advice, I was able to improve my implementation
            Jim> of hashes very much over using two lists and POSITION -
            Jim> ITEM. Could this code be improved any more?

            It looks optimal to me.

            --
            Seth Tisue / http://tisue.net
            lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/
          • Seth Tisue
            ... Nick One thing that concerns me, from the point of view of teaching Nick people how to use lists in NetLogo v4, is the implication of Nick using
            Message 5 of 6 , Jul 5, 2007
            • 0 Attachment
              >>>>> "Nick" == Nick <nickbenn@...> writes:

              Nick> One thing that concerns me, from the point of view of teaching
              Nick> people how to use lists in NetLogo v4, is the implication of
              Nick> using singly-linked lists, with regard to the significant
              Nick> performance difference between fput/but-first and
              Nick> lput/but-last. Most of the people I teach are either gifted
              Nick> high-school students or middle- and high-school teachers; very
              Nick> few of those teachers have a computer science background. Thus, a
              Nick> trick (building a list with fput and using reverse to put it in
              Nick> the proper order) familiar to those of us with early exposure to
              Nick> Lisp or Logo might inspire more confusion than anything else.

              Yeah. It's an efficiency trick I wouldn't introduce until later, when
              someone is actually having trouble with their model being slow and needs
              to speed it up.

              Nick> I would suggest (for what it's worth) that a doubly-linked list
              Nick> (e.g. the java.util.LinkedList class) might be preferable to a
              Nick> singly-linked list, to avoid confusing disparity between the
              Nick> performance of head-of-list operations and that of tail-of-list
              Nick> operations.

              That would require changing the semantics of lists to permit destructive
              operations. Currently lists are immutable and may share structure with
              each other, which is how it's possible for both FPUT and BUTFIRST to be
              O(1). And it's crucial for BUTFIRST to be O(1), because otherwise you
              can't write recursive list-processing code that's O(n). (I lack the
              space/time to go into all the considerations here, but there's a lot of
              good material on this in Abelson & Sussman's Structure and
              Interpretation of Computer Programs. C++ and Java's list types [in the
              STL and the Collections API, respectively] resolve the issue a different
              way: they prohibit sharing of structure between lists, make list
              operations destructive, and provide a separate iterator data type so
              both lists can be processed either iteratively or recursively in O(n)
              time. It's a completely different paradigm.)

              The good news is, we're finishing up work on (mutable) array and hash
              table extensions and I can now definitely say they'll be in the next
              beta release of 4.0.

              --
              Seth Tisue / http://tisue.net
              lead developer, NetLogo: http://ccl.northwestern.edu/netlogo/
            Your message has been successfully submitted and would be delivered to recipients shortly.