Things I've learned at Google so far

Well I've been an employee at Google for about a month. So this seems like as good a place to reflect for a moment.

The first thing that I've learned is that internally Google is incredibly open, but externally there is a lot we can't say. I understand and support a lot of the reasons why it is so, but it can be frustrating. There is a lot of really cool technology at Google that people never hear about. The statistics of what Google deals with are astounding. The technology we use to deal with it is amazing. The way we scale is unbelievable. (I really wish I could go back and have a few discussions on software development methodology raising points about what has proven to scale at Google...) One random fact that I know I can say is that computations happen in our data centers with about half the power drawn for what is industry standard. I'm not allowed to say how we do it, but it is a rather amazing testimony to what smart people can accomplish when we put our minds to it.

Moving on, what about Google's culture? I would describe Google's culture as "creative chaos". There was some confusion about where I was supposed to be when I started. This resulted in the following phone call, "Hello?", "Hello Ben, this is Conner (that's my new manager), where are you?" "Mountain View." "Why are you there?" "Because this is where the recruiter said to go." "Good answer! Nice of them to tell me. Enjoy your week!" This caused me to ask an experienced Googler, "Is it always this chaotic?" The response I got was, "Yes! Isn't it wonderful?" That response sums up a lot about Google's culture. If you're unable to enjoy that kind of environment, then Google isn't the place for you.

Seriously, the corporate culture is based on hiring really smart people, giving them responsibilities, letting them know what problems the company thinks it should focus on, then letting them figure out how to tackle it. What management hierarchy there is is very flat. And people pay little attention to it unless there is a problem. You are expected to be a self-directed person, who solves problems by reaching out to whomever you need to and talking directly. Usually by email. The result is an organization which is in a constant state of flux as things are changing around you, usually for the better. With a permanent level of chaos and very large volumes of email. It is as if an entire company intuitively understood that defect rates are tied to distance on the corporate org-chart, and tried to solve it by eliminating all barriers to people communicating directly with whoever they need to communicate with. (Incidentally the point about defect rates and org charts is actually true, see Facts and Fallacies of Software Engineering for a citation.)

Speaking of email, working at Google you learn really fast how gmail is meant to be used. If you want to deal with a lot of email in gmail, here is what you need to do. Go into settings and turn keyboard shortcuts on. The ones you'll use a lot are j/k to move through email threads, n to skip to the next message, and the space bar to page through text. And m to hide any active thread that you're not interested in (direct emails to you will still show up). There are other shortcuts, but this is enough to let you skim through a lot of email fairly quickly without touching the mouse too much. Next go into labels and choose to show all labels. Your labels are basically what you'd call folders in another email client. (Unfortunately they are not hierarchical, but they do work.) Next as you get email, you need to be aggressive about deciding what you need to see, versus what is context specific. Anything that is context specific you should add a filter for, that adds a label, and skips the inbox. Nothing is lost, you can get to the emails through the list of labels on the left-hand side of your screen in gmail. But now various kinds of automated emails, lower priority mailing lists, and so on won't distract you from your main email until you go looking for them.

When you combine all of these options with gmail's auto-threading features, it is amazing how much more efficiently you can handle email. In fact this is exactly the problem that gmail was invented to handle. Because this was the problem that Paul Buchheit was trying to solve for himself when he started gmail. It is worth pointing out that Paul Buchheit was a software engineer at Google. He didn't need permission to write something like gmail. Corporate culture says that if you need something like that, you just go ahead and do it. In fact this is enshrined as an official corporate policy - engineers get 20% of their time to do with pretty much as they please, and are judged in part on how they use that time. I found a speech claiming that over half of Google's applications started as a 20% project. (I'm surprised that the figure is so low.) To get a sense of how much stuff people just do, visit Google Labs. No corporate decision. No central planning. People just do things like start putting up solar panels in the parking lot, and the next thing you know Google has one of the largest solar panel installations in the world and has decided to go carbon neutral. And the attitude that this is how you should operate is enshrined as official corporate policy!

You've got to love corporate policies like that. Speaking of nice corporate policies, Google has quite a few surprising ones. For instance they have benefits like heavily subsidized massage on site (I've still got to take my free hour massage for joining), free gym membership, and the like. Or take their attitude on dogs. Policy says that if your immediate co-workers don't object, you can bring your dog to work. Cats are different, however. Nothing against cats, but Google is a dog place and cats wouldn't be comfortable. (Yes, there are lots of dogs around the offices, and I've even seen people randomly wander over to find out if they can borrow someone else's dog for a while.) Hmmm. Sick day policy. Don't show up when you're sick and tell people why you're not showing up. Note what's missing. There is no limit to how much sick time you get if you need it. Oh, and food. Official Google policy is that at all times there shall be good, free food within 150 feet of every Googler. OK, admittedly the food quality does vary. That in Mountain View is better than anywhere else (the larger clientele base lets them have a much more varied selection). But you quickly learn why it is common for new Googlers to put on 15-20 pounds in their first year. (I'm trying to avoid that. We'll see if I succeed...)

