Beefy Boxes and Bandwidth Generously Provided by pair Networks
There's more than one way to do things
 
PerlMonks  

comment on

( [id://3333]=superdoc: print w/replies, xml ) Need Help??

grep may be a common solution, but it's not necessarily the most efficient. It probably doesn't matter for small sets or infrequent tests. But if efficiency does matter, one must keep in mind that the grep solution always has an O(n) outcome, even if the item you're looking for is the first element found. grep always searches the entire list.

Any linear search solution where the loop terminates as soon as the item is found will have a worst case of O(n), but an average case of O(n/2) (which isn't really true big-oh notation)...assuming randomly ordered list.

A binary search solution will achieve O(log N), again, assuming that the binary search quits as soon as the item is found. That's an order of magnitude faster than the linear search solution.

A hashing algorithm, well written, such as Perl's %hash can achieve O(1), and is not sensitive to order nor should it be affected by dataset size (see the O'Reilly Wolf book, Mastering Algorithms with Perl, pp. 158-159, 168). So for many purposes a good old fashioned Perl hash might be one of the best solutions. ...assuming the dataset is in memory.

For those unfamiliar with big-oh (O(x)) notation, it's often used as an analysis of order of growth of work an algorithm must do as a dataset grows. "O(1)" means no growth. "O(n)" means a one-to-one growth ratio. "O(log n)" is an order of magnitude slower growth than "O(n)", for example. The reason that I said O(n/2) for average case was not really valid big-oh notation is because big-oh isn't concerned with average cases. Big-O notation represents an "order of growth won't be worse than..." relationship. Just a quick refresher. ;)


Dave


In reply to Re^2: writing perl function like sql IN by davido
in thread writing perl function like sql IN by JAMBOID

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post; it's "PerlMonks-approved HTML":



  • Are you posting in the right place? Check out Where do I post X? to know for sure.
  • Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
    <code> <a> <b> <big> <blockquote> <br /> <dd> <dl> <dt> <em> <font> <h1> <h2> <h3> <h4> <h5> <h6> <hr /> <i> <li> <nbsp> <ol> <p> <small> <strike> <strong> <sub> <sup> <table> <td> <th> <tr> <tt> <u> <ul>
  • Snippets of code should be wrapped in <code> tags not <pre> tags. In fact, <pre> tags should generally be avoided. If they must be used, extreme care should be taken to ensure that their contents do not have long lines (<70 chars), in order to prevent horizontal scrolling (and possible janitor intervention).
  • Want more info? How to link or How to display code and escape characters are good places to start.
Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others browsing the Monastery: (None)
    As of 2024-04-25 00:55 GMT
    Sections?
    Information?
    Find Nodes?
    Leftovers?
      Voting Booth?

      No recent polls found