Berkeley CSUA MOTD:Entry 26263
Berkeley CSUA MOTD
 
WIKI | FAQ | Tech FAQ
http://csua.com/feed/
2025/07/09 [General] UID:1000 Activity:popular
7/9     

2002/10/21-22 [Computer/SW/Languages/Perl] UID:26263 Activity:very high
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?