But, you say, isn't this crazy? Doesn't it cost a fortune? The answer is that of course it does. But it provides value. People bond over food. Even if you're not bonding, having food close by makes short meals easier. And the temptation to continue working until dinnertime is very real. (Particularly if, as with me, you'd like to wait until rush hour is over before going home.) Obviously no normal CFO would crunch numbers and see things that way. But Google stands behind that decision, and the people who work there treasure the company for it.

Speaking of the people who work there, Google has amazing people. It is often said that engineers find working at Google a humbling experience. This is absolutely true. It took me less than a day to realize that the guy sitting next to me is clearly much smarter than I am, and he's nowhere near the top of the range of talent at Google. In fact, as best as I can tell, I'm pretty much average, though I'm trying hard to hold out a ray of hope that I'm slightly better than average.

Let me put that in context. The closest thing that I have to an estimate for my IQ is scoring 2340 on the GRE exam in 1991. Based on conversions that I've seen, that puts me at about the top 0.01% in IQ. Now I was really "on" that day, happen to believe that there are problems with the measurement of intelligence by an IQ test (a subject which I may devote a future blog post to), but without false modesty I wouldn't be surprised to find that I'm as high as being in the top 0.1% in general intelligence (however that could be measured). Which in most organizations means that I get thought of as being very smart.

However software development is a profession that selects for intelligence. By and large only good software developers bother applying to Google. And Google rejects the vast majority of their applicants. Granted the filtering process is far from perfect, but by the time you get through that many filters, someone like me is just average.

This leads to another point of interest. How astoundingly complex the company is. I believe that organizations naturally evolve until they are as complex as the people in them can handle. Well Google is tackling really big, complex problems, and is full of people who can handle a lot of complexity. The result? I've been told that I should expect that after 2 months I'll only be marginally useful. My initial learning curve should start to smooth out after about 6 months. And every year I should expect half of what I've learned to become obsolete. (Remember what I said about Google having a certain level of permanent chaos? If you're like me, it is exhilarating. But sometimes the line between exhilarating and terrifying can be hard to find...)

Oh, and what else did I learn? That we're hiring more people this year. :-)

On jokes

When I was in grad school I had the interesting problem of being a socially inept extrovert. Being an extrovert is OK. Being socially inept is survivable. But a socially inept extrovert is going to wind up being embarrassed. Repeatedly.

So I decided to do something about it. I decided that I'd learn to tell jokes. So I began following rec.humor.funny and would regularly inflict what I thought the funniest jokes were on people around me.

At first my delivery sucked and they wouldn't laugh, or would only laugh politely. Over time my delivery improved and people began laughing for real. Eventually I gained enough social skills to realize that telling bad jokes wasn't the best way towards a normal social life improve my social skills, but kept on doing it anyways because it was fun.

So why are jokes funny? Why do we laugh? When I reflect on it, I don't really know the answer. What I do know is that the structure of a joke inevitably sets up some tension, then relieves it in an unexpected way, and then people laugh. If you can't set up the tension, and then release it, people won't laugh. And once people have started laughing, it is easier to keep them laughing.

To see this in a simple example, consider the lowly pun:

Q: What is the difference between bird flu and swine flu?
A: One requires tweetment while the other requires oinkment!

As soon as you hear the question, you know what is coming. And you try to figure it out. Then you hear the answer, see how it connects, and (hopefully) laugh.

Many jokes rely on cultural references, often topical:

Q: What is the difference between Santa Claus and Tiger Woods?
A: Santa stopped at three hos.

Q: Why did the possum cross the road?
A: There was a car coming.

Q: Why are New Yorker's so cynical?
A: The light at the end of the tunnel is New Jersey!

Q: What is the difference between NY and LA?
A: In NY people say, "Fuck you!" and just mean, "Have a nice day!" In LA people say, "Have a nice day!" and mean "Fuck you!"

If I tell those jokes to the right people I am guaranteed a good laugh. If I tell them to the wrong person I'll get a blank look. Unless you're up on current scandals, have lived somewhere where opossums are common road kill, know that area of NJ or are familiar with stereotypes about NY and LA, those jokes won't cause a laugh.

Those jokes actually work with reasonably broad audiences. Some jokes only work with niche audiences. For example this only works with anglophones who know a little French. (I have great luck with Canadians on this one.)

Q: How do Australians say, "You're welcome" in French?
A: (in your best Australian accent) "Pas de probleme, mate!"

What is interesting about this is that I find it is the act of having to translate it that makes it funny. Living in Southern California I've tried to switch to Spanish, but it simply doesn't work. People hear "No problemo, mate!" as English instead of Spanish, so don't find it funny. But the French version forces the mental translation. For different reasons francophones who speak some English don't find it funny for the simple reason that they don't understand the cultural reference about Australians.

