Обсуждение: Re[2]: [HACKERS] \dt and disk access
How about using a heap sort? Works in order of magnitude better on almost-sorted data than the quick sort. I have the code if anyone is interested. (C++, though.) Leo _______________________________________________________________________________ Subject: Re: [HACKERS] \dt and disk access From: <maillist%candle.pha.pa.us@interlockp.lubrizol.com> at LZ-INTERNET Date: 6/23/97 10:16 PM > >From what I remember, the quick sort algorithm works just as fast on > sorted data as on unsorted data. In other words, the algorithm does not > take advantage of the fact that the data is sorted. > > On the other hand, if you go to something like bubble sort, it will > work faster than quick sort if the data is sorted and you are adding one > more item, but on unsorted data it takes an enormously longer length of > time to sort a large list. > One thing I am going to look into is replacing the btree-build in the current psort with a qsort of HeapTuple pointers. - -- Bruce Momjian maillist@candle.pha.pa.us ------------------------------
I don't believe the data is almost-sorted. > > > How about using a heap sort? Works in order of magnitude better on > almost-sorted data than the quick sort. > > I have the code if anyone is interested. (C++, though.) > > Leo > _______________________________________________________________________________ > Subject: Re: [HACKERS] \dt and disk access > From: <maillist%candle.pha.pa.us@interlockp.lubrizol.com> at LZ-INTERNET > Date: 6/23/97 10:16 PM > > > >From what I remember, the quick sort algorithm works just as fast on > > sorted data as on unsorted data. In other words, the algorithm does not > > take advantage of the fact that the data is sorted. > > > > On the other hand, if you go to something like bubble sort, it will > > work faster than quick sort if the data is sorted and you are adding one > > more item, but on unsorted data it takes an enormously longer length of > > time to sort a large list. > > > > One thing I am going to look into is replacing the btree-build in the > current psort with a qsort of HeapTuple pointers. > > -- > Bruce Momjian > maillist@candle.pha.pa.us > > > > > - -- Bruce Momjian maillist@candle.pha.pa.us ------------------------------
> > I don't believe the data is almost-sorted. I am going to recant this. Often, the data is already sorted, but often it is not. > > > > > > > How about using a heap sort? Works in order of magnitude better on > > almost-sorted data than the quick sort. > > > > I have the code if anyone is interested. (C++, though.) > > > > Leo > > _______________________________________________________________________________ > > Subject: Re: [HACKERS] \dt and disk access > > From: <maillist%candle.pha.pa.us@interlockp.lubrizol.com> at LZ-INTERNET > > Date: 6/23/97 10:16 PM > > > > > >From what I remember, the quick sort algorithm works just as fast on > > > sorted data as on unsorted data. In other words, the algorithm does not > > > take advantage of the fact that the data is sorted. > > > > > > On the other hand, if you go to something like bubble sort, it will > > > work faster than quick sort if the data is sorted and you are adding one > > > more item, but on unsorted data it takes an enormously longer length of > > > time to sort a large list. > > > > > > > One thing I am going to look into is replacing the btree-build in the > > current psort with a qsort of HeapTuple pointers. > > > > -- > > Bruce Momjian > > maillist@candle.pha.pa.us > > > > > > > > > > > > > -- > Bruce Momjian > maillist@candle.pha.pa.us > > - -- Bruce Momjian maillist@candle.pha.pa.us ------------------------------