Adding a collection of neighbors to points in a list, concatenating strings, parallelization/optimizing run-time?

Question

Before beginning, I want to note that there are some similarities with the questions

Combining two lists of different dimensions into a list of all combinations of points?

How can I make threading more flexible?

but I have one more complicating factor beyond that question. Instead of simply adding an offset to each point in a list, I would also like to track which offsets are taken to generate new points, perhaps in the form of a string.

Desired Behavior

Beginning with a list of offsets and some list of points and strings that has been generated thus far

offsets={{0,0, "a"}, {1,0, "b"}, {0,1,"c"}}; list={{1,0, "b"}, {2,3, "bbcc"}};

I would like to create a function addOffsets that would return the following

{{1,0,"ba"}, {2,0,"bb"}, {1,1, "bc"}, {2,3,"bbcca"},{3,3,"bbccb"},{2,4,"bbccc"}}

Notice that the letter for each offset has been added to the end of the current string. Again, I am not devoted to using a string to record this information--If you have an alternative data structure that would be more efficient, I am all game! I primarily care about recovering parents/children (and by extension recovering entire such chains) in my application.

What I have so far

addOneOffset[{x_, y_, string_}] := Table[{x + offsets[[i, 1]], y + offsets[[i, 2]], string <> offsets[[i, 3]]}, {i, 1, Length[offsets]}] addOffset[list_] := Flatten[Map[addOneOffset, list], 1]

Note that this produces the desired output. However, it feels clunky to me. In particular, it seems like there shouldn't be a need for a sub-function. Additionally, while I appreciate what Flatten[...,1] is doing, I almost wish that such a command wasn't necessary. In my mind, it seems like I'm using the wrong Map/Thread/... that is producing the wrong list structure.

The Questions

1. Is this a reasonable implementation? Can anyone see a way to code this more cleanly? Are my mentioned concerns with my implementation valid? I.e., would Mathematica evaluate this more efficiently if it was written as a single function? Or does the kernel not really care?
2. I am mainly interested in running commands like Nest[addOffset,list, 12] and even larger amounts of nesting. On my computer (Intel Core i7-6700k @ 4 GHz (4 physical cores, 8 logical cores), 20GB RAM, ... ) this command takes $3.90625 s$. My naive approach of altering the addOffset function to have ParallelMap instead of Map actually increases the necessary time to $15.2344s$. Is this a process that is reasonable to attempt parallelization? If so, what would be a better way to go about this?
3. What about CUDA / OpenGL / ... implementation? Currently have a Nvidia GeForce GTX 750 Ti and would even potentially consider upgrading if suggested. Is this worth looking into? I admittedly know very little about this (Math grad student, not CS) so I can fully appreciate RTFM/STFW responses; guidelines / suggestions about whether this is even worth trying are appreciated before I devote loads of time to this avenue.

If it matters, I am currently running version 11.0.1.0

Edit

Per @wxffles suggestion (which I rather like, very clean!) I made the new function

