In this answer I found I needed to calculate a bunch of intersections of subsets of vectors, like

takeSubpspaceIntersections[i_, pos_, val_, perms_] :=
   subperms, picked = Range[Length[perms]],
    badPickI, badListsI,
   badPickJ, badListsJ,
   badVals, balValIndMap, badPosJ,
  subperms = perms[[picked]];
  badPickI = Pick[Range[Length[perms]], perms[[;; , i - 1]], val];
  fullInds = Range[Length[perms[[1]]]];
   badPickJ = Pick[Range[Length[picked]], subperms[[;; , j]], val];
   If[Length[badPickJ] > 0,
        subsample set of input vectors, take their intersectiom
    badListsI = perms[[badPickI, Delete[fullInds, i - 1]]];
    badListsJ = subperms[[badPickJ, Delete[fullInds, j]]];
    badVals = Intersection[badListsJ, badListsI];
        remap intersected vectors to corresponding elements of badPickJ
        and resample input vectors
    balValIndMap = AssociationThread[badListsJ, badPickJ ];
    badPosJ = Lookup[balValIndMap, badVals];
    picked = picked[[ Complement[Range[Length[picked]], badPosJ] ]];
    subperms = perms[[picked]]
   {j, pos}

The problem is that this can be slow over large numbers of vectors

perms1000 =
    RandomInteger[3, {1000000, 15}]] // DeleteDuplicates;

(spint = takeSubpspaceIntersections[5, {2}, 1, perms1000];) // 
  RepeatedTiming // First


Some preliminary testing suggests that the slowest part is the number of times I'm doing things like perms[[badPickI, Delete[fullInds, i - 1]]]; which because of the way Mathematica handles tensors internally forces a copy.

Is there a way I can make this subsample/Intersection process faster, maybe by doing the Intersection piece-by-piece over the intersection of Delete[fullInds, i - 1] and Delete[fullInds, j] first, allowing me to iteratively refine the result over smaller chunks of memory? (kinda similar to the ideas here: Pair-wise equality over large sets of large vectors)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.