« A pure heart is an excellent thing, and so is a clean shirt | Main | A change of scene »

January 29, 2006

Comments

I don't know anything about LISP, so I can't answer the first question. I'm not sure I understand the second -- when you say list, what do you mean? A file? If so, the answer is generally yes, but not without the risk of possibly having to open it more than once.

I mean like this: if you have a source of anything, you can select one item from it in something like the following way, in a C-like language:

object getone(object source) {
object cur, tmp;
int i = 1;
while (!exhausted(source)) {
tmp = source.next();
if (i == 1 || random() > float(i-1)/i) { cur = tmp; }
i++;
}
return cur;
}

(forgive lack of formatting.) You don't need to hold all the objects from which you're selecting one in memory in order to get one randomly. My question is, if you want to get n randomly, is there a similar way?

When you say "randomly," do you mean, "uniformly at random?" (So that if the list-of-unknown-length eventually turns out to have length M, the chance of a particular element of that list being in the chosen set is n/M?)

Godd*mn close italics.

Let me try one more time. Sorry for screwing up your comments.

I see now that that "i == 1" clause is redundant if you change the > to >=.

And yes, that is what I mean. (I was motivated to think of this for something where currently I just read in a bunch of lines from a file, shuffle it randomly, and then take the first n.)

Also, isn't quasi-quotation used all over Quine's Mathematical Logic? At least, that's the first place I ever encountered it...

When it comes to quasi-quoting in Lisp and Scheme, I think this is a pretty good motivating paper...

Yeah, I came across a paper that said that Quine introduced it in 1940. But I was curious because I was reading a paper by…Quine, "Philosophy of Logic", which concludes:

Tarski's paradigm cannot be generalized to read:
'p' is true if and only if p
since quoting the schematic sentence letter 'p' produces a name only of the sixteenth letter of the alphabet, and no generality over sentences.
and my first thought was, this looks like a job for quasiquotation! But I didn't know if it had any respectability.

Well, ([pulling down Quine from the bookshelf]) my copy of Mathematical Logic says its "Revised" version was published in 1940, so maybe that's the source of that? Anyway, Chapter 1, Section 6, "Quasi-quotation."

Quasi-quotation would have been convenient at earlier points, but was withheld for fear of obscuring fundamentals with excess machinery. Now, however, it may be a useful exercise to recapitulate some sample points from Sections 1-5 in terms of this device. etc.
And his corner-brackets for qq are all over the rest of the book.

Dunno about the "choose n items at random" problem, but should be fun to think about on the subway ride home. I might have a book of online algorithms at home with the answer, too, who knows...

Thanks!

Verify your Comment

Previewing your Comment

This is only a preview. Your comment has not yet been posted.

Working...
Your comment could not be posted. Error type:
Your comment has been posted. Post another comment

The letters and numbers you entered did not match the image. Please try again.

As a final step before posting your comment, enter the letters and numbers you see in the image below. This prevents automated programs from posting comments.

Having trouble reading this image? View an alternate.

Working...

Post a comment

Your Information

(Name and email address are required. Email address will not be displayed with the comment.)