[XSL-LIST Mailing List Archive Home] [By Thread] [By Date] [Recent Entries] [Reply To This Message]

Re: Efficient way to check sequence membership

Subject: Re: Efficient way to check sequence membership
From: ht@xxxxxxxxxxxx (Henry S. Thompson)
Date: Wed, 02 Mar 2011 23:33:32 +0000
Re:  Efficient way to check sequence membership
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dimitre Novatchev writes:

> One way is to have the strings sorted. Then use binary search -- this
> is O(log(N)).

Maybe that will have an advantage for much bigger sets, but for my
test case it was considerably slower -- 18ms net vs. 9ms net for the
(some $s . . . satisfies) and $w=$stops versions, and 2ms net for the
best (key-based) one.

I'd be very interested if you could compare binSearch with the
key-based version I sent on your large dictionary example. . .

ht
- --
       Henry S. Thompson, School of Informatics, University of Edinburgh
      10 Crichton Street, Edinburgh EH8 9AB, SCOTLAND -- (44) 131 650-4440
                Fax: (44) 131 651-1426, e-mail: ht@xxxxxxxxxxxx
                       URL: http://www.ltg.ed.ac.uk/~ht/
 [mail from me _always_ has a .sig like this -- mail without it is forged
spam]
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.6 (GNU/Linux)

iD8DBQFNbtPMkjnJixAXWBoRAlT4AJ9/c0Thgmzz38+728ZYyGuexwmclACdFiNZ
c5SlTZQDHau9553VUlABs5k=
=aNAZ
-----END PGP SIGNATURE-----

Current Thread

PURCHASE STYLUS STUDIO ONLINE TODAY!

Purchasing Stylus Studio from our online shop is Easy, Secure and Value Priced!

Buy Stylus Studio Now

Download The World's Best XML IDE!

Accelerate XML development with our award-winning XML IDE - Download a free trial today!

Don't miss another message! Subscribe to this list today.
Email
First Name
Last Name
Company
Subscribe in XML format
RSS 2.0
Atom 0.3
Site Map | Privacy Policy | Terms of Use | Trademarks
Free Stylus Studio XML Training:
W3C Member
Stylus Studio® and DataDirect XQuery ™are products from DataDirect Technologies, is a registered trademark of Progress Software Corporation, in the U.S. and other countries. © 2004-2013 All Rights Reserved.