Python Function Challenge

Board Discussion Number 3

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • 4

45 Replies - 9725 Views - Last Post: 11 January 2011 - 06:40 PM Rate Topic: ****- 2 Votes

#31 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5641
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Python Function Challenge

Posted 29 December 2010 - 06:46 AM

You've stated valid characters and that they may be ignored. Now, you're explicitly demanding they be removed?

That is, you want "VWoV^q^ZdJCuseNjtQanxz" to be considered "VWoVqZdJCuseNjtQanxz" and not "VWoV q ZdJCuseNjtQanxz". The problem is, this then will cause other cases to fail, like "comma,nospace,comma".

So, for the record, you want invalid characters removed?

While speed is a valid metric, it's not the only one. If it were, we'd all just write assembly. We certainly wouldn't be considering interpreted languages, like Python, Java, .NET, etc. Readability and maintainability are also valuable. Doing things in a Pythony way can be intuitive and clear, but perhaps not the fastest. A lot of the more clever list one liners are expensive. Doing copies is expensive. We write things using elegant syntax for humans, not computers. Computers are artless iterative beasts.

Just for yuks, I wrote some C code and put it in a Python wrapper. Even in the wrapper, it beat the crap out of my pure python implementation.

Baavgai Avg time: 0.000081
Baavgai in C Avg time: 0.000012



Here's the C:
static char *getCleaned(const char *line) {
	char *buff = malloc(strlen(line)+1);
	int i;
	for(i=0; line[i]!=0; i++) {
		char ch = line[i];
		if (ch>='A'&&ch<='Z') { 
			buff[i] = 'a'+ch-'A';
		} else if (ch>='a'&&ch<='z') {
			buff[i] = ch;
		} else {
			buff[i] = ' ';
		}
	}
	buff[i] = 0;
	return buff;
}

static int isPalindromeChar(char *head) {
	char *tail = head+strlen(head)-1;
	while(head<tail) {
		if (*head==' ') { head++; continue; }
		if (*tail==' ') { tail--; continue; }
		if (*head!=*tail) { return 0; }
		head++; tail--;
	}
	return 1;
}


static int isPalindromeWords(char *line) {
	int wordCount = 0, len = strlen(line), i = 0;
	char **words = malloc(sizeof(char *) * (len/2));
	
	while(len>0 && line[len-1]==' ') { line[--len] = 0; }
	while(i<len) {
		while(line[i]==' ' && i<len) { i++; }
		words[wordCount++] = line + i;
		while(line[i]!=' ' && i<len) { i++; }
		line[i++] = 0;
	}
	
	i=0;
	wordCount--;
	while(i<wordCount) {
		if (strcmp(words[i++],words[wordCount--])!=0) { free(words); return 0; }
	}
	free(words);
	return 1;
}


int isPalindrome(const char *line) {
	char *s = getCleaned(line);
	int result = isPalindromeChar(s);
	result += (isPalindromeWords(s) * 2);
	free(s);
	return result;
}



Not as pretty as Python. Not as flexible. Actually, horribly inflexible. Much faster.

I used SWIG for the wrapper, because I was lazy.

The further wrapped python call looks like:
def isPalindromeC(line):
	n = pali.isPalindrome(line)
	return (n&pali.PALINDROME_IS_CHAR>0, n&pali.PALINDROME_IS_WORDS>0)



Faster still would be to allocate a max buffer size and avoid the mallocs. Then write a more assembly like beast. When you get down to assembly, the re usability of the code will be near zip.
Was This Post Helpful? 1
  • +
  • -

#32 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • Joined: 23-December 08

Re: Python Function Challenge

Posted 29 December 2010 - 07:12 AM

Woah baav, don't take the results personally.

Firstly, I can see where you're coming from about the special characters. I personally think that 'ignoring' would be interpreted to mean 'skip it and go to the next character' where as you interpreted it to mean 'treat it as whitespace.' Rather than making a big deal about it, how about I just remove that particular test? On a side note, ["comma,nospace,comma",(False, True)] was correctly interpreted by everyone's palindrome program.

