Date: Sun, 27 Nov 2016 13:33:41 -0800 From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> To: Alfred Perlstein <alfred@freebsd.org> Cc: Tristan Verniquet <tris_vern@hotmail.com>, =?UTF-8?Q?Arne_Dag_Fidjest=C3=B8l?= <adf@idi.ntnu.no>, Hans Petter Selasky <hps@selasky.org>, freebsd hackers <freebsd-hackers@freebsd.org> Subject: Re: qsort switching to insertsort Message-ID: <CAOgwaMvAfOum%2BXzDnArqphJjwivAH5CQfspxmJX8R%2BAXnm6bEw@mail.gmail.com> In-Reply-To: <8b0bd8e7-a77d-85d8-18e7-e1e33fed78f5@freebsd.org> References: <ME1PR01MB0546A92343D712D8439B299C83880@ME1PR01MB0546.ausprd01.prod.outlook.com> <0bfb49b0-5d24-2766-6982-b4e49b0d5e81@selasky.org> <ME1PR01MB0546D041DC160763C5D3689883880@ME1PR01MB0546.ausprd01.prod.outlook.com> <CAOgwaMvUE%2BK==OE3zkpfpXa5kBC1YT4JAUVhujxEt9PcHXgqTw@mail.gmail.com> <B8ECCF6B-6477-441B-87F1-0DB3B36F828E@idi.ntnu.no> <CAOgwaMtsP159jgT4Faxg2jED1sh3N-zHKZRSqQNE0Cfh1NM1eA@mail.gmail.com> <ME1PR01MB054602129230B98C6127F607838B0@ME1PR01MB0546.ausprd01.prod.outlook.com> <8b0bd8e7-a77d-85d8-18e7-e1e33fed78f5@freebsd.org>
next in thread | previous in thread | raw e-mail | index | archive | help
On Sat, Nov 26, 2016 at 10:40 PM, Alfred Perlstein <alfred@freebsd.org> wrote: > A couple notes: > > 1) It's interesting to me that it's based on a simple heuristic as oppose= d > to also checking the depth of the recursion within the qsort itself. > > Aim is not to enter into quick sort at the beginning . Number of sorted pairs can be counted on ( input or generation ) of data to sort . Based on this count , the sorting method may be selected as either quick or an alternative sort which will be able to sort the data deterministically . It is possible to implement a robust quick sort if ( time and/or resources ) are sufficient to use . When there is not sufficient resources , a simple method is better than a more optimized ( which will not be attainable at present state ) . > 2) Wondering if upon detection of this situation it might even be faster > to perform some randomization (shuffle) of the data and then retry. > > Instead of ( entering into quick sort , fail , and , search a way to recover ) , I would prefer to use another method will will produce a desired result by using more time . Sometimes , it is very difficult to generate a "universal" algorithm that will be able to cure "all" difficulties . > 3) Wondering if there could be a way to return an error and indicate the > data is unsorted if the corner case is hit allowing the caller to make a > choice at that point. Obviously the API would need to be changed. > > Problem is lying in the complexity of writing a very robust quick sort algorithm . There are many ( at least parts in ) books , papers on these subject . There is also a cost of obtaining / reading / utilizing such resources . When the available resource is only a "data structures" book , the cheapest solution may be the above described method to sort the data without entering into error generation and recover from it . > I haven't thought too hard on this. > > One thing to keep in mind: Using qsort in a codepath has "deadlines" or > other deterministic needs is not going to work out well. It's better to > use a sort with a known complexity with an upper bound than something tha= t > can be defeated by a pathological input data set. > > -Alfred > > > On 11/26/16 8:17 PM, Tristan Verniquet wrote: > >> From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> >> Sent: Sunday, 27 November 2016 5:51 AM >> To: Arne Dag Fidjest=C3=B8l >> Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers >> Subject: Re: qsort switching to insertsort >> >> >> >> On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjest=C3=B8l <adf@idi.ntnu.n= o> >> wrote: >> >> On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com= > >>> wrote: >>> >>> In quick sort , it is necessary to check worst case and switch to anoth= er >>> sort method if it is detected . >>> When this is not done , end result is stack overflow , etc . , but not >>> success . >>> Therefore , it is not possible to eliminate an alternative sort method = . >>> >> I you sort the smaller partition recursively first, and then sort the >> larger partition either by tail recursion or iteration, you will only >> consume O(log n) of stack, so stack overflow needn=E2=80=99t be an issue= , >> regardless of the input. >> >> -adf >> >> >> >> Important problem is caused by almost sorted values . Myself , I am >> counting the sorted elements first , if they exceed a large percentage o= f >> number of all elements , then I am switching to an alternative sort , >> otherwise a quick sort is used . This is for a simple application . >> >> In an operating system , more complex algorithms may be more useful . >> >> >> Mehmet Erol Sanliturk >> >> --- >> >> It can still trigger with completely unsorted data in the top and bottom >> half, as long as it chooses the middle value for the pivot. The main rea= son >> nearly sorted data is vulnerable is that it is more likely to match thes= e >> conditions, and more likely to happen in real life situations. >> >> But this is why i don't really consider it an "edge" case, there would b= e >> a whole class of situations (like the one we had) where it would be very >> likely to trigger with very bad side effects. >> >> Maybe, does anyone continue to use FreeBSD qsort while being aware of >> this implementation detail? Under what conditions/assurances? >> >> Does anyone use FreeBSDs qsort because of this feature? >> >> Tristan >> ________________________________ >> From: Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com> >> Sent: Sunday, 27 November 2016 5:51:31 AM >> To: Arne Dag Fidjest=C3=B8l >> Cc: Tristan Verniquet; Hans Petter Selasky; freebsd hackers >> Subject: Re: qsort switching to insertsort >> >> >> >> On Sat, Nov 26, 2016 at 9:14 AM, Arne Dag Fidjest=C3=B8l <adf@idi.ntnu.n= o >> <mailto:adf@idi.ntnu.no>> wrote: >> >> On 26 Nov 2016, at 15:35, Mehmet Erol Sanliturk <m.e.sanliturk@gmail.com >>> <mailto:m.e.sanliturk@gmail.com>> wrote: >>> >>> In quick sort , it is necessary to check worst case and switch to anoth= er >>> sort method if it is detected . >>> When this is not done , end result is stack overflow , etc . , but not >>> success . >>> Therefore , it is not possible to eliminate an alternative sort method = . >>> >> I you sort the smaller partition recursively first, and then sort the >> larger partition either by tail recursion or iteration, you will only >> consume O(log n) of stack, so stack overflow needn=E2=80=99t be an issue= , >> regardless of the input. >> >> -adf >> >> >> >> Important problem is caused by almost sorted values . Myself , I am >> counting the sorted elements first , if they exceed a large percentage o= f >> number of all elements , then I am switching to an alternative sort , >> otherwise a quick sort is used . This is for a simple application . >> >> In an operating system , more complex algorithms may be more useful . >> >> >> Mehmet Erol Sanliturk >> >> >> >> _______________________________________________ >> >> Mehmet Erol Sanliturk
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAOgwaMvAfOum%2BXzDnArqphJjwivAH5CQfspxmJX8R%2BAXnm6bEw>