Data-structure for multiway associativity in Python
qrious
mittra at juno.com
Sun Jan 28 17:48:02 EST 2018
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.
More information about the Python-list
mailing list