in reply to Re^4: Extract the odd and even columns seperately in the hash of arrays or some other data structure apart from arrays
in thread Extract the odd and even columns seperately in the hash of arrays or some other data structure apart from arrays

I would like to know accordingly to you is their any faster way (in terms of time) of reading the file (1,000,000 rows X 1,000,000) and making the comparison of the rows.

...

...taking more than 10 minutes for the computation of (10,000 rows X 3000 columns)on my 8 GB RAM computer.

I'm sorry, but I really don't think you have any idea of the scale of what you are trying to do.

First off, forget about the time taken to read the file. Perl can read 10,000 lines with 3,000 fields in just a few seconds. What is taking the time, is the combinatorial explosion of comparing each of those lines against each other.

For 10,000 records, that's just under 50 million record-to-record comparisons. If you're doing that in 10 minutes. That's a bit over 80,000 per second.

For 1 million unique records, that's 499,999,500,000 comparisons. Even ignoring that each of those 1 million records contain 333 times as many values to compare, that would still take 5e11/8e4 seconds.

And that's over 72 years!

Factor in that the records are 333 times bigger, and that LCSS is an O(n2) algorithm, and you're looking at many life times to process your data in this brute force fashion.

Unless you have access to some seriously parallel hardware--millions of dollars worth, spawing a few perl threads isn't going to help at this scale--you need to seriously reconsider your approach to solving the underlying problem, because your current approach is never going to work.

Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
"I'd rather go naked than blow up my ass"
  • Comment on Re^5: Extract the odd and even columns seperately in the hash of arrays or some other data structure apart from arrays

Replies are listed 'Best First'.
Re^6: Extract the odd and even columns seperately in the hash of arrays or some other data structure apart from arrays
by snape (Pilgrim) on Jan 27, 2010 at 02:16 UTC
    Ok.. i got ur point. thxs a lot in answering my questions :)
[reply]

      You're welcome :) But you shouldn't just give up.

      Just because your current methods are intractable, it doesn't mean that there isn't a viable approach to solving your underlying quest. It just means that you should look at different approaches to that problem.

      For example, the way you are currently storing your data--as tab-delimited streams of 1s and 2s is hugely wasteful of both storage and processing time. Your described 1e6 x 1e6 dataset file must be something close to 2TB (2e12) bytes of data.

      When you realise that the 1s & 2s can be represented by 0s & 1s, and can therefore be stored binary encoded, the size of your data file could be reduced to something like 116 GB. That's the same information, but less than 6% of the volume of data to read, store and manipulate.

      Or if, as your other thread suggests, that you're looking for positions where there is a minimum overlap of ten datapoints then that is only 1024 possible search strings. So, in a single pass, you could index all your records by the 1024 10-value substrings they contain. That might take 1/2 a day or so.

      Now, with the index, you can limit the number of records you need to search. Assuming a random distribution, that means you've reduced your problem by 3 orders of magnitude. Suddenly, 72 years becomes more like 25 days. Which is a whole heap more tractable!

      Of course, there are no guarantees at this stage that such a reduction is achievable, since we are still in the dark as the the reality of your actual problem. And unless you describe it, you will not be able to gain the benefit of the many clever minds here, considering what other methods might be fruitful.

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.
[reply]

In Section Seekers of Perl Wisdom