Re: new sorting algorithm
On 5/1/2022 7:45 PM, Chris Angelico wrote: On Mon, 2 May 2022 at 09:20, Dan Stromberg wrote: On Sun, May 1, 2022 at 1:44 PM Chris Angelico wrote: On Mon, 2 May 2022 at 06:43, Dan Stromberg wrote: On Sun, May 1, 2022 at 11:10 AM Chris Angelico wrote: On Mon, 2 May 2022 at 01:53, Nas Bayedil wrote: We believe that using this method to develop completely new, fast algorithms, approaching the speed of the famous *QuickSort*, the speed of which cannot be surpassed, but its drawback can be circumvented, in the sense of stack overflow, on some data. Hmm, actually TimSort *does* exceed the speed of quicksort for a lot of real-world data. For instance, if you take a large sorted list, append a handful of (unsorted) items to it, and then sort the list, TimSort can take advantage of the fact that the bulk of the list is sorted. It ends up significantly faster than re-sorting the entire list. In fact, Timsort is O(n) for already-sorted data, while many quicksorts are O(n^2) for already-sorted data. Quicksort can be salvaged by using a median-of-3 partitioning, but it's still O(n^2) in the (less common) worst case. This is true, but purely sorted data isn't a very practical case. The case of mostly-sorted data IS practical, though, so it's a quite big win that it can be close to O(n), and still faster than inserting each item individually. You seem to be of the impression that nearly-sorted data isn't an uphill battle with a straightforward quicksort. I'm having a hard time convincing myself of that. The median-of-three partitioning technique makes that work reasonably well, so it won't be pathologically slow. It's hardly Quicksort's best feature, but it could easily be a lot worse. I'd have to check, but I think it still manages to be O(n log n). Merge sort, of course, is a lot more consistent, but the asymptotic cost is still broadly the same. But Timsort manages to be close to O(n) for sorted data, reversed data, nearly-sorted or nearly-reversed data, etc. Makes it very handy for jobs like "click a heading to sort by it", where you might add multiple sort keys. (Plus, Python's implementation has some cool tricks for small collections that make it quite efficient.) ChrisA Some versions of Quicksort switch over to Straight Insertion Sort when the partitions become small enough. The correct size will vary depending on the hardware. I have not kept up with the latest improvements and I am not familiar with TimSort. However Heapsort should always be O(n log n) and there are modifications to Heapsort that can make it faster than vanilla Heapsort and closer to the speed of Quicksort. -- https://mail.python.org/mailman/listinfo/python-list
Re: on writing a while loop for rolling two dice
On 9/7/2021 9:20 PM, Avi Gross wrote:
Greg,
Yes, a smart person may come up with such tricks but a really smart person,
in my view, adjusts. With some exceptions, such as when trying to port
existing code to a new language quickly, someone who is not too obsessive
will try to pick up the goals and spirit of a new language and use them when
it seems reasonable. And, a smart person, if they see nothing new, might
just go back to their old language or ...
Pick a language that easily supports regular expressions and object creation
and functional programming and so on, like python, and ask why you might
want to use it to simulate a really old version of BASIC when you can just
use BASIC.
Admittedly, most people are not flexible. I find that with human languages
too that some learn another language just enough to recognize words but not
to use the changed grammar or the different idioms and never become fluent.
I am amused though at the fact that python, by using indentation rather than
things like curly braces, would make some of the games like shown below
quite a bit more difficult.
-Original Message-
From: Python-list On
Behalf Of Greg Ewing
Sent: Tuesday, September 7, 2021 9:08 PM
To: python-list@python.org
Subject: Re: on writing a while loop for rolling two dice
On 8/09/21 2:53 am, Grant Edwards wrote:
#define IF if (
#define THEN ) {
#define ELSE } else {
#define ENDIF }
...
I gather that early versions of some of the Unix utilities were written by
someone who liked using macros to make C resemble Algol.
I guess you can get away with that sort of thing if you're a Really Smart
Person.
--
Greg
--
https://mail.python.org/mailman/listinfo/python-list
So what do yoy think or feel about a language like RATFOR (Rational
FORTRAN) which was implemented as macros? Should they instead have
simply adapted themselves to FORTRAN?
--
https://mail.python.org/mailman/listinfo/python-list
Re: Can I trust downloading Python?
Steven D'Aprano steve+comp.lang.pyt...@pearwood.info wrote in message news:522c6e4e$0$29988$c3e8da3$54964...@news.astraweb.com... On Sat, 07 Sep 2013 21:04:59 -0600, Michael Torrie wrote: As for trusting python in general, I do trust the python developers, but recent NSA revelations call just about all aspects of computing, trust, and privacy into doubt. Recent revelations? Where have you been for the last, oh, 20 odd years? Remember when people who talked about Carnivore and Echelon were considered in tin-foil hat territory? I do. I think it was Paul Krugman who talks about the one thing worse than being wrong is being right too soon. In context, he's referring to the Bush administration's adventures in Iraq, and how those who were right a decade ago are still routinely ignored even after being proven right, while the Very Serious People who were utterly, obviously wrong are still feted as experts. The same applies to the surveillance society. This didn't just appear overnight. You don't build programmes the size and complexity of PRISM, Tempora, Stellawind, X-Keyscore, Dropmire, and no doubt others that we still don't know about, overnight. When it comes to NSA spying, before Edward Snowden, there were these other guys: http://www.usatoday.com/story/news/politics/2013/06/16/snowden-whistleblower-nsa-officials-roundtable/2428809/ And if you think it's just the NSA, you *really* haven't been paying attention. From 2005: http://www.noplacetohide.net/ -- Steven I think this article is relevant althought the code examples are not Python but C: http://cm.bell-labs.com/who/ken/trust.html -- https://mail.python.org/mailman/listinfo/python-list
Which Version of Python?
I have a lot of programming experience in many different languages and now I want to learn Python. Which version do you suggest I download, Python 2.x or Python 3.x ? Also why should I prefer one over the other? Right now I am thinkng Python 3.x as it has been out since 2008, but I have some concerns about backward compatibility with older packages that I might want to use. Thanks for your ideas and help. -- http://mail.python.org/mailman/listinfo/python-list
