Scattered things...

[pmb]

• I remain skeptical of quite a few things that Hillary Clinton stands for - increased censorship is pretty much always wrong, and she's too willing to roll over and find the "middle ground" between the centrist position and the loony right - but linking the federal minimum wage to the congressional wage is a stroke of genius.
• 12 catches of 5 clubs. And I could count them myself instead of having someone else tell me how many I got. That was most pleasing.
• Conference submission date is May 16th. Work work work. Then I am done with the research project that is turning out to be kind of orthogonal to the research I want to do. Then it's all area exam all the time. Work work work. Then the term is over.
• And this summer I am teaching "Intro to Programming" in Python in a 4-week intensive (7/24-8/16). Using John Zelle's book based on the advice of several people. I am psyched. The rest of the summer is going to be spent biking and hanging out and reading and recovering from a relatively rough year of grad school.

Comments

[minorninth.livejournal.com]

Please, no! It's not worth the overhead for the millions of small lists/arrays that don't need this!

[agthorr.livejournal.com]

It's one extra pointer comparison per operation. That's a very small penalty to pay.

B-trees divide things into blocks (of, say, 512 or 4096 entries) and within a block they work just like arrays. So for the common case of small lists, you have one extra check to determine that the root of the B-tree is also a leaf node (i.e., it's entries are data not more B-tree nodes). Once that's determined, you jump to code that works just like the current array code.

B-trees are good because they're fast for small lists *and* they give you O(log n) performance for big lists.

[minorninth.livejournal.com]

To be honest, I've only ever used B-trees as a disk-based data structure. I guess you could implement it so that it works essentially like Python arrays do now once you're on a leaf node, and pay very little penalty. Perhaps the least efficient operation (relative to Python's current implementation) would be repeatedly appending onto the end, although I guess you could specially optimize that case, too.

Hmmm, would it be possible to subclass Python's list class (as a C extension) and have the ability to create a btree that acts just like a list? My understanding is that subclassing built-in types is supposed to work now; it didn't a couple of versions ago, and I haven't tried it...

[agthorr.livejournal.com]

would it be possible to subclass Python's list class (as a C extension) and have the ability to create a btree that acts just like a list?

Sure, that's entirely do-able.