Problems? Is your data what you think it is? | |
PerlMonks |
Re^3: Bidirectional lookup algorithm? (Solution.)by BrowserUk (Patriarch) |
on Jan 24, 2015 at 13:15 UTC ( [id://1114361]=note: print w/replies, xml ) | Need Help?? |
bitingduck thankyou for your research. The links provided for fascinating, (if at times somewhat bewildering :) reading. In particular the Schnell article made the CHM algorithm understandable; and the pyDAWG code is relatively concise and understandable. I think I understand the process (if not the implementation) enough to see a problem (for my application). Given that my datasets are generated at runtime, and the goal is to be able to make them as large as available memory will allow (but no larger), it would be necessary to run the CHM algorithm within the same process, and after the dataset has been generated. The problem is, that even using the most parsimonious implementation of a DAG, the combined size of the node and edge structures (with their required pointers) require substantially more memory per string-number pair than the data itself. Using the pyDAWG implementation as an example; each pairing requires two DAWGNodes at 18bytes each; and each word required one DAWGEdge struct per letter (say ave. 5*9 + 8*9 = 117bytes ). Thus a quick estimate is that for each 13 bytes of data (5-byte string + 8-byte integer); the algorithm would require a minimum of 117+38 = 155 bytes of structs * no_of_pairs, in order to build the DAG. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday'
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".
I'm with torvalds on this
In the absence of evidence, opinion is indistinguishable from prejudice. Agile (and TDD) debunked
In Section
Seekers of Perl Wisdom
|
|