Data-structure for multiway associativity in Python

[qrious]

On Sunday, January 28, 2018 at 7:00:38 AM UTC-8, Steven D'Aprano wrote:

> 
> Since you specified that there are no lists with shared members, why 
> bother returning a list of lists? There will only ever be a single 
> matching list.
> 

That's correct. It will be a single list. My mistake in typing. 

> 
> To speed it up more, we'd need to know more information about how you are 
> using this. For example, if the values c1, ... d1, ... etc have some sort 
> of relationship, 

No relationship. 

> you might be able to generate some kind of multiway tree 
> that avoids having to search all of the thousands of lists before giving 
> up.

Which brings us to the Subject line of this thread. Without any relationship among the members, could we solve this using clever data structure? 
> 
> Are searches going to typically hit the same set c1... over and over 
> again? If so, then after matching, bring it to the front of the master 
> list. (You might want to use a deque for that.)
> 
> 
> 
> > Here a hash may be a way to go, but need help in figuring it out. Also,
> > can there be a faster and more memory efficient solution other than
> > hashes?
> 
> Probably not, not unless you have some sort of internal structure you can 
> take advantage of. For example, if all the strings in any group start 
> with the same letter, then you can dispatch directly to the right list:
> 
> data = {'c': {c1, c2, c3, ..., cn},
>         'd': {d1, ... } # and so on...
>         }
> 
> def getAssocList(element):
>     if element in data[element[0]]:
>         return L
>     raise ValueError('not found')
> 
> 
> But if there is no structure at all, and the elements in each list are 
> completely arbitrary, then there is nothing better than a linear search 
> through the entire collection of lists, looking at every single element 
> until you've matched what you're after.

The motivation of posting this thread is to explore if the above is true. 

> 
> But your description is pretty vague and for all I know what you actually 
> want is already a solved problem. Can you give more detail and cut-down 
> example of your data set? Say, two or three values per list, and two or 
> three lists.
> 
> 

First list = { 1, 2, 3} 
Second list = { 4, 5, 6} 
Third list = { 7, 8, 9} 

If I pass 9 as the argument, the return value of the function would be {7, 8}.


> -- 
> Steve

Thanks very much for your help and thoughts.