- Qucksort for Linked List - 20 Updates
- Legal name clash? - 1 Update
- Class Design for ASCII Input Tables - 2 Updates
- Threads and Object Methods - 2 Updates
| Gareth Owen <gwowen@gmail.com>: Dec 18 10:56PM > complex plane is an abstraction and no I don't think complex number > theory is bullshit. This is not the same kind of abstraction as made > with projective geometry. "God created the integers. Everything else is the work of man." -- Leonard Kronecker (he was a mathematician, you won't know him) In other words, its all abstractions, darling. Instead of claiming to read me like a book, go read an actual book. |
| Gareth Owen <gwowen@gmail.com>: Dec 19 05:48AM > It is ironic that you mentioned Stuckle as I am now classifying you > the same as I classify him... *plonk* Oh deary. Did getting called out on your nonsense hurt you feelings? Try saying sausages a few times. |
| David Brown <david.brown@hesbynett.no>: Dec 19 08:58AM +0100 On 18/12/16 23:22, Paavo Helde wrote: > So, how do you tell apart which abstractions are good and which are bad? > In my naivety I have always thought all the maths is abstractions, > basically about the same kind ... "God made the integers, all else is the work of man" I don't think Mr. Flibble likes any mathematics that can't be described in terms of sausages. You can count sausages, so positive integers are okay. You can owe someone sausages, so negative numbers are okay. You can divide them, so rationals are okay. Basic geometry can be done with strings of sausages. But algebraic structures of sausages, functions of sausages, sausages in non-Euclidian spaces, all that is, in his mind, irrelevant. (There is nothing wrong with not being good at maths, or not knowing much about higher level maths. Some people have studied maths at university level - but most people have not. What bugs me about Mr. Flibble is not that he doesn't know much maths - it's that he thinks he knows all /real/ maths and that everything else is irrelevant nonsense.) |
| Juha Nieminen <nospam@thanks.invalid>: Dec 19 08:06AM > particular, the entire linked list can be scanned, any constant > number of times, looking for a pivot value, without changing the > order of the algorithm. In addition, it's possible to optimize the constant factor of the computational complexity, for example if you would want to use the median-of-the-first-last-and-middle pivot method: The very first time you perform the partitioning just choose the first element as the pivot, but as you distribute the nodes into the two new lists, keep note of the last and middle elements of said lists. Then when partitioning them, you can choose their pivots from those three nodes. No need to scan the lists. |
| Juha Nieminen <nospam@thanks.invalid>: Dec 19 08:09AM >> Show your working. > Fuck off you self important cunt. You do realize that's pretty much a concession? If you were an honest person, you would simply admit outright that you were wrong. Instead, you have to make the admission indirectly by resorting to insults. |
| Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 18 11:07PM On 18/12/2016 22:52, Gareth Owen wrote: > Anglo-Saxon vocabulary). Maybe best stick to saying "sausages" and > pissing off fundies, yeah? > Clearly, that is where you true abilities lie. It is ironic that you mentioned Stuckle as I am now classifying you the same as I classify him... *plonk* /Flibble |
| leigh.v.johnston@googlemail.com: Dec 19 04:46AM -0800 Answer me this: why do all std::list::sort implementations use merge sort rather than qsort? Sausage sorting is a tricky business. |
| bartekltg <bartekltg@gmail.com>: Dec 19 03:04PM +0100 > Answer me this: why do all std::list::sort implementations use merge sort rather than qsort? > Sausage sorting is a tricky business. And why std::sort uses introsort (qsort + heapsort as fallback), and not, for example, in place merge sort? Both have complexity O(n log n). Because introsort is faster. Mergesort run log_2(n) times through the whole list. Qsort, 2 ln(2) log_2(n) = 1.39 log_2(n) times in average case (with median pivot a bit better, 1.188). Qsort for list is ~40% worse. But it is still a valid sorting methods for lists. Just not the best one nor the easiest one. bartekltg |
| gwowen <gwowen@gmail.com>: Dec 19 06:17AM -0800 On Monday, December 19, 2016 at 7:58:50 AM UTC, David Brown wrote: > What bugs me about Mr. Flibble is not that he doesn't know much maths - > it's that he thinks he knows all /real/ maths and that everything > else is irrelevant nonsense.) I agree completely with this sentiment. Incidentally, one could probably abstract projective geometry using the approximately-spherical layer of sausage meat that surrounds a scotch egg. Maybe if someone were to formulate like that.... |
| gwowen <gwowen@gmail.com>: Dec 19 06:40AM -0800 > Answer me this: why do all std::list::sort implementations use merge sort > rather than qsort? LMGTFY: http://stackoverflow.com/questions/1717773/which-sorting-algorithm-is-used-by-stls-listsort https://www.quora.com/What-algorithm-do-popular-C++-compilers-use-for-std-sort-and-std-stable_sort Short answer: These days they mostly use introsort. And they do so because introsort is faster, particularly on almost-sorted datasets, and its good to avoid pathological behaviour, even if it isn't necessary to meet the average-case complexity. They used to use merge-sort, because merge-sort is stable, and quicksort/intro-sort is unstable unless you do some extra bookkeeping (which does not increase the big-Oh behaviour). NB: All those intro/quick/merge sort behaviours are the same for arrays, vectors and other containers. |
| bartekltg <bartekltg@gmail.com>: Dec 19 06:48PM +0100 On 19.12.2016 15:40, gwowen wrote: >> Answer me this: why do all std::list::sort implementations use >> merge sort rather than qsort? > LMGTFY: At leas you could do it correctly. > because introsort is faster, particularly on almost-sorted datasets, > and its good to avoid pathological behaviour, even if it isn't > necessary to meet the average-case complexity. And yo get it from what? From this sentence from the first answer: "...std::sort is implemented as a intro-sort (introspective sort),..." Jerry Coffin didn't understand the question. When you go to the second answer or to the second thread: http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort You get the real answer. You can also look at the code in your computer. In my it is mergesort gcc (Ubuntu 5.4.0-6ubuntu1~16.04.4) 5.4.0 > NB: All those intro/quick/merge sort behaviours are the same for > arrays, vectors and other containers. What do you mean? bartekltg |
| Gareth Owen <gwowen@gmail.com>: Dec 19 06:53PM > second answer or to the second thread: > http://stackoverflow.com/questions/1717899/which-sorting-algorithm-is-used-by-microsofts-stllistsort > You get the real answer. I stand corrected[0]. See also here. http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists#5223117 Leigh please note: The answer is *not* because quicksort on linked lists is worse O(n log n) on average. > What do you mean? That intro-sort is a better choice that quicksort for sorting all sorts of containers for exactly the same reasons its a better choice for sorting lists. Which is true. [0] Well, I suppose I could just shout abuse at you, or call you a troll. |
| Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 19 07:09PM On 19/12/2016 14:40, gwowen wrote: > Short answer: These days they mostly use introsort. And they do so because introsort is faster, particularly on almost-sorted datasets, and its good to avoid pathological behaviour, even if it isn't necessary to meet the average-case complexity. > They used to use merge-sort, because merge-sort is stable, and quicksort/intro-sort is unstable unless you do some extra bookkeeping (which does not increase the big-Oh behaviour). > NB: All those intro/quick/merge sort behaviours are the same for arrays, vectors and other containers. So qsort is 40% slower than merge sort on a linked list eh Gareth matey?. So I was correct. 40. %. slower. If I am totally honest I have not actually looked at the implementation of qsort for linked lists I just had a gut feeling that it would be non-optimal compared to other methods as qsort was designed for arrays however you are forgetting one very important thing: Being wrong (even deliberately so) on the Internet is the quickest way to illicit correct information on the Internet. /Flibble P.S. Liver and onions tonight not sausages. |
| Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 19 07:14PM On 19/12/2016 19:09, Mr Flibble wrote: > Being wrong (even deliberately so) on the Internet is the quickest way > to illicit correct information on the Internet. s/illicit/elicit/ /Flibble |
| Gareth Owen <gwowen@gmail.com>: Dec 19 07:31PM >> arrays, vectors and other containers. > So qsort is 40% slower than merge sort on a linked list eh Gareth > matey?. So I was correct. 40. %. slower. No. You said average-case algorithmic complexity was worse. That's not the same thing at all. |
| Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 19 07:45PM On 19/12/2016 19:31, Gareth Owen wrote: >> matey?. So I was correct. 40. %. slower. > No. You said average-case algorithmic complexity was worse. > That's not the same thing at all. No I said (as a complete guess I admit) the worst-case complexity was more likely (which may be wrong, don't much care). However I have already said that I haven't actually looked at linked list qsort implementation and I don't intend to ever do so as I would never use qsort to sort a linked list. /Flibble |
| Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 19 08:14PM On 19/12/2016 07:58, David Brown wrote: > university level - but most people have not. What bugs me about Mr. > Flibble is not that he doesn't know much maths - it's that he thinks he > knows all /real/ maths and that everything else is irrelevant nonsense.) Yes I agree totally: sausages are important. If it doesn't work with sausages it is woo. /Flibble |
| Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Dec 19 08:19PM On 19/12/2016 19:45, Mr Flibble wrote: > already said that I haven't actually looked at linked list qsort > implementation and I don't intend to ever do so as I would never use > qsort to sort a linked list. From Wikipedia: "Although quicksort can be implemented as a stable sort using linked lists, it will often suffer from poor pivot choices without random access." https://en.wikipedia.org/wiki/Quicksort#Relation_to_other_algorithms /Flibble |
| bartekltg <bartekltg@gmail.com>: Dec 19 09:26PM +0100 On 19.12.2016 19:53, Gareth Owen wrote: > http://stackoverflow.com/questions/5222730/why-is-merge-sort-preferred-over-quick-sort-for-sorting-linked-lists#5223117 > Leigh please note: The answer is *not* because quicksort on linked lists > is worse O(n log n) on average. I'm not sure, did you change your opinion? std::list::sort is almost (*) always mergesort *) I didn't see implementation with different algorithm, but of course I can't be sure there is none ;-) > That intro-sort is a better choice that quicksort for sorting all sorts > of containers for exactly the same reasons its a better choice for > sorting lists. Containers with random access, so vector (array...) implemented in continuous memory block. Merge sort do _less_ work, but mergesort need either additional (linear in size) memory or quite complicated tricks, while qsort is quite cache friendly. As a results, qsort work faster on vector and similar containers. Both, disadvantage of mergesort and advantage of qsort, disappears in the case of a list. Just write both and compare. For a list mergesort (written in proper way, look at std::list::sort) is faster. bartekltg |
| Gareth Owen <gwowen@gmail.com>: Dec 19 08:32PM >> Leigh please note: The answer is *not* because quicksort on linked lists >> is worse O(n log n) on average. > I'm not sure, did you change your opinion? Which opinion? > std::list::sort is almost (*) always mergesort I agree with this now. > *) I didn't see implementation with different algorithm, > but of course I can't be sure there is none ;-) Of course. > As a results, qsort work faster on vector and similar containers. But only by a multiplicative factor, so time-big-Oh sense they're the same. Or rather intro-sort and merge-sort are big-Oh-the-same (worst case n*log n) but the multiplicative factor changes depending on whether you can do random access or you have to traverse the list. |
| legalize+jeeves@mail.xmission.com (Richard): Dec 19 07:11PM [Please do not mail me a copy of your followup] Paul <pepstein5@gmail.com> spake the secret code >omitted). >When I write int min = -3; I would expect the compiler to interpret this >as meaning (int std::min = 3). Why would you expect this? 'using namespace std' makes the namespace std available for looking up names. It doesn't put newly declared names inside the namespace 'std'. There's nothing wrong with this code: >#include <iostream> >#include <algorithm> >using namespace std; This tells the compiler "when I use a name that I haven't declared, go look for it in namespace 'std' and see if it is declared there." >{ > cout << min(5,7) << " "; > int min = -3; This declares a local variable names 'min' of type 'int'. > cout << min; Names from the local scope are always preferred before looking in any namespaces added with a 'using namespace' statement. -- "The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline> The Terminals Wiki <http://terminals-wiki.org> The Computer Graphics Museum <http://computergraphicsmuseum.org> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com> |
| Christian Gollwitzer <auriocus@gmx.de>: Dec 19 03:32PM +0100 > Converters tend to generate horrible code. yes and no - Fortran 66 is so simple that it can be converted to C almost mechanically - f2c from netlib is not that bad. The code is typically still horrible mostly because it was horrible before (6 char identifiers and similar nonsense) > In addition to porting > the code to C++, we also plan on a major update to the program > overall architecture to make it much easier to maintain and modify. That makes sense. > What would be nice is to see a UML diagram of what a table class > would contain. At this point I am just look for a top level class > overview to see how it might work.... Nobody can do that without knowing the program. Only you can judge what classes or containers are actually needed. Maybe it is possible to separate the real algorithm from the I/O stuff. Then try to strip down the original program until it only does computations from one array to another array. Then convert to C (can be done by a converter) and write the I/O stuff afresh. Christian |
| legalize+jeeves@mail.xmission.com (Richard): Dec 19 07:08PM [Please do not mail me a copy of your followup] 1. Create an automated acceptance test suite around the existing system 2. Port the existing system before you add new features 3. Use TDD and the automated acceptance tests from 1) on your replacement system TL;DR: When porting legacy code from one language to another, you are essentially talking about a complete rewrite. Unfortunately, unless you do this in an automated way, you are likely to introduce many bugs along the way. So how do we guard against such bugs, minimize them, and find them as soon as possible? First, start by writing an automated test suite around your current system. Think of these as integration tests, regression tests, or acceptance tests, but they aren't unit tests. Try to create tests that surround the major subsystems of your code base. A great tool for expressing acceptance tests is FitNesse <http://fitnesse.org>, which gives you a nice editable wiki as a way of expressing your tests as tables and allows you to write any additional explanatory notes or links to images or other files directly in the wiki pages describing your tests. These keeps the test and all the other information about the subsystem together. This automated suite of tests can be run against the existing system and your replacement system to identify discrepencies between the two. Given that your original system is FORTRAN 66, it most likely operates on input files and creates output files. It is very easy to wrap a test harness around this by creating the input files from the FitNesse wiki table data, invoke the system under test, and then read the output files for comparison against the expected results in the FitNesse wiki table. Second, try to change only one thing at once. In your followup posts you described how the desire to port the code was motivated by the need to more easily extend the existing system with new features. Don't try to add new features at the same time as you are trying to capture the existing behavior. Your first goal should be to create new code that can replace the existing code with no change in observable behavior. How far "deep" you want the existing behavior preserved depends on the organization of your existing system. It may be useful to literally replace the exsisting FORTRAN 66 subroutines with C++ functions/procedures that are declared 'extern "C"' so that they can be linked into the FORTRAN code. However, it could be considerably easier to replace things one subsystem at a time instead of one function at a time. Perhaps your FORTRAN code consists of multiple executables which each do a very specific thing. Each executable can be thought of as a subsystem to be converted. If your FORTRAN code is a single, large, monolithic executable, then the subsystem boundaries are going to be inside that executable. Look for groups of functions that work together to identify subsystems. It is highly unlikely that every subroutine interacts with every other subroutine. It is more likely they are connected in clusters. If you don't know the code well enough to identify the clusters, use a source code analyzer to identify the interactions. FORTRAN COMMON blocks are a way that functions are coupled that is unique to FORTRAN, so don't forget to check for those. Third, write your new code using test-driven development. Make your new code easy to unit test by writing the test first and then satisfy the test with new code in your replacement module. If you're using FitNesse for the regression acceptance tests, have a way to run those against your new system to know that your new system is reproducing the behavior of the old system. If you kept your subsystem boundaries relatively high level (e.g. not at the level of individual FORTRAN subroutines), then you will have more freedom in the C++ that you write in your replacement subsystem. -- "The Direct3D Graphics Pipeline" free book <http://tinyurl.com/d3d-pipeline> The Terminals Wiki <http://terminals-wiki.org> The Computer Graphics Museum <http://computergraphicsmuseum.org> Legalize Adulthood! (my blog) <http://legalizeadulthood.wordpress.com> |
| ruben safir <ruben@mrbrklyn.com>: Dec 18 09:15PM -0500 On 12/18/2016 04:40 PM, Vir Campestris wrote: > a pointer to an object of the class and invokes a corresponding > non-static member. > Andy Not really. There are data members of the object that are dynamically altered and stored in the private encapsulation of the object which a a method handles inside the thread. read_chunk is a member of the Image class and it is assigned indexes within a block of memory, and a chunk of raw data. It interprets the block of memory and writes to the block of memory which is private to an instance of Image. The idea was to create a number of threads that write to the block, each in its assigned area, simultaneously in parallel. read_chunk looks like this void Image::read_chunk ( ) { CHUNKY * new_chunk = set_chunk();//the chunk construction call is within std::cout << "Type " << new_chunk->type() << std::endl; std::cout << "Length " << new_chunk->length() << std::endl; std::cout << "CRC " << new_chunk->cr() << std::endl; if(new_chunk->type() == "IHDR") { std::cout << "we have a header chunk " << std::endl; IHDR * head = new IHDR; unsigned char * cur = new_chunk->data(); //NOTE:: cur is now point at the new heap for in CHNUNK and not the index for the file head->width = ntohl( *(reinterpret_cast<int32_t *>(cur ) ) ); cur += 4; head->height = ntohl( *(reinterpret_cast<int32_t *>( cur ) ) ); cur += 4; head->depth = *( reinterpret_cast<int8_t *>( cur ) ); cur++; head->color_type = *( reinterpret_cast<int8_t *>( cur ) ); cur++; head->compress = *( reinterpret_cast<int8_t *>( cur ) ); cur++; head->filter = *( reinterpret_cast<int8_t *>( cur ) ); cur++; head->interlace = *( reinterpret_cast<int8_t *>( cur ) ); cur++; canvas_size = static_cast<long int>(head->height) * static_cast<long int>(head->width) * blank_canvas_psize(*head); canvas = new unsigned char[ canvas_size ]; std::cout << "Canvas made: " << static_cast<long int>(head->height) * static_cast<long int>(head->width) * blank_canvas_psize(*head) << " bytes" << std::endl; //char tmp; //std::cin >> tmp; } if(new_chunk->type() == "IDAT") { //confusion here. Do we want to create a new data array on the heap to pass through to the images for placement on canvas? //No. Not needed. Use the CHUNKY object instead. It already has the data array. Have the chunky obj schedule itself for //copy to the canvas set_canvas(*new_chunk); //SET MUTEX LOCK and assign canvas index to a CHUNKY object } if(new_chunk->type() == "IEND") { std::cout << "we have a IEND chunk " << std::endl; //set_index(get_index() + 12 + new_chunk->length() ) ; return; } std::thread ctch = getNext(); //calls this method in recursion ctch.join(); //I want this to be detached //read_chunk(); return ; } /* ----- end of method Image::read_chunk ----- */ |
| ruben safir <ruben@mrbrklyn.com>: Dec 18 09:23PM -0500 On 12/18/2016 09:15 PM, ruben safir wrote: > //read_chunk(); > return ; > } /* ----- end of method Image::read_chunk ----- */ and I had to use a lamda for the thread std::thread Image::getNext () { std::cout << std::endl << "getNext" << std::endl; // next_index(); std::thread paint( [this]{ read_chunk(); } ); std::cout << std::endl << "**created thread**" << paint.get_id() << std::endl; return paint; } /* ----- end of method Image::getNext ----- */ |
| You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page. To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com. |
No comments:
Post a Comment