10/20 What's a good data structure / pattern for a winamp-style
"Jump-To" dialog? User types in a "foo bar", and the window
returns existing files such as "Foomatic Hyperbaric", "Bare Food"
etc.
\_ I checked out XMMS, and it just uses an iterative approach:
separate the words by whitespace, then
foreach filename {
f = lowercase (filename)
foreach word {
if (!strstr(f, word) return NO_MATCH
}
return MATCH
}
It turns out that processors are just fast.
\_ I doubt there's any magic. I think most likely it just does a
substring search on each filename. of course, if you want it to
be interactive like winamp, you can progressively filter the
results.
\_ the poster wants to avoid iterating on each filename
\_ obviously, but how do you expect to be able to filter on
arbitrary strings without it? You're going to need to go
through each filename. Or maybe you can index all the
filenames by what letters they contain; the user types 'f',
and the program returns a precalculated list of all items
that contain the letter 'f'.
\_ duh, perl.
\_ a trie is good for searching strings with so-and-so prefix.
don't know if that's so great for your examples though.
\_ perl.
\_ Perl is actually one of the slowest languages for regular
expression matching.
\_ And the fastest few would be...?
\_ C, C++, ocaml.
\_ wait-- would you really consider this a data-structure?
\_ no, I don't answer the questions, I provide the solutions.
most motd posters who ask detailed and specific technical
questions are already in a thought rut and need a kick in
the ass to get out and solve the real problem.
\_ apparently you miss sarcasm as well.
\_ if there was any I would've spotted it. since this is
the motd, i expect people to post stupid things and
mean them.
\_ Thank you Comic Book Guy!
\_ See what I mean? |