# 关于稀疏空间结构的访问问题

although the data of Sparse Spatial Data Struct has been sparse, but it still is dense for different purpose , if we want to find some the couples of data that satisfy some condition. Or we want to process a part of datas of field for some specific purpose . below is current code.

``````tp = ti.types.struct(...)
f = tp.field(shape=(M,N))

@ti.kernel
def kernel():
for i,j in f:
for ri, rj in f:
if compare(f[i,j], f[ri,rj]):
#do some thing
....
``````

it is simple but it is a O(n^2) algorithm, and it must create n thread, n is size of field. and it has the half of compute being redundant at least. if only a couple of data satisfy condition, then 99% of compute is redundant. And if we find a triple data that satisfy some condition, this code will is below:

``````...
for i,j in f:
for i1, j1 in f:
for i2, j2 in f:
if compare(f[i,j], f[i1,j1], f[i2, j2]):
#do some thing
....
...
``````

it is O(n^3) and the 5/6 compute is redundant at least. if we find m data, it only has 1/m! of compute is valid at most .

Can we do better ? yes, it is a universal problem that comparison each other among n datas. so we can abstract it to a funtion, we name it as ti.involvere. then we give a condition needing satisfied to finish it. then we will get a mask that is special optimized for access parted data. below is new code:

``````tp = ti.types.struct(...)
f = tp.field(shape=(M,N))

@ti.func
def discriminant(a, b):
if ...
#do some thing
return a # or b or a,b or None

@ti.kernel
def kernel():
for i,j in f:
...
``````

the number of parameter of discriminant(a,b) rely on the number of referenced data. it is inconsequential that how to process a and b. our focus is what will be returned. obviously, it have four kinds return-value while 2 parameter.

now , we need to compile python to c++ to implement ti.involvere. unfortunately, i am not good at c++, so i write pseudo here.

``````#the number of parameter rely on python code.
def discriminant(any_type a, any_type  b) -> int:
if ...
...
return 0
#the return value is only four kinds while 2 parameter.
#we use b0000,b0001,b0010,b0011 to stand for None, a,b,ab

class Involvere:
self.discriminant= discriminant

#get index of next WAIT_FOR_COMPARISON from mask, if arrive the end+1 of mask, return None.
def next():
return self.next_pointer

#here define how to select data for discriminant.
def volvere(int index_0):
self.next_pointer = index_0      # a anchor that indicating which data has been processed

index_1 = self.next()
#index_2 = self.next()  if is not 2 data to participate in comparison,
#index_3 ...

while self.next_pointer:

switch index_of_obsolete:
case 0:             # no data is obloleted.
#if discriminant has 3 parameter, here is index_2,  4 parameter to index_3 ...
index_1 = self.next()

case index_of_obsolete & b0010:
self.mask[index_1] = OBSOLETE   # define OBSOLETE 0
index_1 = self.next()

#case index_of_obsolete & b0100:   # discriminant has 3 parameter
#   index_2 = self.next()

# ...

case index_of_obsolete & b0001:  # if the first data is obsoleted, return
return

def kernel():
...

#i don't know taichi how to implement parallel execute, remaining the same is ok

#i don't know taichi how parallelly use the index of field.
#i assume t.i and t.i stand for i and j of f[i,j]
involvere.volvere(t.i * field.shape + t.j)  # see funtion code.
...
``````

1.it can be generated by field.mask() to extract active/deactive status.
2.several masks of the same field can be merged to a mask by AND, OR, NOT, XOR…
3.can access a field by mask of this field.

Hi @mustang, 非常抱歉，对你的需求还是不太明白。