# Faster counting of sequences

**URL:** <https://discourse.julialang.org/t/faster-counting-of-sequences/66359>\
**Category:** Performance\
**Tags:** dataframes, data\_structures\
**Created:** [August 13, 2021, 8:08pm UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359 "2021-08-13T20:08:00Z")\
**Posts on this page:** 11\
**Page:** 1

<div class="post-metadata">

**Author:** ![danielw2904](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielw2904/32/10890_2.png) [@danielw2904](https://discourse.julialang.org/u/danielw2904)\
**Post date:** [August 13, 2021, 8:08pm UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/1 "2021-08-13T20:08:00Z")

</div>

I have a problem in which I am trying to figure out how many items were first selected by user i and later by user j for all users.

My idea was to create a sparse matrix M with n-users \times n-users in which the rows selected first and columns second s.t. M\_{i,j} shows the number of items that were first selected by user i and later by user j (the diagonal should accumulate the total number of items selected by a user).

My table looks like this:

| User | Item | time |
| --- | --- | --- |
| “abc” | “ijk” | 2020-01-01 |
| “def” | “ijk” | 2020-01-02 |
| \vdots | | |

Which should result in matrix M

\begin{bmatrix} 1\quad 1 \\ 0\quad 1 \end{bmatrix}

I group a time-sorted `DataFrame` by item and then process each item separately (This allows for associative reduction). Since `GroupedDataFrame` does not work directly with `Floops` I am using the indices. Is that a problem? Any suggestions for making this faster?  
Here is a minimal example of my approach:

```julia
using Random, StatsBase, Dates, DataFrames, SparseArrays, Tables, FLoops

Random.seed!(1)

items = [randstring(10) for _ in 1:300]
users = [randstring(5) for _ in 1:5000]

item_selection = sample(items, 20000, replace = true)
user_selection = sample(users, 20000, replace = true)
dates = sample(Date("2015-01-01"):Day(1):Date("2021-01-20"), 20000, replace = true)

data = DataFrame(items = item_selection, users = user_selection, dates = dates)
sort!(data, :dates)
# only look at first selection
data = combine(groupby(data, [:items, :users]), first)

uniqueusers = unique(data.users)
user_index = Dict(uniqueusers .=> eachindex(uniqueusers))
nusers = length(uniqueusers)

gitems = groupby(data, :items)

M = spzeros(nusers, nusers)

function processitem(itemdata, userdict)
    nusers = length(userdict)
    M_tmp = spzeros(Int, nusers, nusers)
    dates = itemdata.dates
    users = itemdata.users
    for item in Tables.namedtupleiterator(itemdata)
        startindex = findfirst(>(item.dates), dates)
        if !isnothing(startindex)
            later_users = users[startindex:end]
            current_index = userdict[item.users]
            later_indices = [userdict[user] for user in later_users]
            M_tmp[current_index, later_indices] .+= 1
            M_tmp[current_index, current_index] += 1
        end
    end
    return M_tmp
end

@time @floop ThreadedEx() for i in 1:length(gitems)
    item = gitems[i]
    @reduce(Mfloop += processitem(item, user_index))
end;

@time Mmapfoldl = mapfoldl(i -> processitem(i, user_index), +, gitems);

Mfloop == Mmapfoldl

```

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 14, 2021, 2:30am UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/2 "2021-08-14T02:30:43Z")

</div>

