From: Robert Klemme Date: 2007-08-06T20:49:35+09:00 Subject: Re: Determining the common prefix for several strings ------=_Part_111584_14226503.1186400979032 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Content-Disposition: inline 2007/8/6, Pe=F1a, Botp : > From: Gavin Sinclair [mailto:gsinclair@gmail.com] > # On Aug 3, 5:58 pm, Pe=F1a, Botp wrote: > # > min =3D list.sort!{|a,b| a.size <=3D> b.size}.first > # > break if list.all?{|a| a =3D~ /^#{min}/} while min.chop! > # I just realised that the solution I just posted elsewhere in this > # thread is very very similar to this one. > # Be careful that using bang methods in chains is sometimes problematic, > # as they can return nil if nothing changes (sort! doesn't have this > # problem). > > indeed. as long as the array has no nil elements, w're ok w sort! > > irb(main):009:0> s=3D"test" > =3D> "test" > irb(main):010:0> s.downcase!.downcase! > NoMethodError: undefined method `downcase!' for nil:NilClass > from (irb):10 > from :0 > irb(main):011:0> a=3D[1,1,1] > =3D> [1, 1, 1] > irb(main):012:0> a.sort!.sort! > =3D> [1, 1, 1] > > i realized just now that i posted the first code. That should be, > > min =3D list.sort!{|a,b| a.size <=3D> b.size}.shift # <--shift instead o= f first > break if list.all?{|a| a =3D~ /^#{min}/} while min.chop! > > but anyway, after a couple of tests, the sort does not help much, so > > min =3D list.min{|a,b| a.size <=3D> b.size} > break if list.all?{|a| a =3D~ /^#{min}/} while min.chop! > > hmm.. Gavin, your until code just gave me a hint. if we reverse logic, w= e can save the break and make it more readable too. > > min =3D list.min{|a,b| a.size <=3D> b.size} > min.chop! until list.all?{|a| a =3D~ /^#{min}/} > > and we can use switch w #any? anytime too :) > > min =3D list.min{|a,b| a.size <=3D> b.size} > min.chop! while list.any?{|a| a !~ /^#{min}/} > > ruby power, indeed. All these solutions have the issue that they modify the list which might or might not be ok. I tend to prefer to view the item list as read only. So I'd do: min =3D list.min{|a,b| a.size <=3D> b.size}.dup min.chop! until list.all?{|a| a =3D~ /^#{min}/} I have added some interesting benchmarking: $ ./prefix.rb user system total real 1000 * list.rx 0.016000 0.000000 0.016000 ( 0.014000) 1000 * list.rx with conversion 0.031000 0.000000 0.031000 ( 0.030000) 1000 * list.one_pass 0.219000 0.000000 0.219000 ( 0.218000) 1000 * list.min 0.328000 0.000000 0.328000 ( 0.337000) 1000 * list.first.dup 0.640000 0.000000 0.640000 ( 0.641000) 1 * large.rx 0.000000 0.000000 0.000000 ( 0.000000) 1 * large.rx with conversion 0.000000 0.000000 0.000000 ( 0.000000) 1 * large.one_pass 25.985000 0.000000 25.985000 ( 26.298000) 1 * large.min 34.953000 0.000000 34.953000 ( 35.098000) 1 * large.first.dup 27.719000 0.000000 27.719000 ( 27.732000) (see attachment for code) Kind regards robert ------=_Part_111584_14226503.1186400979032 Content-Type: application/x-ruby; name="prefix.rb" Content-Transfer-Encoding: base64 Content-Disposition: attachment; filename="prefix.rb" X-Attachment-Id: f_f50wi4qz IyFydWJ5DQoNCnJlcXVpcmUgJ2JlbmNobWFyaycNCg0KUkVQID0gMTAwDQoNCmxpc3QgPSA8PFhY WC50b19hLmVhY2gge3x4fCB4LmNob21wITsgeC5mcmVlemV9LmZyZWV6ZQ0KaXRlbTAwMQ0KaXRl bTAwNA0KaXRlbTAwMg0KaXRlbTAwMmINCml0ZW0wMDJDDQppdGVtIDUNCml0ZW0gMTANCml0ZW1p emUgdGhpcw0KWFhYDQoNCmxhcmdlID0gbGlzdC5kdXANCmxhcmdlLmNvbmNhdCBsYXJnZSB3aGls ZSBsYXJnZS5zaXplIDwgMV8wMDBfMDAwDQpsYXJnZS5mcmVlemUNCg0KQmVuY2htYXJrLmJtIDMw IGRvIHx4fA0KICB7Imxpc3QiID0+IFtsaXN0LCAxXzAwMF0sICJsYXJnZSIgPT4gW2xhcmdlLCAx XX0uZWFjaCBkbyB8bGFiZWwsIChzZXQsIHJlcCl8DQoNCiAgICBzdHJpbmcgPSBsaXN0LmpvaW4o IlxuIikuZnJlZXplDQoNCiAgICB4LnJlcG9ydCAiI3tyZXB9ICogI3tsYWJlbH0ucngiIGRvDQog ICAgICByZXAudGltZXMgZG8NCiAgICAgICAgbWluID0gL1xBKC4qKS4qKFxuXDEuKikqXFovLm1h dGNoKHN0cmluZylbMV0NCiAgICAgIGVuZA0KICAgIGVuZA0KDQogICAgeC5yZXBvcnQgIiN7cmVw fSAqICN7bGFiZWx9LnJ4IHdpdGggY29udmVyc2lvbiIgZG8NCiAgICAgIHJlcC50aW1lcyBkbw0K ICAgICAgICBzdHJpbmcgPSBsaXN0LmpvaW4oIlxuIikuZnJlZXplDQogICAgICAgIG1pbiA9IC9c QSguKikuKihcblwxLiopKlxaLy5tYXRjaChzdHJpbmcpWzFdDQogICAgICBlbmQNCiAgICBlbmQN Cg0KICAgIHgucmVwb3J0ICIje3JlcH0gKiAje2xhYmVsfS5vbmVfcGFzcyIgZG8NCiAgICAgIHJl cC50aW1lcyBkbw0KICAgICAgICBtaW4gPSBzZXQuZmlyc3QuZHVwDQogICAgICAgIHNldC5lYWNo IGRvIHxzfA0KICAgICAgICAgIGkgPSAwDQogICAgICAgICAgd2hpbGUgbWluW2ldID09IHNbaV0g JiYgaSA8IG1pbi5zaXplDQogICAgICAgICAgICBpICs9IDENCiAgICAgICAgICBlbmQNCiAgICAg ICAgICBtaW4uc2xpY2UhIGkuLi0xDQogICAgICAgIGVuZA0KICAgICAgZW5kDQogICAgZW5kDQoN CiAgICB4LnJlcG9ydCAiI3tyZXB9ICogI3tsYWJlbH0ubWluIiBkbw0KICAgICAgcmVwLnRpbWVz IGRvDQogICAgICAgIG1pbiA9IHNldC5taW57fGEsYnwgYS5zaXplIDw9PiBiLnNpemV9LmR1cA0K ICAgICAgICBtaW4uY2hvcCEgdW50aWwgc2V0LmFsbD97fGF8IGEgPX4gL14je21pbn0vfQ0KICAg ICAgZW5kDQogICAgZW5kDQoNCiAgICB4LnJlcG9ydCAiI3tyZXB9ICogI3tsYWJlbH0uZmlyc3Qu ZHVwIiBkbw0KICAgICAgcmVwLnRpbWVzIGRvDQogICAgICAgIG1pbiA9IHNldC5maXJzdC5kdXAN CiAgICAgICAgbWluLmNob3AhIHVudGlsIHNldC5hbGw/e3xhfCBhID1+IC9eI3ttaW59L30NCiAg ICAgIGVuZA0KICAgIGVuZA0KDQogIGVuZA0KZW5kDQo= ------=_Part_111584_14226503.1186400979032--