[gameprogrammer] Re: Let's play... Name That Algorithm! :)
- From: Bob Pendleton <bob@xxxxxxxxxxxxx>
- To: gameprogrammer@xxxxxxxxxxxxx
- Date: Sat, 29 Aug 2009 10:44:11 -0500
Very nice. If I read that correctly you dropped your execution time
from 3.6 hours to 4 to 8 seconds by using memoization. Is that
correct? Sounds like what what passes for thinking in you world is
pretty high grade stuff.
I'm going to get a bit philosophical here for a minute. Recently I've
been doing some work on atomic operations and find most of the
literature that applies is from the middle 1960s through the middle
1970s. Atomic ops started showing up in products around 1964. The word
memoization was first used in 1968 to describe a concept that was
already being used at that time.
Computing has been studied seriously for less that 100 years. There is
still a lot to learn. But, a lot has already been solved. There is a
huge amount of knowledge trapped in the old papers and books from the
1940s on. If you want to learn about a subject go look at when it was
being invented or when it was the normal state of existence.
Minimizing memory use was the norm in the '60s because memory cost a
minimum of one US cent per bit. (Due to inflation a it would take 7 US
cents to equal the value of 1 cent in 1964.) OTOH, last month of
bought 4 Gigabytes at a cost of 0.000000001455 US cents per bit. If I
had had to pay 7 cents per bit that memory would have cost
$2,405,181,685.76. (IIRC MIT had a patent on magnetic core memory and
charged a royalty of 1 cent per bit for manufacturing that kind of
memory.)
Parallel processing was becoming common in the middle 1960s and a lot
of work was being done on how to solve synchronization problems that
result from them. By the middle 1960s atomic operations were showing
up in hardware an all sorts of papers were being published on how to
make the best use of them.
You owe yourself the favor of reading books on the history of computing.
Bob Pendleton
On Sat, Aug 29, 2009 at 5:57 AM, Mike Gillissie<Niyoto@xxxxxxxxxx> wrote:
> Hey folks,
>
> Just an unsolicited follow-up - after trying a lot of different approaches,
> I ended up sticking with the recursive model I had already, but worked in
> Bob's momoization concept.
>
> Warning - I might go a little long on this one, so read only if you're
> curious, bored, masochistic or find humour in the way I attempt to explain
> what passes for "thinking" in my world. ;)
>
> My main concern - even with mid-range input quantities (say, 3000 units) my
> function executes at least 10s of billions of times (I never bothered going
> long int to get an actual count). This means that everything I do in this
> function can have a drastic effect on performance - even using
> non-synchronized collections costs too many cycles.
>
> So, as my way of caching results, I perform a pre-check on the adjacency
> table, determining which rows of bools are subsets of others (or are
> identical, meaning they're compatible with the same sets of other units).
> Essentialy I determine which unit compatibility sets are subsets of others,
> and store this information in an array - unit index, subset-of index, delta
> (number of values that are different) and dependancy.
>
> Quick note - in the following example, 1 represents an incompatibility. Thus
> 0 represents compatibility.
>
> 1)01110 (incompatible with 2, 3, 4)
> 2)10011 (incompatible with 1, 4, 5)
> 3)10001 etc...
> 4)11001
> 5)01110
>
> In the above, I find that 1 and 5 are equal, and 3 is a subset of 4 with a
> delta of 1 (representing unit 2 which is compatible with 4 but not with 3).
>
> Since 1 and 5 are identical, I need only calculate for Unit 1. I can then
> take all of the resulting combinations for Unit 1 and replace the 1 with a
> 5.
>
> Since 3 is a subset of 4, I calculate for Unit 3 first (which has LESS
> incompatibilities than Unit 4), and then simply perform the same "search and
> replace" to create the combinations for Unit 4, only I exclude any that
> contain the "Delta" element (in this case, Unit 2).
>
> The same subset approach would be done to calculate Unit 2, since Unit 3 is
> also a subset of 2.
>
> As Bob suggests, the success of this approach depends strongly on the make
> up of the data itself - there are always going to be situations where you
> just don't have enough subsets to justify the overhead of searching for
> them. But in the data set I'm currently working on, my execution time (which
> had previously gone from 3.6 hours to just over 1 hour) dropped to 4-8
> seconds. And this can surely be fine-tuned further.
>
> A further look at the problem told me that, while some compatibility sets
> will just not have any subsets to exploit, I could always measure the
> Similarity between two sets. In the above, Unit 1 and Unit 2 have a
> similarity of 1 (representing their shared compatibility with Unit 4). So if
> I was to create a "virtual" compatibility set containing Unit 4, it would
> become a subset of both Unit 1 and Unit 2, meaning I would only have to
> recursively calculate that combination once, and then use the above-approach
> for both Units 1 and 2. The challenge here is in finding the optimal
> grouping that minimizes the number of recursive calls without overpaying in
> overhead cycles.
>
> It's definitely an interesting problem for me... :)
> -Mike
>
> ----- Original Message ----- From: "Bob Pendleton" <bob@xxxxxxxxxxxxx>
> To: <gameprogrammer@xxxxxxxxxxxxx>
> Sent: Tuesday, August 18, 2009 10:59 AM
> Subject: [gameprogrammer] Re: Let's play... Name That Algorithm! :)
>
>
>> On Tue, Aug 18, 2009 at 9:45 AM, Mike Gillissie<Niyoto@xxxxxxxxxx> wrote:
>>>
>>> Hi Bob!
>>>
>>> Your note on memoization looks very interesting, especially considering
>>> the
>>> approach I'm currently using. I just need to identify which problems are
>>> being repeated - something keeps flashing in my mind as I think of this,
>>> so
>>> I need to get back to pencil and paper and work my way through this.
>>>
>>> My main concern with caching results, though, is that size of the entire
>>> resultset can be astounding - it might not be feasible to add search and
>>> storage to the approach...
>>
>> Yep, it is a classic space/speed trade off. And, yes, the space needed
>> can become huge. OTOH, if you only cache a small percentage of the
>> cases you can still get a significant speed up. I've tried to use it
>> many times. Some times the results are wonderful, other times it was a
>> total failure because there were so many results.
>>
>>
>> Bob Pendleton
>>
>>>
>>> -Mike
>>>
>>> ----- Original Message ----- From: "Bob Pendleton" <bob@xxxxxxxxxxxxx>
>>> To: <gameprogrammer@xxxxxxxxxxxxx>
>>> Sent: Tuesday, August 18, 2009 9:15 AM
>>> Subject: [gameprogrammer] Re: Let's play... Name That Algorithm! :)
>>>
>>>
>>> Yeah, this is the right solution. The problem is called finding the
>>> transitive closure on a set.
>>>
>>> I don't know if it applies in this case, but in a lot of problems like
>>> this you find your self solving the same sub problem over and over.
>>> That means you can save a lot of time by remembering the solutions to
>>> previously solved problems. This is called memoization
>>> (http://en.wikipedia.org/wiki/Memoization). For example, if you are
>>> about to add "b" to the processing list, first look up "b" and see if
>>> you have already come up with its compatibility list, if so, add the
>>> whole results. That way you avoid resolving the problem for "b". This
>>> technique works really well for recursive solutions to problems
>>> because each recursive call can just check its arguments to see if
>>> that combination has already been solved and each function call can
>>> add its arguments and the final value for that call to the set of
>>> remembered solutions.
>>>
>>> Bob Pendleton
>>>
>>> On Mon, Aug 17, 2009 at 10:41 PM, Kevin
>>> Jenkins<gameprogrammer@xxxxxxxxxx> wrote:
>>>>
>>>> This is equivalent to determining if a set of vertices is connected by
>>>> edges, while adding additional vertices to check, and also checking if
>>>> the
>>>> vertice is connected to itself. The most efficient way to do so is add
>>>> single vertices at a time, and compare the new vertice to the existing
>>>> ones.
>>>>
>>>> Then returning the combination set of the maximum fully connected
>>>> graphs.
>>>>
>>>> 1. Add all vertices (in your case, indices) to a processing list.
>>>> 2. Pop the first vertex from the processing list.
>>>> 3. For each additional vertex, if that vertex connects to all vertices
>>>> in
>>>> the working list, add it to the working list. Else add it to a
>>>> next-round
>>>> processing list.
>>>> 4. Add the working list to the completed list (list of lists)
>>>> 5. Swap the processing and next-round processing list.
>>>> 6. Goto 2
>>>>
>>>> So now you have the set of maximum sized fully connected meshes. Since
>>>> you
>>>> appear to also want the combination set, just do a combination set
>>>> process
>>>> on the completed list. For example, 0,1,2 would return 0-1, 0-2, 1-2.
>>>> This
>>>> is different from your example output, which I believe is incorrect.
>>>>
>>>> Mike Gillissie wrote:
>>>>>
>>>>> I did just an excellent job of not completing my first attempt at an
>>>>> email
>>>>> - hopefully my second attempt came though to completion... ;)
>>>>> The Karnaugh Map thingie looks pretty interesting, though admittedly
>>>>> I'm
>>>>> going to have to take a closer look at its scalability to 5000-ish
>>>>> values
>>>>> (squared-ish)... thanks for sharing! :)
>>>>> My ultimate goal is to determine all combinations of mutually
>>>>> compatible
>>>>> units based on the truth table.
>>>>> From Vince's example,
>>>>> 0 1 2 3
>>>>> 0 [1, 1, 0, 1]
>>>>> 1 [1, 1, 1, 1]
>>>>> 2 [0, 1, 1, 0]
>>>>> 3 [1, 1, 0, 1]
>>>>> In this case, starting with element 0, I'm currently building a tree
>>>>> using a recursive function. I see that 0 and 1 are compatible - I
>>>>> recurse
>>>>> down one level and see if 0-1 is compatible with 3 (the next compatible
>>>>> element to 0) - since all three are mutually compatible (0-1, 0-3 and
>>>>> 1-3)
>>>>> my first "stored" combination is 0-1-3.
>>>>> From 1, I look at 1-2. I recurse down to see if 1-2-3 is compatible - I
>>>>> find that it's not since 2-3 are not compatible. So I end up storing
>>>>> the
>>>>> combinations 1-2 and 1-3.
>>>>> Finally, since 2-3 is not compatible, I end up storing 2 and 3 as
>>>>> separate "combinations" (albeit combinations of 1 element).
>>>>> My final set from the Vince-List:
>>>>> 0-1-3
>>>>> 1-2
>>>>> 1-3
>>>>> 2
>>>>> 3
>>>>> My code actually eliminates the "south-west" portion of the matrix,
>>>>> since
>>>>> I will only compare against higher-value indexes from my starting
>>>>> point.
>>>>> Well said, Mike... yeesh... ;)
>>>>> 0 1 2 3
>>>>> 0 [*, 1, 0, 1]
>>>>> 1 [*, *, 1, 1]
>>>>> 2 [*, *, *, 0]
>>>>> 3 [*, *, *, *]
>>>>> While slightly complicating my indexing, it more than doubles my
>>>>> capacity.
>>>>> Looking at this, even considering a 5000x5000 truth table (stored as a
>>>>> 4999+4998+4997...3+2+1 one-dimensional array), it just looks like
>>>>> something
>>>>> that a more experienced algorithmagician must have solved nicely in the
>>>>> past... ;)
>>>>> My apologies for the half-email that I started this with - Outlook
>>>>> Express
>>>>> probably does a send when you hit some combination of
>>>>> Control/Shift/Enter,
>>>>> or if you're trying to impress your betters... =/
>>>>> Thanks guys! :)
>>>>> -Mike
>>>>>
>>>>> ----- Original Message -----
>>>>> *From:* Alan Wolfe <mailto:alan.wolfe@xxxxxxxxx>
>>>>> *To:* gameprogrammer@xxxxxxxxxxxxx
>>>>> <mailto:gameprogrammer@xxxxxxxxxxxxx>
>>>>> *Sent:* Monday, August 17, 2009 8:24 PM
>>>>> *Subject:* [gameprogrammer] Re: Let's play... Name That Algorithm! :)
>>>>>
>>>>> I'm not sure 100% what you are trying to achieve but Karnaugh maps
>>>>> might help you
>>>>> http://en.wikipedia.org/wiki/Karnaugh_map
>>>>> they let you take an array of bools and simplify it into groups.
>>>>> They are used on 2d arrays mostly to take boolean output and try
>>>>> to come up with the simplified boolean equation to make that
>>>>> output, but i think they could work for what you want too, and
>>>>> they deffinately work on both 1d and 3d arrays (and higher) as well :P
>>>>> On Mon, Aug 17, 2009 at 5:13 PM, Vince <uberneen@xxxxxxxxx
>>>>> <mailto:uberneen@xxxxxxxxx>> wrote:
>>>>>
>>>>>
>>>>>
>>>>> --- On Mon, 8/17/09, Mike Gillissie <Niyoto@xxxxxxxxxx> wrote:
>>>>>
>>>>> > From: Mike Gillissie <Niyoto@xxxxxxxxxx>
>>>>> > Subject: [gameprogrammer] Let's play... Name That Algorithm! :)
>>>>> > To: gameprogrammer@xxxxxxxxxxxxx
>>>>> <mailto:gameprogrammer@xxxxxxxxxxxxx>
>>>>> > Date: Monday, August 17, 2009, 11:57 PM
>>>>> >
>>>>> >
>>>>> >
>>>>> >
>>>>> >
>>>>> >
>>>>> >
>>>>> > Hi folks!
>>>>> > > I'm in the middle of a
>>>>> > situation - I have a problem
>>>>> > I'm trying to solve, and it looks like the sort of
>>>>> > problem that has a very nice
>>>>> > algorithm named after some fine studious person. Here's
>>>>> > the skinny:
>>>>> > > At this point in my code I
>>>>> > have a square boolean
>>>>> > array that's used to indicate
>>>>> > "compatibilities" - so if I have 5 units and I
>>>>> > calculate each one's compatibility with each other unit
>>>>> > (as either a Yes or a
>>>>> > No), I might have values something like:
>>>>> > > compat[0][1]=true;
>>>>> >
>>>>> > compat[0][1]=true;
>>>>> >
>>>>> > compat[0][1]=true;
>>>>> >
>>>>> > compat[0][1]=true;
>>>>> >
>>>>> >
>>>>>
>>>>> I'm looking three redundant statements here.
>>>>> If I'm reading your description correctly, compat might look
>>>>> more like this: (adjust 0, 1 for true, false if you please)
>>>>> 0 1 2 3
>>>>> 0 [1, 1, 0, 1]
>>>>> 1 [1, 1, 1, 1]
>>>>> 2 [0, 1, 1, 0]
>>>>> 3 [1, 1, 0, 1]
>>>>>
>>>>> If you're testing to see if something along X is compatible
>>>>> with something along Y, you could
>>>>> #define OPTION1 0
>>>>> #define OPTION2 1
>>>>> and so on, then you could check with any pair like so :
>>>>> iscompat = compat[OPTION1][OPTION2]
>>>>>
>>>>> Is that what you're after?
>>>>>
>>>>> Vince~
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> ---------------------
>>>>> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>>>>>
>>>>>
>>>>>
>>>>
>>>> ---------------------
>>>> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>>>>
>>>>
>>>>
>>>
>>>
>>>
>>> --
>>> +-----------------------------------------------------------
>>> + Bob Pendleton: writer and programmer
>>> + email: Bob@xxxxxxxxxxxxx
>>> + web: www.TheGrumpyProgrammer.com
>>>
>>> ---------------------
>>> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>>>
>>>
>>>
>>>
>>>
>>> ---------------------
>>> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>>>
>>>
>>>
>>
>>
>>
>> --
>> +-----------------------------------------------------------
>> + Bob Pendleton: writer and programmer
>> + email: Bob@xxxxxxxxxxxxx
>> + web: www.TheGrumpyProgrammer.com
>>
>> ---------------------
>> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>>
>>
>>
>
>
>
> ---------------------
> To unsubscribe go to http://gameprogrammer.com/mailinglist.html
>
>
>
--
+-----------------------------------------------------------
+ Bob Pendleton: writer and programmer
+ email: Bob@xxxxxxxxxxxxx
+ web: www.TheGrumpyProgrammer.com
---------------------
To unsubscribe go to http://gameprogrammer.com/mailinglist.html
Other related posts:
