CODEWITHSUNDEEP
pythonalgorithmdata-structures
MLister
MLister

Reputation: 10310

Efficient algorithm for pairwise computation

I have a list of agents a = {a1, a2, a3,..., an}, in which each agent may be paired up with zero or more other agents. For example, for n = 6, I can have:

a1: a2, a3, a5
a2: a1, a3, a4
a3: a1, a2. a5
a4: a2
a5: a1, a3
a6:

Each pair interact with each other, and each agent obtains a value as the result of this interaction (e.g. they can play a game, but the details of interaction can be abstracted away here). I am interested in computing and storing the results of these interactions based on a given pairwise structure such as above.

Obviously, a naive algorithm would be to go through each agent and then compute the pairwise interaction with each of his interacting partners one-by-one. However, it is also obvious that this approach will duplicate some (or potentially many) computation. Using the example above:

by the time we finish for agent a1, we would've already obtained the results for (a1, a2), (a1, a3), and (a1, a5), thus rendering the later computation among these pairs redundant when we do it for agent a2, a3, and a5,

An improved algorithm would be to sort the input structure in an ascending order in both dimensions (i.e. along agents themselves and along their respective partners) as in the example above, so that for each agent (e.g. a3), we only need to compute for the interactions between this agent (a3) and the ones that are 'higher' than him (a5), since we know the interactions between himself and 'lower' partners ((a1, a3), (a2, a3)) have already been computed.

I wonder if there is different and better algorithm for this problem? By better, I mean more efficient computation in terms of both time and space.

Upvotes: 1

Views: 1458

Answers (5)

MLister
MLister

Reputation: 10310

Based on @gnibbler's answer, I come up with this:

agents = {
    'a1': ['a2', 'a3', 'a5'],
    'a2': ['a1', 'a3', 'a4'],
    'a3': ['a1', 'a2', 'a5'],
    'a4': ['a2'],
    'a5': ['a1', 'a3'],
    'a6': []
}

pairs = {tuple(sorted((k,v))) for k in agents for v in agents[k]}

Sorting is still needed but only restricted to a pair.

Upvotes: 0

Trevor
Trevor

Reputation: 9578

You can compare the agent ids with something like this:

agents = {
    'a1': ['a2', 'a3', 'a5'],
    'a2': ['a1', 'a3', 'a4'],
    'a3': ['a1', 'a2', 'a5'],
    'a4': ['a2'],
    'a5': ['a1', 'a3'],
    'a6': []
}

interactions = []
for agent, connections in agents.iteritems():
    interactions.extend((agent, connection) for connection in connections if agent < connection)

print interactions
# [('a1', 'a2'), ('a1', 'a3'), ('a1', 'a5'), ('a3', 'a5'), ('a2', 'a3'), ('a2', 'a4')]

Upvotes: 2

John La Rooy
John La Rooy

Reputation: 304355

Yes this tries to add each pair to the set twice, but I feel that this may be more efficient than the conditional. Does anyone want to try timing the alternatives?

agents = {
    'a1': ['a2', 'a3', 'a5'],
    'a2': ['a1', 'a3', 'a4'],
    'a3': ['a1', 'a2', 'a5'],
    'a4': ['a2'],
    'a5': ['a1', 'a3'],
    'a6': []
}
pairs = {(k,v) for k in agents for v in agents[k]}

This is still O(n), so in terms of efficiency beats anything involving sorting

You'd probably get a minor speedup by using

pairs = {(k,v) for k,vs in agents.iteritems() for v in vs}

Upvotes: 3

Sergei Danielian
Sergei Danielian

Reputation: 5025

As far as I understand your question, why don't you take into account a 2D matrix? At first stage, just set intersection cells equals to 1 if two agents can cooperate with each other. At second stage, just set a cycle around the matrix and calculate some values only between those agents, who has a interconnection (i.e. where cell is equal to 1). And instead of 1 there will be a real value. So in that case you don't need to do redundant calculations. The only redundant part is to fill calculated value twice in matrix.

Upvotes: 0

Nick Craig-Wood
Nick Craig-Wood

Reputation: 54107

itertools to the rescue

>>> from itertools import combinations
>>> agents=['a1','a2','a3','a4','a5']
>>> list(combinations(agents, 2))
[('a1', 'a2'), ('a1', 'a3'), ('a1', 'a4'), ('a1', 'a5'), 
 ('a2', 'a3'), ('a2', 'a4'), ('a2', 'a5'),
 ('a3', 'a4'), ('a3', 'a5'),
 ('a4', 'a5')]
>>>

Upvotes: 0

Related Questions