External sorting in Data structure ppt

external sorting polyphase merge ppt and internal and external sorting ppt
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Your Website URL(Optional)
ECE 250 Algorithms and Data Structures External Sorting Douglas Wilhelm Harder, M.Math. LEL Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada ece.uwaterloo.ca dwharderalumni.uwaterloo.ca © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.External Sorting 2 Outline In this topic we will look at external sorting: – Suppose we are sorting entries stored in secondary memory – What if we can’t load everything into main memory? – Can we sort sections of the unsorted data?External Sorting 3 Situation 8.10 Suppose we are sorting n entries stored in secondary memory (a hard drive or tape drive) than cannot be loaded into main memory – These secondary storages are block addressable – Assume each block is 4 KiB and there are b entries per block – Note, 4 KiB blocks are a common division of both hard drives and of main memory pagesExternal Sorting 4 Naming Convention 8.10.1 Convention: – Lower-case variables will sort the number of entries being sorted • Entries being sorted, entries per block, etc. – Upper-case variables will store the size of larger structuresExternal Sorting 5 Strategy 8.10.2 First, assume we can load M blocks at a time into main memory – Divide the data we are sorting into N sections of M blocks – Each section has m = Mb entries and n = NMb – Here, we are loading the first M = 10 blocks into main memoryExternal Sorting 6 Strategy 8.10.2 On these m = Mb entries, apply an in-place sorting algorithm such as quicksort or merge sort – The run time is Q( m ln(m) )External Sorting 7 Strategy 8.10.2 Write these M sorted blocks back into secondary memoryExternal Sorting 8 Strategy 8.10.2 Repeat this process for all N blocks – The run time is Q( Nm ln(m) ) = Q( n ln(m) ) External Sorting 9 Strategy 8.10.2 Next, load the first block of each of the N sections into corresponding input buffers allocated in main memory – If we had 2 GiB of main memory, we could load 512 such input buffers – We would need to sort more than 1 EiB before this was not possible 31 2GiB 2 19 – The math: 2GiB 2GiB 2GiB 21EiB 12 4KiB 2External Sorting 10 Strategy 8.10.2 Now, perform an N-way merge of these N sorted blocks into a single block-sized output bufferExternal Sorting 11 Strategy 8.10.2 When this output buffer is full, we will write it into secondary memory and start again with an empty buffer – Because we are using merging, we cannot do this in-place on secondary memory—we will require Q(n) additional secondary memoryExternal Sorting 12 Strategy 8.10.2 Whenever one of the N input buffers is entirely merged, we load the next block from the corresponding section into the input bufferExternal Sorting 13 Strategy 8.10.2 We continue this process of storing the merged block into secondary memory and reading subsequent blocks into main memoryExternal Sorting 14 Strategy 8.10.2 We continue this process of storing the merged block into secondary memory and reading subsequent blocks into main memory – At some point we will be merging the last blocks of each of the sectionsExternal Sorting 15 Strategy 8.10.2 When the last block is written out, the collection of MN blocks now contain a sorted list of the initial n entriesExternal Sorting 16 Run-time Analysis 8.10.3 With merge sort, we saw that merging was an Q(n + n ) operation 1 2 when merging lists of size n and n 1 2 – From slide 8, this suggests the run time is Q( n ln(m) ) – If m is sufficiently small, this suggests the run-time is Q(n) External Sorting 17 Run-time Analysis 8.10.3 This, however, is a mathematical fallacy… – A binary merge can be performed in linear time, an N-way merge cannot – The best we can hope for is using a binary min-heap • Each will require O(ln(N)) time for a total of Q( n ln(N) ) Thus, the total run time is Q( n ln(m) + n ln(N) ) = Q( n ln(mN) ) = Q( n ln(n) ) Recall that n = mNExternal Sorting 18 Run-time Analysis 8.10.3 To be complete, we should also consider the run time associated with loading and saving data to the disk: – Each item of data is copied from or to the external disk four times – We will assume the memory size of each item is fixed and reasonable – Thus, the run time of these operations is Q(n) – If we are considering the size of the objects to be variable, say k bytes, we would have to revise our run time to Q( n ln(n) + nk )External Sorting 19 Additional Remarks 8.10.4 With 4 KiB blocks and 2 GiB of available main memory, we determined we could sort up to 1 EiB of data What if our available memory was smaller, say 1 MiB? 20 1MiB 2 8 1MiB1MiB1MiB 2 256MiB 12 4KiB 2 Solution? – Divide the data into 256 MiB blocks – Sort each of these individually use external sorting – Now merge these using the same strategy • We are restricted by the number of blocks we can merge – This process can be repeated arbitrarily often—doing so K times allows K K us to sort 20   1MiB 2 8K 1MiB1MiB 2 MiB   12 4KiB 2  External Sorting 20 Additional Remarks 8.10.4 We have focused on one implementation of using block-sized buffers—optimizations, however, are always possible: – Performing the initial sorting (quick sort) in parallel – Storing at least a portion of the data in solid-state drives – Using larger input and output buffers (useful if the data is contiguous on the hard drive)