Now many people have told me that they can't remember jokes. Let me give a longish joke to illustrate the problems people encounter.

A little girl decided that she wanted to sell toothbrushes. So she went to a manager at a manufacturer and convinced him that, even though she was young, there was no harm in giving her a try. So he gave her her chance.

The first day she showed up, took her sample, went out, and came back. He asked, "How did you do today?" She said, "I thold ONE toothbwuth!" He said, "I'm sorry, but you're going to have to do better than that if this is going to work out."

The second day she showed up, took her sample, went out, and came back. He asked, "How did you do today?" She said, "I thold TWO toothbwutheth!" He said, "I'm sorry, but you're going to have to do a lot better than that if this is going to work out."

The third day she showed up, took her sample, went out, and came back. He asked, "How did you do today?" She said, "I thold THREE THOUTHAND toothbwutheth!" He said, "Three thousand? Wow! How did you do that?" She said, "Well, I went to the mall and offered people chipth and dip. They thaid, 'Thith tathtth like cwap!' I thaid, 'Thith ith cwap, want a toothbwuth?'"

(Incidentally that is one of my wife's favorites.)

Now the first problem people have in remembering a joke like this is that by the time they've heard the end of it, they've forgotten most of it. Memory is an odd thing. We don't realize it, but anything you remember 30 seconds is actually in long term memory. However we've got many levels of long term memory. So just because you've remembered something for 30 seconds doesn't mean that you'll remember it 5 minutes later. If you're going to remember something, you have to work for it. What you're going to need to do is remind yourself on a schedule until it really sticks. My minimal effective schedule is about 30 seconds later, 5 minutes later, again that day, then again the next day, then again sometime in the next week.

And that leads into the second problem. When people hear a joke like this, the most memorable thing is what sticks in your mind. So people remember, "Thith ith cwap, want a toothbwuth?" and then have no referent from which to remember how to start the joke. Or if they start the joke, they keep on jumping directly to the punch line. But it doesn't work without the build-up.

What you've therefore got to do is learn that, "Joke ___ starts with ___". And then you need to practice telling it. And every time you go off track, you've got to back up just slightly, and start telling it, correctly, from before you make the error. This is a subtle and important point that people miss. If you practice telling it, mess up, then start right at the error then you're practicing making the error. And you'll never stop making the error. You've got to practice leading up to the potential error without making the error to get it right. (This is something I learned in choir, but it works for jokes as well as it does for songs.)

And then the third problem is that no matter how many jokes you tell, and how well you tell them, you will forget jokes. I've told hundreds of different jokes. At no point do I remember most of them. Or even most of the good ones. But as long as you have some good ones, that doesn't matter.

Enough on telling jokes, what makes them funny?

As I said, I've noticed that the sudden release of tension is an element. The corollary of this is that it is easier for a joke to be funny when it's about something we have tension about. For instance if you want to make a pre-school child laugh, talk about poop.

Of course grown-ups don't have so much tension around potty training, but we do around sex. Which is why most of us remember and like dirty jokes. Like these.

Micky Mouse and his lawyer were talking. "I'm sorry Mr. Mouse, but the fact that your wife is crazy is not grounds for divorce." "I didn't say she was crazy, I said she was fucking Goofy!"

Q: What is the difference between good, very good, and showing off?
A: Spitting, swallowing, and gargling.

A little girl asked her dad for a GI Joe doll. He said, "Why do you want a GI Joe doll?" "For Barbie to play with." "I thought Barbie came with Ken?" "No, Barbie comes with GI Joe. She fakes it with Ken."

And to finish, here is the dirtiest joke that I am willing to repeat in public:

A businessman was going on a trip. So he decided to get his wife a special present to keep her happy while he was gone. Knowing her tastes, he decided to go to a sex shop.

Looking around the shop, nothing caught his eye. Sure they had a good selection of dildos, vibrators, and what not, but his wife was pretty experienced and nothing was really special. So he asked the woman who ran it.

She said, "Well I do have the voodoo penis, but I'm not sure I really want to sell it." "The what?" "Voodoo penis." Even though it was not really for sale, his curiosity was up and he convinced her to bring it out.

She went in back and came out with a weird wooden box. She opened it up and there was a wooden dildo with all sorts of strange occult symbols on it. He said, "Well that looks weird, but it's basically just a dildo." She said, "That's because you haven't seen what it can do."

Then she said, "Voodoo penis, the door!" And the voodoo penis flew out of the box, flew up to the door and began banging on it. Then she said, "Voodoo penis, the table!" It went over and began banging on the table. Then she said, "Voodoo penis, the box!" and it went back into the box.

When he saw this, he knew his wife had to have it. A thousand bucks later she was convinced to sell it, and he took it home. And he gave it to his wife with the instructions, "If you get bored while I'm gone, just lie back, get comfy, open the box and say, 'Voodoo penis, my crotch!' and you'll have an interesting experience."

She thought it was odd, but she accepted the present. And while he was away on his trip she decided that she would give it a try. Despite how silly she felt about it she took her clothing off, laid back, opened the box, and said, "Voodoo penis, my crotch!"

Of course the voodoo penis flew out and began fucking her! It was amazing! Soon she had a wonderful orgasm. But it wasn't all brute strength, because before long it had brought her back to a peak and she had a second! After her third, she decided that this was a good thing but she'd had enough for now. Besides, she was getting sore.

So she said, "Voodoo penis, stop!" It didn't. She tried grabbing it and pulling it out. She wasn't strong enough. Desperate she decided to throw on a dress and go to the hospital. Unfortunately, halfway to the hospital, she went off the road during yet another orgasm and hit a tree.

As she was lying there in her car the policeman came up and asked why she hit the tree. She said, "Because (pant) I'm being (ooh) fucked by (pant) a voodoo penis!" "You're what?" "Being (oooh) fucked (gasp) by a voodoo penis! (pant)" "Yeah, right. Voodoo penis, my ass!"

Pictures

A couple of weeks ago my family had a good photographer come in for a photo shoot with me, my wife, her parents, and our children Sam and Claire.

Today you can see both photos my father-in-law took and the professional photographer's favorites.

This was money well spent. :-)

