Algorithm Complexity Reduction

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Prelates, Moderators General

Algorithm Complexity Reduction

Postby naschilling » Mon Sep 26, 2011 7:50 pm UTC

I built a simple script to perform some search/optimization for me, and I'm wondering there is a way to reduce it's runtime and complexity significantly. Here's the problem.

There are P products {p0, p1, p2, p3,... p(P-1)}.
There are N planets {n0, n1, n2, n3, ... n(N-1)}.
The cost of each product, and if it can be traded on that planet, C(n, p) is different on each planet. (If C(n, p)==0 then p cannot be bought or sold)
The cost of each product is deterministic (C(n, p) never changes for a given combination of n and p), but there is no pattern to availability or cost.
A product sells for 10% less than the purchase price.
The algorithm musst be deterministic. (No probabilistic methods.)

My solution:
Code: Select all
for (i=0; i<P; i++) { //Source Planet
    for (j=0; j<P; j++) { //Destination Planet
        maxValue = 0;
        maxProduct = -1;
        for (k=0; k<N; k++) { //Product to carry
            if ((C(i, k)>0) && (C(j, k) > C(i, k)) { //Ensure both planets deal in product
                tradeValue = (.9 * C(j, k)) - C(i, k);
                if (tradeValue > maxValue) {
                    maxValue = tradeValue;
                    maxProduct = k;
                }
            }
        }//Next k
        /* Do something with per-path result */
    }//Next j
}//Next i

This function yields correct results (assuming no typos), but has a runtime of O(PN^2). Can better be done?
If you don't have walls, why would you need Windows?
User avatar
naschilling
 
Posts: 142
Joined: Wed Apr 06, 2011 2:52 pm UTC

Re: Algorithm Complexity Reduction

Postby jaap » Mon Sep 26, 2011 8:36 pm UTC

You should be able to do it O(NP).

Each product (and its pattern of cost) is independent of the P-1 other products. So you can see this problem as being P independent problems, where each problem consists of finding the planets with the highest and lowest price for that product.
Finding the best/worst price for a product is order N - you just go through all the planets once and keep track of the best/worst price found so far.
You have to do this P times, once for each product, keeping track of the best product found so far.

Edit to add: Obviously it cannot be done faster than O(NP), since there are N*P costs that have to be looked at.

(Edited to swap most P's and N's)
Last edited by jaap on Tue Sep 27, 2011 6:20 pm UTC, edited 2 times in total.
User avatar
jaap
 
Posts: 1789
Joined: Fri Jul 06, 2007 7:06 am UTC

Re: Algorithm Complexity Reduction

Postby Yakk » Tue Sep 27, 2011 3:50 pm UTC

The first problem is that the only description of what is optimized is in the source code.

And while jaap does solve a reasonable optimization problem given the data (for each product, who is the cheapest seller and highest price buyer), it isn't the same one as the source code solves (for each pair of planets, what is the most profitable trade good).

I don't see an obvious way to extend jaap's solution to the solution to the posted problem. Then again, a less "here is code" description to what the OP is trying to optimize might mean that jaap's solution is optimal!
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10324
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Algorithm Complexity Reduction

Postby jaap » Tue Sep 27, 2011 4:16 pm UTC

Yakk wrote:The first problem is that the only description of what is optimized is in the source code.

And while jaap does solve a reasonable optimization problem given the data (for each product, who is the cheapest seller and highest price buyer), it isn't the same one as the source code solves (for each pair of planets, what is the most profitable trade good).

I don't see an obvious way to extend jaap's solution to the solution to the posted problem. Then again, a less "here is code" description to what the OP is trying to optimize might mean that jaap's solution is optimal!


You're right, I may have misread the problem. I was trying to find the most profitable product overall, rather than for each pair of planets.
User avatar
jaap
 
Posts: 1789
Joined: Fri Jul 06, 2007 7:06 am UTC

Re: Algorithm Complexity Reduction

Postby Yakk » Tue Sep 27, 2011 5:44 pm UTC

So, for each pair of planets, we want to find the least/greatest element of the difference between their production/consumption arrays.

And we want to do this without subracting one production array from the other.

This is a "for each pair of planets" problem, so you have a required P^2 (because that is the length of the output). So (almost) anything you do on a per-planet basis is going to be cheap (barring an N^2 factor).

A naive improvement is to sort the production/consumption pairs by their value, then start building up the differences using the most/least expensive subsets. Ie, if the most expensive product on planet 1 is the cheapest on planet 2, then that is guaranteed to be the ideal pairing regardless of other product prices. This, however, sort of requires that you get lucky. (if we assume random price distributions, can we show that we get lucky usually in some sense? The cost to this is sorting is probably a lg(n) factor in the worst case, which isn't that bad -- if an "average" case performance goes up that is).
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10324
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Algorithm Complexity Reduction

Postby naschilling » Tue Sep 27, 2011 5:57 pm UTC

My apologies if my OP was unclear. I suspected there may not be any better mechanism because the output is N^2 values, but I considered that there might have been a mechanism using vectors that wasn't apparent to me. It's always nice to get extra eyes on the problem.
If you don't have walls, why would you need Windows?
User avatar
naschilling
 
Posts: 142
Joined: Wed Apr 06, 2011 2:52 pm UTC

Re: Algorithm Complexity Reduction

Postby jaap » Tue Sep 27, 2011 7:30 pm UTC

By the way, the code in the OP used N and P the opposite from the text. I edited my previous post to assume there are P products and N planets.
I don't see any way either of improving on O( P N2 ) for the worst case, but I suspect that Yakk is right that it might be possible to reduce the average runtime if you sort things.
User avatar
jaap
 
Posts: 1789
Joined: Fri Jul 06, 2007 7:06 am UTC

Re: Algorithm Complexity Reduction

Postby naschilling » Tue Sep 27, 2011 10:33 pm UTC

The problem with the sort idea is that not all products cost the same order of magnitude. The most profitable item may go from $90,000 -> $110,000 on one route and may be $6 -> $7,000 on another.

Just for the purpose of discussion, I actually built this as a Google Doc Spreadsheet. The problem comes from an old BBS game, Planets: The Exploration of Space (TEOS). I've been playing it lately on Convolution.us. My original implementation of this problem took so long to run that Google Docs aborted the script as hung. (Take THAT Halting Problem!) It then occurred to me that using getValue() and setValue() was the expensive operations and I was calling it O(PN^2) times. A few revisions later, I now have the run time down to 3 seconds. Not too bad for N=26 and P=19, but I'd love to reduce the run time down to under .5 seconds. I suspect to achieve that would require reducing the big-O complexity, or using C.
If you don't have walls, why would you need Windows?
User avatar
naschilling
 
Posts: 142
Joined: Wed Apr 06, 2011 2:52 pm UTC

Re: Algorithm Complexity Reduction

Postby mfb » Fri Sep 30, 2011 3:06 pm UTC

PN^2 = 12844.
While it may be possible to increase the average time, N and P are too small to implement really tricky stuff of O(N^2) or O(PN).

Sorting things in O(NP*log(P)) may help (for example, you can drop all products if their sell value is smaller than the current maxValue, begin with the highest sell values), pre-calculating 0.9*C(j, k) can save a bit (so you just calculate it PN times instead of PN^2).
But I don't know why the code needs 3 seconds to execute.
mfb
 
Posts: 827
Joined: Thu Jan 08, 2009 7:48 pm UTC

Re: Algorithm Complexity Reduction

Postby Yakk » Fri Sep 30, 2011 3:10 pm UTC

By the way, why do you want to know the best product to trade at each pairwise set of planets?

I'd think that the best product to buy and sell in the galaxy would be more useful. And that, as noted, faster to calculate.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10324
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Algorithm Complexity Reduction

Postby naschilling » Sat Oct 01, 2011 1:23 pm UTC

Every day, a randomly determined flight path is generated for each player. At any time, the player may travel from any one planet to any other. It is possible to ignore your flight path and travel to a destination that you choose, but the cost is 2x more. In order to know if the base flight path is worth taking, you have to know how much profit can be made or if a different destination is worth more by at least double.

You guys should join in on http://convolution.us
If you don't have walls, why would you need Windows?
User avatar
naschilling
 
Posts: 142
Joined: Wed Apr 06, 2011 2:52 pm UTC

Re: Algorithm Complexity Reduction

Postby Yakk » Sat Oct 01, 2011 4:27 pm UTC

So, that is a different problem completely. Solving for all pairs of planets is pointless?

You first want to calculate the profit of this flight path (including subtracting the cost).

Then, you want to find the most globally profitable flight path (including subtracting double the cost).

How is cost a function of flight path? That could make things messy.

"worth more by at least double" -- given that profits are (income - expenses), how does that help when you said "costs are double"? Doubling costs and halving profits are completely different things.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.
User avatar
Yakk
Poster with most posts but no title.
 
Posts: 10324
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

Re: Algorithm Complexity Reduction

Postby mfb » Sat Oct 01, 2011 10:07 pm UTC

naschilling wrote:It is possible to ignore your flight path and travel to a destination that you choose, but the cost is 2x more.

So just the destination can be changed? That reduces the complexity to O(PN) and there is no way to reduce it further as you have to check every price once. Or do you want some prediction for the next cycle?
mfb
 
Posts: 827
Joined: Thu Jan 08, 2009 7:48 pm UTC


Return to Computer Science

Who is online

Users browsing this forum: No registered users and 4 guests