8 Replies - 12124 Views - Last Post: 18 March 2013 - 11:57 AM

#1 shintetsu_80  Icon User is offline

  • D.I.C Head

Reputation: 31
  • View blog
  • Posts: 105
  • Joined: 01-July 08

looping algorithm suckyness

Posted 16 March 2013 - 08:18 AM

Background:

I've got 1 object (we'll call this MainObj ) 3 arrays of objects. Two of them have data that is unrelated. The third is and association array that contains objects with properties for determining how the two otherwise unrelated arrays can be related to the MainObj.

Here's some pseudocode as an example of the arrays.
a1.id = 1;
a2.id = 2;
a3.id = 3;
as = [a1, a2];

b1.id = 'some value'
b2.id = 'another value'
b3.id = 'again value'
bs = [b1, b2];

// note there are only associations for a1, b1, a2, b2
// which means those all relate to the MainObj and a3, b3 do not related to the MainObj
assoc1.a = 1
assoc1.b = 'some value'
assoc2.a = 2
assoc2.b = 'another value'
associations = [assoc1, assoc2];



The end goal is to have a subarray of the related as and bs.
I realize that this could be solved with maps in the MainObject unfortunately I'm dealing with an api that queries a database for these values and three individual queries returning three individual arrays is the only starting point. The length of these arrays as, bs, associations can and will be different.

Potential solutions:

So the obvious approach is to loop through all three arrays to determine this.
assocAs = [];
assocBs = [];
for(i=0; i<associations.length; i++) {
  for(i=0; i<as.length; i++) {
    if (associations[i].a == as[i].id) {
      assocAs.push(as[i]);
    }
  }
  for(i=0; i<bs.length; i++) {
    if (associations[i].b == bs[i].id) {
      assocAs.push(bs[i]);
    }
  }
}


That's a lot of loops but the only solution I can come up with. Any other idea?

Is This A Good Question/Topic? 0
  • +

Replies To: looping algorithm suckyness

#2 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 1956
  • View blog
  • Posts: 4,057
  • Joined: 11-December 07

Re: looping algorithm suckyness

Posted 16 March 2013 - 02:59 PM

Encapsulate the problem in a class. Then you don't have to care if the class materialises the view or scans your arrays every time it is queried. I'm not entirely clear on how your association array works but something suitable can probably be adapted from the following:

public class Relation<A, B> {

	public Relateion(A[] as, B[] bs, Object[] associations) {
		// TODO Auto-generated constructor stub
	}
	
	public List<A> associatedAs(B B)/>/> {
		// TODO Implement
		return null;
	}

	public List<B> associatedBs(A a) {
		// TODO Implement
		return null;
	}

}


This post has been edited by cfoley: 16 March 2013 - 03:00 PM

Was This Post Helpful? 0
  • +
  • -

#3 stackoverflow  Icon User is offline

  • D.I.C Addict
  • member icon

Reputation: 164
  • View blog
  • Posts: 545
  • Joined: 06-July 11

Re: looping algorithm suckyness

Posted 17 March 2013 - 06:36 AM

What about caching the initial query locally in maps so subsequent queries are in constant time?
Was This Post Helpful? 0
  • +
  • -

#4 shintetsu_80  Icon User is offline

  • D.I.C Head

Reputation: 31
  • View blog
  • Posts: 105
  • Joined: 01-July 08

Re: looping algorithm suckyness

Posted 17 March 2013 - 10:23 AM

stackoverflow you're correct that this would at least limit doing this multiple times; however, in this case it's going to be used as a utility function where the cache would not reflect updates unless it was refreshed. The api in this case doesn't support page queries. So it's an all or nothing query. Meaning I couldn't just query for the updates an merge them in.

This post has been edited by shintetsu_80: 17 March 2013 - 11:00 AM

Was This Post Helpful? 0
  • +
  • -

#5 shintetsu_80  Icon User is offline

  • D.I.C Head

Reputation: 31
  • View blog
  • Posts: 105
  • Joined: 01-July 08

Re: looping algorithm suckyness

Posted 17 March 2013 - 10:39 AM

View Postcfoley, on 16 March 2013 - 10:59 PM, said:

Encapsulate the problem in a class. Then you don't have to care if the class materialises the view or scans your arrays every time it is queried. I'm not entirely clear on how your association array works but something suitable can probably be adapted from the following:

public class Relation<A, B> {

	public Relateion(A[] as, B[] bs, Object[] associations) {
		// TODO Auto-generated constructor stub
	}
	
	public List<A> associatedAs(B B)/>/>/> {
		// TODO Implement
		return null;
	}

	public List<B> associatedBs(A a) {
		// TODO Implement
		return null;
	}

}



cfoley I don't understand how this solves the looping issue. I'm reading your answer to imply creating a utility class that builds the two association arrays that are needed via the Relateion method. So the Relateion method would still do the exact same looping algorithm, but you get the accessor methods associatedAs and associatedBs. Maybe I wasn't clear in the initial post, or I misunderstand you're solution. Creating a wrapper or utility object to hold the finished products is really a non-issue. I only interested in trying to find a better solution to the initial looping algorithm.

To be fair these are completely disparate objects so there just might not be a better solution.
Was This Post Helpful? 0
  • +
  • -

#6 shintetsu_80  Icon User is offline

  • D.I.C Head

Reputation: 31
  • View blog
  • Posts: 105
  • Joined: 01-July 08

Re: looping algorithm suckyness

Posted 17 March 2013 - 10:40 AM

Starbucks internet connection sucks! Removing a double post cuz I don't know how to just delete.

This post has been edited by shintetsu_80: 17 March 2013 - 10:57 AM

Was This Post Helpful? 0
  • +
  • -

#7 cfoley  Icon User is online

  • Cabbage
  • member icon

Reputation: 1956
  • View blog
  • Posts: 4,057
  • Joined: 11-December 07

Re: looping algorithm suckyness

Posted 17 March 2013 - 02:06 PM

I think my point about the looping issue is that it might not be an issue. If you put it behind an interface then you can swap in a different implementation if you have performance problems. Other than that, it's a nice simple piece of code that communicates your intent.

If you have a large set of data, it's an n^2 algorithm so you might find that it's slow. If and only if you find it's slow, you can switch to maps which will give you a linear algorithm. Don't worry about having to construct the maps from the arrays. That will still be fast compared to the original algorithm.
Was This Post Helpful? 1
  • +
  • -

#8 shintetsu_80  Icon User is offline

  • D.I.C Head

Reputation: 31
  • View blog
  • Posts: 105
  • Joined: 01-July 08

Re: looping algorithm suckyness

Posted 18 March 2013 - 09:19 AM

cfoley I wholly agree with you and in fact my implementation is similar to your encapsulation idea. O(n^2) is probably not going to be an issue in my case. I was really just curious if someone smarter than me might have a solution that I wasn't seeing. Thanks for you input.
Was This Post Helpful? 0
  • +
  • -

#9 baavgai  Icon User is online

  • Dreaming Coder
  • member icon

Reputation: 5805
  • View blog
  • Posts: 12,644
  • Joined: 16-October 07

Re: looping algorithm suckyness

Posted 18 March 2013 - 11:57 AM

You need a dictionary. What is the programming language in question, btw? I'm guessing Javascript? Does the API return JSON?
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1