For anyone in Southern California, I would highly recommend Leo Flores as a photographer.

More random stuff on the sexes

A couple of posts ago I discussed some complications in relations between the sexes. Nobody seemed too offended or disagreed too much, so I'll tackle the topic again, in a more haphazard way. (I touched on a somewhat related topic lst year when I claimed that males may have started as parasites.)

But as before, if you think you'll be offended you should stop reading now. Unlike before I'll actually touch on something interesting that applies to homosexuals at the end, though most of this is not about homosexuality.


My last blog reminded me of a book I read years ago that I wanted to re-read. So now I've bought it and am re-reading it. The book is Shadows of Forgotten Ancestors. It starts off slowly, with a basic overview of the history of the Earth, the history of life, how genes work, and so on. All pretty basic if you're conversant with science, though at some point it is likely to get detailed enough that you'll probably to find yourself in unfamiliar territory.

But what I like about it is the second half. This is where we encounter a discussion of the documented effects of testosterone on personality, an analysis of the social lives of our near primate relatives, and so on. I won't try to summarize, so much as to hit the some high points. Anyone who believes that women are basically men without the penis who can have babies should read through the effects of testosterone on personality. Anyone who has wondered why we say, "Fuck you!" when we're mad should read through accounts of how sex and dominance are intertwined in different primates. I'm not sure what lessons we should be drawn from a comparisons of militaristic chimpanzees with the free love bonobos, both of whom are very closely related to us, but I certainly saw strong parallels between both societies and human groups. All in all I rank this book as being one of of the strongest challenges to my preconceptions of how I want to see the world.

Moving on, a friend told me that a lot of what I said in my previous post is echoed in more detail, at longer length, and more amusingly in Sperm are from Men, Eggs are from Women. I haven't read the book, but the reviews look promising.

If I'm guessing right from the reviews it touches on one of my favorite pieces of evolutionary trivia: that there is good evidence that humans have significant sexual selection for large penises. That such selection exists is not surprising in light of all of the jokes and obvious sexual interest. (I will never forget having it pointed out to me 15 years ago women could estimate the size of a guy's penis from looking at the bulge in his pants. I was quickly assured that I had nothing to worry about in that department, which did absolutely nothing to lessen my self-awareness of people potentially looking at my crotch for the next couple of weeks...) However the actual concrete evidence is the simple fact that the human penis is about 3 times the size that would be expected based on estimates made from our size and the proportions of our close relatives the chimpanzees and gorillas.


Moving on, by coincidence this week on NPR I heard an interview with the authors of Why Women Have Sex: Understanding Sexual Motivations from Adventure to Revenge (and Everything in Between). It sounded interesting in the interview, and at some point I suspect I'll buy it as well.