Secondly, doing a C program and putting it in a Python wrapper is hardly what was intended and you know it. Can't we try to keep this all in good fun?

Thirdly, I stand by what I said. Readability, scalability, and maintainability all eventually become subjective when comparing similar code. I'm not going to pick someone's function and say "I likes this one!" and then have people jump on me because they don't like the choice (kinda like the choice to use randomly generated strings...). If I knew some legitimate way to measure these things, I'd absolutely test based on that.

This post has been edited by atraub: 29 December 2010 - 11:39 AM

Was This Post Helpful? 1
  • +
  • -

#33 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4309
  • View blog
  • Posts: 7,457
  • Joined: 08-June 10

Re: Python Function Challenge

Posted 29 December 2010 - 07:15 AM

I think the reason he's using speed as a metric is because it's actually a measurable one, since this is ostensibly a competition. I 100% agree with you that "readability and maintainability" are very, very important, but they're subjective in the sense of saying "between these four snippets, this one is the most maintainable."

Also, I realize that compared to things like assembly and C, python is slow as hell. But since we're limiting the contest to the domain of python, fast is relative to the speed of python itself.
Was This Post Helpful? 1
  • +
  • -

#34 baavgai  Icon User is offline

  • Dreaming Coder
  • member icon

Reputation: 5641
  • View blog
  • Posts: 12,359
  • Joined: 16-October 07

Re: Python Function Challenge

Posted 29 December 2010 - 11:14 AM

Sorry, if it looked like I took it personally, I didn't. You'll have to actively try to make me take something personally, which I guess I would take personally. :P

This is actually a common real world scenario. The client defines a set of behavior. The programmer does their best to meet the criteria given. Then exceptions to what was spelled out are found. When the client complains that behavior isn't what was expected, everyone goes to the design spec. If it's not there, amendments are made and the programmer gets paid more. The actual scope of development can be very difficult to agree on.

Leave the second test in. It's by far the most complex and therefore the most fun. Then just give the test cases that define expected behavior and we're all happy programmers.


View Postatraub, on 29 December 2010 - 08:12 AM, said:

Readability, scalability, and maintainability all eventually become subjective when comparing similar code.


I agree. Speed is the number one criteria for program fitness and also the easiest to test.

However, the subjective elements, the ones you obviously can't test for, are just as important. Maintainability is not something you can measure; until you have to do it. Most of the more important elements of programming can't be seen in our little snippets. They only become obvious when things get big and ugly.
Was This Post Helpful? 1
  • +
  • -

#35 soldner  Icon User is offline

  • New D.I.C Head

Reputation: 3
  • View blog
  • Posts: 28
  • Joined: 07-December 09

Re: Python Function Challenge

Posted 29 December 2010 - 11:21 AM

Unless Guido judges the Pythoness, the speed and accuracy should be the criterion.

baavgai, you get design specs? Wow, how neat!
Was This Post Helpful? 1
  • +
  • -

#36 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • Joined: 23-December 08

Re: Python Function Challenge

Posted 29 December 2010 - 11:42 AM

Despite the horrible feeling in my stomach yelling, "ABORT!! This is a bad idea!!!" I suppose I can offer some thoughts on the 'python-ness' of some of the approaches...

Quote

this is ostensibly a competition.


I know I haven't gotten nearly the response that Dogstopper's Java challenge got, but this is my first shot at something like this. Give a guy some slack.

This post has been edited by atraub: 29 December 2010 - 11:43 AM

Was This Post Helpful? 0
  • +
  • -

#37 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4309
  • View blog
  • Posts: 7,457
  • Joined: 08-June 10

Re: Python Function Challenge

Posted 29 December 2010 - 11:44 AM

