Algorithm: map[string][]string -> reversed map[string][]string – Getting Assist

You could have a dataset that represents the relationships between canines and cats. The dataset is structured as a map, the place every canine is related to a listing of cat names. The cat names for a given canine are distinctive. Total, all cat names and canine names are distinctive, though 2 canines might belong the identical cat, and two cats might belong to the identical canine.

Drawback: Your objective is to generate a brand new dataset that reverses the relationships, the place every cat is related to a listing of distinctive canine names.

How would you resolve this effectively ? What do you do with giant information ? Does Go supply any help/library information constructions for this state of affairs ? What’s the idiomatic option to strategy this drawback ?

PS: I’ve already experimented with the “iterate via the enter map, for every worth add it to the brand new map, at its corresponding key, if not already there”. In search of one thing extra environment friendly than this. Equally, the “use an auxiliary map to test if a canine already belongs to this cat”.

  dogscats := make(map[string][]string)  // map every canine to a catlist.
  for cat, doglist := vary catsdogs {
    for _, canine := vary doglist {
       dogscats[dog] = append(dogscats[dog], cat)
    }
  }

For a lot of cats per canine, it’s possible you’ll be reallocating catlists. If that’s a efficiency drawback,
loop via catsdogs as soon as to rely the variety of cats per canine so you’ll be able to allocate the catlists to the proper preliminary measurement. One other efficiency drawback might come from rising the map. You’ll be able to rely the distinctive canines to pre-allocate the scale of dogscats, however doing that you just’ll want a set of canines (as a map) that would wish to develop equally to dogscats, so it will not be worthwhile.

Only for enjoyable, right here’s @mje ‘s algorithm in a runnable atmosphere: https://goplay.instruments/snippet/6UoNk3saTo8

I’m curious what extra environment friendly stuff folks give you. Possibly even one thing with reminiscence enviornment’s or what not?

in case there are a number of duplicates, have an auxiliary information construction, dogCats is a map[string]map[string]interface{}. After you construct this auxiliary information construction, you construct your consequence from it.

But it’s extremely depending on what number of duplicates, you allocate extra reminiscence than wanted, and so on.

Right here’s one other model however this time with the dummy information initialised in stead of constructed with append: https://goplay.instruments/snippet/r5lLSEkJTRW

Underlying information construction is map[string][]string.

Essentially the most environment friendly resolution might be encoding the dog-cats relationship in a [][]bool-matrix. No want to change the matrix since you’ll be able to simply iterate over it with columns and rows switched (in impact transposing the matrix).

Operating instance:

 canines := [3]string{"dog1", "dog2", "dog3"}
cats := [4]string{"cat1", "cat2", "cat3", "cat4"}
                                                                           
dogm := [3][4]bool{
	[4]bool{true, true, true, true},    // dog1 has cat1, cat2, cat3, cat4
	[4]bool{true, false, true, false},  // dog2 has cat1, cat3
	[4]bool{true, false, false, false}, // dog3 has cat1
}
                                                                           
// print supply information
printmatrix(canines[:], cats[:], dogm)

At present I’m nonetheless attempting to write down a (maybe generic) printmatrix-function in stead of the two separate ones that avoids copying the matrix (with hard-coded dimensions) to slices.

hello @duckduck

Your thought is a transparent instance of pondering out of the field, congratulations to you sir. Having stated that, I don’t suppose I can use it: when you have N hundreds of thousands of canines and M hundreds of thousands of cats, or much more, it’s essential to contemplate the prices of storing a N*M bool matrix in reminiscence, on this case it appears an excessive amount of.

In a roundabout way associated, if a canine entity is only a easy small string, like “dog1”, the distinction between storing a bool or the string itself, isn’t sufficiently big to advantage memoization. A bool is a byte, whereas a string is one thing like 3 ints (certainly one of them being a pointer to the immutable rune slice itself).

Preserve coming with modern concepts, I’m positive this drawback might be solved extra effectively than a pair of maps.

The canine/cat instance is more likely to very sparse. In case your actual drawback can be very sparse, contemplate a sparse matrix implementation like CSR. Sparse matrix implementations are optimized for (comparatively) quick matrix/matrix operations, so that you’ll pay a runtime penalty for random component entry.

It’s also possible to cut back house through the use of an int64 to carry 64 matrix components, however this might work in opposition to, and definitely complicate, a sparse implementation.