# A Tree? Multi-dimensional Array? hmm

**URL:** <https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969>\
**Category:** Performance\
**Tags:** question, array, optimization, tree\
**Created:** [November 9, 2022, 7:50am UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969 "2022-11-09T07:50:31Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![theboiwholived](https://avatars.discourse-cdn.com/v4/letter/t/aeb1de/32.png) [@theboiwholived](https://discourse.julialang.org/u/theboiwholived)\
**Post date:** [November 9, 2022, 7:50am UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969/1 "2022-11-09T07:50:31Z")

</div>

Hey all, could really use your expertise in determining if what i need here is a tree… and how i would go about doing that

At the moment my code basically determines out the difference of all trades between currencies.  
c.Ai represents the name of a currency, example USD or EUR, represented numerically.

Lets say i have a 10 currencies  
[1,2,3,4,5,6,7,8,9,10]

The code below takes all of my exchanges and computes the grand total difference.

```julia
    for (Δ, Λ, c) in zip(r.Δs, r.Λs, r.exchanges)
        difference[c.Ai] += Λ - Δ
    end

```

an example result:  
[100, 0, 4, 50, 70000, 450, 20, 1, 42, .01]

coinciding to the final output of currency 1 - 10

What i need to do is instead of grab just total difference, id like to be create a path of what was exchanged. Tracking more or less what my loop is doing  
ex

```julia
[1,2...10]
 3 7 5
 6 1 8 
 2 4 9

```

basically a tree i think? Essentially say from currency 10, user converted to 5 then 8 then 9. Id also like to like highlight in the event a user took a currency and split it into more than one currency, ex:

```julia
[1,2......10]
 3 7 5
 6 1 8 4 
 2 4 9 3

```

which is makes me think a tree is valid here. Is there a smart clear cut way to accomplish this in Julia without introducing a ton of code debt weighing me down? Similar to how i have the for loop that just rips through the zip for totals?

Can trees store multi values? Like in addition to the path, also the difference at each step?

* * *

extra question out of curiosity:  
was doing some research on for loops with multi threads for enhanced speed, or GPU based Arrays with CUDA - should i look into multi thread here?

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [November 9, 2022, 8:37am UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969/2 "2022-11-09T08:37:43Z")

</div>

How large is your dataset, is it like millions of entries or just a few. Depending on that different approaches might be good.

Naively, I would create for every user a 10 by N matrix which represents after every step hoe much in each currency the user owns. E.g. in percentage or total amount.

Doing a tree seems more complicated for following computations.

---

<div class="post-metadata">

**Author:** ![theboiwholived](https://avatars.discourse-cdn.com/v4/letter/t/aeb1de/32.png) [@theboiwholived](https://discourse.julialang.org/u/theboiwholived)\
**Post date:** [November 10, 2022, 1:27am UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969/3 "2022-11-10T01:27:58Z")

</div>

Hey Steffen, thanks for the reply !  
Less about users and more on the currencies exchanged. So lets just say for one user.

Its really about \< 5000 for currencies in the array c.Ai, ex [1,2,3,4,5…4560] - I was hoping i could somehow wrap it in to the :

```julia
difference[c.Ai] += Λ - Δ 

```

for one spread or DF or tree or something. To then iterate upon if need be -

my concern would be in instances where they take a number of currency X and split it into two different currencies , i would lose out on that vector of accuracy for what really happened to find the total difference. 😕

“Naively” How would you go about it? I must admit any all help would be huge at this point. Quite stuck.

Thanks!

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [November 10, 2022, 7:17am UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969/4 "2022-11-10T07:17:28Z")

</div>

First of all, there might be packages for your task, for example:

- For conversion between currencies: [GitHub - JuliaPackageMirrors/Currencies.jl: Julia package mirror.](https://github.com/JuliaPackageMirrors/Currencies.jl)
- It could also be nice to use [DataFrames!](https://github.com/JuliaData/DataFrames.jl)

That having said, this is how I would do it with plain Julia. I use sparse matrices to represent the transitions in each step. That allows you to have full control, you can even convert into multiple currencies at the same time… To get the final amount one has to multiply all transition matrices with the initial vector. (Of course, I assume there is no fee between transitions, but you could also extend it to that case)

```julia
using LinearAlgebra, SparseArrays

# initial currencies 
n_currencies = 500
n_steps = 2

transactions = [sparse(1.0I(n_currencies)) for i in 1:n_steps]

rates = sparse(1.0I(n_currencies))

# I don't know, some random data, say [usd, jpy and yuan]
rates[1:3,1:3] .= [1.0 1/146.0 1/7.25; 146.0 1.0 1/0.05; 7.25 0.05 1.0]

# sent in first step money from currency #1 to currency #2  
transactions[1][1:2, 1] .= [0.0, 1.0] .* rates[1:2,1]

# sent in second step money from currency #2: 30% to currency #1 and 50$ to #3, 20% we keep
transactions[2][1:3, 2] .= [0.3, 0.2, 0.5] .* rates[1:3,2]

init_x = zeros(n_currencies)
init_x[1:3] .= [100.0, 0.0, 0.0]

x = init_x[:]

for transaction in transactions
    x .= transaction * x
end

x[1:3] # -> [29.999999999999996, 2920.0, 365.0]

```

---

<div class="post-metadata">

**Author:** ![theboiwholived](https://avatars.discourse-cdn.com/v4/letter/t/aeb1de/32.png) [@theboiwholived](https://discourse.julialang.org/u/theboiwholived)\
**Post date:** [November 10, 2022, 10:45pm UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969/5 "2022-11-10T22:45:43Z")

</div>

@SteffenPL , legend! This is awesome! 😃 massively helpful.

I think I’m in line with you across the board outside of the rates portion.

And particular to your example but just want to make sure i entirely understand the low down of the knowledge your providing.

What are we emulating here from the rates changing in rates[1:2,1] to rates[1:3,2] ? Just want to understand the example if there was a reason you switched from just doing rates[1:2,2] for transaction 2. Is this just to demonstrate a possible change in rate data from like day 1 or 2 ?

Separate to that How then would you suggest i track the path of the swapped currencies held with the transactions sparsearrays?

Is there a way we could combine transaction 1 and 2 for a total path of what was exchanged?

```julia
julia> transactions[1][1:2, 1]
2-element SparseVector{Float64, Int64} with 2 stored entries:
  [1] = 0.0
  [2] = 146.0

julia> transactions[2][1:3, 2]
3-element SparseVector{Float64, Int64} with 3 stored entries:
  [1] = 0.00205479
  [2] = 0.2
  [3] = 0.025

```

I imagine there’s a cleaner way than a for loop to push or append the numbers at position 1 in transaction[x] to a new array for a net profit/loss path? Ideally it would be this for all 500. To somehow from all transactions print just the column of change for a position, ex 1 for usd?

```julia
[1] = 0.0 (tx 1)
[2] = 0.00205479 (tx 2)

```

Lastly, i need to track the change of what currencies were converted per tx in the path rather than just overall net change.

So when you wrote “sent in first step money from currency #1 to currency #2” - how could we take this example to track that exact path, so at the end we could print the path from say USD or currency 1 just like how we track net change per step in transactions[x]? 😮  
ex:

```julia
[1] = 1 
[2] = 2
[3] = 10 
etc..

```

Thanks again Steffen, learning worlds from this already.

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [November 11, 2022, 6:21am UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969/6 "2022-11-11T06:21:39Z")

</div>

Oh, I think there is a unlucky coincidence in the example that the i th transaction happens in the i th column of the matrices…

With the approach of the example, in each step the transaction matrix `transactions[1]` can represent any kind of transfer from any currency to any other currency (all at once). If I write `Ai = transactions[i]` then the entry `Ai[n,m]` represents the amount of transfer (in percentage) from currency `m` to currency `n`.  
(But there could be another transfer in the other direction at the same time, which might balance out.)

These `Ai` matrices could be seen as adjacency matrices of the graph representing the flow of money in the `i` th step.

You can get the transactions between the initial and the final state via

```julia
total_transaction = prod( transactions ) # EDIT: is should be prod(reverse(transactions))

```

here, the indices `total_transaction[i,j]` again indicate the transfer from currency `j` to currency `i`.

In the given example

```julia
prod(transactions)[1:3,1:3] # EDIT: it should be reverse(transactions)...
3×3 SparseMatrixCSC{Float64, Int64} with 6 stored entries:
   0.0 0.0 ⋅ 
 146.0 0.5 ⋅ 
    ⋅ 0.025 1.0

```

and if you want to know how an initial amount of money propagates, you can use `total_transactions * init_x` and similar, the j th column gives you where the j th currency went too.

(I know, it’s a bit the opposite way of indices compared to what one would expect. Otherwise you have to transpose the matrix or use row-vectors from the left side, instead of the matrix-vector produce.)

* * *

EDIT: by the way, you can also use normal matrices instead of sparse ones. I think sparse onces are only needed for very large problems.  
Or, if you know that in each step only one currency is converted, you can just just `(idx = 2, targets = [0.3,0.2,0.5])`. Many possibilities.

---

<div class="post-metadata">

**Author:** ![theboiwholived](https://avatars.discourse-cdn.com/v4/letter/t/aeb1de/32.png) [@theboiwholived](https://discourse.julialang.org/u/theboiwholived)\
**Post date:** [November 12, 2022, 12:47am UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969/7 "2022-11-12T00:47:38Z")

</div>

😃 visibly makes all the sense, amazing!!! Is there a good way without reiterating on the list the final path it traversed? Or maybe i need to iterate again on total\_transaction which is okay, but curious how to capture in code the final path list of steps in a more human readable format  
ex: total\_transaction[1:3,1:3] = or prod(transactions)[1:3,1:3] =

```julia
prod(transactions)[1:3,1:3]
3×3 SparseMatrixCSC{Float64, Int64} with 6 stored entries:
   0.0 0.0 ⋅ 
 146.0 0.5 ⋅ 
    ⋅ 0.025 1.0

```

prod(transactions) translates to a transaction path of USD to step 1 to step 2, being

totalpath =

```julia
[1] = JPY  
[2] = USD, JPY, YUAN  

```

or as we defined earlier as numbers, currency 1 2 and 3

```julia
[1] = 2 
[2] = 1, 2 ,3 

```

or perhaps

[[1] , [1,2,3] ]

I’d like to be able to capture this list for a more human readable output to keep as record, and then also be able to iterate on everything else like you so graciously taught me.

* * *

Lastly just a general question on the result here, where is the 0.5 coming from in column 2 row 2 for prod(transactions)[1:3,1:3] ? Should that number be 0.2 ? Or am I misunderstanding that value and where its coming from ? And the # above that in column 2 row 1 be 0.00205479 ?

```julia
julia> transactions[2][1:3, 1:3]
3×3 SparseMatrixCSC{Float64, Int64} with 5 stored entries:
 1.0 0.00205479 ⋅
  ⋅ 0.2 ⋅
  ⋅ 0.025 1.0

julia> transactions[1][1:3, 1:3]
3×3 SparseMatrixCSC{Float64, Int64} with 4 stored entries:
   0.0 ⋅ ⋅
 146.0 1.0 ⋅
    ⋅ ⋅ 1.0

julia> prod(transactions)[1:3,1:3]
3×3 SparseMatrixCSC{Float64, Int64} with 6 stored entries:
   0.0 0.0 ⋅
 146.0 0.5 ⋅
    ⋅ 0.025 1.0

```

You have no idea how grateful i am of the help here 😃 . Thanks so much again @SteffenPL !!! Once i understand that human readable output part i think we can consider this absolutely more than solved \<3

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [November 12, 2022, 1:52pm UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969/8 "2022-11-12T13:52:13Z")

</div>

Oh! First about the `0.2`. That was a very stupid mistake in my code… You see that we compute T x to apply the transactions T to a vector x. To combine transactions T\_1,\dots,T\_n we need to compute T\_n \cdots T\_1 x, but wrongly I computed `prod(transactions)` which is T\_1 \cdots T\_n, i.e. in the wrong order.

The corrected code is

```julia
total_transaction = prod(reverse(transactions))

```

which then yields

```julia
julia> total_transaction[1:3, 1:3]
3×3 SparseMatrixCSC{Float64, Int64} with 7 stored entries:
  0.3 0.00205479 ⋅ 
 29.2 0.2 ⋅ 
  3.65 0.025 1.0

```

Sorry again for the mistake!

* * *

About the output, here is a quick code which gives your output. For sure, it could be done better but I guess it doesn’t matter too much:

```julia
using Printf

function print_transaction(T, rates, names = string.(1:size(T,1)))
    A = Matrix(T) 

    for col in 1:size(A, 2)
        targets = A[:, col]

        if any(targets .!= 0)
            printstyled("Transactions from [$(names[col])]:\n", color = :green)
            for row in 1:size(A,1)
                v = targets[row]
                p = targets[row] / rates[row, col] * 100
                if p != 0.0
                    @printf " %.2f → %s " p names[row] 
                    @printf "\t(1 %s → %.4f %s)\n" names[col] v names[row]
                end
            end
        end
    end
end

print_transaction(total_transaction, rates, ["USD", "JPY", "YUAN"])

```

gives

```julia
Transactions from [USD]:
  30.00 → USD (1 USD → 0.3000 USD)
  20.00 → JPY (1 USD → 29.2000 JPY)
  50.34 → YUAN (1 USD → 3.6500 YUAN)
Transactions from [JPY]:
  30.00 → USD (1 JPY → 0.0021 USD)
  20.00 → JPY (1 JPY → 0.2000 JPY)
  50.00 → YUAN (1 JPY → 0.0250 YUAN)
Transactions from [YUAN]:
  100.00 → YUAN (1 YUAN → 1.0000 YUAN)

```

Note that the `50.34` percent are because the rates I got from google do not match exactly, i.e. you gain money when you convert a few times back and forth. With correct numbers that problem shouldn’t be there.

---

<div class="post-metadata">

**Author:** ![theboiwholived](https://avatars.discourse-cdn.com/v4/letter/t/aeb1de/32.png) [@theboiwholived](https://discourse.julialang.org/u/theboiwholived)\
**Post date:** [November 13, 2022, 9:22am UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969/9 "2022-11-13T09:22:23Z")

</div>

Absolute legend! Cheers @SteffenPL 😃

beyond grateful for the help and time you’ve spent here teaching me. Really your guidance couldn’t be any more appreciated.

Absolutely solved. Did just want to validate column one with the new answer

```julia
julia> total_transaction[1:3, 1:3]
3×3 SparseMatrixCSC{Float64, Int64} with 7 stored entries:
  0.3 0.00205479 ⋅ 
 29.2 0.2 ⋅ 
  3.65 0.025 1.0

```

Should column one reflect similarly transaction[1] as column two the answers from the initial transaction[2] ?

```julia
julia> transactions[1][1:3, 1:3]
3×3 SparseMatrixCSC{Float64, Int64} with 4 stored entries:
   0.0 ⋅ ⋅
 146.0 1.0 ⋅
    ⋅ ⋅ 1.0

```

Curious how total\_transactions column 2 is the same as transaction[2] but not transaction[1] with column 1

for ex total\_transaction column 2 is the same as transaction 2

```julia
transactions[2][1:3, 2]
3-element SparseVector{Float64, Int64} with 3 stored entries:
  [1] = 0.00205479
  [2] = 0.2
  [3] = 0.025

```

I could be groggy overthinking the initial math, but regardless. Thanks again, wishing you and yours the merriest of holidays.  
🙂

---

<div class="post-metadata">

**Author:** ![SteffenPL](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/steffenpl/32/206270_2.png) [@SteffenPL](https://discourse.julialang.org/u/SteffenPL)\
**Post date:** [November 13, 2022, 11:02am UTC](https://discourse.julialang.org/t/a-tree-multi-dimensional-array-hmm/89969/10 "2022-11-13T11:02:25Z")

</div>

Thanks, I’m very happy if replies are useful. 🙂

If some columns of transaction matrices occur in the final one depends on the transactions before and afterwards.  
For example, the second transaction is the first time JPY is converted into something else and there is no transaction afterwards which further converts the initial JPY into something else. That’s why the column in the total transaction matrix is the same. But in general the total transaction matrix can be completely different than the individual ones.

In the example, the first column of total transactions is actually a multiple of the second column. Since we convert all USD into JPY and then we spread JPY in the second step. Since 1USD is 146JPY, you see that the first column of total transactions if 146 times the second 😉 [anyway, hope it does lead to more confusion.]