Talk:Matrix chain multiplication

From Wikipedia, the free encyclopedia

[edit] cost of string concatenation

I think it's not justified to say that string concat is O(n+m), one has to distinguish

  • the search for the end token (in O(n), but only READ), and
  • the creation of the new string (requiring
  • memory allocation (which might be more expensive than all the rest, depending on implementation (default MEM_CLEAR or so))
  • COPYING of the first and then the second string (READ + WRITE in another memory segment, O(n+m) operations)

On the other hand, if one uses reference counting and allows for segmented string storage, then the concatenation takes virtually no time.

Concerning "memoization", why the heck did this guy not call it memorization ??? (Or memo'ization ?)

And finally, I would be astonished if there was no better ("local") method for optimizing this matrix problem, rather than checking all possible combinations... I'll think about this... MFH 13:43, 24 Mar 2005 (UTC)

Greedy algorithms don't work well for this problem, because locally optimal solutions may turn out to force a globally poor solution — not that there aren't decent approximation algorithms based on heuristics. If you click on the memoization link, you'll discover that this is not a misspelling, like everyone always assumes (I wish they'd pick a less confusing word). You're right that different approaches to string concatenation take very different amounts of time. This is mostly irrelevent, since the technique works with any cost function, but the specific cost I give is for a C strcat() call without any reallocation (it's assumed sufficient space is available after the first string). Deco 23:15, 24 Mar 2005 (UTC)

[edit] Ambiguity due to using variable 'l'

I had a hard time understanding the pseudocode because of the variable 'l', which is defined in the outer-most main loop. The statements "n-l+1" and "i+l-1" appeared to me as "n-1+1" and "i+1-1". (I could not distinguish the 'l' variable from the '1'. In anti-aliased Courier New font, the difference was very small for my eye to see.)

I first thought that these statements may be intended by the writer to indicate that 1 was removed for some reason and added for a different reason (as when a loop is said to run (n-1)+1 times). I then couldn't figure out the reasons, and it took me quite some time to understand that it is an 'l'. (Actually I was already writing in the discussion page to ask how the algorithm could be like that - it would be definitely wrong.)

I wish you could take this into consideration (in this and other articles), and use a variable other than 'l'. In this specific algorithm, the name "len" may be good.

Thanks. --Hosam Aly 19:39, 7 January 2007 (UTC)