Neat little python string trick

[Mathematix]

Originally Posted by dmarsh26

I'm with harry and mgoldwasser, reversing the string should be (and by look of it is) a linear time operation. Think STL iterators or indeed the aforementioned loops. Its a bounded loop with direction, nothing more complex, no need to consider sorting whatsoever.

No mate. I know I said that I would give up, but I have to make a point:

1. The problem would be linear if and only if the letters were first in a completely random order and the requirement were to sort them in reverse alphabetical order.

2. Given that the string was already in alphabetical order, part of the work was already done, so half the effort was required to reverse the order, hence the n/2 complexity that the author disagrees with.

[dmarsh26]

1. The problem would be linear if and only if the letters were first in a completely random order and the requirement were to sort them in reverse alphabetical order.

No you are wrong, the definition of the problem was not to sort, it was to REVERSE. The alphabet string was just used as an example candidate string to demonstrate the reverse. There is no need to sort the string, not because its already 'sorted' but because that is not part of the requirements, the string could of been 'gobledegook' and the reversal would be 'koogedelbog', no sort is needed.

2. Given that the string was already in alphabetical order, part of the work was already done, so half the effort was required to reverse the order, hence the n/2 complexity that the author disagrees with.

You are diverting the thread to disscuss O notation of popular sorting algorithms when the algorithm is a reverse algorithm. The linear time complexity is less than the logarithmic complexity of a sorting algorithm.
A simple observation for reverse might be N chars will require N reads, N writes and N termination comparisions so N*3 operations. Worst case for bubble sort would be something like N pow 2 comparisons and swaps (read*2&comp&write*2) so (N pow2)*5. Average case will of course be less and prob some logarithmic function. http://www.nist.gov/dads/HTML/bubblesort.html - Has bubble sort as O(npow2), quicksort is N log N.
http://warpelican.com/?page_id=3

[Mathematix]

Originally Posted by dmarsh26

No you are wrong, the definition of the problem was not to sort, it was to REVERSE. The alphabet string was just used as an example candidate string to demonstrate the reverse. There is no need to sort the string, not because its already 'sorted' but because that is not part of the requirements, the string could of been 'gobledegook' and the reversal would be 'koogedelbog', no sort is needed.

Dude, I don't know where you get off. I have proved you wrong on many occasions before and have done so again.

When you rearrange the order of elements according to a set of criteria, and the position of those elements are considered sorted when that criteria is met, then they are sorted. When you look on the web or in a book, those are examples of the fundamental sorting algorithms. these are not the be all and end all of the possibilities of sorting! Jeez...

Originally Posted by dmarsh26

You are diverting the thread to disscuss O notation of popular sorting algorithms when the algorithm is a reverse algorithm. The linear time complexity is less than the logarithmic complexity of a sorting algorithm.
A simple observation for reverse might be N chars will require N reads, N writes and N termination comparisions so N*3 operations. Worst case for bubble sort would be something like N pow 2 comparisons and swaps (read*2&comp&write*2) so (N pow2)*5. Average case will of course be less and prob some logarithmic function. http://www.nist.gov/dads/HTML/bubblesort.html - Has bubble sort as O(npow2), quicksort is N log N.
http://warpelican.com/?page_id=3

I wasn't using any of the sorting algorithms described above. Go back an read what I did! The facts are there! Stop digging a hole for yourself, for heavens sake!

[tripwire45]

Ok you two...step back for a sec. From my experience, you are both very intelligent guys who generally know what you're talking about. Take a moment and try to understand where the other guy is coming from. Is it that he's wrong or is there some sort of misunderstanding operating here that's causing you to be at loggerheads. If you are in a disagreement, so be it, but there's absolutely no reason to personalize it. Please keep that in mind. A friendly message from "the management".

[dmarsh26]

I wasn't using any of the sorting algorithms described above. Go back an read what I did! The facts are there! Stop digging a hole for yourself, for heavens sake!

I was just trying to clarify the thread topic, thats what a forums for is it not ?

Dude, I don't know where you get off. I have proved you wrong on many occasions before and have done so again.

