[algogeeks] Sort the data from a big file.
Hi All, Suppose I have a big file (~100M) containing integer data. I want to sort this file. The problem is I don't want to load the complete file data into main memory in one shot. I mean I can read the file in batches and sort the batch and save it in another file but cannot store the entire file contents in main memory. Can somebody help me with algorithm or pseudo code? Thanks in advance. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sort the data from a big file.
If the numbers are unique you could use a bitmap-sort this way you could easily read just parts of the file at a time. If they aren't unique it gets a bit trickier. /L dinesh bansal wrote: Hi All, Suppose I have a big file (~100M) containing integer data. I want to sort this file. The problem is I don't want to load the complete file data into main memory in one shot. I mean I can read the file in batches and sort the batch and save it in another file but cannot store the entire file contents in main memory. Can somebody help me with algorithm or pseudo code? Thanks in advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sort the data from a big file.
On Mon, Dec 21, 2009 at 6:47 PM, Linus Probert linus.prob...@gmail.comwrote: If the numbers are unique you could use a bitmap-sort this way you could easily read just parts of the file at a time. If they aren't unique it gets a bit trickier. /L dinesh bansal wrote: Hi All, Suppose I have a big file (~100M) containing integer data. I want to sort this file. The problem is I don't want to load the complete file data into main memory in one shot. I mean I can read the file in batches and sort the batch and save it in another file but cannot store the entire file contents in main memory. Can somebody help me with algorithm or pseudo code? Thanks in advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Hi Linus, Thanks for the reply. But yes we cannot guarantee that data value are unique. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sort the data from a big file.
could you describe what kind of data exists . i mean are duplicates allowed? On Mon, Dec 21, 2009 at 6:47 PM, Linus Probert linus.prob...@gmail.comwrote: If the numbers are unique you could use a bitmap-sort this way you could easily read just parts of the file at a time. If they aren't unique it gets a bit trickier. /L dinesh bansal wrote: Hi All, Suppose I have a big file (~100M) containing integer data. I want to sort this file. The problem is I don't want to load the complete file data into main memory in one shot. I mean I can read the file in batches and sort the batch and save it in another file but cannot store the entire file contents in main memory. Can somebody help me with algorithm or pseudo code? Thanks in advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Ram Karthik Reddy Ginuga karthik.ginuga[at]gmail.com CCNA,MCP Mozilla Campus Ambassador SPOJ world rank #1088 http://www.spoj.pl/users/karthu/ (91)40 27425999 (91)9247818845 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sort the data from a big file.
A merge sort would be helpful i guess... it can also happen in parallel and IIRC databases use them internally. Please correct me if im wrong. Regards, Abhilash On Mon, Dec 21, 2009 at 7:06 PM, dinesh bansal bansal...@gmail.com wrote: On Mon, Dec 21, 2009 at 6:47 PM, Linus Probert linus.prob...@gmail.comwrote: If the numbers are unique you could use a bitmap-sort this way you could easily read just parts of the file at a time. If they aren't unique it gets a bit trickier. /L dinesh bansal wrote: Hi All, Suppose I have a big file (~100M) containing integer data. I want to sort this file. The problem is I don't want to load the complete file data into main memory in one shot. I mean I can read the file in batches and sort the batch and save it in another file but cannot store the entire file contents in main memory. Can somebody help me with algorithm or pseudo code? Thanks in advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Hi Linus, Thanks for the reply. But yes we cannot guarantee that data value are unique. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Sort the data from a big file.
This wikipedia article on external sorting may help : http://en.wikipedia.org/wiki/External_sorting On Mon, Dec 21, 2009 at 8:18 PM, Abhilash L L llabhil...@gmail.com wrote: A merge sort would be helpful i guess... it can also happen in parallel and IIRC databases use them internally. Please correct me if im wrong. Regards, Abhilash On Mon, Dec 21, 2009 at 7:06 PM, dinesh bansal bansal...@gmail.comwrote: On Mon, Dec 21, 2009 at 6:47 PM, Linus Probert linus.prob...@gmail.comwrote: If the numbers are unique you could use a bitmap-sort this way you could easily read just parts of the file at a time. If they aren't unique it gets a bit trickier. /L dinesh bansal wrote: Hi All, Suppose I have a big file (~100M) containing integer data. I want to sort this file. The problem is I don't want to load the complete file data into main memory in one shot. I mean I can read the file in batches and sort the batch and save it in another file but cannot store the entire file contents in main memory. Can somebody help me with algorithm or pseudo code? Thanks in advance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Hi Linus, Thanks for the reply. But yes we cannot guarantee that data value are unique. -- Dinesh Bansal The Law of Win says, Let's not do it your way or my way; let's do it the best way. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Siddharth Prakash Singh http://www.spsneo.com -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.