I don't know if it is in the book, but there was an interesting piece of trivia that came up in the interview. It turns out that if you take a man and dress him up in a Burger King outfit, he's much less attractive to women than if you dress him up in a suit. By contrast men don't care about the clothing on a woman. In comparisons they'll judge her equally attractive in a Burger King outfit and in a nice cocktail dress. This ties very well with what I said in my last post about how women are looking for a good provider (status helps) while men are looking for evidence of fertility (status doesn't matter). Which helps explain why women remember what people wear while most men I know, including me, can't really remember what someone was wearing 30 seconds after they leave.

Moving on to men noticing signs of fertility, how sensitive are we? The answer is more than you'd think. For instance research has found that men react to how fertile a stripper is. It turns out that when you analyze how much strippers make in tips per night, the closer she is to ovulation, the more she makes, with income varying by a factor of 2. By contrast strippers who are on the pill permanently make about what strippers who are not on the pill would make during their period.

How do men notice? I don't know whether the full story is known, but at least some of it is behavioral. Women who are ovulating have been demonstrated to dress more provocatively, act more provocatively, put down the appearance of other women more, and show an increased attraction to men, particularly ones with masculine appearances. All of these behavioral cues reverse during her period. Even when strippers are trying to be provocative, perhaps the ones who are ovulating have a slight edge. Perhaps there are as yet unknown pheromones that men react to. Whatever the cause, men do react.

Moving on, the point about men with a masculine appearance is interesting to me. When researchers examined the subject, both men and women rank feminized faces as more attractive. But when push comes to shove, women are interested in other traits more than appearance, which gives a definite edge to men with masculine features. (Masculine is here defined by things such as a big jaw, square face, prow nose, and heavy brow. More on why it is defined that way shortly.)

Interestingly researchers in other studies have found that people form a variety of first impressions on men based on how masculine or feminine their faces are. For instance fathers are more likely to trust their teenage daughter's with a man whose face is feminine. But what can appearance tell you?

More than you'd think. It turns out that all of the characteristics that are linked with a masculine face are tied to testosterone exposure. Men who are judged as having masculine faces do turn out to have higher testosterone levels in their saliva. And the various personality judgments that are made based on this trait have a surprisingly good grounding in the known personality effects of testosterone.

Speaking personally, I am the kind of man who is more likely to be described as "beautiful" than "rugged". As much as I don't like it, this is concrete evidence of somewhat low testosterone levels when I was growing up, and it affects how people interact with me. In ways that most people don't even notice.

Moving on, the whole masculine/feminine thing leads to an odd piece of trivia that is not too widely known. Most people assume that gay men must be responsible for homosexual abuse. Not so fast. The little data that exists says that heterosexual men are far more likely to engage in homosexual abuse of boys than homosexual men! Now let's be clear, once a boy passes puberty, homosexual men may develop an interest. Legally an adult man and a 16 year old teenager might be child abuse. But that teen has sexually matured. Those examples notwithstanding, homosexual men do not seem to be attracted to sexually immature boys.

Why? Well when you ask adult heterosexuals who abuse boys why they are attracted to boys, all of the answers have to do with the feminine characteristics that boys have. By contrast when gay men are asked what they like about other men they cite masculine characteristics which boys don't have. It seems that attraction is tied to perceptions of masculinity/femininity in a very direct way that leaves little to no room for someone to be a gay pedophile. (I know of no research on the topic, but I have to wonder if this connects in any way to the fact that pedophilia appears to be very rare among women.)

As always I could ramble on, but this is enough for this post.

Solving Project Euler problems

Late last year I got into Project Euler in my spare time for a couple of months. I solved over 150 of the problems, then I lost interest and have only sporadically solved any since. However I know I could do many more if I put some more time into it. I also contributed P240 which a number of people liked.

That's not a great track record, but it is not a bad one either.

This post is my advice for people who can solve basic Project Euler problems but want to get better at solving them. I happened to use Perl to solve problems, but the advice should work in a variety of languages. The techniques I used use closures a lot, but that's because that's the kind of guy I am.

First if you are unable to solve the first 5 then I would suggest that you're missing some basic background. I would suggest learning a programming language first, then some math. Only after that should you try Project Euler.

If you're going to tackle Project Euler problems, there are some things that come up over and over again. In particular I would recommend learning how to use dynamic programming to solve problems. That comes up a lot. Secondly I would recommend learning how to handle infinite streams of data. Thirdly do not be afraid of attempting brute force techniques with clever bucketing and pruning. If your program runs in a minute, you've found what they were looking for.

With those basic techniques out of the way, as you solve problems you'll develop a library of functions you use over and over again. Here are the functions in my library, in no particular order, with no particular attempt at good design (after all PE is just one throw away program after another...):

• gcd Calculates the GCD using the Euclidean Algorithm


• prime_iterator Returns a function which, every time it is called, will return the next prime. Internally I use the Sieve of Eratosthenes to generate this list. Note that in this code an "iterator" is always a function which iterates through some (possibly infinite) set as you call it.


• is_prime Takes a number, makes sure I've generated all of the primes up to that number, then checks whether it is prime.


• is_prime2 Takes a number, generates all of the primes up to the square root of that number, then uses trial division to check whether it is prime. This routine is slower than the previous if you're going to check a lot of primes, but uses much less memory. P118 is a good example of where you would use this version.


• ith_prime Access the list of primes as if it were an array. (I had ith_prime(0) return 2, ith_prime(1) return 3, and so on. Remember what I said about not being carefully designed?)


• factor Takes a number, returns a hash of prime factors and multiplicities. Trial division by primes up to the square root was efficient enough for all of the PE problems that I tackled.


• factors Returns the prime factors of a number as an array with duplication to represent multiplicity.


• n_pow_m_mod_k What the name says. I used it for P133 and stuck it in my library because I wanted to reuse it for P66 but it didn't work for the second one. (Search for Pell's Equation for how to handle that problem.)


