Announcement

Collapse
No announcement yet.

inverting an array

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

  • Rodney Hicks
    replied
    Code:
    MACRO revorder(arr,desiredelement)=(arr(UBOUND(arr)-desiredelement))
    This macro delivers the desired element of a reverse ordered array without having to reverse the whole array.

    Usage:
    asneeded= revorder(arrayname,element)

    Tested.

    Leave a comment:


  • Michael Mattias
    replied
    My point re support is more about personnel.

    Not so much with PB, because they've had a lot of the same folks on board for a pretty long time.

    But it's hard to bring new people to speed on ALL releases, especially when they are in Bangalore or Chennai.

    MCM

    Leave a comment:


  • Edwin Knoppert
    replied
    Sure, valid point.
    PB have helped me well, before and the last month with PB9.
    I just hope we don't get an update during my holidays

    Oh btw, 99 USD or ~ 65 Euro for an update is a no-brainer.. if you use the software professionally.

    Afaik you can pay for support so i guess even PB/DLL 6 is not really a big deal.
    Unless the problem is solved in a newer release.
    Last edited by Edwin Knoppert; 1 Sep 2008, 02:20 PM.

    Leave a comment:


  • Michael Mattias
    replied
    Edwin, there's lots of reasons to upgrade other than one specific new feature, or any group of new features.

    One of my favorite reasons to upgrade is to have support available if I need it.

    E.g, What kind of support do you think I would get from PowerBASIC if I called with a problem I am having with PB/DLL 6.0?

    And do you think you could guess what the support person might recommend very quickly, say, right after he hears "six" before he hears "point oh?"

    Leave a comment:


  • Edwin Knoppert
    replied
    Don't get carried away
    Afaik you are not an OOP man.
    Maybe the other new things may suit you though.
    I bought it mainly to keep up to date (PwrDev development), at the office i'll remain using v8 for longer time as before.
    (In fact i don't have a need for new things regarding PB at the office)

    I like the COM part but i have no idea what to do with it at this time.
    No serious things i couldn't do before (i had classes already).

    Leave a comment:


  • Michael Mattias
    replied
    >Wasn't ARRAY SORT in PB9 not being extended with a callback feature?

    Yes. It's in the online doc here.

    I have not yet ordered my upgrade but I think this one will order earlier than usual.

    I've been going really slowly on upgrades since there were 6.11, 7.01, 7.02, 7.03, 7.04, 8.01, 8.02 and 8.03 updates. (I will exempt 8.04 from this list because it was - announcement and version number choice notwithstanding - a major change).

    With this many maintenance updates I would have been spending more time re-testing than developing (aka "putting food on the table").

    The stability of both 8.03 and apparently 8.04 has convinced me the old quality is back, and I don't need to worry that I'll be installing maintenance updates non-stop.

    MCM

    Leave a comment:


  • Edwin Knoppert
    replied
    Wasn't ARRAY SORT in PB9 not being extended with a callback feature?

    Leave a comment:


  • Michael Mattias
    replied
    Here's kind of an interesting (and only 10 ticks if using LONGs) swap of c and b, no temp needed
    Sounds like a useful "MACRO SwapLong (a, b)"

    I'd seen that before, a long time ago. IIRC at the time I drove myself half-silly trying to figure out how/why it worked. But now I can see it clearly.

    Leave a comment:


  • John Gleason
    replied
    Here's kind of an interesting (and only 10 ticks if using LONGs) swap of c and b, no temp needed:
    Code:
    'c and b are any integer type, and could theoretically include float data as integers using pointers.
        c = c XOR b
        b = b XOR c
        c = c XOR b
    'or in PB ver. 9:
         c XOR= b
         b XOR= c
         c XOR= b

    Leave a comment:


  • Michael Mattias
    replied
    Perhaps you could leave the array uninverted* and access the required element with:
    A$=b$(UBOUND(b$)-requiredelement)
    Duh.

    Of course that's the best solution!

    MCM

    Leave a comment:


  • Marco Pontello
    replied
    Originally posted by Michael Mattias View Post
    or maybe even "SWAP AS LONG x, y" ....
    Seem a bit on the ugly side.
    Since the var type is known at compile time, the compiler should be able to infer the optimal way / fastest code to do it.

    Definitely using SWAP for swapping two array items took far many instructions that swapping two vars (as the timing test clearly shown). For example:

    Two LONGs, something like:
    Code:
    MOV EAX,DWORD PTR [EBP-0104h]
    XCHG EAX,DWORD PTR [EBP-0100h]
    MOV DWORD PTR [EBP-0104h],EAX
    Two items of an array of LONGs, something like:
    Code:
    MOV EAX,04h
    ADD EAX,DWORD PTR [EBP-0178h]
    MOV EBX,EAX
    PUSH EBX
    XOR EAX,EAX
    ADD EAX,DWORD PTR [EBP-0178h]
    MOV EBX,EAX
    POP EDX
    MOV EAX,DWORD PTR [EBX]
    XCHG EBX,EDX
    XCHG EAX,DWORD PTR [EBX]
    XCHG EBX,EDX
    MOV DWORD PTR [EBX],EAX
    Swapping two DOUBLEs is entirely different, and involve calling an utility function:
    Code:
    LEA EBX,[EBP-010Ch]
    LEA EDX,[EBP-0104h]
    MOV EAX,08h
    CALL 0403377h ' -- something magical happen here! :-)
    Bye!

    Leave a comment:


  • Michael Mattias
    replied
    SWAP() has been in BASIC since the hatchet was a hammer so you'd probably want to go slow on any changes or enhancements to it...

    Besides, any "non-optimal" speed in SWAP is probably not in the data-type resolution code.....ooh, ooh..... wait a minute....

    I wonder if "swap a, b" works like "select case x".... which ALWAYS (thru 8x anyway) uses the EXT (single? double?) form of numeric variables? In which case, "SWAP&" and "SWAP!" and "SWAP##" might make some sense after all...... or maybe even "SWAP AS LONG x, y" ....

    ???

    MCM

    Leave a comment:


  • Rodney Hicks
    replied
    Perhaps you could leave the array uninverted* and access the required element with:
    A$=b$(UBOUND(b$)-requiredelement)
    May be the quickest.
    (* a non word in place of the non word verted meaning not inverted)
    Last edited by Rodney Hicks; 30 Aug 2008, 01:58 PM.

    Leave a comment:


  • Erich Schulman
    replied
    Originally posted by Michael Mattias View Post
    Any newbies looking to speed up their programs need to remember something:

    The PB intrinsic functions - e.g., SWAP() - are perforce generic, and include all kinds of checking for data types, checking for null pointers, setting ERR and other goodies... the things which make those functions safe and easy to use.

    But I could only do that because in this particular application I know what is being SWAP'ed is in fact a 32-bit entity which is KNOWN to be valid ... and since you can treat any 32-bit entity as a LONG integer, I did so to take advantage of that compiler feature.
    Maybe then SWAP should have an optional type specifier, either SWAP??? a,b or SWAP SINGLE a,b. Leaving it out would be the same kind of SWAP we have now, but using it would cause a compile-time check on the variables.

    If you want to swap integers, what about using the stack instead of a temp variable?

    Leave a comment:


  • Michael Mattias
    replied
    Any newbies looking to speed up their programs need to remember something:

    The PB intrinsic functions - e.g., SWAP() - are perforce generic, and include all kinds of checking for data types, checking for null pointers, setting ERR and other goodies... the things which make those functions safe and easy to use.

    All optimization, however, is application-specific. That is, there is no such thing as the "universal silver bullet."

    eg in above... I treated the PTRs to the array elements not as what they are - "pointers to string handles" - but as pointers to signed LONG integers, and LONG integers are what the compiler eats for breakfast.

    But I could only do that because in this particular application I know what is being SWAP'ed is in fact a 32-bit entity which is KNOWN to be valid ... and since you can treat any 32-bit entity as a LONG integer, I did so to take advantage of that compiler feature.

    Leave a comment:


  • John Gleason
    replied
    Wholly begeebers, that's a screamer and a half!

    Leave a comment:


  • Michael Mattias
    replied
    I don't normally get involved in these peeing contests, but your code was good and it SHOULD have been faster.

    But I recalled something I read here in the mists of times long past about the SWAP instruction being not quite the fastest tool in the box.

    So.... I decided to eschew the use of SWAP and handle it myself with a temporary variable.

    I put all four methods into the demo and got these results:
    Code:
    Creating test array of 20,000,001 elements
    
    Now using ARRAY SORT (DESCEND)..
    ARRAY SORT (DESCEND) took 75.0465
    
    Now using SWAP of Array Elements (uses array engine)  ...
    SWAP thru array engine took .374625000000002
    
    Now using PTR with SWAP (no array engine)
    PTR with SWAP (no array engine) took .390625
    
    Now using PTR (no array engine no SWAP ) with temp var
    Using PTR (no array engine no SWAP ) with temp var took 6.20000000000012E-2
    
    Freeing 'A()'
    A() freed, end of demonstration
    Rather than 120 times difference, I got pretty much a wash on "PTR using array engine" and "PTR not using array engine".

    But eschewing SWAP made a pretty nice difference

    MCM
    Code:
    'Testswap.bas
    ' MCM
    ' 08-30-08
    ' PB/CC 4.03
    
    #COMPILE  EXE
    #DIM      ALL
    #REGISTER NONE           ' we'll decide ourselves, thank you anyway.
    %ARRAYSIZE = 20000000    '   2,000,000 too fast on my machine, below timer resolution
                             '  10,000,000 also too fast
                             '  darned I wish compiler supported comma-formatted numbers here;
                             '  counting the zeros stinks.
                           
    FUNCTION PBMAIN () AS LONG
        
      REGISTER ii AS LONG, l AS LONG
      
      LOCAL t AS SINGLE
      LOCAL A() AS STRING
      LOCAL aPtr1, aPtr2 AS LONG PTR
      
      ? USING$ ("Creating test array of #, elements", %ARRAYSIZE + 1)
      REDIM a(%ARRAYSIZE)
      FOR ii = 0 TO %ARRAYSIZE
           a(ii) = MKL$(ii)   'fill a() with test string data
      NEXT
      ?
    
    '---------------------------------------------------------------
        ? "Now using ARRAY SORT (DESCEND).."
        t     = TIMER
        ARRAY SORT a(), DESCEND
        ? "ARRAY SORT (DESCEND) took" & STR$(TIMER - t)
        ?
    '---------------------------------------------------------------
        ? "Now using SWAP of Array Elements (uses array engine)  ..."
        t      = TIMER
        FOR ii = 0 TO %ARRAYSIZE \ 2     ' I think these need to be integer division
           SWAP a(%ARRAYSIZE - ii), a(ii) 'invert it in place
        NEXT
        ? "SWAP thru array engine took"   & STR$(TIMER - t)
        ?
        
    '---------------------------------------------------------------
        ? "Now using PTR with SWAP (no array engine)"
        t     = TIMER
        aPtr1 = VARPTR(a(0))
        aPtr2 = VARPTR(a(%ARRAYSIZE))
        FOR ii = 0 TO %ARRAYSIZE / 2
           SWAP @aPtr1, @aPtr2
           INCR aPtr1
           DECR aPtr2
        NEXT
        ? "PTR with SWAP (no array engine) took"   & STR$(TIMER - t)
        ?
        
    '---------------------------------------------------------------
        ? "Now using PTR (no array engine no SWAP ) with temp var"
        'WAITKEY$
        t     = TIMER
        t     = TIMER
        aPtr1 = VARPTR(a(0))
        aPtr2 = VARPTR(a(%ARRAYSIZE))
    
        FOR ii = 0 TO %ARRAYSIZE / 2
           l      =  @aptr2            ' save high value
           @aPtr2 =  @aPtr1            ' move low value to high value
           @aPtr1 = l                  ' move former high value to low value
           INCR     aPtr1
           DECR     aPtr2
       NEXT
        
        ? "Using PTR (no array engine no SWAP ) with temp var took"   & STR$(TIMER - t)
        ?
        
        ? "Freeing 'A()'"    ' this takes a while at 20,000,000 elements!
        ERASE A()
        ? "A() freed, end of demonstration"
        
       WAITKEY$
    
        
    END FUNCTION

    Leave a comment:


  • John Gleason
    replied
    >Imo swap already swap's pointers..?
    Yep, I agree and didn't see a difference. MCM had asked about it so I posted the code.

    >N^2
    For some reason, even tho I know about it, exponential increases still seem to baffle my linear brain.

    Leave a comment:


  • Edwin Knoppert
    replied
    Imo swap already swap's pointers..?
    Not data..
    So is there a need to use pointers?

    Leave a comment:


  • Paul Dixon
    replied
    John,
    I for one was surprised at the big 124x speed difference
    Really? It doesn't surprise me at all!
    For each item of data a straight swap is very much simpler than a sort and a swap algorithm of N items has a complexity or order N but a sort algorithm is anything from N*Log(N) to N^2 so as the array gets bigger the sort becomes increasingly bad compared to a swap.

    Paul.

    Leave a comment:

Working...
X