X-Original-To: pgsql-sql-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by svr1.postgresql.org (Postfix) with ESMTP id CE6A1DA1A9 for ; Wed, 19 Oct 2005 07:43:05 -0300 (ADT) Received: from svr1.postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 19829-07 for ; Wed, 19 Oct 2005 10:43:00 +0000 (GMT) Received: from tomts22-srv.bellnexxia.net (tomts22.bellnexxia.net [209.226.175.184]) by svr1.postgresql.org (Postfix) with ESMTP id BCC78DA1A1 for ; Wed, 19 Oct 2005 07:43:01 -0300 (ADT) Received: from acer.sympatico.ca ([65.95.165.161]) by tomts22-srv.bellnexxia.net (InterMail vM.5.01.06.10 201-253-122-130-110-20040306) with ESMTP id <20051019104303.QPQU21470.tomts22-srv.bellnexxia.net@acer.sympatico.ca> for ; Wed, 19 Oct 2005 06:43:03 -0400 Message-Id: <5.2.1.1.0.20051019054006.0455bec0@pop6.sympatico.ca> X-Sender: b1wudu74@pop6.sympatico.ca X-Mailer: QUALCOMM Windows Eudora Version 5.2.1 Date: Wed, 19 Oct 2005 06:42:33 -0400 To: pgsql-sql@postgresql.org From: Frank Bax Subject: Re: SEVEN cross joins?!?!? In-Reply-To: <434E5B44.7080204@brandywine.com> References: <5.2.1.1.0.20051012211223.00a34dd0@pop6.sympatico.ca> <434CE6B8.5060106@archonet.com> <5.2.1.1.0.20051011071510.0364d850@pop6.sympatico.ca> <5.2.1.1.0.20051011071510.0364d850@pop6.sympatico.ca> <5.2.1.1.0.20051011145705.00a31440@pop6.sympatico.ca> <434CE6B8.5060106@archonet.com> <5.2.1.1.0.20051012211223.00a34dd0@pop6.sympatico.ca> Mime-Version: 1.0 Content-Type: text/plain; charset="us-ascii"; format=flowed X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, hits=0.536 required=5 tests=[AWL=-0.371, FORGED_RCVD_HELO=0.05, MANY_EXCLAMATIONS=0, PLING_QUERY=0.857] X-Spam-Level: X-Archive-Number: 200510/218 X-Sequence-Number: 23071 At 09:04 AM 10/13/05, Daryl Richter wrote: >Frank Bax wrote: > >[snip] > >>Richard, you've summed it up nicely. >>Splitting locations into subsets (like 2,2,3) doesn't work because it is >>possible that low values in one location can be offset by high values in >>another location, and still result in an excellent combo. >>The good news is these suggestions got me thinking outside the box. I >>think I can program a modified brute-force that bypasses large numbers of >>combos early. It might still be too large/slow, so I'd be interested in >>finding more info about these "smarter algorithms" in option 2. >>Where do I look? > >If you're mathematically inclined, I would first look at using >Lagrangian Relexation, it may be appropriate for your problem: > >http://www.2112fx.com/lagrange.html Thanks, but that's a little too complex for me to turn into code! I did rewrite my code from a simple cross join SQL in PHP to custom searching in perl. I sucked subselects into arrays and then looked at all possible combinations. For those that forgot/missed the background, my table has 514 rows. Using subselect, this table is split into 7 subtables. These seven subtables are cross joined with each other to produce 770 billion rows that need to be searched (to assemble a 'made-to-order' suit of armour). By using more intelligent code (and not simple brute-force), I was able to analyse a complete set of 770 billion states in just under 70 hours on a P4-2.8Ghz system, which is fast enough for today. A faster cpu will help, since process does no i/o except at beginning and end of script. I realised that if I am ever able to figure out coding for multi-processor or systems (even remote like set@home), I can exploit either/both of these for this problem by slitting problem on items in first subtable into 50-60 subtasks, then merging results from each of those subtasks. This might become a requirement if the underlying table grows to be quite large. Thanks for pointing me in the right direction, it's been an interesting week. Frank