4 replies to this topic

[prasenjitnandy]

i want to write one programme that finds the longest increasing sequence from a file that contains huge amount of integer values..i have made one program that does it for me..but the programme takes near about 78 mb!!!!!
its too much high.i have copied all the contents of file to an array.and after that have used ologn algorithm to find the highest sequence..now the problem is with memory..anybody please suggest me that is there any way by which i can optimise my programme memory:confused:
thanks in advance

[WingedPanther]

I would NOT load the entire file into memory. That guarantees you need at least enough memory to hold the entire file. I would process it as you go, only keeping track of the current longest sequence, and perhaps where you found it.

[fayyazlodhi]

I guess i know what is your bottleneck.

You must be using the standard most efficient Dynamic programming solution

Longest increasing subsequence - Wikipedia, the free encyclopedia

which runs in nlogn. You have to read the entire file contents into array because you cannot access the file randomly. You need to access file randomly because the nlogn algorithm uses binary search in the end.

Instead, use the n^2 algorithm. This will not require you to have random access and you can only keep a subset of file in memory at any given point.

I did not go very deep to assess this. If you have problems, let me know. I might be able to help you out if stuck some where.

[haltox]

Isn't the file allocated to the heap when loaded? If that were the case, how could it affect the executable size?

[prasenjitnandy]

ya..actually i wanted to mean that the file takes this much of memory on execution..i want to
reduce it

---------- Post added at 07:16 PM ---------- Previous post was at 07:07 PM ----------

firstly thanks to everybody..@fayyazlodhi yaa you are correct..im not understanding the method n^2..can you please provide me any link..