Geeeezz take a chill pill man, when I am wrong or mistaken I am more than willing to admit I am wrong, thats what heathly debate is all about no ? "Change your mind, prove you have one..."

When you rearrange the order of elements according to a set of criteria, and the position of those elements are considered sorted when that criteria is met, then they are sorted. When you look on the web or in a book, those are examples of the fundamental sorting algorithms. these are not the be all and end all of the possibilities of sorting! Jeez...

Never said they were did I if you bother to read the posts. The point is the fact that the example string happened to be sorted in this case is irrelevant to the reverse algorithm under disscussion.

I wasn't using any of the sorting algorithms described above. Go back an read what I did! The facts are there! Stop digging a hole for yourself, for heavens sake!

Demo: (swapped elements in bold)

Step 1 - 'dbca'
Step 2 - 'dcba'

So we have four elements reversed in two steps! (O(n/2))

This is a type of sort no ? O notation is generally concerned with worst case,

Step 1 - bdca
Step 2 - adcb
Step 3 - acdb
Step 4 - abdc
Step 5 - abcd

As you can see scanning from the ends with one sweep is not sufficient for truely random data, your algorithm would require multiple passes to succeed and could result in swapping elements that were in the correct location.

A general algorithm will need at best N log N swaps in worst case, best case (sorted) zero swaps, note number comparisons can be a lot larger than the number of swaps (best case log2(n!) ?), therefore its no where near n/2 for worst case and your algortihm is fundamentally broken. You are assuming the data is part sorted or partitioned.

http://en.wikipedia.org/wiki/Sorting_algorithm

No usable sorting algorithm comes close to you level of performance of O(n/2).

N log N is the general lower bound for most sorting algorithms, for 4 elements roughly 2.4 which is more than 2 ie N/2.

You could try some other algorithms to get closer to your measure, however in reality these performance measurements are skewed to large datasets because they discount the cost of the 'minor' operations. For small datasets like in our examples these operations are not minor and the timings for many popular algorithms will be very similar.

[Mathematix]

Originally Posted by tripwire45

Ok you two...step back for a sec. From my experience, you are both very intelligent guys who generally know what you're talking about. Take a moment and try to understand where the other guy is coming from. Is it that he's wrong or is there some sort of misunderstanding operating here that's causing you to be at loggerheads. If you are in a disagreement, so be it, but there's absolutely no reason to personalize it. Please keep that in mind. A friendly message from "the management".

Point taken, Trip.

