| Home | Forums | Reviews | Guides | Newsgroups | Register | Search |
 |
| Thread Tools |
|
Guest
Posts: n/a
|
|
|
|
||
|
|
| |
|
Guest
Posts: n/a
|
|
|
|
|
||
|
|
| |
|
Guest
Posts: n/a
|
|
|
|
|
||
|
Guest
Posts: n/a
|
|
|
|
|
||
|
Guest
Posts: n/a
|
|
|
|
|
||
|
Guest
Posts: n/a
|
Lasse Reichstein Nielsen wrote:
> Thomas 'PointedEars' Lahn <> writes: >> OMG. Have you just forgot that there are RegExp? > > Most likely not. He gave a generic way to test for a finite number of > strings. It wokrs whether there are structure to the strings or not. Undoubtedly. But his method consumes much more memory and computing time than mine, no matter if the strings are structured or not. IOW: Compared to my method, his is highly inefficient in *every* case. > Regexps take more work to make, and are harder to read. Not generally, no. > And *much* harder to extend with new numbers, if it becomes necessary No, see below. >> return(!/^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|40[1-35-9]|41[02])$/.test(o.value)); >> } > > Are you sure that your regexp matches exactly the correct strings?  Pretty sure. > (It probably does, but comparing RegExps to string is ExpSpace complete ^^^^^^^^^^^^^^^^ Define that. > in general, so very hard to do). Not at all. It is primarily a matter of structured building of the RegExp, finding similarities first. See the numbers again the RegExp should match. I remove the duplicate 93199 and group the numbers so one sees clearly what they have in common. 93101, 93102, 93103, 93105, 93106, 93107, 93108, 93109, 93110, 93111, 93116, 93117, 93118, 93120, 93121, 93130, 93140, 93150, 93160, 93190, 93199, 93401, 93402, 93403, 93405, 93406, 93407, 93408, 93409 93410, 93412 Obviously all numbers begin with 93: /^93/ There are numbers continuing with 1 and with 4: /^93(1|4)/ Numbers continuing with 1 continue with either 0 to 6, or 9: /^93(1(0|1|2|3|4|5|6|9)|4)/ Numbers continuing from there with 0 continue with digits from 1 to 9, except of 4: /^93(1(0[1-35-9]|1|2|3|4|5|6|9)|4)/ Numbers continuing from there with 1 continue with 0, 1, and 6 to 8: /^93(1(0[1-35-9]|1[016-8]|2|3|4|5|6|9)|4)/ Numbers continuing from there with 2 continue with either 0 or 1: /^93(1(0[1-35-9]|1[016-8]|2[01]|3|4|5|6|9)|4)/ Numbers continuing from there with 3 to 6 and 9 continue with 0: /^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0)|4)/ If the fourth digit was 9, also 9 can follow: /^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|4)/ (One could have also grouped 93190 and 93199 together: ...|[3-6]0|9[09])...) Numbers having a 4 as third digit continue with either 0 or 1: /^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|4[01])/ Because the fourth digit is followed by different sets of digits we write /^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|4(0|1))/ instead. If the third digit is 4 and the fourth digit is 0, digits from 1 to 3 and 5 to 9 may follow: /^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|4(0[1-35-9]|1))/ If the third digit is 4 and the fourth digit is 1, the fifth may be only 0 and 2: /^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|4(0[1-35-9]|1[02]))/ For we match whole numbers, we finally add the end-of-text meta character: /^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|4(0[1-35-9]|1[02]))$/ Now compare that to my RegExp which was built (but only in mind) using the same procedure: /^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|40[1-35-9]|41[02])$/ The only difference is that I wrote `40[...]|41[...]' instead of `4(0[...]|1[...])' which is semantically equal, though. You will not tell me that the above was hard work, will you? Because the RegExp was built *this* way, it is easy as well to find out the strings it will match, going from left to right, creating a branch in a build tree every time we find an alternative (including sets of characters): 93 931 9310 93101 93102 93103 93105 93106 93107 93108 93109 9311 93110 93111 93116 93117 93118 9312 93120 93121 9313 93130 9314 93140 9315 93150 9316 93160 9319 93190 93199 934 9340 93401 93402 93403 93405 93406 93407 93408 93409 9341 93410 93412 We take only the leaves of the build tree: 93101 93102 93103 93105 93106 93107 93108 93109 93110 93111 93116 93117 93118 93120 93121 93130 93140 93150 93160 93190 93199 93401 93402 93403 93405 93406 93407 93408 93409 93410 93412 Group them: 93101, 93102, 93103, 93105, 93106, 93107, 93108, 93109 93110, 93111, 93116, 93117, 93118, 93120, 93121 93130, 93140, 93150, 93160, 93190, 93199, 93401, 93402, 93403, 93405, 93406, 93407, 93408, 93409 93410, 93412 And compare with what was provided (already grouped here and removed dupes): 93101, 93102, 93103, 93105, 93106, 93107, 93108, 93109, 93110, 93111, 93116, 93117, 93118, 93120, 93121, 93130, 93140, 93150, 93160, 93190, 93199, 93401, 93402, 93403, 93405, 93406, 93407, 93408, 93409 93410, 93412 q.e.d. We have only five-digit numbers with few linear exceptions here, one should manage it to see that the above RegExp matches without writing the matches down, especially if one has built the RegExp by themselves as described above. If reading the entire RegExp is still too difficult, one can also manage it to divide the RegExp into many (say each for every third or fourth digit) and have the tests combined with `&&'. So new numbers are not be a problem at all. If in doubt, one can simply add another alternative: If 93429 should be forbidden, too, the RegExp can be simply changed to /^(93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|4(0[1-35-9]|1[02])|93429)$/ ^ ^^^^^^^ which, of course, could (later) be optimized to /^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|4(0[1-35-9]|1[02]|29))$/ An additional test may be as well combined with `&&' without wasting to much computing time. PointedEars |
|
|
|
|
|||
|
Guest
Posts: n/a
|
|
|
|
|
||
|
Guest
Posts: n/a
|
Lasse Reichstein Nielsen wrote:
> Thomas 'PointedEars' Lahn <> writes: >> Lasse Reichstein Nielsen wrote: >> But his method consumes much more memory and computing time than >> mine, no matter if the strings are structured or not. IOW: Compared >> to my method, his is highly inefficient in *every* case. > > Have you tested it? I do not have with JavaScript, and I must admit that `*every* case' was a bit exaggerated. > It consumes much less computing time, Well, apparently that depends on the implementation and on the complexity of the RegExp. AFAIS Mozilla/5.0's engine is on the average much faster on RegExp than other engines of ECMAScript implementations. > and the memory is constant. I think you underestimate the complexity of > interpreting a regular expression (or more likey: running the finite > state automaton it has been compiled into) on a string. > [...] > So, your method is, by far, less efficient than a table lookup, and > even in IE, which (IIRC) uses a linear lookup for object properties. It depends on how you build the RegExp, i.e. on how it is composed. What you overlook here is that I used an RegExp optimized for length. Of course, the matching can be also done with the longer /^(93101|93102|93103|...)$/, respectively, where the RegExp *wins* in matters of speed, size and amount of maintenance effort. >>> Regexps take more work to make, and are harder to read. >> >> Not generally, no. > > Definitly yes. Wrong, see above and below. > I am very familiar with regular expressions, but I still have to think > to read and understand one. The table is obvious. A list of simple-formed alternatives separated by `|' is obvious, too, if not even more than a table solution. > And while the table might take more space (that is a relevant parameter), > it is easier to write. /(foo|bar)/ *is* easy to write. > Given the list of numbers, it won't take long in Emacs to turn > it into a table. Although I'd prefer `vi', same goes for RegExps. >>> And *much* harder to extend with new numbers, if it becomes necessary >> >> No, see below. > > To extend the regular expression, you have to either find the place in it > that requires changing, or rebuild it from scratch. You do not have to. As I wrote, when in doubt, simply add another alternative expression at the lowest subexpression level. Since it is not evaluated if the previous does match, it then only takes a little bit more of memory, not really of computing or maintenance time. > In a (sorted) table, you just have to find the correct place and add the > line (or add it anywhere if you don't sort the table). In a RegExp, you just have to find the place where the `(' and `)' for alternatives must be placed and add another alternative. Or for testing matches you simply AND-combine the previous test with another one testing the new number expression (or a subexpression of it). > It might not be a big difference, but it is definitly there. > Regular expressions requires thought. The table can be automated. You can do that with RegExps, too. Using the RegExp(...) constructor function and a string argument, you can even accomplish that with JavaScript. >>> (It probably does, but comparing RegExps to string is ExpSpace complete >> ^^^^^^^^^^^^^^^^ >> Define that. > > It's a complexity class. > [...] Thanks. >> Not at all. It is primarily a matter of structured building of the >> RegExp, finding similarities first. > > It takes thought and familiarity with regular expressions. It takes thought and at least average familiarity with JavaScript to create an object/array (literal) from a given set of strings. Your turn. >> You will not tell me that the above was hard work, will you? > > [...] Building the table was *no* work at all. I seriously doubt that  >> Because the RegExp was built *this* way, it is easy as well to find out >> the strings it will match, > > This regular expression is also special in that it only recognizes a > finite number of strings. That makes it easier to handle than ones > with "*" or "+" in them. So, the general hardness of the problem > doesn't necessarily apply to this case. You can easily add alternatives or additional tests no matter how the original RegExp was composed. >> So new numbers are not be a problem at all. If in doubt, one can simply >> add another alternative: If 93429 should be forbidden, too, the RegExp >> can be simply changed to >> >> /^(93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|4(0[1-35-9]|1[02])|93429)$/ >> ^ ^^^^^^^ >> >> which, of course, could (later) be optimized to >> >> /^93(1(0[1-35-9]|1[016-8]|2[01]|[3-69]0|99)|4(0[1-35-9]|1[02]|29))$/ > > Yes. It's a relatively simple case. > But regualr expressions are not as obvious to a lot of other people. It is all about how to add another alternative. The optimization for length (which turned out as the opposite regarding computing speed) that I performed here is _not_ required. > The test: > --- > //<script> Why have you added the `//' *in* *front* of the `<script>' tag? > [...] Thanks. I tried that and got about the same as you did in the mentioned UAs. Now guess what changed when using number atoms as alternative expressions: The RegExp solution then proved to be about 4 to 6 (according to repeated tests) times faster than the table solution, but (surprisingly) only with Mozilla/5.0. (Seems that IE's and Opera's RegExp engines need a little bit of tuning )For Regular Expressions are widely known as *the* efficient method for matching strings, the opposite would have been very surprising to me. Note: Mozilla/4.0 (compatible; MSIE 5.01; Windows NT 5.0; Q312461) requires the property identifiers here to be quoted as they do not conform to valid identifiers in the version of JScript it supports by default. For Mozilla also accepts string literals, without having the access method to differ from numeric ones, one should always quote the identifier if in doubt. PointedEars |
|
|
|
|
|||
|
Guest
Posts: n/a
|
|
|
|
|
||
|
|
| |
|
| Thread Tools | |
|
|
Similar Threads
|
||||
| Thread | Thread Starter | Forum | Replies | Last Post |
| How to validate that at least one text box has input | Homer | ASP .Net | 1 | 08-28-2007 11:56 PM |
| Width of text input box vs. password input box | cjl | HTML | 1 | 10-31-2005 11:46 AM |
| Off Topic: Width of text input box vs. password input box | cjl | Javascript | 7 | 10-30-2005 10:11 PM |
| can i pass data with input text instead of input hidden? | Walter | ASP General | 6 | 09-17-2004 11:16 AM |
| why does form with only 1 text input and 1 button input submit on enter? | Guy | HTML | 5 | 12-13-2003 06:44 AM |