wxfflesOffset[input_] := Flatten[Outer[{#1[[1]] + #2[[1]], #1[[2]] + #2[[2]], #1[[3]] <>#2[[3]]} &, input, offsets, 1], 1] Running Nest[wxfflesOffset,list,12] takes $5.25s$, which surprised me. My guess would have been that Outer would have been faster than my version of using Map to apply a user defined function (which has another Table command inside). Perhaps there's a better way to nest @wxffles use of Outer?

Answer 1

I don't know if this late answer will be read but I was looking through unanswered questions and this one seems to have fallen through the cracks.

Your operation will be more efficient if you vectorize it to the extent possible.

• Since you will be operating over a very long list (as built up by the Nest operation) and a short offsets it makes sense to map over the shorter set.

• I will Transpose your data at the outset to cast it in a more favorable shape.

• Rather than using Strings I will use integer "labels" for your tracking purpose and simply accumulate a list of them rather than joining them in some way. I choose Integers because they can form a packed array.

Here is my proposal in code. First I convert your input data into my format:

offsets = {{0, 0, "a"}, {1, 0, "b"}, {0, 1, "c"}};
list = {{1, 0, "b"}, {2, 3, "bbcc"}};

osT = offsets\[Transpose] /. {"a" -> 1, "b" -> 2, "c" -> 3}
listT = list\[Transpose] /. {"b" -> {7}, "bbcc" -> {77}}

{{0, 1, 0}, {0, 0, 1}, {1, 2, 3}}

{{1, 2}, {0, 3}, {{7}, {77}}}

I chose 1, 2, 3, 7 and 77 as arbitrary Integer labels.

Now my function:

fn[{o_, p_, q_}][{x_, y_, h_}] := 
  Join @@@ {x + # & /@ o, y + # & /@ p, ArrayFlatten[{{h, #}}] & /@ q}

(See Prepend 0 to sublists for my choice of ArrayFlatten.)

Applied:

fn[osT][listT]

{{1, 2, 2, 3, 1, 2},
 {0, 3, 0, 3, 1, 4},
 {{7, 1}, {77, 1}, {7, 2}, {77, 2}, {7, 3}, {77, 3}}}

Transpose this to get back to your original output shape:

fn[osT][listT]\[Transpose]

{{1, 0, {7, 1}}, {2, 3, {77, 1}}, {2, 0, {7, 2}},
 {3, 3, {77, 2}}, {1, 1, {7, 3}}, {2, 4, {77, 3}}}

Performance is much higher than your code:

Nest[fn[osT], listT, 12]  // Dimensions // RepeatedTiming

Nest[addOffset, list, 12] // Dimensions // RepeatedTiming

{0.111, {3, 1062882}}

{5.321, {1062882, 3}}

---

A variation of the code above that may be useful is to use linked lists for the tracker rather than packed arrays. These prove to be slower than the code above for the example given but unlike that code they do not rely on packable data (like machine integers) for speed. If you would need to translate from a String label to integers and back again to use the code above the overhead of that would be significant. This code will let you use any non-List label directly:

fn2[{o_, p_, q_}][{x_, y_, h_}] :=
  {Join @@ (x + # & /@ o), Join @@ (y + # & /@ p), Tuples[{h, q}]}

Example:

result = Nest[fn2[offsets\[Transpose]], list\[Transpose], 2]

{
 {1, 2, 2, 3, 1, 2, 2, 3, 3, 4, 2, 3, 1, 2, 2, 3, 1, 2},
 {0, 3, 0, 3, 1, 4, 0, 3, 0, 3, 1, 4, 1, 4, 1, 4, 2, 5},
 {{{"b", "a"}, "a"}, {{"b", "a"}, "b"}, {{"b", "a"}, "c"},
  {{"b", "b"}, "a"}, {{"b", "b"}, "b"}, {{"b", "b"}, "c"},
  {{"b", "c"}, "a"}, {{"b", "c"}, "b"}, {{"b", "c"}, "c"},
  {{"bbcc", "a"}, "a"}, {{"bbcc", "a"}, "b"}, {{"bbcc", "a"}, "c"},
  {{"bbcc", "b"}, "a"}, {{"bbcc", "b"}, "b"}, {{"bbcc", "b"}, "c"},
  {{"bbcc", "c"}, "a"}, {{"bbcc", "c"}, "b"}, {{"bbcc", "c"}, "c"}}
}

You can either Flatten or StringJoin one of these linked lists:

Flatten /@ result[[3]]

StringJoin /@ result[[3]]

{{"b", "a", "a"}, {"b", "a", "b"}, {"b", "a", "c"},
 {"b", "b", "a"}, {"b", "b", "b"}, {"b", "b", "c"},
 {"b", "c", "a"}, {"b", "c", "b"}, {"b", "c", "c"},
 {"bbcc", "a", "a"}, {"bbcc", "a", "b"}, {"bbcc", "a", "c"},
 {"bbcc", "b", "a"}, {"bbcc", "b", "b"}, {"bbcc", "b", "c"},
 {"bbcc", "c", "a"}, {"bbcc", "c", "b"}, {"bbcc", "c", "c"}}

{"baa", "bab", "bac", "bba", "bbb", "bbc", "bca", "bcb", "bcc", "bbccaa",
 "bbccab", "bbccac", "bbccba", "bbccbb", "bbccbc", "bbccca", "bbcccb", "bbcccc"}

Timing for this second function:

Nest[fn2[offsets\[Transpose]], list\[Transpose], 12] // Dimensions // RepeatedTiming

{0.154, {3, 1062882}}