Tuesday, August 27, 2019

N-Dimensional matrix to 1-D array indexing translations.


Having done the 2-D address indexing translations, I thught about how to translate between a set of 3-D indices and a linear 1-D array index then extrapolated to n-dimensions.

I liked the idea of testing the solution and have brought that across too (with additions)

The class

1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42


# -*- coding: utf-8 -*-
"""
Created on Tue Aug 27 01:49:51 2019

@author: Paddy3118
"""

from collections import OrderedDict
from itertools import product
from functools import reduce

#%%

class ND21D_Addressing():
    """
    Convert n-dimensional indexing to/from 1-D index as if packed  
    into 1-D array. 
    All indices assumed to start from zero
    """
    def __init__(self, *extent):
        "extent is tuple of index sizes in each dimension"
        n_dim = len(extent) # Dimensionality
        self._extent = extent
        self._offsets = [reduce(int.__mul__, 
                               extent[n + 1:], 1) 
                        for n in range(n_dim)]

    # What n-dimensional index-tuple is stored at linear index.
    def i2ndim(self, index_i):
        "1-D array index to to n-D tuple of indices"
        return tuple((index_i // s) % c 
                     for s, c in zip(self._offsets, self._extent))
    
    # What linear 1-D index stores n-D tuple of indices.
    def ndim2i(self, ni):
        "n-D tuple of indices to 1-D array index"
        return sum(d * s for s, d in zip(self._offsets, ni))
    
    def __repr__(self):
        return f"{self.__class__.__name__}({str(self._extent)[1:-1]})"
#%%

The test

43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
def _irange(mini, maxi):
    "Integer range mini-to-maxi inclusive of _both_ endpoints"
    # Some think ranges should include _both_ endpoints, oh well.
    return range(mini, maxi+1)

def _print_n_dim(ranges_from_zero):
    "Represent the indexing of an n-D matrix"
    last = [0] * len(ranges_from_zero)
    for ni in product(*ranges_from_zero):
        for s, t in zip(last, ni):
            if s != t and t == 0: print()
        last = ni
        print(str(ni).replace(' ', ''), end=' ')
    print()

#%%
if __name__ == "__main__":
    # Dimensionality for test
    n_dim = 4
    
    # range of values in each dimension.
    dranges = [_irange(0, d+1) for d in range(n_dim)]
    # Num of values in each dim.
    extent = [len(dr) for dr in dranges]  
    
    ## The address mapper instance
    admap = ND21D_Addressing(*extent)
    
    ## A test matrix of given dimensionality
    # Optimum size of mapping to 1-dim. array
    size_1d = reduce(int.__mul__, extent)  
    # Range of all mapped to 1-dim. array index values
    range_1d = _irange(0, size_1d - 1)  

    print(f"\n## ORIGINAL {n_dim}-D ARRAY:")
    _print_n_dim(dranges)

    print(f"\n# TEST TRIAL MAP {n_dim}-D TO/FROM 1-D ARRAY ADDRESSING")
          
    # Representing a 1-D array mapped to n-D index tuple 
    dim_1 = OrderedDict((index_i, admap.i2ndim(index_i)) 
                        for index_i in range_1d)
    all_ndim = set(dim_1.values())
    all_by_dim  = [set(d1) for d1 in zip(*all_ndim)]
    assert len(all_ndim) == size_1d, "FAIL! ndim index count"
    for a_dim, its_count in zip(all_by_dim, extent):
        assert len(set(a_dim)) == its_count, \
               "FAIL! ndim individual index count"
               
    # Representing n-D index tuple mapped to 1-D index
    dim_n = OrderedDict(((ndim), admap.ndim2i(ndim))
                        for ndim in product(*dranges))
    all_i = set(dim_n.values())
    assert min(all_i) == 0, "FAIL! Min index_i not zero"
    assert max(all_i) == size_1d - 1, \
           f"FAIL! Max index_i not {size_1d - 1}"

    # Check inverse mappings
    assert all(dim_1[dim_n[ndim]] == ndim 
               for ndim in dim_n), \
           "FAIL! Mapping n-D to/from 1-D indices"
    assert all(dim_n[dim_1[index_i]] == index_i 
               for index_i in range_1d), \
           "FAIL! Mapping 1-D to/from n-D indices"

    print(f"  {admap}: PASS!")



The test output


## ORIGINAL 4-D ARRAY:
(0,0,0,0) (0,0,0,1) (0,0,0,2) (0,0,0,3) (0,0,0,4) 
(0,0,1,0) (0,0,1,1) (0,0,1,2) (0,0,1,3) (0,0,1,4) 
(0,0,2,0) (0,0,2,1) (0,0,2,2) (0,0,2,3) (0,0,2,4) 
(0,0,3,0) (0,0,3,1) (0,0,3,2) (0,0,3,3) (0,0,3,4) 

(0,1,0,0) (0,1,0,1) (0,1,0,2) (0,1,0,3) (0,1,0,4) 
(0,1,1,0) (0,1,1,1) (0,1,1,2) (0,1,1,3) (0,1,1,4) 
(0,1,2,0) (0,1,2,1) (0,1,2,2) (0,1,2,3) (0,1,2,4) 
(0,1,3,0) (0,1,3,1) (0,1,3,2) (0,1,3,3) (0,1,3,4) 

(0,2,0,0) (0,2,0,1) (0,2,0,2) (0,2,0,3) (0,2,0,4) 
(0,2,1,0) (0,2,1,1) (0,2,1,2) (0,2,1,3) (0,2,1,4) 
(0,2,2,0) (0,2,2,1) (0,2,2,2) (0,2,2,3) (0,2,2,4) 
(0,2,3,0) (0,2,3,1) (0,2,3,2) (0,2,3,3) (0,2,3,4) 


(1,0,0,0) (1,0,0,1) (1,0,0,2) (1,0,0,3) (1,0,0,4) 
(1,0,1,0) (1,0,1,1) (1,0,1,2) (1,0,1,3) (1,0,1,4) 
(1,0,2,0) (1,0,2,1) (1,0,2,2) (1,0,2,3) (1,0,2,4) 
(1,0,3,0) (1,0,3,1) (1,0,3,2) (1,0,3,3) (1,0,3,4) 

(1,1,0,0) (1,1,0,1) (1,1,0,2) (1,1,0,3) (1,1,0,4) 
(1,1,1,0) (1,1,1,1) (1,1,1,2) (1,1,1,3) (1,1,1,4) 
(1,1,2,0) (1,1,2,1) (1,1,2,2) (1,1,2,3) (1,1,2,4) 
(1,1,3,0) (1,1,3,1) (1,1,3,2) (1,1,3,3) (1,1,3,4) 

(1,2,0,0) (1,2,0,1) (1,2,0,2) (1,2,0,3) (1,2,0,4) 
(1,2,1,0) (1,2,1,1) (1,2,1,2) (1,2,1,3) (1,2,1,4) 
(1,2,2,0) (1,2,2,1) (1,2,2,2) (1,2,2,3) (1,2,2,4) 
(1,2,3,0) (1,2,3,1) (1,2,3,2) (1,2,3,3) (1,2,3,4) 

# TEST TRIAL MAP 4-D TO/FROM 1-D ARRAY ADDRESSING
  ND21D_Addressing(2, 3, 4, 5): PASS!


END.
at

No comments:

Post a Comment