> [@danielw2904](#):
>
> My idea was to create a sparse matrix M MM with n-users \times ×\times n-users in which the rows selected first and columns second s.t. M\_{i,j} Mi,jM\_{i,j} shows the number of items that were first selected by user i ii and later by user j jj (the diagonal should accumulate the total number of items selected by a user).

can’t understand it

---

<div class="post-metadata">

**Author:** ![danielw2904](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielw2904/32/10890_2.png) [@danielw2904](https://discourse.julialang.org/u/danielw2904)\
**Post date:** [August 14, 2021, 9:49am UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/3 "2021-08-14T09:49:39Z")

</div>

Thanks for the reply, sorry for being unclear. Basically I want to determine which users always follow another user in their selection. The goal is to have for a given user (user1)

1. The number of unique items a user selected
2. For all other users the number of items they have selected that were previously selected by user1.  
So for example if there are apples, bananas and chocolate and I get an apple today I’d like to add 1 to my number of selections. If you get an apple and chocolate tomorrow I’d like to add 2 to your number of selections and add 1 to the number of items I have selected before you. If I then select chocolate on yet another day I’d like to add 1 to my number and 1 to the number of items you have selected before me.

---

<div class="post-metadata">

**Author:** ![xiaodai](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/xiaodai/32/15937_2.png) [@xiaodai](https://discourse.julialang.org/u/xiaodai)\
**Post date:** [August 14, 2021, 11:23am UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/4 "2021-08-14T11:23:22Z")

</div>

still very confusing to be honest. Not sure how that description relates to the matrix you have shown.

---

<div class="post-metadata">

**Author:** ![danielw2904](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielw2904/32/10890_2.png) [@danielw2904](https://discourse.julialang.org/u/danielw2904)\
**Post date:** [August 14, 2021, 12:42pm UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/5 "2021-08-14T12:42:43Z")

</div>

Sorry I’m having a hard time explaining the problem. So in the data above we have two users and one item. The matrix is my current approach to represent the solution. Since both users pick the item the diagonal is 1 for both. Since the first user picked the item before the second user the element 1,2 is 1. If I do this over all items and sum the matrices I get a diagonal with the number of chosen items and off diagonal of how many items were first chosen by the user mapped to the row and later the user mapped to the column.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [August 14, 2021, 2:20pm UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/6 "2021-08-14T14:20:58Z")

</div>

There is a reason for using a `Matrix` here? It needs to be a `Matrix` to work with `Floops`?

---

<div class="post-metadata">

**Author:** ![danielw2904](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielw2904/32/10890_2.png) [@danielw2904](https://discourse.julialang.org/u/danielw2904)\
**Post date:** [August 14, 2021, 3:36pm UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/7 "2021-08-14T15:36:35Z")

</div>

The main reason is that I am not well versed in data structures but know matrices well. I guess floops can do any reduction. Do you have any suggestions for a better structure?

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [August 14, 2021, 4:28pm UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/8 "2021-08-14T16:28:07Z")

</div>

Did you try to work over the `DataFrame` itself?

For the number of unique items, I would do:

```julia
julia> df = DataFrame(:user => ["abc", "def"], :item => ["ijk", "ijk"], :time => Date.(["2021-01-01", "2021-01-02"]))
2×3 DataFrame
 Row │ user item time       
     │ String String Date       
─────┼────────────────────────────
   1 │ abc ijk 2021-01-01
   2 │ def ijk 2021-01-02

julia> combine(groupby(df, :user), :item => length ∘ unique! ∘ sort => :qt_unique_items)
2×2 DataFrame
 Row │ user qt_unique_items 
     │ String Int64           
─────┼─────────────────────────
   1 │ abc 1
   2 │ def 1

```

For the second value I need more info. If some user buys the same item in two different moments, which time does count for checking if the item was previously selected by the primary user? It only counts if the first time the item was bought by a secondary user happened before the first time of the primary user?

---

<div class="post-metadata">

**Author:** ![danielw2904](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielw2904/32/10890_2.png) [@danielw2904](https://discourse.julialang.org/u/danielw2904)\
**Post date:** [August 14, 2021, 5:00pm UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/9 "2021-08-14T17:00:29Z")

</div>

Yes for the own counts that works. As for the second value I am only looking at the very first purchase of each user. I first sort by time and the group by user and item and select the first row.

---

<div class="post-metadata">

**Author:** ![Henrique\_Becker](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/henrique_becker/32/15443_2.png) [@Henrique\_Becker](https://discourse.julialang.org/u/Henrique_Becker)\
**Post date:** [August 15, 2021, 12:05am UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/10 "2021-08-15T00:05:47Z")

</div>

I have written the code below, but I have reached the conclusion I yet do not understand your problem well. What I have written computes the sum of how many other people have selected each unique item before you selected it. Now I am in doubt, do you wanna a single value per user, or do you wanna a single value for **pair** of users? Because in your example you say:

> [@danielw2904](#):
>
> and add 1 to the number of items I have selected before you. If I then select chocolate on yet another day I’d like to add 1 to my number and 1 to the number of items you have selected before me

So it seems like you are keeping an score for each pair of users, what would kind of explain your idea of a matrix. Because `m[1, 2]` would give how many items user 1 selected before user 2, and `m[2, 1]` would give how many items user 2 selected before user 1.

```julia
function compute_qt_selected_before(df)
    unique_users = unique!(sort(df[!, :user]))
    qt_selected_before = Dict{String, Int}(unique_users .=> 0)
    df_unique = combine(groupby(df, [:user, :item]), :time => first)
    sort!(df_unique, [:item, :time_first])
    c = 0
    for (row_idx, item) in pairs(df_unique[!, :item])
        item != last_item && (c = 0)
        qt_selected_before[df_unique[row_idx, :user]] += c
        c += 1
    end
    return qt_selected_before
end

```

---

<div class="post-metadata">

**Author:** ![danielw2904](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/danielw2904/32/10890_2.png) [@danielw2904](https://discourse.julialang.org/u/danielw2904)\
**Post date:** [August 15, 2021, 3:00pm UTC](https://discourse.julialang.org/t/faster-counting-of-sequences/66359/11 "2021-08-15T15:00:14Z")

</div>

> [@Henrique\_Becker](#):
>
> Because `m[1, 2]` would give how many items user 1 selected before user 2, and `m[2, 1]` would give how many items user 2 selected before user 1.

Yes exactly! Thank you for your suggestion! I went a bit overboard but this is the final implementation

```julia
using LinearAlgebra, Random, StatsBase, Dates, DataFrames, Tables, Chain, ProgressMeter

Random.seed!(1)
items = [randstring(10) for _ in 1:30]
users = [randstring(5) for _ in 1:50]

item_selection = sample(items, 100, replace = true)
user_selection = sample(users, 100, replace = true)
dates = sample(Date("2020-10-15"):Day(1):Date("2021-01-20"), 100, replace = true)

data = DataFrame(item = item_selection, user = user_selection, date = dates)

function proc(fulldata)
    fulldata = @chain fulldata begin
        sort!(:date)
        groupby([:item, :user])
        combine(first)
        sort!([:item, :date])
    end
    uuser = unique(fulldata.user)
    nuser = length(uuser)
    user_index = Dict(uuser .=> eachindex(uuser))
    transform!(fulldata, :user => ByRow(x-> user_index[x]) => :user_id)
    
    M = zeros(Int, nuser, nuser)
    indexer = Vector{Int}(undef, nuser)
    prev_date = Date(1971,1,1)
    prev_item = " __NOT_AN_ITEM__"
    offset = 0
    tab = Tables.rows((user_id = fulldata.user_id, item = fulldata.item, date = fulldata.date))
    M = procinner(tab, indexer, M, prev_date, prev_item, offset)
    return M, fulldata
end

function procinner(table, indexer, M, prev_date, prev_item, offset) 
    c = 0; daystartsat = 1
    @showprogress for r in table
        ruser_id = r.user_id
        ritem = r.item
        rdates = r.date
        # Accumulate number of previous listers
        same_item = (prev_item == ritem)
        same_item || (c = 0; daystartsat = 1)
        c += 1
        # Offset for same date listings (should not count as previous)
        same_date = (prev_date == rdates)
        offset = ifelse(same_item && same_date, offset + 1, 0)
        offset == 1 && (daystartsat = c-1)
        @inbounds indexer[c] = ruser_id
        for u in @inbounds(view(indexer, 1:daystartsat-1))
            @inbounds M[u, ruser_id] += 1
        end
        for u in @inbounds(view(indexer, daystartsat+offset:c))
            @inbounds M[u, ruser_id] += 1
        end
        prev_item = ritem
        prev_date = rdates
    end
    return M
end
M, data_id = proc(data)

```

And a version that is equivalent but uses a more `DataFrame` based approach:

```julia
function getrow(data, user_id)
    user = subset(data, :user_id => ByRow(==(user_id)))
    rout = []
    for comb in zip(user.item, user.date)
        rows = subset(data_id, :item => ByRow(==(comb[1])), :date => ByRow(>(comb[2])))
        push!(rout, rows)
    end
    out = combine(groupby(reduce(vcat, rout),:user_id), x->nrow(x))
    return rename(out, :x1 => :n)
end

function makeM(data_id)
    Mdiag = sort(combine(groupby(data_id, :user_id), :item => length), :user_id).item_length
    Mmanual = zeros(Int, length(Mdiag), length(Mdiag))
    Mmanual[diagind(Mmanual)] = Mdiag
    for i in 1:size(Mmanual,1)
        other = getrow(data_id, i)
        Mmanual[i, other.user_id] += other.n
    end
    return Mmanual
end

makeM(data_id) == M
```