IntyBASIC Select from Array Index at Random?

First Spear · March 26, 2015

Hey all. I have multiple [7] values in the below array. I want to pick a random index from the array where the value is [7], which means I want a 2 or 3 or 4. How can I do that in IntyBASIC?

.

Dim myarray(17)
myarray(0) = 0
myarray(1) = 6
myarray(2) = 7
myarray(3) = 7
myarray(4) = 7
myarray(5) = 3
myarray(6) = 14
myarray(7) = 15
myarray( = 15
myarray(9) = 15
myarray(10) = 11
myarray(11) = 11
myarray(12) = 13
myarray(13) = 13
myarray(14) = 15
myarray(15) = 15
myarray(16) = 9

Or should I turn this idea on its head and instead do something like this

Dim myarray0(1)
myarray0(0) = 0
Dim myarray6(1)
myarray6(0) = 1
Dim myarray7(3)
myarray7(0) = 2
myarray7(1) = 3
myarray7(2) = 4
mynuvar = myarray7(rand and 3)

?

Thanks.

intvnut · March 26, 2015

Is the array dynamic (meaning, it can change when the game runs), or is it known at compile time?

First Spear · March 26, 2015

"myarray" is known at compile-time.

Is the array dynamic (meaning, it can change when the game runs), or is it known at compile time?

intvnut · March 27, 2015

Might I suggest a two-level structure, then?

Level 1 is indexed by value (7 in your example), and level 2 contains the indices that the value appeared at in the original array.

The idea is this: Each value appears at a variable number of places in the original table, so you need a way to handle that.

Step #1: Write down all the indices that each value appears at. For example, value 0 appears at index 0. Value 15, however, appears at indices 7, 8, 9, 14 and 15.

Step #2: Concatenate all of these lists of indices into a larger list. Concatenate in increasing order of value. If a given value didn't appear in the original data, it just has an empty list of indices. In my example below, I call this larger list RevMap2.

Step #3: Make a second list which indicates which spans within the list created in the previous step represent indices for each value. In the example below, I just indicate where each span starts. Because we've concatenated in increasing order by value, we know one span ends where the next begins. I've called this list RevMap1 in the example below.

Note that I call the table built in Step #2 the "second level table", and the table built in step #3 the "first level table." This refers to the order you look things up in when referring to the table. For example, if I want to look up indices for the value 7, I'd first look up RevMap1(7) and RevMap1(7+1). That tells me what range of indices to look at in RevMap2.

Without further ado, an example of this structure, including code to pick a random index from the original data given the value.

.

' MyData is the original data array provided in the question.  I've put it here for
' reference, along with the index associated with each value.  It's not used in the 
' code below, however.
'
'           Index   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
MyData:     DATA    0,  6,  7,  7,  7,  3, 14, 15, 15, 15, 11, 11, 13, 13, 15, 15, 9 
                                       
' RevMap1 is the first level reverse-mapping table.  By reverse map, I mean it maps
' values back to the indices that they appear at.
' 
' The list of indices for each value is in a contiguous span of RevMap2. 
' The span is denoted by [ RevMap1(value), RevMap1(value+1) ).  
'
' Values which did not appear in the original array will have an empty span.  That's 
' denoted by the fact that RevMap1(value) = RevMap1(value+1).
'
'           Value   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
RevMap1:    DATA    0,  1,  1,  1,  2,  2,  2,  3,  6,  6,  7,  7,  9,  9, 11, 12, 17

' RevMap2 is the second level reverse-mapping table.  This contains the actual indices each
' unique value is found at.  Some values don't appear in the original table.  Those values
' have no entries in RevMap2.
RevMap2:    DATA    0                       ' 0 appears at index 0 only
            DATA    5                       ' 3 appears at index 5 only
            DATA    1                       ' 6 appears at index 1 only
            DATA    2, 3, 4                 ' 7 appears at indices 2, 3, 4
            DATA    16                      ' 9 appears at index 16
            DATA    10, 11                  ' 11 appears at indices 10, 11
            DATA    12, 13                  ' 13 appears at indices 12, 13
            DATA    6                       ' 14 appears at index 6 only
            DATA    7, 8, 9, 14, 15         ' 15 appears at indices 7, 8, 9, 14, 15    


' Pick a random index for a given value.  Pass argument in the variable named 'value'.
' Returns result in 'index'.
RandValIdx: Procedure

            ' Optional debug code: Detect if 'value' wasn't in original array and die.
crash:      IF RevMap1(value) = RevMap1(value+1) THEN GOTO crash

            index = RevMap2( rand % ( RevMap1(value+1) - RevMap1(value) ) )

            RETURN 
            End

.

I've also attached this code as a .BAS file.

revmap.bas

Edited March 27, 2015 by intvnut

intvnut · March 28, 2015

Might I suggest a two-level structure, then?

Level 1 is indexed by value (7 in your example), and level 2 contains the indices that the value appeared at in the original array.

The idea is this: Each value appears at a variable number of places in the original table, so you need a way to handle that.

Step #1: Write down all the indices that each value appears at. For example, value 0 appears at index 0. Value 15, however, appears at indices 7, 8, 9, 14 and 15.

Step #2: Concatenate all of these lists of indices into a larger list. Concatenate in increasing order of value. If a given value didn't appear in the original data, it just has an empty list of indices. In my example below, I call this larger list RevMap2.

Step #3: Make a second list which indicates which spans within the list created in the previous step represent indices for each value. In the example below, I just indicate where each span starts. Because we've concatenated in increasing order by value, we know one span ends where the next begins. I've called this list RevMap1 in the example below.

Note that I call the table built in Step #2 the "second level table", and the table built in step #3 the "first level table." This refers to the order you look things up in when referring to the table. For example, if I want to look up indices for the value 7, I'd first look up RevMap1(7) and RevMap1(7+1). That tells me what range of indices to look at in RevMap2.

Without further ado, an example of this structure, including code to pick a random index from the original data given the value.

.
' MyData is the original data array provided in the question.  I've put it here for
' reference, along with the index associated with each value.  It's not used in the 
' code below, however.
'
'           Index   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
MyData:     DATA    0,  6,  7,  7,  7,  3, 14, 15, 15, 15, 11, 11, 13, 13, 15, 15, 9 
                                       
' RevMap1 is the first level reverse-mapping table.  By reverse map, I mean it maps
' values back to the indices that they appear at.
' 
' The list of indices for each value is in a contiguous span of RevMap2. 
' The span is denoted by [ RevMap1(value), RevMap1(value+1) ).  
'
' Values which did not appear in the original array will have an empty span.  That's 
' denoted by the fact that RevMap1(value) = RevMap1(value+1).
'
'           Value   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
RevMap1:    DATA    0,  1,  1,  1,  2,  2,  2,  3,  6,  6,  7,  7,  9,  9, 11, 12, 17

' RevMap2 is the second level reverse-mapping table.  This contains the actual indices each
' unique value is found at.  Some values don't appear in the original table.  Those values
' have no entries in RevMap2.
RevMap2:    DATA    0                       ' 0 appears at index 0 only
            DATA    5                       ' 3 appears at index 5 only
            DATA    1                       ' 6 appears at index 1 only
            DATA    2, 3, 4                 ' 7 appears at indices 2, 3, 4
            DATA    16                      ' 9 appears at index 16
            DATA    10, 11                  ' 11 appears at indices 10, 11
            DATA    12, 13                  ' 13 appears at indices 12, 13
            DATA    6                       ' 14 appears at index 6 only
            DATA    7, 8, 9, 14, 15         ' 15 appears at indices 7, 8, 9, 14, 15    


' Pick a random index for a given value.  Pass argument in the variable named 'value'.
' Returns result in 'index'.
RandValIdx: Procedure

            ' Optional debug code: Detect if 'value' wasn't in original array and die.
crash:      IF RevMap1(value) = RevMap1(value+1) THEN GOTO crash

            index = RevMap2( rand % ( RevMap1(value+1) - RevMap1(value) ) )

            RETURN 
            End
            
.

I've also attached this code as a .BAS file.

*sigh*

I realized a small (but very important) bug in RandValIdx. The 'rand' statement picks a value from 0 .. N-1 to pick among 'N' alternatives. But, to index into RevMap2 correctly, you need to add that back to RevMap1(value).

Here's the revised RandValIdx. Full code attached.

.

' Pick a random index for a given value.  Pass argument in the variable named 'value'.
' Returns result in 'index'.
RandValIdx: Procedure

            ' Optional debug code: Detect if 'value' wasn't in original array and die.
crash:      IF RevMap1(value) = RevMap1(value+1) THEN GOTO crash

            index = RevMap2( RevMap1(value) + ( rand % ( RevMap1(value+1) - RevMap1(value) ) ) )

            RETURN
            End

.

revmap.bas

freewheel · March 28, 2015

"myarray" is known at compile-time.

Just to hammer this point home - if the values don't change, never, ever use an array for something like this. You're chewing up a heck of a lot of RAM (variables) needlessly. Use a DATA statement and do your randomization from there. Even if, as intvnut's example shows, you end up using a bunch of DATA statements. Those bytes are really not that costly in the grand scheme of things.

I haven't looked closely at what you're trying to do here (it's late), but my gut says there's a much simpler way of accomplishing your goal. Try thinking of the problem from a very different angle and see if there's a very different way of doing this. I have a few hunches about what you may be trying to do and there are often much faster/more efficient/less ROM methods of doing the same thing, with a slight (but significant) twist to how the logic works.

intvnut · March 28, 2015

Just to hammer this point home - if the values don't change, never, ever use an array for something like this. You're chewing up a heck of a lot of RAM (variables) needlessly. Use a DATA statement and do your randomization from there. Even if, as intvnut's example shows, you end up using a bunch of DATA statements. Those bytes are really not that costly in the grand scheme of things.

Agree 1000✕! I guess it was tacit in my example, and I should have spiked out that observation. If you have a table of values that's fixed at compile time and never changes at run time, use DATA statements and the built-in array indexing. The generated code is reasonably efficient—no less efficient than getting it from RAM to read a value, and way more efficient (zero runtime cost!) to initialize it at run time—and it will save precious RAM. It's actually smaller in ROM, too, than manually initializing the array as the original example did.

I haven't looked closely at what you're trying to do here (it's late), but my gut says there's a much simpler way of accomplishing your goal. Try thinking of the problem from a very different angle and see if there's a very different way of doing this. I have a few hunches about what you may be trying to do and there are often much faster/more efficient/less ROM methods of doing the same thing, with a slight (but significant) twist to how the logic works.

Indeed, I'm curious what exact problem First Spear is trying to solve as well. There may be an even better representation than the stab I came up with. Although, I will say that the stab I came up with isn't too bad in the efficiency department either, given no further information about the problem.

Here's what the lookup compiled to:

.

        ;[41]             index = RevMap2( RevMap1(value) + ( rand % ( RevMap1(value+1) - RevMap1(value) ) ) )
        SRCFILE "revmap.bas",41
        MVII #Q2,R1
        MVI V1,R2
        INCR R2
        ADDR R2,R1
        MVI@ R1,R1
        MVII #Q2,R2
        ADD V1,R2
        MVI@ R2,R2
        SUBR R2,R1
        MVI _rand,R2
        XORR R1,R2
        XORR R2,R1
        XORR R1,R2
        TSTR R2
        BEQ T3
T4:
        SUBR R2,R1
        BC T4
        ADDR R2,R1
T3:
        MVII #Q2,R2
        ADD V1,R2
        MVI@ R2,R2
        ADDR R2,R1
        MVII #Q3,R2
        ADDR R2,R1
        MVI@ R1,R0
        MVO R0,V2

.

If I counted right, that's 195 cycles, plus the cost of the modulo. The cost of the modulo is the value returned (0, 1, 2... whatever) times 15. So 0 costs 195 cycles, 1 costs 210 cycles, 2 costs 225 cycles, etc. The most costly for the data presented would be a modulo of 4, which would happen if you asked for a random index containing the value 15, and it picked the index 15. That would cost you 255 cycles.

Now... a note to nanochess: I'm scratching my head a little at this stretch of generated code:

.

        MVI _rand,R2
        XORR R1,R2
        XORR R2,R1
        XORR R1,R2
        TSTR R2
        BEQ T3

.

I'm sure part of it is an artifact of the translation strategy, but it seems like:

The XOR swap is entirely superfluous, as you could, in principle, just swap the register usage the rest of the way down.
Testing for 0 and branching around the repeated subtract papers over bugs when someone asks for X % 0, and costs an extra 13 cycles.

But, that's a different issue altogether.

And, a bit of CSE could easily make this quite a bit faster. All that said, I think what I wrote is the fastest or close to the fastest way to write this particular lookup in IntyBASIC 1.0.3 w/out resorting to assembly language. To go faster would require thinking on the data structure further, as freeweed noted.

Edited March 28, 2015 by intvnut

intvnut · March 30, 2015

It occurred to me over coffee this morning that adding one more small table (called RevMap1b below) makes the code clearer and more efficient. I break RevMap1 into two tables, RevMap1a/RevMap1b. RevMap1a gives the starting index of each span, and RevMap1b gives the length of the span.

Here's the resulting code:

.

' MyData is the original data array provided in the question.  I've put it here for
' reference, along with the index associated with each value.  It's not used in the 
' code below, however.
'
'           Index   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
MyData:     DATA    0,  6,  7,  7,  7,  3, 14, 15, 15, 15, 11, 11, 13, 13, 15, 15, 9

' RevMap1a and RevMap1b provide the first level reverse-mapping table.  By reverse map, I 
' mean it maps values back to the indices that they appear at.  
' 
' The list of indices for each value is in a contiguous span of RevMap2.  Each span starts 
' at the index given by RevMap1a(value), and has RevMap1b(value) entries.
'
' Values which did not appear in the original array will have an empty span.  That's 
' denoted by RevMap1b(value) = 0.
'
'           Value   0   1   2   3   4   5   6   7   8   9  10  11  12  13  14  15  16
RevMap1a:   DATA    0,  1,  1,  1,  2,  2,  2,  3,  6,  6,  7,  7,  9,  9, 11, 12, 17
RevMap1b:   DATA    1,  0,  0,  1,  0,  0,  1,  3,  0,  1,  0,  2,  0,  2,  1,  5

' RevMap2 is the second level reverse-mapping table.  This contains the actual indices each
' unique value is found at.  Some values don't appear in the original table.  Those values
' have no entries in RevMap2.
RevMap2:    DATA    0                       ' 0 appears at index 0 only
            DATA    5                       ' 3 appears at index 5 only
            DATA    1                       ' 6 appears at index 1 only
            DATA    2, 3, 4                 ' 7 appears at indices 2, 3, 4
            DATA    16                      ' 9 appears at index 16
            DATA    10, 11                  ' 11 appears at indices 10, 11
            DATA    12, 13                  ' 13 appears at indices 12, 13
            DATA    6                       ' 14 appears at index 6 only
            DATA    7, 8, 9, 14, 15         ' 15 appears at indices 7, 8, 9, 14, 15


' Pick a random index for a given value.  Pass argument in the variable named 'value'.
' Returns result in 'index'.
RandValIdx: Procedure

            ' Optional debug code: Detect if 'value' wasn't in original array and die.
crash:      IF RevMap1b(value) = 0 THEN GOTO crash

            index = RevMap2( RevMap1a(value) + ( rand % RevMap1b(Value) ) )

            RETURN
            End

.

The generated assembly for the lookup is much shorter and faster:

.

        ;[42]             index = RevMap2( RevMap1a(value) + ( rand % RevMap1b(Value) ) )
        SRCFILE "revmap_b.bas",42
        MVI _rand,R1
        MVII #Q3,R2
        ADD V1,R2
        MVI@ R2,R2
        TSTR R2
        BEQ T3
T4: 
        SUBR R2,R1
        BC T4
        ADDR R2,R1
T3: 
        MVII #Q2,R2
        ADD V1,R2
        MVI@ R2,R2
        ADDR R2,R1
        MVII #Q4,R2
        ADDR R2,R1
        MVI@ R1,R0
        MVO R0,V2

.

This is a mere 119 + 15*modulo cycles, 76 cycles faster.

revmap_b.bas

Edited March 30, 2015 by intvnut

intvnut · March 30, 2015

Ugh... I just realized a flaw with my reasoning on cycle counts for the modulo. rand gives an 8-bit value, but the moduli are small (1, 2, 3). This will lead to very long run times. 255 % 3 would iterate 85 times, at 15 cycles per iteration—nearly 1300 cycles! OUCH!

And for 255 % 1 (which can only ever give the result 0), would take over 3800 cycles. DOUBLE OUCH.

So don't use modulo here. Use multiplication.

.

            index = RevMap2( RevMap1a(value) + ( rand * RevMap1b(Value) ) / 256 )

.

Just a code writing note: The cost of the multiply appears proportional to the right hand side of the multiply operator. Since RevMap1b varies between 1 and 5, this loop will go around between 1 and 5 times, getting the cycle counts back in the range where I thought they should be.

.

        ;[42]             index = RevMap2( RevMap1a(value) + ( rand * RevMap1b(Value) ) / 256 )
        SRCFILE "revmap_b.bas",42
        MVI     _rand,R1                ;   10
        MVII    #Q3,R2                  ;    8
        ADD     V1,R2                   ;   10
        MVI@    R2,R2                   ;    8
        MOVR    R2,R4                   ;    6
        MOVR    R1,R5                   ;    6
        CLRR    R1                      ;    6
        TSTR    R4                      ;    6
        BEQ     T3                      ;    7
                                        ;-----
                                        ;   67
T4:
        ADDR    R5,R1                   ;    6
        DECR    R4                      ;    6
        BNE     T4                      ;    9
                                        ;-----
                                        ;   21*k
T3:
        SWAP    R1                      ;    6
        ANDI    #$00ff,R1               ;    8
        MVII    #Q2,R2                  ;    8
        ADD     V1,R2                   ;   10
        MVI@    R2,R2                   ;    8
        ADDR    R2,R1                   ;    6
        MVII    #Q4,R2                  ;    8
        ADDR    R2,R1                   ;    6
        MVI@    R1,R0                   ;    8
        MVO     R0,V2                   ;   11
                                        ;-----
                                        ;   79
                                        ;   67  (carried forward)
                                        ;   21*k
                                        ;-----
                                        ;  146 + 21*k

.

So there you go. Roughly 146 + 21*k cycles, where k is the modulus looked up from RevMap1b.

First Spear · March 31, 2015

That might be the most gangsta thing I have seen in a long, long time.

It occurred to me over coffee this morning that adding one more small table (called RevMap1b below) makes the code clea[snip]

This is a mere 119 + 15*modulo cycles, 76 cycles faster.

intvnut · March 31, 2015

That might be the most gangsta thing I have seen in a long, long time.

*chuckle*

So, did you follow the data structure and how the lookup works?

IntyBASIC Select from Array Index at Random?

Recommended Posts

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Link to comment

Share on other sites

Join the conversation

Recently Browsing 0 members