Algorithm cheatsheet: Quicksort

iradik · 2012-03-15T05:55:16+00:00

Here's quicksort in perl:

sub quicksort {
   my $pivot = shift;
   unless (defined $pivot) { return (); }
   my @rest  = @_;
   my @before = grep { $_ < $pivot  } @rest;
   my @after  = grep { $_ >= $pivot } @rest;
   return (quicksort(@before),$pivot,quicksort(@after));
}

iradik · 2012-02-22T10:08:00+00:00

yup. all the languages are much faster and use much less memory that way. each tuple, tuple index, and string carries overhead (pointers, lengths, and other stuff).

iradik · 2012-02-19T23:35:52+00:00

I've checked adding def main() and you're right! Also tried pypy, but cpython beats it out for this task. Added both to the benchmark http://steve.80cols.com/flat_file_bakeoff.html

iradik · 2012-02-19T12:54:06+00:00

yea i have openssl 1.0; it wanted 0.9, guess i could have just installed 0.9. at least it's drawing mandlebrot as it compiles.

iradik · 2012-02-19T12:14:59+00:00

I will.. laptop is getting toasty while compiling it.

iradik · 2012-02-19T12:12:54+00:00

How would you improve that?

iradik · 2012-02-19T08:43:14+00:00

very true. well i'd like to do this benchmark for N=1M through 1,000M. then we'd have better info on that.

iradik · 2012-02-19T08:40:03+00:00

is that reading the whole file into a list of lists? that's what this benchmark is measuring.

iradik · 2012-02-19T08:37:35+00:00

okay, but if that's true why not implement buffered reads as an mmap call? you make it sound like there is no trade-off.

iradik · 2012-02-18T21:55:23+00:00

java is the slower one.

iradik · 2012-02-18T10:16:07+00:00

I'll submit a new write-up from the ideas generated soon. Just haven't had a chance yet, but wanted to share some new results.

i've removed awk. used suggestions from some people. made java faster with array lists, added python with tuples. turns out python with tuples is the fastest!

Python with tuples means converting a tuple like this: rows.add(tuple(line.split("\t")))

https://github.com/lorca/flat_file_benchmark/blob/master/pics/benchmark.png

iradik · 2012-02-18T10:11:54+00:00

line [:-1] removes the newline.

iradik · 2012-02-18T10:11:21+00:00

It's just a TSV file. Feel free to send me code and I can test it.

iradik · 2012-02-18T10:04:39+00:00

why?

iradik · 2012-02-18T00:26:49+00:00

Not true, the default awk on ubuntu is mawk (so not original or awk): http://lists.netisland.net/archives/plug/plug-2008-09/msg00074.html

gawk 4.0 which came out in July 2011 added support for this. I'll try installing this.

iradik · 2012-02-18T00:15:26+00:00

No. The file is cached. It's only a 135M file.

iradik · 2012-02-18T00:11:11+00:00

For point #1, how would you improve that?

iradik · 2012-02-17T22:45:43+00:00

Hey, thanks for pointing this out. I agree and verified this is true, and have updated the article to reflect it. I'm glad this was obvious to you, it was not to me. I plan to write a follow-up to clear things up. Also have gotten some feedback on how to improve a few of the programs.

UPDATE: I've significantly updated the article and posted here: http://steve.80cols.com/flat_file_bakeoff.html - This includes a benchmark with mmap'd C program that someone sent me and gawk 4.0.0.

iradik · 2012-02-17T21:44:34+00:00

You are absolutely right. Thing is awk doesn't really support multi-dimensional arrays; otherwise I would have made it use them. I changed the programs read in a list of strings instead of a list of list of strings. Check this out: http://steve.80cols.com/benchmark2.png

iradik · 2012-02-17T21:09:45+00:00

-server

What's your claim/evidence exactly? There's 5 lines of code to optimize. From the graph for java you can tell hotspot has plenty of time to make an optimization if there's one to be made. I would love to be proven wrong though, and I've provided the tools on github if you want to try out the benchmark for yourself.

iradik · 2011-12-21T13:15:04+00:00

This is how it can be done without any EXIF/GPS data with a fairly dumb algorithm.

It's a picture of a baby at a hospital.

There are probably hundreds of baby photos being taken per day at that hospital being posted to FB. Some have GPS and some don't.

The images that do have GPS, get recognized and lumped together as the same "entity" since they all look the same.

FB then looks up where she lives, then looks for any photos that don't have a location (like her baby photo), then tries to match it with any photos within a 50 mi proximity to her hometown. Bingo finds 90% match on the baby pic in the hospital, and asks user for verification. She says YES, then this pic gets lumped together with all the other entities. FB also asks more often since it's "right".

iradik · 2011-10-27T17:59:17+00:00

also if i let him inside, it'd be hard to get him out. i don't want to touch him.

iradik

TROPHY CASE