Disclaimer - I recognize this is not a practical exercise. There are
many implementations around that would do the job better, more
efficiently (Meaning in C) or whatever.
I caught some thread about sorting and started thinking about shell
sort.... and as part of my trying to pythonise my mind and break my
java mindset
So I decided to tackle this old school problem with the python mindset.
I played around with some list comprehensions, trying to use slicing
inteligently etc. Anyway this is what I came up with. If anyone has
suggestions on a more pythonic way to go (all attempts at using list
comprehensions turned into unruly rubbish quite quickly) I'd
appreciate the input. An aside - can anyone tell me where the use +=
and -= is documented? it works but I can't find it in my docs.
(don't ask about shellSorters 1 thru 3)
class shellSorter4(object):
def __init__(self,gapSeq):
self.gapSeq = gapSeq # gap sequences are
notoriously hard to tune
self.gapSeq.sort(reverse=True)
def sort(self,myList):
for gap in self.gapSeq:
for i in range(1,gap+1):
self.gapInsertionSort(myList,i,gap)
def gapInsertionSort(self,theList,start,gap):
for i in range(start,len(theList),gap):
j = i
curElem = theList[j]
while (j > 0) and (theList[j-gap] > curElem):
j -=gap # undocumented
feature??
if j!=i:
theList.insert(j,theList.pop(i))
theList.insert(j+gap,theList.pop(j+1)) 5 2195
On 10/06/2006 7:00 AM, ak*********@gmail.com wrote: Disclaimer - I recognize this is not a practical exercise. There are many implementations around that would do the job better, more efficiently (Meaning in C) or whatever.
I caught some thread about sorting and started thinking about shell sort.... and as part of my trying to pythonise my mind and break my java mindset
So I decided to tackle this old school problem with the python mindset.
I played around with some list comprehensions, trying to use slicing inteligently etc.
Slicing? I don't see any, and besides you don't want to be copying
chunks of your list anyway -- see below.
Anyway this is what I came up with. If anyone has suggestions on a more pythonic way to go (all attempts at using list comprehensions turned into unruly rubbish quite quickly) I'd appreciate the input. An aside - can anyone tell me where the use += and -= is documented? it works but I can't find it in my docs. (don't ask about shellSorters 1 thru 3)
class shellSorter4(object):
def __init__(self,gapSeq): self.gapSeq = gapSeq # gap sequences are notoriously hard to tune self.gapSeq.sort(reverse=True)
Not exactly stand-alone, if it needs another sort for its initialisation :-) def sort(self,myList): for gap in self.gapSeq: for i in range(1,gap+1):
Use xrange instead of range, to save memory.
self.gapInsertionSort(myList,i,gap)
def gapInsertionSort(self,theList,start,gap):
Having a method call here will slow it down somewhat.
for i in range(start,len(theList),gap): j = i curElem = theList[j] while (j > 0) and (theList[j-gap] > curElem):
I think that you mean "while j >= gap" ... otherwise theList[j-gap] will
be using Python's wrap-around negative subscripting to access something
at the other end of the list! And you'll never know, because the last
pass with gap == 1 will (laboriously) clean up any mess. You should
instrument your code with counts of comparisons and rearrangements, and
compare those with examples from the textbooks and the literature *AND*
your pencil-and-paper experiments with a gap-list of (say) [5, 1] on a
small number of elements.
j -=gap # undocumented feature?? if j!=i: theList.insert(j,theList.pop(i)) theList.insert(j+gap,theList.pop(j+1))
Quadruple yuck. Each pop() and insert() could involve moving many list
elements unnecessarily. It's not "pythonic" to use advanced language
features when they are inefficient for the job at hand. All you need is
len(alist), alist[i] = value, and value = alist[i]. A simple translation
of a shellsort written in C would do the job admirably.
Perhaps to Pythonise your mind you should try an object-oriented example
-- one that truly needs a class or two; your shellsort doesn't really
need a class (that's your Java background shining through!).
HTH,
John
Thanks for the critique.
John Machin wrote: On 10/06/2006 7:00 AM, ak*********@gmail.com wrote: Disclaimer - I recognize this is not a practical exercise. There are many implementations around that would do the job better, more efficiently (Meaning in C) or whatever.
I caught some thread about sorting and started thinking about shell sort.... and as part of my trying to pythonise my mind and break my java mindset
So I decided to tackle this old school problem with the python mindset.
I played around with some list comprehensions, trying to use slicing inteligently etc. Slicing? I don't see any, and besides you don't want to be copying chunks of your list anyway -- see below.
That was two of the other sort implementations I tried - far uglier
than this. there were sorts 1-3. And while I liked the idea of using
the list manipulations built into python - they absolutely were
horrible for this. I was almost tempted to post that as well - but it
really was an abomination. Anyway this is what I came up with. If anyone has suggestions on a more pythonic way to go (all attempts at using list comprehensions turned into unruly rubbish quite quickly) I'd appreciate the input. An aside - can anyone tell me where the use += and -= is documented? it works but I can't find it in my docs. (don't ask about shellSorters 1 thru 3)
class shellSorter4(object):
def __init__(self,gapSeq): self.gapSeq = gapSeq # gap sequences are notoriously hard to tune self.gapSeq.sort(reverse=True) Not exactly stand-alone, if it needs another sort for its initialisation :-)
def sort(self,myList): for gap in self.gapSeq: for i in range(1,gap+1):
Use xrange instead of range, to save memory.
for large sorts, yeah xrange is good. with the runs I was doing, it
was irrelevant self.gapInsertionSort(myList,i,gap)
def gapInsertionSort(self,theList,start,gap): Having a method call here will slow it down somewhat.
true enough, performance wasn't a consideration on this one
for i in range(start,len(theList),gap): j = i curElem = theList[j] while (j > 0) and (theList[j-gap] > curElem): I think that you mean "while j >= gap" ... otherwise theList[j-gap] will be using Python's wrap-around negative subscripting to access something at the other end of the list! And you'll never know, because the last pass with gap == 1 will (laboriously) clean up any mess. You should instrument your code with counts of comparisons and rearrangements, and compare those with examples from the textbooks and the literature *AND* your pencil-and-paper experiments with a gap-list of (say) [5, 1] on a small number of elements.
good catch on that one. Didn't think about it. and with the low
probability of it happening it WOULD have been missed - doh. The
versions I was running were instrumented - but took that out for
clarities sake. However j>= gap would not work - say on the first
run where gap should be N/2 (just the worst case) but obviously the
first elements would never get sorted. . An additional test for j-gap0 would suffice.
j -=gap # undocumented feature?? if j!=i: theList.insert(j,theList.pop(i)) theList.insert(j+gap,theList.pop(j+1)) Quadruple yuck. Each pop() and insert() could involve moving many list elements unnecessarily. It's not "pythonic" to use advanced language features when they are inefficient for the job at hand. All you need is len(alist), alist[i] = value, and value = alist[i]. A simple translation of a shellsort written in C would do the job admirably.
I didn't really think of pop and insert as advanced features. But it
was part of my goals to use features that exist in python - remembering
that they are python lists, not funky arrays.
As far as C goes, that was shellSorter1. Since performance wasn't my
goal - I rather liked the expresiveness of the pop and insert. makes
it almost read like a book.
Perhaps to Pythonise your mind you should try an object-oriented example -- one that truly needs a class or two; your shellsort doesn't really need a class (that's your Java background shining through!).
True enough - java is hard to break sometimes. I was tempted to add
some try catches just for fun too. I've written quite a bit that is
more complex - then I get caught in just making it work. Hence the
point of writing simple well understood problems.
HTH, John
On 11/06/2006 1:26 PM, ak*********@gmail.com wrote: Thanks for the critique.
John Machin wrote: On 10/06/2006 7:00 AM, ak*********@gmail.com wrote:
[snip] def sort(self,myList): for gap in self.gapSeq: for i in range(1,gap+1): self.gapInsertionSort(myList,i,gap)
def gapInsertionSort(self,theList,start,gap): for i in range(start,len(theList),gap): j = i curElem = theList[j] while (j > 0) and (theList[j-gap] > curElem):
[some other comments and responses snipped above, to show the relevant
code in one piece] I think that you mean "while j >= gap" ... otherwise theList[j-gap] will be using Python's wrap-around negative subscripting to access something at the other end of the list! And you'll never know, because the last pass with gap == 1 will (laboriously) clean up any mess. You should instrument your code with counts of comparisons and rearrangements, and compare those with examples from the textbooks and the literature *AND* your pencil-and-paper experiments with a gap-list of (say) [5, 1] on a small number of elements. good catch on that one. Didn't think about it. and with the low probability of it happening it WOULD have been missed - doh. The versions I was running were instrumented - but took that out for clarities sake. However j>= gap would not work - say on the first run where gap should be N/2 (just the worst case) but obviously the first elements would never get sorted. . An additional test for j-gap 0 would suffice.
I don't understand your response. Let len(theList) == N and assume that
the first gap is N/2. The first time that gapInsertionSort is called,
start will be 1 and gap will be N/2.
Loop index i becomes start i.e. 1.
j becomes 1.
while (j > 0) [True, must test the other part of the "and"] and
.... (theList[j-gap] > curElem) *BUT* the subscript is 1-(N/2) which is
negative and thus will wrap around and cause an utterly meaningless
comparison.
In fact it will happen the first time in gapInsertionSort for any gap >
1. In one trial I did sorting list('qwertyasdfgzxcvb') (i.e. N == 15) it
made 20 meaningless comparisons.
Question 1: What do you mean by "the low probability of it happening"?
Question 2: I don't understand "obviously the first elements would never
get sorted", as the last pass with gap == 1 cleans up any errors of
commission or omission made by the earlier passes. Could you please
explain that? Or alternatively can you show your code with the "an
additional test for j-gap > 0 would suffice" fix applied to it?
Question 3: All implementations and descriptions of shellshort that I
have found consist of THREE nested loops. This includes Knuth's TAOCP
and K&R 2nd edition. Yours consists of FOUR nested loops (FIVE if you
count the looping inside insert() and pop()). Where did you get your
implementation from?
j -=gap # undocumented feature?? if j!=i: theList.insert(j,theList.pop(i)) theList.insert(j+gap,theList.pop(j+1)) Quadruple yuck. Each pop() and insert() could involve moving many list elements unnecessarily. It's not "pythonic" to use advanced language features when they are inefficient for the job at hand. All you need is len(alist), alist[i] = value, and value = alist[i]. A simple translation of a shellsort written in C would do the job admirably.
I didn't really think of pop and insert as advanced features.
They are relatively advanced compared with subscripting, which is *all*
that is needed to implement shellsort.
But it was part of my goals to use features that exist in python - remembering that they are python lists, not funky arrays.
What kind of arrays are "funky" arrays?
As far as C goes, that was shellSorter1. Since performance wasn't my goal - I rather liked the expresiveness of the pop and insert. makes it almost read like a book.
IMHO, like a book written by James Joyce. :-) Perhaps to Pythonise your mind you should try an object-oriented example -- one that truly needs a class or two; your shellsort doesn't really need a class (that's your Java background shining through!).
True enough - java is hard to break sometimes. I was tempted to add some try catches just for fun too.
Try adding some assertions, like:
assert 0 <= j-gap < n
I've written quite a bit that is more complex - then I get caught in just making it work.
So it seems. Simple design, testing, desk-checking, testing, *permanent*
instrumentation, testing, *permanent* assertions, testing, ... all these
can help :-)
Cheers,
John This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Ville Vainio |
last post by:
Pythonic Nirvana - towards a true Object Oriented Environment
=============================================================
IPython (by Francois Pinard) recently (next release - changes are...
|
by: Bulba! |
last post by:
Hello everyone,
I'm reading the rows from a CSV file. csv.DictReader puts
those rows into dictionaries.
The actual files contain old and new translations of software
strings. The dictionary...
|
by: Majnu |
last post by:
Hi community,
just in case somebody needs a shellsort in c#, I rewrote the pascal
code that I found in another newsgroup. Here are both. For more
explanation on the pascal code you can search...
|
by: krypto.wizard |
last post by:
Is there any editor or IDE in Python (either Windows or Linux) which
has very good debugging facilites like MS VisualStudio has or something
like that.
I like SPE but couldn't easily use winPDP....
|
by: Pythor |
last post by:
I wrote the following code for a personal project. I need a function
that will plot a filled circle in a two dimensional array. I found
Bresenham's algorithm, and produced this code. Please tell...
| |
by: ToddLMorgan |
last post by:
I'm just starting out with python, after having a long history with
Java. I was wondering if there were any resources or tips from anyone
out there in Python-land that can help me make the...
|
by: micklee74 |
last post by:
hi
I have a file with columns delimited by '~' like this:
1SOME STRING ~ABC~12311232432D~20060401~00000000
2SOME STRING ~DEF~13534534543C~20060401~00000000
3SOME STRING ...
|
by: robert |
last post by:
As more and more python packages are starting to use the bloomy
(Java-ish) 'logging' module in a mood of responsibility and as I am not
overly happy with the current "thickener" style of usage, I...
|
by: Dixie |
last post by:
Is there a way to shell to Microsoft Word from Access and load a specific
template - using VBA?
dixie
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can...
|
by: Oralloy |
last post by:
Hello folks,
I am unable to find appropriate documentation on the type promotion of bit-fields when using the generalised comparison operator "<=>".
The problem is that using the GNU compilers,...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows...
|
by: agi2029 |
last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing,...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The...
|
by: 6302768590 |
last post by:
Hai team
i want code for transfer the data from one system to another through IP address by using C# our system has to for every 5mins then we have to update the data what the data is updated ...
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence...
| |