• minimal_divisible_repunit See P129 and P130 for what this is about. Internally this reuses the n_pow_m_mod_k function in its calculations.


• pythagorean_triple_iterator Iterates through all Pythagorean triples ordered by the lengths of their sides. I'll have more to say on the algorithm in a bit.


• generate_stream A promise is a function which, every time it is called, will return some set of future values you haven't reached yet, returning nothing when it runs out. This function takes a promise and lets you treat it like an infinite array, ask for the 1st, 5th or 500th element and it will generate the promise until it has enough stuff then return the value.


• generate_memoryless_stream Like the previous but instead of accessing it like an array you access it like an iterator. This is useful for cases where it is convenient to calculate a block of values at a time. A perfect and pertinent example is the Sieve of Eratosthenes, which calculates blocks of primes at a time.

Now on to the Pythagorean triple iterator. How do I iterate through them? Well first I use Euler's formula to generate all primitive triples in the order that I want, and then I merge together all of the multiples of that stream to get all triples. To understand how that merging works, it would be good to go back to the infinite streams article and actually read it.

This sounds simple in theory. But in practice you have a problem. I'm merging a lot of data. I do that by maintaining a partially sorted pool of things I want to merge in, and then always taking the least next element. There is a data structure for that. It is called a heap. A heap is a tree, which has the heap property that each node is less than or equal to its children. This makes the top node at the root of the tree the smallest element. (Why do CS people always draw trees upside down so that the root is at the top? Really it would make more sense to call it a "root system" or else to draw it the other way around. Oh well, that's the convention.)

Luckily CPAN has multiple heap implementations. Unfortunately the one named Heap sucks, and I couldn't be bothered to look through the rest to find one that met my needs. So I took pointers from an implementation by Abigail, and implemented my own. The clever (and standard) trick in that implementation is that arrays can be used to represent a tree. The two nodes below the n'th element in the tree are at 2n+1 and 2n+2. So you can take an array of data, turn it into a heap, and then manipulate it as if it was a tree.

Writing your own heap implementation is a good exercise, so I'll just give the methods in my heap implementation for anyone who wants to duplicate it.

• new Construct a new Heap. There is one optional argument, which is the comparison function. (Which is passed in as a closure, as you might expect.)


• append Push a new element on the end, then let it "bubble up" to its natural position. Here is what I mean by "bubbling up". If it is currently at position $n > 0 then its parent is at position int(($n-1)/2). If it is greater than or equal to its parent you're done. Otherwise you need to swap with its parent and continue until it either has a smaller parent or reaches the root.


• top Peek at the root element.


• swap_top Take the root element out, replace it with something else, and let the something else "fall down" to its natural level. Returns the previous top.


• extract First pop the last element off of the array, then call swap_top. This trick gives you the least element in the heap and makes everything else be represented in an array that is 1 smaller than the previous.

Hopefully this helps others who are trying to tackle Project Euler problems and haven't made much headway yet.

Why are relations between the sexes so complicated?

Note: The subject of this blog post is likely to offend many people. If you think you're one of them the do us all a favor and don't read it.

Disclaimer. Everything in this essay is about my understanding of mainstream heterosexuality. If you disagree, remember that I'm talking about my opinions, not facts. Also, a certain proportion of people wind up homosexual, asexual, or otherwise don't fit the sexual norms. From the surveys I've seen, definitely over 90% and probably over 95% of people are, some experimentation notwithstanding, relatively normal heterosexuals. I have no idea how much or little any of this applies to the remaining minority.

You have been warned.


When I was young I wondered why relations between the sexes are so complicated. After all both genders desire the same thing, why not pair off in some orderly fashion with much less pain and complication? I could see that things didn't work that way, but it seemed to me to be a more sensible way for the world to work than how it actually does.

As I've grown older I've learned about complication after complication. As I learn about complications and see why they happen, the overall picture becomes clearer. Yes, the simpler world I imagined would be convenient, but it can't happen. Why not?

Well let's take my first assumption, that the sexes desire the same thing. We can actually tell what they desire from the questions they ask, and Google correlates those questions and summarizes what they find in autocompletes. When you compare what women and men want their boyfriends and girlfriends to do you get an interesting picture. Men and women want different things.

If we oversimplify, men want sex and women want commitment. Oversimplifying a tad less, men want sex and are willing to provide commitment as a way of getting it, while women want commitment and are willing to provide sex as a way of getting it. If you review the bf/gf comparison and pair the first few questions up, they answer each other in amusing ways. Partially that is coincidence. And partially it is that meeting of different goals.

