Announcement

Collapse
No announcement yet.

inverting an array

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • inverting an array

    Consider a 1-dimension string array, 1 TO n. I need to turn the entire array upside down.

    Before:
    A(1) = "A"
    A(2) = "B"
    A(3) = "C"
    ...
    A(26) = "Z"

    After:
    A(1) = "Z"
    A(2) = "Y"
    A(3) = "X"
    ...
    A(26) = "A"

    That is just for illustration. The real data are much bigger, and we can't assume n will be an even number. What would be an efficient way to do this in PBCC?

    BTW, I already sent an ARRAY INVERT wish list item to [email protected]
    Erich Schulman (KT4VOL/KTN4CA)
    Go Big Orange

  • #2
    Since your swap may not be sorting related as your example suggests i can only come up with SWAP()

    You are using strings and by using the winapi your out of luck with moving memory.
    Therefore.. SWAP

    An extended for next loop should do.
    hellobasic

    Comment


    • #3
      Code:
      x= int(numberofelements/2)
      for y=1 to x
        swap a(y),a(numberofelements-(y-1))
      next y
      should work on odd or even number of elements
      PS
      pseudo code neither compiled nor ever used
      Last edited by Rodney Hicks; 27 Aug 2008, 04:55 PM. Reason: add PS
      Rod
      In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

      Comment


      • #4
        If data are sorted coming in as shown...
        Code:
        ARRAY SORT ARRAY(), DESCEND
        Last edited by Michael Mattias; 27 Aug 2008, 05:06 PM.
        Michael Mattias
        Tal Systems (retired)
        Port Washington WI USA
        [email protected]
        http://www.talsystems.com

        Comment


        • #5
          Sorting? Not mentioned in the first post. So simple SWAP algo works i INVERT your array.

          Code:
          #COMPILE EXE
          #DIM ALL
          
          FUNCTION PBMAIN () AS LONG
          
              LOCAL i,j, k AS LONG
              LOCAL msg1,msg2 AS STRING
          
              k= 26   'change k to odd number, e.g. 27, to
          
              DIM a1(1 TO k) AS STRING
          
              'Fill the array and create BEFORE string for this sample.
              FOR i& = 1 TO k
                  a1(i) = CHR$(64+i)
                  msg1 = msg1 + a1(i)
              NEXT
              '----------------------------------------------
              ' The inversion happens here:
              ' we only need swap until we reach the last pair
              ' of elements at mid-array.  In an odd mumber of
              ' elements, the very middle element never moves.
              j = UBOUND(a1()) +1
              FOR i& = 1 TO (j-1)\2
                  SWAP a1(i), a1(j-i)
              NEXT
              '----------------------------------------------
              'create AFTER string for this sample.
              FOR i& = 1 TO k
                  msg2 = msg2 + a1(i)
              NEXT
              'show the Before and After strings
              ? BUILD$(msg1,$CRLF,msg2)
          
          END FUNCTION
          Rick Angell

          Comment


          • #6
            Rick
            Same as mine, only different.
            Much better kind of different.
            Rod
            In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

            Comment


            • #7
              That's correct Rodney,

              The method has been around for quite a long time.

              Hopefully we'll hear form Erich which of these various posts helps with what his original intent was.

              BTW, Erich or anyone who does not yet have the latest compilers, BUILD$ is a super-fast concatenating function which can simply be replaced for earlier compilers (e.g. PBWin 8 or PBCC 4):

              MSGBOX msg1+$CRLF+msg2
              Rick Angell

              Comment


              • #8
                My intention started here at http://www.powerbasic.com/support/pb...ad.php?t=37839 and Michael Mattias had a great answer back then.

                I'm sure we all know the "joys" of trying to retrofit code, and this had happened twice. I did what I was told to do, but since I don't know anything about their industry I did not account for a tax I'd never heard of or for differences between their cash and non-cash customers. Adding a ,DESCEND to Mr. Mattias's answer actually became a clever albeit kludgy part of reaching the goal. I knew their accounting software was getting the plant's orders in reverse order, and they didn't seem to either know or care.

                Now it occurs to them that the person in charge of this could be sick or on vacation, so we updated the plant's upload script to append rather than overwrite. Sure enough, she missed two days soon after and then noticed the last day's orders came first. Their accounting software is ok with reverse order within the same day, but there are problems with reverse order crossing dates.

                The final CSVs (yes, two) have more total lines than the input CSV from the plant because line items have to added for the tax, where applicable. So the easiest way to deal with this is to turn the array upside down before I compile stats and write everything out to disk.

                I ordered PBCC5 (upgrade from 4) for home but don't have it yet. My boss got PBCC4 last November for me at work, and we do have it. I also finally convinced them to get PBWin8 which we ordered less than 48 hours before PBWin9 was announced. We got our PBWin9, too. At home, I have PBDOS and PBCC, and I have been debating getting PBWin.
                Erich Schulman (KT4VOL/KTN4CA)
                Go Big Orange

                Comment


                • #9
                  Their accounting software is ok with reverse order within the same day, but there are problems with reverse order crossing dates.
                  The new releases allow for multi-key sorting. So for example if you get files with multiple days worth of transactions, you might be able to use this new ARRAY SORT enhancement to your advantage. However, MCM's solution is a classical method that many have used for similar situations for a long time.
                  Rick Angell

                  Comment


                  • #10
                    >The new releases allow for multi-key sorting

                    Well, yes and no.

                    I did not see this in the "What's New" so I scurried on over to the help desk to "rtfm."

                    I see ARRAY SORT() has added a callback function option for custom sort comparisons - a pretty powerful option by the way; pretty neat - and yes you could do a multi-key comparison in your callback function.

                    But when you say "supports multi-key sorting" what I evision would be native supprt for something like...
                    Code:
                     
                     ARRAY SORT MyArray(), _ 
                          FROM 1 to 4 ASCEND, _ 
                          FROM 17 to 28 DESCEND, _
                         [FROM start& to end& ASCEND|DESCEND]...
                    Although actually what I'd like (yes I did send this in)

                    Code:
                     
                     ARRAY SORT MyArray(), _ 
                          FROM 1 to 4 AS LONG ASCEND, _ 
                          FROM 17 to 28 AS STRING DESCEND, _
                         [FROM start& to end& AS datatype ASCEND|DESCEND]...
                    MCM
                    Michael Mattias
                    Tal Systems (retired)
                    Port Washington WI USA
                    [email protected]
                    http://www.talsystems.com

                    Comment


                    • #11
                      Tagarray

                      I have had luck inverting arrays with user defined data
                      types using this "sort" of code implementation

                      Code:
                       
                      DIM  a(1 TO 5)AS STRING  , nums(1 TO 5) AS INTEGER,  k%
                      ARRAY ASSIGN a() = "A", "B", "C", "D", "E"
                      ARRAY ASSIGN nums() =  4, 3, 2, 1 ,0
                      ARRAY SORT nums(), TAGARRAY a()
                       FOR k% = 1 TO 5
                        PRINT a$(k%), nums(k%)
                        NEXT k%
                        WAITKEY$
                      What turned out to be most interesting to me regarding this section of code was that when the DIM statement read

                      Code:
                       DIM  a(5) AS STRING, nums(5) as INTEGER , k%
                      Code:
                       
                      ARRAY SORT nums(), TAGARRAY  a()
                      did not produce the intended result. { yes, FOR k%= 0 to 4 replaced
                      FOR k% = 1 to 5 }


                      Ron

                      Comment


                      • #12
                        Code:
                        ARRAY ASSIGN nums() =  4, 3, 2, 1 ,0
                        ARRAY SORT nums(), TAGARRAY a()
                        Now that is a clever idea, creating a numeric index like that!

                        >did not produce the intended result

                        It should have, if you were careful with your array subscripts.

                        I think I'd go a step further and create a generic, reusable function...
                        Code:
                        FUNCTION  InvertStringarray (Z() AS STRING) AS LONG
                        
                        LOCAL I AS LONG, ta() AS LONG 
                        
                          REDIM ta (LBOUND(Z,1) TO UBOUND (Z,1)) 
                        
                          FOR I = LBOUND(Z,1) TO UBOUND (Z,1)
                             ta(I) = I 
                          NEXT
                          ARRAY SORT ta(), TAGARRAY Z(), DESCEND 
                        
                        END FUNCTION
                        Michael Mattias
                        Tal Systems (retired)
                        Port Washington WI USA
                        [email protected]
                        http://www.talsystems.com

                        Comment


                        • #13
                          Uhm... I may be wrong, but I don't think that building and additional tag array with a loop, and then sorting using that tag array is the more efficent, or just the most elegant solution, if you just need to invert an an array.
                          A simple loop with swaps seems more simpler and probably even faster.
                          A timed test may confirm (or not).

                          Bye!
                          -- The universe tends toward maximum irony. Don't push it.

                          File Extension Seeker - Metasearch engine for file extensions / file types
                          Online TrID file identifier | TrIDLib - Identify thousands of file formats

                          Comment


                          • #14
                            Marco, I expect your right about the speed but what I find neat about Michael's solution is that it doesn't need commenting. The tools used do the commenting.
                            Rod
                            In some future era, dark matter and dark energy will only be found in Astronomy's Dark Ages.

                            Comment


                            • #15
                              >Uhm... I may be wrong, but I don't think that building and additional tag array ..

                              You're not wrong.

                              You're just concerned about nothing. The 'net cost' of using an array versus using SWAP has got be less than measureable, leave alone noticeable.

                              If ever there was a "six-five and pick 'em" choice to make, this is it.

                              MCM
                              Michael Mattias
                              Tal Systems (retired)
                              Port Washington WI USA
                              [email protected]
                              http://www.talsystems.com

                              Comment


                              • #16
                                Originally posted by Michael Mattias View Post
                                You're just concerned about nothing. The 'net cost' of using an array versus using SWAP has got be less than measureable, leave alone noticeable.
                                Not exactly.
                                It's not just about the speed. I was thinking about doing something not necessary (creating another array), or doing something more complex than needed (a sort with a tag, that mean a serie of checks, branch, etc.) when just some swap can do the job, etc.
                                And more than that, it doesn't seems to me that the result is a more clear or simple or elegant code, so something suggest me that's not a good way to do it. Except if it's done just to show the use of some PB features.

                                The loop trough half of the elements with swaps, seems to me the most simple, linear and clear way to do it.
                                Why complicate it?

                                Bye!
                                Last edited by Marco Pontello; 29 Aug 2008, 10:26 AM.
                                -- The universe tends toward maximum irony. Don't push it.

                                File Extension Seeker - Metasearch engine for file extensions / file types
                                Online TrID file identifier | TrIDLib - Identify thousands of file formats

                                Comment


                                • #17
                                  > more clear or simple or elegant code....
                                  Code:
                                  #INCLUDE "InvertStringArrray.Inc" 
                                  
                                  ...
                                      CALL InvertStringArray (X())
                                  Simple and clear enough? Now who cares how the hell it's done?

                                  MCM
                                  Michael Mattias
                                  Tal Systems (retired)
                                  Port Washington WI USA
                                  [email protected]
                                  http://www.talsystems.com

                                  Comment


                                  • #18
                                    Originally posted by Michael Mattias View Post
                                    Simple and clear enough? Now who cares how the hell it's done?
                                    Come on MCM. You nitpick often about writing better code, and doing things in the better way.

                                    The one who call it may not care about how it's written / work, but the one who wrote the function should!
                                    You especially!

                                    Bye!
                                    -- The universe tends toward maximum irony. Don't push it.

                                    File Extension Seeker - Metasearch engine for file extensions / file types
                                    Online TrID file identifier | TrIDLib - Identify thousands of file formats

                                    Comment


                                    • #19
                                      I did a test and the SWAP was > 120 times faster than the sort on my machine:
                                      Code:
                                      #COMPILE EXE
                                      #DIM ALL
                                      %ARRAYSIZE = 2000000
                                      
                                      FUNCTION PBMAIN () AS LONG
                                      
                                          DIM a(%ARRAYSIZE) AS STRING
                                          LOCAL ii AS LONG, t AS SINGLE
                                          FOR ii = 0 TO %ARRAYSIZE
                                             a(ii) = MKL$(ii)   'fill a() with test string data
                                          NEXT
                                      
                                      '---------------------------------------------------------------
                                          ? "Here we go using DESCEND..."
                                          'WAITKEY$
                                          t = TIMER
                                          ARRAY SORT a(), DESCEND
                                      
                                          ? "DESCEND took" & STR$(TIMER - t)
                                          'WAITKEY$
                                      '---------------------------------------------------------------
                                          ? "now using SWAP..."
                                          'WAITKEY$
                                          t = TIMER
                                          FOR ii = 0 TO %ARRAYSIZE / 2
                                             SWAP a(%ARRAYSIZE - ii), a(ii) 'invert it in place
                                          NEXT
                                          ? "SWAP took" & STR$(TIMER - t)
                                          'WAITKEY$
                                      END FUNCTION

                                      Comment


                                      • #20
                                        I'll keep that in mind next time I have an '%ARRAYSIZE = 2000000'

                                        But even at that...
                                        Code:
                                        SWAP a(%ARRAYSIZE - ii), a(ii) 'invert it in place
                                        Nothing quite like hitting the array engine twice per loop with a fresh inline subtraction each time when pointer variables would let you use a couple of INCR/DECR instructions instead.
                                        Michael Mattias
                                        Tal Systems (retired)
                                        Port Washington WI USA
                                        [email protected]
                                        http://www.talsystems.com

                                        Comment

                                        Working...
                                        X