EDIT to respond to atraub:
"ostensibly" was a poor choice of words. I was trying to imply that even though it is a competition, we're not all necessarily in it to beat each other as much as just try a different way of doing things. Just trying to remind people that hey, it's not just a "post your code" and that we have to have a measurable metric to judge by.

End Edit, though it really does segue nicely into what I originally posted:

Well, I really do think I'm going to adapt this question into a C# discussion thread. But instead of being a competition, it'll probably be a "how many different solutions to the same problem" can we come up with. Some (like me) would use LINQ to solve this, and some (like baavgai, who doesn't like LINQ) would use other methods.

For the same reason you wrote a recursive way, and dogstopper wrote one with classes, and baavgai wrote one in C using a python wrapper...I feel like we'd get several different solutions.

This post has been edited by insertAlias: 29 December 2010 - 11:46 AM

Was This Post Helpful? 0
  • +
  • -

#38 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • Joined: 23-December 08

Re: Python Function Challenge

Posted 29 December 2010 - 11:47 AM

I look forward to seeing your discussion. I think a more open challenge rather than a competition is probably a better approach.

I truthfully wrote the recursive function thinking, "Well, I can show off a cool and clean approach to this problem. Surely one that will look nice, but not a real competitor." I had no idea that it would actually be a serious contender. I think that recursion gets a worse rap than it deserves but I admit that I won't use it frequently in real world scenarios. This challenge at least showed that recursion can actually hold its' own in efficency... Who knew?

This post has been edited by atraub: 29 December 2010 - 11:49 AM

Was This Post Helpful? 0
  • +
  • -

#39 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4309
  • View blog
  • Posts: 7,457
  • Joined: 08-June 10

Re: Python Function Challenge

Posted 29 December 2010 - 11:58 AM

Well, as to recursion...I've had a lot of intimate use of it lately.

I've got an object that has several children, which may themselves be objects, arrays, or value types (or strings, which I have to treat as if it were a value type). I know the object will be one of several defined in a specific assembly, but not which one it might be.

The task is to instantiate the object and all child objects, and make a treeview containing textboxes and headers for each node (including arrays, that's difficult right there). Then I have to traverse the treeview and populate the object with their values. Then they have to be serialized, processed on a server, and an XML response is returned and deserialized into another object.

So, the only way I could think of to guarantee I traversed every node was recursion. And it's dog slow, combined with System.Reflection. There's a noticeable pause (mitigated by being on a different thread) during the instantiation of the object.

It is slow, but sometimes it's the only graceful solution to the problem at hand.
Was This Post Helpful? 0
  • +
  • -

#40 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • Joined: 23-December 08

Re: Python Function Challenge

Posted 29 December 2010 - 12:04 PM

I would argue that there are times where recursion can be faster. The test cases involving smaller strings seem to prove it. Of course, in both scenarios, the recrusive depth was limited.

This post has been edited by atraub: 29 December 2010 - 12:05 PM

Was This Post Helpful? 0
  • +
  • -

#41 Curtis Rutland  Icon User is online

  • (╯□)╯︵ (~ .o.)~
  • member icon


Reputation: 4309
  • View blog
  • Posts: 7,457
  • Joined: 08-June 10

Re: Python Function Challenge

Posted 29 December 2010 - 12:12 PM

Well, yeah, blanket statements like "recursion is slow" are patently false, but more along the lines of recursion can be faster under certain circumstances. Also, there are times where it will be elegant enough to outweigh it's relative performance compared to an iterative solution.
Was This Post Helpful? 0
  • +
  • -

#42 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • Joined: 23-December 08

Re: Python Function Challenge

Posted 05 January 2011 - 12:01 PM

Don't forget, the contest isn't over until 1/10/11. If anyone wants to make any last second revisions or submissions, there is still time!




P.S. did anyone notice that I chose a palindromic date for the deadline?
Was This Post Helpful? 0
  • +
  • -

#43 atraub  Icon User is offline

  • Pythoneer
  • member icon

Reputation: 756
  • View blog
  • Posts: 1,990
  • Joined: 23-December 08

Re: Python Function Challenge

Posted 11 January 2011 - 03:28 PM

With no new submissions, the old results stand:



Small Strings
insertAlias
Elapsed time: 0.533268928528
Average time: 5.33268928528e-05

Dogstopper Dogstopper
Elapsed time: 0.53926897049
Average time: 5.3926897049e-05

baavgai baavgai
Elapsed time: 0.509850025177
Average time: 5.09850025177e-05

baavgai baavgaiCached
Elapsed time: 0.0319018363953
Average time: 3.19018363953e-06

atraub AtraubRecursion
Elapsed time: 0.491166114807
Average time: 4.91166114807e-05

StevenSmith StevenSmith
Elapsed time: 0.77411699295
Average time: 7.7411699295e-05






Lots of Bad Characters
atraub AtraubRecursion
Elapsed time: 0.437238931656
Average time: 4.37238931656e-05

baavgai baavgai
Elapsed time: 0.617779970169
Average time: 6.17779970169e-05

Dogstopper Dogstopper
Elapsed time: 0.460546016693
Average time: 4.60546016693e-05

StevenSmith StevenSmith
Elapsed time: 0.974539041519
Average time: 9.74539041519e-05

baavgai baavgaiCached
Elapsed time: 0.0210049152374
Average time: 2.10049152374e-06

insertAlias
Elapsed time: 0.503103017807
Average time: 5.03103017807e-05






Big Strings
baavgai baavgai
Elapsed time: 2.16325092316
Average time: 0.000216325092316

StevenSmith StevenSmith
Elapsed time: 2.56431889534
Average time: 0.000256431889534

Dogstopper Dogstopper
Elapsed time: 1.88621520996
Average time: 0.000188621520996

atraub AtraubRecursion
Elapsed time: 2.69212698936
Average time: 0.000269212698936

baavgai baavgaiCached
Elapsed time: 0.0213510990143
Average time: 2.13510990143e-06

insertAlias
Elapsed time: 1.90147399902
Average time: 0.000190147399902




Unique Strings
StevenSmith StevenSmith
Elapsed time: 0.161891937256
Average time: 9.21096593399e-06

baavgai baavgaiCached
Elapsed time: 0.0967390537262
Average time: 5.50404265625e-06

Dogstopper Dogstopper
Elapsed time: 0.117145061493
Average time: 6.66505811862e-06

baavgai baavgai
Elapsed time: 0.0819129943848
Average time: 4.6605026391e-06

atraub AtraubRecursion
Elapsed time: 0.063915014267
Average time: 3.63649375665e-06

insertAlias
Elapsed time: 0.138894081116
Average time: 7.90248527058e-06
Was This Post Helpful? 0
  • +
  • -

#44 AdamSpeight2008  Icon User is offline

  • MrCupOfT
  • member icon


Reputation: 2216
  • View blog
  • Posts: 9,351
  • Joined: 29-May 08

Re: Python Function Challenge

Posted 11 January 2011 - 05:21 PM

View Postatraub, on 05 January 2011 - 07:01 PM, said:

Don't forget, the contest isn't over until 1/10/11. If anyone wants to make any last second revisions or submissions, there is still time!


But we've got about 9 months yet.

This post has been edited by AdamSpeight2008: 11 January 2011 - 05:22 PM

Was This Post Helpful? 0
  • +
  • -

#45 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2857
  • View blog
  • Posts: 10,960
  • Joined: 15-July 08

Re: Python Function Challenge

Posted 11 January 2011 - 05:36 PM

View PostAdamSpeight2008, on 11 January 2011 - 07:21 PM, said:

View Postatraub, on 05 January 2011 - 07:01 PM, said:

Don't forget, the contest isn't over until 1/10/11. If anyone wants to make any last second revisions or submissions, there is still time!


But we've got about 9 months yet.


I think that's in American notation, not British...meaning January 10th
Was This Post Helpful? 0
  • +
  • -

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • 4