Evolutionarily that picture makes a lot of sense. It takes little work for men to make children and a lot of work for women to. Therefore biologically men should be selected for a willingness to make children. However raising a human child takes enough effort to need multiple adults. Therefore it is to a woman's advantage to secure that commitment. A man who helps raise his own children benefits his genes, so he should be able to be convinced to do so. The point of lining up help for a woman is to make having children possible, so once the help is lined up, a willingness to have children should follow.

It should be noted that what I've described is not particular to humans. The same evolutionary tendencies and results can be seen in a wide variety of pair bonding species. Though when you apply it to humans people are more likely to be offended than when you describe some type of birds. Though for obvious reasons I find the human case of more personal interest.

It should also be noted very clearly that these strategies are not conscious on the part of the people involved. We have been genetically selected for traits that will cause us to act in these ways. And we directly react to those traits. For instance when a man meets an attractive woman, the parts of his brain that are not associated with libido are invited to take a short vacation. Sometimes with amusing results, such as a temporary inability to speak coherently. He certainly doesn't want this sudden burst of stupidity, but the immediate refocusing of his priorities aligns him with the evolutionarily successful agenda he is literally bred to follow.


Now let's introduce a complication. Sexual partners are not created equal. We have preferences about who of the opposite sex we'd like to have relations with. Preferences vary widely, but some interesting generalizations can be made.

First of all, what do men want? Well health is a good thing. Traits such as clear skin and symmetric faces are signs of a good immune system. Humans have established secondary sexual characteristics such as breasts as signs, and men's attraction to them is obvious. Signs of being good at childbearing as well. Cross-cultural studies have supported the importance of the waist-hip ratio, and even a brief acquaintance with the difficulties of human childbirth with large heads can illustrate why. And, of course, youth.

The subject of attraction to youth is an interesting one. I won't elaborate much on that topic, instead I'll direct your attention to Neotenty and Two-Way Sexual Selection in Human Evolution by David Brin, which is one of the most fascinating pieces of speculation on human evolution that I've read. I don't think he is entirely right, but I think he is right on several things I never thought of until I read that essay. The short summary that doesn't do justice to the essay is that men are attracted to youthful women, which poses the challenge of telling apart young mature women from as yet immature women. We do this through secondary sexual characteristics such as breasts. But this mechanism is fallible, and results in high incidences of pedophilia. (The essay has several parts, I would advise reading all of it.)

Since I have it, I'll give one random instance supporting Brin's thesis from the Google data that I have that he didn't. If you type into Google How do I get my ____ to with either girlfriend or wife in the blank, high among the suggestions will be shave. (Presumably the pubic area is referred to.) Why do so many men want this? Well general lack of hair is a sign of youth. But lack of pubic hair is a direct sign that a woman is not yet sexually mature. Isn't this awfully close to pedophilia?


Moving on, what do women want? Well, obviously, commitment from someone who will be a good care giver. Therefore it is no surprise that cross-cultural surveys (see Brin's essay for a reference) have found that top characteristics women say they desire are kindness, intelligence, and self-confidence. And other desired characteristics include accomplishment, reputation, health, vigor, reliability, and sense of humor. (Random note, the desire to prove accomplishment and reputation pushes men to create many social groups with their own hierarchies that men can try to get on top of.) All of these traits are associated with men who will have the ability and inclination to make good care givers. Note that physical handsomeness is not on the list. Women appreciate it but rate it more lowly, except when looking for extra-marital affairs. (A complication we haven't yet reached.)

Of course the above list isn't complete. For instance there is evidence that women react to pheromones, particularly ones that suggest that a man has a very different immune system. (When people with different immune systems mate, their children are likely to get protection from a broad spectrum of diseases.) Also what women react to and what they say they react to aren't always perfectly aligned, but that detail will have to wait.


OK, time for another complication that causes the pattern to fold in on itself into a pattern of fractal complexity. We have preferences in mates. We each would like to wind up with the best mate(s). But we can't all wind up with the best. Therefore each person tries to wind up with the best person they can, and the extent which we're willing to compromise to get a person depends on the person in question.

What do I mean by this? Well recall that men are aiming for sex, and are willing to provide commitment to get it. Women are aiming for commitment, and are willing to provide sex to get it. The million dollar question as a couple engages is who budges first. In general the higher status the other, the more willing we are to compromise. So the same man who may be willing to claim undying devotion for a chance at a gorgeous woman may be willing to sleep with an unattractive one, but won't commit to her. And a woman who may be willing to have sex with a high status man in hope of commitment may be only willing to have sex with a lower status man after commitment is established.

Tiger Woods provides a good illustration of the latter dynamic. Many women were interested enough in his wealth and talent to give him sexual access. However part of the dynamic was that he tried to make each believe that she was the other woman in his life, so there was a hope that at some point commitment could happen. When the news of his affairs broke and they reach realized how badly they'd been had, they got upset and one by one went public.

