On Sat, 27 Jan 2018 10:01:47 -0800, qrious wrote:
> I need a data structure and a corresponding (hopefully fast) mechanism
> associated with it to do the following. While I am looking for the
> concept first, my preference for implementation of this will be in
> Python.
>
> [c1, c2,..., cn] is a list of strings (for my own implementation, but
> could be any other type for the generic problem). There will be many
> hundreds, if not thousands, of such lists with no shared member.
>
> The method getAssocList(e) will return lists of the lists for which e is
> an element.
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.
data = [
[c1, c2, ..., cn],
[d1, d2, ..., dn],
# hundreds more...
[z1, z2, ..., zn],
]
def getAssocList(element):
for L in data:
if element in L:
return L
raise ValueError('not found')
For faster results, use sets {c1, c2, ..., cn} rather than lists. The
outer list still has to be a list though.
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, 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.
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.
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.
--
Steve
--
https://mail.python.org/mailman/listinfo/python-list