One of my primary responsibilities at work is optimisation/reverse engineering, both in terms of algorithms and resource allocation. They respect my work and knowledge a great deal - there is no reason why it should be any different here. I'm just a little tired of knowing exactly what I'm talking about and people coming along trying to teach an old dog new tricks (although I'm not an 'old dog') which are incorrect in the first place.

Seriously, if the general public on certforums want to thrive on incorrect/incomplete information on computing science then so bid. It's disgraceful that I should be challenged for something that I've especially clearly proven.

Rant over.

[dmarsh26]

It's disgraceful that I should be challenged for something that I've especially clearly proven.

Where have you proven that N/2 is lower limit O notation for a sort ? What exactly have you proven ?

Your opinion or mine alone do not count as fact or even a consensus. Nobody deserves respect they have to earn it, and it has to be earned in each new domain/forum (excuse the pun.).

I'm not trying to teach you anything, you started to try to teach several of your elders (old dogs?) that reversing a string is fundamentally related to sort when it is not.

Seriously, if the general public on certforums want to thrive on incorrect/incomplete information

Thats precisely why myself, hbromhall and mgoldwasser have voiced our opinions, because we want certforums readers to have as complete a picture as possible given the nature of a forum.

[Mathematix]

Originally Posted by dmarsh26

Where have you proven that N/2 is lower limit O notation for a sort ? What exactly have you proven ?

You guys said that reversing the string is a linear time process in its best case, right? Linear time is O(n). I showed via an alternative algorithm that it is infact not a linear problem, in that elements can be swapped as shown, given the criteria in half the time O(n/2). We even have Knuth's works here at our studio, and I have them at home. I've double-checked my definitions even on the web, asked a colleague who sits directly next to me. None of them disagree.

My colleague actually thought it was quite cool how I reveresed the string.

Originally Posted by dmarsh26

Your opinion or mine alone do not count as fact or even a consensus. Nobody deserves respect they have to earn it, and it has to be earned in each new domain/forum (excuse the pun.).

I completely agree. But then I put to you what is the purpose of proof if you still cannot earn respect for your findings. I'm not asking to be treated like a god, just not to be pressed further for proof when I have already clearly provided one that others have accepted.

Originally Posted by dmarsh26

I'm not trying to teach you anything, you started to try to teach several of your elders (old dogs?) that reversing a string is fundamentally related to sort when it is not.

I was referring to myself when saying 'old dog'. How is reversing a string not fundamentally related to sort?

Originally Posted by dmarsh26

Thats precisely why myself, hbromhall and mgoldwasser have voiced our opinions, because we want certforums readers to have as complete a picture as possible given the nature of a forum.

I agree that eveyone should give their perspective, otherwise there wouldn't be room for healthy discussion. I have admitted in the passed when I've made mistakes on these forums, and it's clear that others have a clear problem doing so. Fromm your last posts I can pick out a number of errors and misunderstandings, but to avoid WW3 I'm steering clear.

If you want me to say you're right, then here you go: "You're right, dmarsh." (Even though I don't believe it for one moment. ;) )

[dmarsh26]

Linear time is O(n).

Maybe in the most purest sense yes, however linear in a more general term means 'proportional', non-exponential, non logarithmic, not a curve, ie it simply means it can be represented as a line on a graph, the are many more possible functions that would generate a line. I'd be the first to admit my math and O notation knowledge is poor.

I showed via an alternative algorithm that it is infact not a linear problem, in that elements can be swapped as shown, given the criteria in half the time O(n/2).

This is also linear, just its a linear relationship that 'ramps' at half the rate. People who therefore stated it was a 'linear' relationship are therefore still correct.

Believe it or not this is not the best way to sort these items in your linear time. I can propose a solution in O(n/2) just off the top of my head. Let me show you by example:

You maybe can do one swap sweep at O(n/2), you cannot sort though, sort requires comparison and potentialy more swaps. Read any text on sort, it will state N log N as lower bound.

Replace sort with reverse and we are in total agreement. However a swap algorithm will probably still perform worse than a reverse iterator copy. A copy would require N operations vs your alleged N/2 but they would most likely be cheaper operations. You would probably require more conditional logic, plus the original method was framed in terms of 'immutable strings' hence hinting at a copy, why copy and swap when you can just copy ?

But then I put to you what is the purpose of proof if you still cannot earn respect for your findings. I'm not asking to be treated like a god, just not to be pressed further for proof when I have already clearly provided one that others have accepted.

I do not believe I have seen any 'proof' ? If you are as good at maths as you say you will understand how hard a good proof is to construct. Who has accepted what exactly ?

How is reversing a string not fundamentally related to sort?

Reversing a string is generally changing the order of elements in memory so that character elements at all indexes are swapped around the midpoint. You do not need to even inspect the contents of the elements, there need be no comparison or collation. You need not even swap, a straight copy is enough providing you have a reverse iterator. A copy with no comparision is therefore not anything like a sort, it is however linear and time taken is directly related to the number of elements.

Fromm your last posts I can pick out a number of errors and misunderstandings, but to avoid WW3 I'm steering clear.

Feel free to point out my misunderstandings or poor explanations, I never said my understanding of the subject was legendary, neither was I rude or abbrasive in any of my posts.

[Mathematix]

As said, dmarsh. You're right. Now go play.

[ffreeloader]

Originally Posted by Mathematix

As said, dmarsh. You're right. Now go play.

Wow, do you have "issues".

[Mathematix]

Originally Posted by ffreeloader

Wow, do you have "issues".

Says the man who goes round every forum in a bad mood.

If he wants me to say he's right, so bid. Just want this crap to end.