laziness, impatience, and hubris PerlMonks

### Comment on

 Need Help??
Fair enough !

"You don't want to use the straight forward linear calculation because it will be too slow, but you don't want to build the obvious tree structure because it takes too much memory? Is there some magical third way?"

A:Correct, and there is some magical third way by doing O(1) checkups in the Spares table. The problem is to reduce ST entries to bits (0,1).

"You've describe the query you need to satisfy as given a range of positions (n,m), where along it lies the minima. How many of those queries do you have to satisfy?

Are they effectively random queries. Ie. random start position and random length?

Or are you calculating one (or a few) length(s) for all start positions?

Or all lengths for all start positions?"

A: All possible queries and all possible lengths!

"You mentioned 300GB. Is that a single huge bit-vector, or many short vectors?"

A:One big and many short vectors due to the reduction that I have described in the earlier post.

So this is a really big string of 0's and 1's and i have no idea what is it for i only know that it is used in string matching and alignment. the thing is, this is a classical LCA problem because you have an ordered structure in the background (that you cannot change because then the whole concept of the algorithm falls apart) and you need to solve it.

solving it means converting it to an array of integers. And if this is done then memory requiremants jump through the roof. The reason why i have tried to simplify things is because when you give an extensive description of the problem people, me being the first, loose interest in messing with it because ,if you are not in the field then there is a bunch of strange stuff going on that needs to be accounted for and then it all comes down to google , Sedgewick, Gusfield, Fischer ..... which is what i am trying to avoid, been there done that and now i'm looking for a person to give an opinion on this particular sub-problem that i feel could do the trick. If not, then back to the drawing board for me:). So I avoided the higher purpose and just focused on the small bit which may not be well explained but i feel it is simple enough to at least receive couple of suggestions (like the ones you guys made ), and this is what i prefer more, and find more informative, then referencing me to a google site.

So thank you and any suggestion comment or even saying that the problem as given cannot be solved is more then welcome!

Cheers

baxy

In reply to Re^4: bit-vector > global minimum by baxy77bax
in thread bit-vector > global minimum by baxy77bax

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":

• Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
• Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
• Read Where should I post X? if you're not absolutely sure you're posting in the right place.
• Please read these before you post! —
• Posts may use any of the Perl Monks Approved HTML tags:
a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
• You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
 For: Use: & & < < > > [ [ ] ]
• Link using PerlMonks shortcuts! What shortcuts can I use for linking?
• See Writeup Formatting Tips and other pages linked from there for more info.
• Log In?
 Username: Password:

What's my password?
Create A New User
Chatterbox?

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (7)
As of 2017-11-23 21:08 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In order to be able to say "I know Perl", you must have:

Results (338 votes). Check out past polls.

Notices?