Let’s say I have a non-const value which is size of subvector. I want to sort part of vector. I do not want to make a sorting algorithm. Is this possible?
sort() allows to specify the number of elements to sort.
So for a subvector, first copy it at the beginning of another vector, using copy(), sort it with sort() and copy back the sorted values at the original location, again with copy().
That’s the thing though. I can’t do it here:
foo:
eval "
const size_of_images=256*256;
number_of_colors=0;
assumed_number_of_colors_in_image=v(2,256);
list_of_color_ints=vector(#size_of_images);
repeat(assumed_number_of_colors_in_image,p,
list_of_color_ints[p]=v(0,16777215) # Assumed Int8 representation of colors;
++number_of_colors;
);
ref('temp',vector(#number_of_colors));
"
In my case, using a image wouldn’t work as images are in float, not double.
The only way to optimize this following code for huge image size is to somehow being able to sort only part of a vector using non-const values.
The code I'm basing the simple foo off
rep_random_colors_from_palette:
bucket_counts:=1<<8
foreach {
r 1,{whd},1,100%,-1
{[1,h#-1+2,1,(ceil((s#0*8)/24))<<1]}
0x$bucket_counts
eval "
const S=s#0;
const da_S=s#1;
const da_secsize=da_S>>1;
const seed="{v(131,1049)}";
const dictionary_bit_mask=$bucket_counts-1;
const float_max=1<<24;
const dec_float_max=float_max-1;
const max_value=(1<<(S<<3))-1;
float_bitshift_vector=expr('<begin(m=started=0;);started?(m+=24;):(started=1;0;);',da_secsize);
int8_bitshift_vector=big_bitshift_vector=expr('<begin(m=started=0;);started?(m+=8;):(started=1;0;);',S);
vint82sint(v)=sum(v<<int8_bitshift_vector);
vfloat2sint(v)=sum(v<<float_bitshift_vector);
sint2vfloat(v)=(v>>float_bitshift_vector)&dec_float_max;
list_of_color_ints=vector(#h#0,inf);
sizes=vector(#$bucket_counts);
last_color=vector(#s#0,nan);
number_of_colors=0;
repeat(h#0,p,
current_color=I[#0,p];
dictionary_index=0;
repeat(S,q,
dictionary_index=xor(((dictionary_index<<1)-dictionary_index)*seed,current_color[q]);
dictionary_index&=dictionary_bit_mask;
);
bucket_size_ind=dictionary_index;
dictionary_index+=2;
H=sizes[bucket_size_ind];
!(H?(same(current_color,last_color)?1:find(#dictionary_index,(H-1)*S,-S)+1))?(
# Section 1 - Add into dictionary
if(H==h(#dictionary_index),
new_size=max(8,h(#dictionary_index)<<1);
resize(#dictionary_index,S,new_size,1,1,-1);
);
copy(i(#dictionary_index,0,H,0,0),current_color);
++sizes[bucket_size_ind];
# Section 2 - Add into list of colors
list_of_color_ints[number_of_colors++]=vint82sint(current_color);
);
last_color=current_color;
);
list_of_color_ints=sort(list_of_color_ints);
last_int=nan;
dec_number_of_colors=number_of_colors-1;
list_of_color_ints[0]?(
repeat(dec_number_of_colors,p,
current_int=list_of_color_ints[p];
p?(
I[#1,p]=[sint2vfloat(last_int+1),sint2vfloat(current_int-1)];
):(
I[#1,p]=[sint2vfloat(0),sint2vfloat(current_int-1)];
);
last_int=current_int;
);
current_int=list_of_color_ints[p];
current_int<max_value?(
I[#1,p++]=[sint2vfloat(last_int+1),sint2vfloat(current_int-1)];
I[#1,p]=[sint2vfloat(current_int+1),sint2vfloat(max_value)];
):(
I[#1,p]=[sint2vfloat(last_int+1),sint2vfloat(max_value)];
);
i[#1,h#1-1]=p+1;
);
"
}
Note that recoding a custom quicksort algorithm in the math parser is trivial.
See code of command sort_list that does it:
#@cli sort_list : _ordering={ +:Increasing | -:Decreasing },_criterion
#@cli : Sort list of selected images according to the specified image criterion.
#@cli : Default values: 'ordering=+', 'criterion=i'.
#@cli : $ (1;4;7;3;9;2;4;7;6;3;9;1;0;3;3;2) split y sort_list +,i append y
sort_list : skip ${1=+},${2=i}
s0="descending" s1="ascending"
e[^-1] "Sort list of image$? in "${s{['$1']=='+'}}" order, according to the image criterion '$2'."
if $!
if isin('$2','n','N') # Special case : lexicographic order from image names (n: ignore case, N: consider case)
op={`;['$1']=='-'?_'>':_'<'`}
if ['$2']=='n' fn=lowercase else fn= fi
$!,1,1,1,"n = name(#x,1024); find(n,0)%1025" slen:=iM rm. # Largest name length
eval "
const lm1 = l - 1;
const slen = "$slen";
strcmp(n0,n1) = (for (k = 0, k<slen && !(diff = "$fn"(n0[k]) - "$fn"(n1[k])), ++k); diff);
quicksort(lo0,hi0) = (
stack = vector(#2*l);
stacksize = 0;
push(elt0,elt1) = (stack[stacksize++] = elt0; stack[stacksize++] = elt1);
pop() = (_s1 = stack[--stacksize]; _s0 = stack[--stacksize]; [_s0,_s1]);
push(lo0,hi0);
while (stacksize>0,
range = pop();
lo = range[0];
hi = range[1];
pivot = int((lo + hi)/2);
npivot = name(#pivot,slen);
while (lo<hi,
while ((nlo = name(#lo,slen); strcmp(nlo,npivot)<0), ++lo);
while ((nhi = name(#hi,slen); strcmp(npivot,nhi)<0), --hi);
lo<=hi?(lo!=hi?run('rv[',lo,',',hi,']'); ++lo; --hi);
);
if (range[0]<hi,push(range[0],hi));
if (lo<range[1],push(lo,range[1]));
)
);
quicksort(0,lm1)"
else # Generic case
i=$! repeat $! { ({$>,$2}) } a[$i--1] y +f. y a[-2,-1] x sort. $1,y z. 1,1
repeat h { nm$>={$>,n} =>[$>] sortlist$> }
repeat h { mv[sortlist{i(0,$>)}] -1 }
repeat h { =>[$>] ${nm{i(0,$>)}} }
rm.
fi
fi
Actually, for my recent case, I found a way to make sure that linear insertion sort does the job just fine and keep the sorting O(n log n) except not really sorted. Just cycled somewhat. My idea is to insert elements in the middle of array, have variable denoting low pos and high pos, and append onto both side, and do linear search from both end when a number found is between min and max, which keeps it performant for the application I have in mind.