Now if you go back and look at the list of traits women want, you have a problem. The characteristics they are looking for are not immediately visible. Therefore women need to read between the lines to establish them. This pushes them towards judging based on secondary traits. For instance a man who is attractive to women who know him well is likely to have several positive characteristics, and therefore is judged as potentially more interesting. And anything that suggests such attractiveness will be seen as positive.

If you read a guide for pickup artists (I highly recommend that every woman should, just so you know what to watch out for), you'll find some odd consequences of this. For instance a man who demonstrates initial disinterest in a woman is demonstrating that he has access to more attractive women. This is evidence that he has what women wants, and therefore must be of more interest. The fastest way to demonstrate disinterest is to make an apparently thoughtless and somewhat insulting comment. If he follows up with nice comments then he has portrayed himself as being of interest but within reach. If the woman believes this message then she is more likely to offer sex without having required commitment first. Which is exactly what the pickup artist wants.

What woman would say that she wants a guy who subtly puts her down? None, obviously. Yet the technique is apparently effective on a lot of women! (Or at least on enough to make pickup artists happy.)


Moving on, what about the way that women tend to be insecure in relationships and the various games they play? I see at least two purposes of these. The first is to test the strength of a man's commitment. It is easy for men to say that they are committed, but if a guy stays through an emotional coaster ride and some demands then he's much more likely to actually be committed. But it isn't simple, because if she pushes it too far, then she has no relationship. How far she can push it will depend on the relationship, which varies widely.

The second purpose is to set clear expectations about how she wants him to behave. This pushes him towards accepting higher levels of commitment, and also makes it clear to him what she will and will not accept.

For an example of a book that helps women use these strategies, see The Rules. I would recommend that all single guys read it so that you can see what you need to defend yourself against. As you'll note from the reviews, it is very controversial, there is roughly an even divide between people who are offended and women who are happy with the men they landed using the strategy.


This brings us to an important point. I am trying to describe the natural dynamics as I see them. Those dynamics tend to be more clear when you look at people who consciously try to manipulate them. The two examples that I've used are pickup artists and The Rules. Most people's natural reaction to those strategies is to dislike how manipulative they are. A second reaction that follows closely is to point out that they result in significant power imbalances. Both reactions are perfectly accurate. They are manipulative and do cause power imbalances. However the manipulation mimics what happens naturally. Power imbalances are common within relationships. The point of the manipulation is to create a power imbalance that gets the manipulator's agenda to the fore. As much as we decry the means, most of us would be interested in the result.


Continuing, let's move on to a tricky complication. Cheating.

It is clear from the basic male agenda why men would cheat. Men cheat because more sexual encounters means more chances to have babies. But women don't want their men to cheat for fear that he'll wind up attached to someone else and leave. And men who are properly bonded will resist cheating, because that is part of what it means to be bonded. So men will not universally cheat, but will at least feel the temptation.

From the basic female agenda, cheating is not immediately obvious. After all it is not a good way to get commitment. But a woman who has a guy doesn't need commitment from anyone else. She has her caregiver, now she wants good genetic material for babies. Cheating offers her two advantages. The first is diversity of genetic material - you never know what combination of genes will work out best and experimentation has value. The second is that she can get superior genetic material than the guy she can get to commit. Of course the downside is that if she gets discovered, she may find herself out of a caregiver.

I've seen widely varying estimates on the levels of cheating in people. I know that some pair-bonded bird species have been found with up to 40% of the population born due to cheating. Humans are hopefully quite a bit lower than that. However one estimate I saw several years ago from England found that about 10% of children are not the children of the person who thought he was the father. That's pretty significant. And in any case it is high enough to contribute to high school biology teachers' reluctance to demonstrate the laws of genetics using the families of their pupils as examples. And is also high enough that a common first reaction among men to seeing his child is to look for a feature that verifies it is truly his. (I've experienced this reaction first hand, and felt silly but did it anyways. I also know someone who noticed that the child wasn't his, with appropriately bad results...)

At this point you get an interesting divergence between men and women. The reasons why men would want relationships and want to cheat are basically the same, so they are attracted to the same women for both purposes. (Though his standards are usually higher for commitment than cheating.) However women are different. A woman is looking for a relationship and affairs for different reasons. Therefore they are attracted to different men for those purposes. In particular for a relationship women want men who they think will make good caregivers. But for affairs women care much more about physical attractiveness. So attractiveness does matter to women, but not in as straightforward a way as it does for men. (Remember that when discussing Brin's essay I said I would come back to the survey result that women care more about appearance for extra-marital affairs than for relationships? Well I just did...)


I could go on but I've rambled quite enough and probably offended a good number of people in the process. Hopefully people found it interesting food for thought, whether or not you agree with all of it. I know that as recently as a few years ago I would have strongly disagreed with several items I stated, and wouldn't be surprised if I disagreed with several others in a few more years.