BorlandTalk.com Borland discussion newsgroups   Archives   FAQ   Search   Memberlist   Usergroups   Register   Profile   Log in to check your private messages   Log in  Pending polls Goto page 1, 2  Next          BorlandTalk.com Forum Index -> Delphi Language BASM View previous topic :: View next topic   Author Message Avatar Zondertau Guest Posted: Sun Oct 09, 2005 6:56 am    Post subject: Pending polls It think two polls can be closed. I think we can close the sort validation rules poll now. This would result in rule 3 being accepted (see below). If closed the web master should place the rule on the Fastcode website at the poll results page and on the Sort B&V page. It also means that the rules to which a valid sort function should comply should be shown there. 1) A sort function should execute successfully for any compare function. Avatar 2) A sort function may raise an exception (including EAccessViolation) when passed an invalid compare function, but must still terminate on every compare function. Eric, Hrvoje 3) A sort function may raise an exception or go into an infinite loop or infinite recursion state when passed an invalid compare function (so basically the result would be undefined). Aleksander, Pierre, Anders I think we can close this poll too. This would mean that rule (2) is selected. Should the Sort B&V contain a subbenchmark that measures performance for worst-case situations of several algorithms (especially Quicksort)? 1) No Aleksandr, Avatar, Sasa (?) 2) Yes, with little weight (since this situation is uncommon in real usage) Bruce, Dennis 3) Yes, with weight equal to the other subbenchmarks 4) Either 2 or 3 Dan, Pierre Back to top Sasa Zeman Guest Posted: Sun Oct 09, 2005 2:06 pm    Post subject: Re: Pending polls Avatar Zondertau wrote: Quote: I think we can close the sort validation rules poll now. This would result in rule 3 being accepted (see below). If closed the web master should place the rule on the Fastcode website at the poll results page and on the Sort B&V page. It also means that the rules to which a valid sort function should comply should be shown there. 3) A sort function may raise an exception or go into an infinite loop or infinite recursion state when passed an invalid compare function (so basically the result would be undefined). Aleksander, Pierre, Anders My wote here is 3). Only validation should be correct sorted array. If function go to endless loop or recursion, it should be eliminated. How you exactly validate corrections of sored array after performed sort? Quote: Should the Sort B&V contain a subbenchmark that measures performance for worst-case situations of several algorithms (especially Quicksort)? 1) No Aleksandr, Avatar, Sasa (?) 2) Yes, with little weight (since this situation is uncommon in real usage) Bruce, Dennis 3) Yes, with weight equal to the other subbenchmarks My wote is 3) (since original QuickSort is not forbiden, as well as any other much slower algorithm). Someone can make even original QuickSort ("last element pivot") which worst case is common. trying to sorting already sorted or inversed sort will make any application useless. What mean exactly "little weight " in 2) ? Trying to execute test with more than 100.000 elements will be difficult and for 1.000.000, time is not computable. Again, user/programmer should not care which sort specific component use. Sasa -- www.szutils.net Back to top Avatar Zondertau Guest Posted: Sun Oct 09, 2005 2:26 pm    Post subject: Re: Pending polls Quote: How you exactly validate corrections of sored array after performed sort? I don't know what you mean by this sentence. What corrections are you talking about? Quote: Should the Sort B&V contain a subbenchmark that measures performance for worst-case situations of several algorithms (especially Quicksort)? 1) No Aleksandr, Avatar, Sasa (?) 2) Yes, with little weight (since this situation is uncommon in real usage) Bruce, Dennis 3) Yes, with weight equal to the other subbenchmarks My wote is 3) (since original QuickSort is not forbiden, as well as any other much slower algorithm). Someone can make even original QuickSort ("last element pivot") which worst case is common. trying to sorting already sorted or inversed sort will make any application useless. Such an implementation would surely lose anyways, because there are already subbenchmarks that sort a sorted and a reversely sorted list. Therefore the original QuickSort (using first or last element as pivot) has nothing to do with this poll. We're speaking mostly about worst cases for middle element QuickSort. Quote: What mean exactly "little weight " in 2) ? Trying to execute test with more than 100.000 elements will be difficult and for 1.000.000, time is not computable. I mean that in calculating the benchmark result from the subbenchmarks the worst-case subbenchmark has less weight than the other subbenchmarks. Back to top Sasa Zeman Guest Posted: Sun Oct 09, 2005 4:10 pm    Post subject: Re: Pending polls Avatar Zondertau wrote: Quote: How you exactly validate corrections of sored array after performed sort? I don't know what you mean by this sentence. What corrections are you talking about? I'm sorry, wrong word. Instead of 'corrections' should be 'correctness'... To preformulate anyway. How you insure that resulting array after sort is passed (ie sorting array is correct)? Do you compare each element with already sorted by default RTL algorithm or use another way? Validation based on comparison functioin can only help as brief check. Even X[0] <= X[1] <= ... <=X[n-1] is not suitable, since algorithm may populate array with the same value or not include last and first element... Quote: Such an implementation would surely lose anyways, because there are already subbenchmarks that sort a sorted and a reversely sorted list. Therefore the original QuickSort (using first or last element as pivot) has nothing to do with this poll. We're speaking mostly about worst cases for middle element QuickSort. Can you explain exactly what is worst-case sequence you using for "middle element pivot" QuickSort? Quote: I mean that in calculating the benchmark result from the subbenchmarks the worst-case subbenchmark has less weight than the other subbenchmarks. To preformulate question: what exactly value for little weight is (0.8, 0.5,0.1,0.01)? That is essencial and very dependable on 'n', where complexity of worst case is O(n*n). Sasa -- www.szutils.net Back to top Avatar Zondertau Guest Posted: Sun Oct 09, 2005 4:35 pm    Post subject: Re: Pending polls Quote: How you exactly validate corrections of sored array after performed sort? I don't know what you mean by this sentence. What corrections are you talking about? I'm sorry, wrong word. Instead of 'corrections' should be 'correctness'... To preformulate anyway. How you insure that resulting array after sort is passed (ie sorting array is correct)? Do you compare each element with already sorted by default RTL algorithm or use another way? Validation based on comparison functioin can only help as brief check. Even X[0] <= X[1] <= ... <=X[n-1] is not suitable, since algorithm may populate array with the same value or not include last and first element... The correctness of the sort is validated by two functions: ListSameElements - checks if the result list contains the same elements (with the same muliplicity) as the original list ListIsOrdered - checks if the list is correctly sorted with respect to the compare function You can find them in the B&V (FastcodeChallengeSortUnit). Quote: Such an implementation would surely lose anyways, because there are already subbenchmarks that sort a sorted and a reversely sorted list. Therefore the original QuickSort (using first or last element as pivot) has nothing to do with this poll. We're speaking mostly about worst cases for middle element QuickSort. Can you explain exactly what is worst-case sequence you using for "middle element pivot" QuickSort? It has been explained to you several times: you place the lowest number on the middle element. Then you repeat this procedure with the next lowest number for the new list that one iteration of QuickSort would cause (there is only one sublist because the number was the lowest one). By continuing this approach you will fill the entire list with numbers. This resulting list is a worst case for the middle element pivot QuickSort. I believe one of the posters here offered to make a function which creates such lists. You could take a look at it when it's finished. Quote: I mean that in calculating the benchmark result from the subbenchmarks the worst-case subbenchmark has less weight than the other subbenchmarks. To preformulate question: what exactly value for little weight is (0.8, 0.5,0.1,0.01)? That is essencial and very dependable on 'n', where complexity of worst case is O(n*n). The B&V is normally calibrated to have the same outcome for the best function on a blended target (for example, outcome 1000 for each subbenchmark). Note that by this time the n has already been fixed, so it's not relevant anymore. Reduced weight would mean that in this calibration process we would choose the factors in such a way that the outcome is lower than the others (again for the fastest function on the blended target). Back to top Pierre le Riche Guest Posted: Sun Oct 09, 2005 6:39 pm    Post subject: Re: Pending polls Hi Avatar, Quote: I think we can close this poll too. This would mean that rule (2) is selected. I count 3 votes for (3) and only 2 votes for (2). Adding Sasa's vote (3) has a clear majority. Quote: Should the Sort B&V contain a subbenchmark that measures performance for worst-case situations of several algorithms (especially Quicksort)? Looks like 2 wins. Regards, Pierre Back to top Sasa Zeman Guest Posted: Sun Oct 09, 2005 9:04 pm    Post subject: Re: Pending polls Pierre le Riche wrote: Quote: I count 3 votes for (3) and only 2 votes for (2). Adding Sasa's vote (3) has a clear majority. Should the Sort B&V contain a subbenchmark that measures performance for worst-case situations of several algorithms (especially Quicksort)? Looks like 2 wins. Perhaps Avatar should show final list of used sequences for all subbenchmarks (i.e., random, random with many equal elements, etc..) and about weighting all and give a chance to more voters (7 voters is too little) or creating new vote. Sasa -- www.szutils.net Back to top Sasa Zeman Guest Posted: Sun Oct 09, 2005 9:04 pm    Post subject: Re: Pending polls Avatar Zondertau wrote: Quote: The correctness of the sort is validated by two functions: ListSameElements - checks if the result list contains the same elements (with the same muliplicity) as the original list ListIsOrdered - checks if the list is correctly sorted with respect to the compare function You can find them in the B&V (FastcodeChallengeSortUnit). I believe there is a bug in ListSameElements. Parameters are two pointer lists: one for sorted list and second is original list. You sort it both again with RTL sort and compare it pointers - In that case you will always have positive result!! I believe you should sort original list with RTL sort and compare pointers with given sorted list by selected sort. ListIsOrdered is not self depend (as I'm expain) and it is not needed because comparison each element sorted with RTL sort. I suppose, RTL sort alwas return correct sorting. :-) Quote: It has been explained to you several times: you place the lowest number on the middle element. Then you repeat this procedure with the next lowest number for the new list that one iteration of QuickSort would cause (there is only one sublist because the number was the lowest one). I have'n interest by theoretical approach, but current sequence used in B&V. I see, you havn't implemented it yet (v 0.9 is the last in attachments). Stephen Howe gives link to AntiQSort algorithm article. In case of including that subbenchmark, on 1 shl 22 time needed to be calculated is inpractical (it is logical to be choosen smaller computable 'N' for O(N*N)). Probability of deliberately created worst case for "middle elemen pivot" very near to zero. I belive you didn't precisely wrote which QuickSort varian you mean nor that you will/have include sorted or reversely sorted array in subbenchmark. Mentioned arrays was counted among other variants in form of suggestion only. Please wrote final list of array sequences for subbenchmarks. Quote: Reduced weight would mean that in this calibration process we would choose the factors in such a way that the outcome is lower than the others (again for the fastest function on the blended target). I belive that radnom and random sorting with small rage (more equal elements) is more frequently than sorting already sorted or reversely sorted arrays. Perhaps these results should be reduced as well. Anyway, all thaht should be clearer when you show final list of choosen sequence for subbenchamrks. Sasa -- www.szutils.net Back to top Avatar Zondertau Guest Posted: Mon Oct 10, 2005 6:26 am    Post subject: Re: Pending polls Quote: The correctness of the sort is validated by two functions: ListSameElements - checks if the result list contains the same elements (with the same muliplicity) as the original list ListIsOrdered - checks if the list is correctly sorted with respect to the compare function You can find them in the B&V (FastcodeChallengeSortUnit). I believe there is a bug in ListSameElements. Parameters are two pointer lists: one for sorted list and second is original list. You sort it both again with RTL sort and compare it pointers - In that case you will always have positive result!! This is the most effective way of checking if the lists have equal element. Note that i'm sorting by the pointers, not the data pointed to. This function is just mean to check if the elements in the lists are the same, not if the order is correct. That is what the other function is for. Quote: I believe you should sort original list with RTL sort and compare pointers with given sorted list by selected sort. That doesn't work because the sort algorithms needn't be stable. Quote: ListIsOrdered is not self depend (as I'm expain) and it is not needed because comparison each element sorted with RTL sort. I suppose, RTL sort alwas return correct sorting. The lists are being copied before ListSameElements sorts them. The original lists are left untouched. Take a better look at the source code before claiming it is wrong. Quote: I have'n interest by theoretical approach, but current sequence used in B&V. I see, you havn't implemented it yet (v 0.9 is the last in attachments). Stephen Howe gives link to AntiQSort algorithm article. Pierre offered to write it. Quote: In case of including that subbenchmark, on 1 shl 22 time needed to be calculated is inpractical (it is logical to be choosen smaller computable 'N' for O(N*N)). Probability of deliberately created worst case for "middle elemen pivot" very near to zero. I know. That's why i voted against. Quote: I belive you didn't precisely wrote which QuickSort varian you mean nor that you will/have include sorted or reversely sorted array in subbenchmark. Mentioned arrays was counted among other variants in form of suggestion only. Please wrote final list of array sequences for subbenchmarks. I have included both a sorted and reversly sorted list. I also posted the final list before. Take a better look at the posts and the source code. Back to top Avatar Zondertau Guest Posted: Mon Oct 10, 2005 6:31 am    Post subject: Re: Pending polls Quote: I think we can close this poll too. This would mean that rule (2) is selected. I count 3 votes for (3) and only 2 votes for (2). Adding Sasa's vote (3) has a clear majority. This is the outcome with Sasa moved: 1) No Aleksandr, Avatar 2) Yes, with little weight (since this situation is uncommon in real usage) Bruce, Dennis 3) Yes, with weight equal to the other subbenchmarks Sasa 4) Either 2 or 3 Dan, Pierre I see 2 direct votes for (2) and 2 indirect votes for (2) (through (4)) which makes a total of 4 votes. (2) only has 3 votes. Also since (1) won't be winning anyways i'll be moving my vote to (2), which is closer to (1) than the alternative. This gives the following result: (1) 1 (2) 3 (+2 from (4)) (3) 1 (+2 from (4)) Looks like a clear win for (2), but of course people can still change their votes if they want to. Back to top Avatar Zondertau Guest Posted: Mon Oct 10, 2005 6:31 am    Post subject: Re: Pending polls Quote: I count 3 votes for (3) and only 2 votes for (2). Adding Sasa's vote (3) has a clear majority. Should the Sort B&V contain a subbenchmark that measures performance for worst-case situations of several algorithms (especially Quicksort)? Looks like 2 wins. Perhaps Avatar should show final list of used sequences for all subbenchmarks (i.e., random, random with many equal elements, etc..) and about weighting all and give a chance to more voters (7 voters is too little) or creating new vote. I have posted the list as it currently is. All are weighed equally there. Back to top Sasa Zeman Guest Posted: Mon Oct 10, 2005 8:40 am    Post subject: Re: Pending polls Avatar Zondertau wrote: Quote: This is the most effective way of checking if the lists have equal element. Note that i'm sorting by the pointers, not the data pointed to. This function is just mean to check if the elements in the lists are the same, not if the order is correct. That is what the other function is for. Unfortunately, you didn't understand. Seems there is a bug in the code. There is nothig wrong comparing pointers to data - they point on the same memory in case they are equal... if not ListSameElements(@List[0], @ListSort[0], Len) then ---- function ListSameElements(List1, List2: PPointerList; Count: Integer): Boolean; var I: Integer; List1Sort, List2Sort: PPointerList; begin Result := True; GetMem(List1Sort, Count * SizeOf(Pointer)); GetMem(List2Sort, Count * SizeOf(Pointer)); try Move(List1^, List1Sort^, Count * SizeOf(Pointer)); Move(List2^, List2Sort^, Count * SizeOf(Pointer)); Sort_RTL(List1Sort, Count, CompareInt); // Sorting ListSort list which is result sorted list performed by // choosen algorithm. You sort it's copy again, this time with RTL!! Sort_RTL(List2Sort, Count, CompareInt); // <- Should be disabled for I := 0 to Count-1 do if List1Sort^[I] <> List2Sort^[I] then begin Result := False; Break; end; finally FreeMem(List2Sort); FreeMem(List1Sort); end; end; Quote: The lists are being copied before ListSameElements sorts them. The original lists are left untouched. Take a better look at the source code before claiming it is wrong. No. Nothing wrong with function ListIsOrdered. It is good for brief checking only, just it is not self dependent and it is not needed when you check each element - unnecessary soubled check. Quote: I have included both a sorted and reversly sorted list. I also posted the final list before. Take a better look at the posts and the source code. I do not agree with the list you show 2005-09-27. Please read my suggestion carefuly. In summary: 1. Random list OK. 2. Random list with high likelyhood of items appearing multiple times Factor is currently 2, based on total ammount of data. That is too little of equal elements. Furthermore, in practice, they are mostly used elements in small ranges from K to J, where K N elements from 0 to 1023 or 0 to 65535 - I do not suggested it concrete). Meaning Factor should higher or usedd random number in specific range. 3. Sorted list OK. 4. Partially sorted list; first part sorted, then appended random entries See: Subject: Re: Fastcode Sort B&V version 0.9 Date: 3 Oct 2005 06:05:35 -0700 Added 15% is too high. Should be enough less than 5% (or fixed number of elements) to simulate adding situation. 5. Reversely sorted list OK. 6. List sorted by criterium B to be sorted by criterium A + B IMO, this is unnatural situation. Sasa -- www.szutils.net Back to top Sasa Zeman Guest Posted: Mon Oct 10, 2005 8:40 am    Post subject: Re: Pending polls Avatar Zondertau wrote: Quote: This is the outcome with Sasa moved: 1) No Aleksandr, Avatar 2) Yes, with little weight (since this situation is uncommon in real usage) Bruce, Dennis 3) Yes, with weight equal to the other subbenchmarks Sasa 4) Either 2 or 3 Dan, Pierre Also since (1) won't be winning anyways i'll be moving my vote to (2), which is closer to (1) than the alternative. This gives the following result: Consider that decision again. As well, other people here can vote as well (I doubt only 7 people are interesting). Because sorted and reversely sorted arrays are included and with that eliminate "first/last element pivot" QuickSort, I vote: 1) No Reasons: 1. Worst-cases for all algorithms are "unnatural" ind probability to happend in practice is nearly zero. I havn't notice all those years that someone complain that RTL version has enter in O(N*N). 2. Weighting and infinite testing time problem for O(N*N) worst-cases. 3. Dificultie to create different test to all used algoritms (meaning several benchmarks). 4. Favoryzing other than QuickSort algorithm (or on it based hibrids), depending on number of worst-case benchmarks (for quick sort there is at least 2 versions). I'm not aware that other in average O(N LOG N) algorithms have O(N*N) worst-cases, except in-place MergeSort and non-balanced binary TreeSort. Sasa -- www.szutils.net Back to top Avatar Zondertau Guest Posted: Mon Oct 10, 2005 9:05 am    Post subject: Re: Pending polls Quote: Sort_RTL(List1Sort, Count, CompareInt); // Sorting ListSort list which is result sorted list performed by // choosen algorithm. You sort it's copy again, this time with RTL!! Sort_RTL(List2Sort, Count, CompareInt); // <- Should be disabled You don't understand what i'm doing here. I'm just checking if both lists contain the same elements. I have no intention of checking the order here! List2 is a correct sorted version of List1 if and only if both of these are true: - List1 contains the same elements as List1 (that is, the sorting didn't remove or duplicate any elements) - List2 is sorted These are checked separately. This is needed because two correctly sorted lists may not have the same order (because if instabity equal elements may not be at the same places). Quote: I have included both a sorted and reversly sorted list. I also posted the final list before. Take a better look at the posts and the source code. I do not agree with the list you show 2005-09-27. Please read my suggestion carefuly. In summary: Start votes about these if you wish. IMHO the current choices are more useful and realistic than your suggestions. Back to top Avatar Zondertau Guest Posted: Mon Oct 10, 2005 9:08 am    Post subject: Re: Pending polls Quote: This is the outcome with Sasa moved: 1) No Aleksandr, Avatar 2) Yes, with little weight (since this situation is uncommon in real usage) Bruce, Dennis 3) Yes, with weight equal to the other subbenchmarks Sasa 4) Either 2 or 3 Dan, Pierre Also since (1) won't be winning anyways i'll be moving my vote to (2), which is closer to (1) than the alternative. This gives the following result: Consider that decision again. As well, other people here can vote as well (I doubt only 7 people are interesting). OK, so you're changing your vote (again)? Anyways my preference is this: (1) if it can reach a majority though my votes (2) if that is not possible, to avoid (3) from winning Back to top Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First         BorlandTalk.com Forum Index -> Delphi Language BASM All times are GMT Goto page 1, 2  Next Page 1 of 2   Jump to: Select a forum C++ Builder Newsgroups----------------C++ BuilderC++ Builder (ActiveX)C++ Builder (Announcements)C++ Builder (Command Line Tools)C++ Builder DatabasesC++ Builder Databases (ADO)C++ Builder Databases (Desktop)C++ Builder Databases (InterBase Express)C++ Builder Databases (Multi-Tier)C++ Builder Databases (SQL Servers)C++ Builder (Graphics)C++ Builder (IDE)C++ Builder (Internet)C++ Builder (Internet Socket)C++ Builder (Internet Web)C++ Builder (Jobs)C++ Builder (Language)C++ Builder (Language C++)C++ Builder (Compatibility with MFC)C++ Builder (Native API)C++ Builder (Non-Technical)C++ Builder (Students)C++ Builder (Third Party Tools)C++ Builder (Upgrade)C++ Builder (VCL)C++ Builder (VCL Components Usage)C++ Builder (VCL Components Development)C++ Builder (VCL Usage)C++ Builder (WinAPI)C++ Builder Installation Delphi Newsgroups----------------Delphi (General)Delphi ActiveX Controls UsageDelphi ActiveX Controls DevelopmentDelphi As400Delphi DatabasesDelphi Databases (ADO)Delphi Databases (dbExpress)Delphi Databases (Desktop)Delphi Databases (InterBase Express)Delphi Databases (Multi-Tier)Delphi Databases (SQL Servers)Delphi DeploymentDelphi GraphicsDelphi IDEDelphi InternationalizationDelphi InternetDelphi Internet Isapi-WebBrokerDelphi Internet WebSnapDelphi Internet WinsockDelphi JobsDelphi Language BASMDelphi Language ObjectPascalDelphi Model Driven Architecture (General)Delphi Model Driven Architecture (Third Party)Delphi MultimediaDelphi Native APIDelphi Non-TechnicalDelphi ObjectPascalDelphi OLE AutomationDelphi OO designDelphi OpenToolsAPIDelphi Reporting-ChartingDelphi RTLDelphi StudentsDelphi TeamSourceDelphi Thirdparty ToolsDelphi Thirdparty Tools (General)Delphi Thirdparty Tools (IntraWeb)Delphi Thirdparty Tools (RaveReports)Delphi UpgradeDelphi VCLDelphi VCL ComponentsDelphi VCL Components UsingDelphi VCL Components WritingDelphi WebServices SOAPDelphi WinAPIDelphi XMLDelphi Installationcomp.lang.pascal.delphi.components.misccomp.lang.pascal.delphi.components.usagecomp.lang.pascal.delphi.components.writingcomp.lang.pascal.delphi.databasescomp.lang.pascal.delphi.misccomp.sources.delphi JBuilder Newsgroups----------------JBuilderJBuilder AnnouncementsJBuilder Applet IssuesJBuilder As400JBuilder CompilerJBuilder CORBA/RMIJBuilder DatabasesJBuilder DB SwingJBuilder DebuggerJBuilder DeploymentJBuilder DocumentationJBuilder EnterpriseJBuilder HandheldJBuilder IDEJBuilder JavaJBuilder JavaAPIJBuilder Java LanguageJBuilder Java SwingJBuilder Java BeansJBuilder Java Beans UsageJBuilder Java Beans DevelopmentJBuilder JBCLJBuilder JDataStoreJBuilder JobsJBuilder LinuxJBuilder MacintoshJBuilder & MobileSetJBuilder MultiLingual AppsJBuilder Non-TechnicalJBuilder OpenToolsJBuilder Servlets (JSP)JBuilder StudentsJBuilder Team DevelopmentJBuilder Thirdparty ToolsJBuilder UpgradeJBuilder Installation InterBase Newsgroups----------------InterBaseInterBase Bug DiscussionInterBase GeneralInterBase IBConsoleInterBase OpenSourceInterBase ReplicationInterBase SQLInterBase ThirdpartyInterBase Installation Miscellaneous Borland Newsgroups----------------AppCenterAppServerEnteraVisiBroker  You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum Powered by phpBB © 2001, 2006 phpBB Group SEO toolkit © 2004-2006 webmedic.