Frank Shearar uploaded a new version of ToolBuilder-Morphic to project The Trunk:
http://source.squeak.org/trunk/ToolBuilder-Morphic-fbs.88.mcz ==================== Summary ==================== Name: ToolBuilder-Morphic-fbs.88 Author: fbs Time: 27 February 2013, 1:09:05.096 pm UUID: 4d9369c3-4545-408c-8fdf-976048e72eb0 Ancestors: ToolBuilder-Morphic-cwp.87 Allow finding classes by specifying patterns - 'MC*Test' finds all Monticello test cases, for instance. This commit favours implementation clarity over efficiency. Part of http://bugs.squeak.org/view.php?id=7745. =============== Diff against ToolBuilder-Morphic-cwp.87 =============== Item was changed: ----- Method: ListChooser>>updateFilter (in category 'event handling') ----- updateFilter selectedItems := searchText isEmptyOrNil ifTrue: [ fullList ] + ifFalse: [ | pattern patternMatches prefixMatches | + pattern := (searchText beginsWith: '*') + ifTrue: [searchText] + ifFalse: ['*', searchText, '*']. + prefixMatches := fullList select: [:s | (s findString: searchText startingAt: 1 caseSensitive: false) = 1]. + patternMatches := (fullList select: [:s | pattern match: s]) difference: prefixMatches. + prefixMatches addAllLast: patternMatches; yourself]. - ifFalse: [ - | prefixMatches otherMatches | - prefixMatches := OrderedCollection new. - otherMatches := OrderedCollection new. - fullList do: [ :each | - | index | - index := each findString: searchText startingAt: 1 caseSensitive: false. - index = 1 ifTrue: [ prefixMatches add: each ]. - index > 1 ifTrue: [ otherMatches add: each ] ]. - prefixMatches - addAllLast: otherMatches; - yourself ]. self changed: #list. self selectedIndex: 1. self changed: #selectedIndex.! |
This will be inefficient if there are many prefixMatches and
patternMatches, because #difference will take O(n*m) time. I started measuring it and the highest number I got was 100ms, which is acceptable, but on a slower machine without Cog it can be a few seconds, which is rather slow. I have an optimized version, but it's not clear what the goal of this code is: > + pattern := (searchText beginsWith: '*') > + ifTrue: [searchText] > + ifFalse: ['*', searchText, '*']. If searchText is "*MC", then pattern will be "*MC", but if the searchText is "MC*", then it will be "*MC*". I think using #includes: instead of #beginsWith: matches with what the intention was. Anyway, I'll just push my version to the Inbox. Levente On Wed, 27 Feb 2013, [hidden email] wrote: > Frank Shearar uploaded a new version of ToolBuilder-Morphic to project The Trunk: > http://source.squeak.org/trunk/ToolBuilder-Morphic-fbs.88.mcz > > ==================== Summary ==================== > > Name: ToolBuilder-Morphic-fbs.88 > Author: fbs > Time: 27 February 2013, 1:09:05.096 pm > UUID: 4d9369c3-4545-408c-8fdf-976048e72eb0 > Ancestors: ToolBuilder-Morphic-cwp.87 > > Allow finding classes by specifying patterns - 'MC*Test' finds all Monticello test cases, for instance. > > This commit favours implementation clarity over efficiency. > > Part of http://bugs.squeak.org/view.php?id=7745. > > =============== Diff against ToolBuilder-Morphic-cwp.87 =============== > > Item was changed: > ----- Method: ListChooser>>updateFilter (in category 'event handling') ----- > updateFilter > selectedItems := > searchText isEmptyOrNil > ifTrue: [ fullList ] > + ifFalse: [ | pattern patternMatches prefixMatches | > + pattern := (searchText beginsWith: '*') > + ifTrue: [searchText] > + ifFalse: ['*', searchText, '*']. > + prefixMatches := fullList select: [:s | (s findString: searchText startingAt: 1 caseSensitive: false) = 1]. > + patternMatches := (fullList select: [:s | pattern match: s]) difference: prefixMatches. > + prefixMatches addAllLast: patternMatches; yourself]. > - ifFalse: [ > - | prefixMatches otherMatches | > - prefixMatches := OrderedCollection new. > - otherMatches := OrderedCollection new. > - fullList do: [ :each | > - | index | > - index := each findString: searchText startingAt: 1 caseSensitive: false. > - index = 1 ifTrue: [ prefixMatches add: each ]. > - index > 1 ifTrue: [ otherMatches add: each ] ]. > - prefixMatches > - addAllLast: otherMatches; > - yourself ]. > self changed: #list. > self selectedIndex: 1. > self changed: #selectedIndex.! > > > |
On 2 March 2013 00:28, Levente Uzonyi <[hidden email]> wrote:
> This will be inefficient if there are many prefixMatches and patternMatches, > because #difference will take O(n*m) time. I started measuring it and the > highest number I got was 100ms, which is acceptable, but on a slower machine > without Cog it can be a few seconds, which is rather slow. > > I have an optimized version, but it's not clear what the goal of this code > is: > > >> + pattern := (searchText beginsWith: '*') >> + ifTrue: [searchText] >> + ifFalse: ['*', searchText, '*']. > > > If searchText is "*MC", then pattern will be "*MC", but if the searchText is > "MC*", then it will be "*MC*". I think using #includes: instead of > #beginsWith: matches with what the intention was. Anyway, I'll just push my > version to the Inbox. Yes: I'd intended "no wild cards" to mean "match on substring", with the assumption that the use of a wildcard implies the user knows what she wants. I'd be happy to see the code optimised; I thought about trying to do the thing in one traversal but the code looked really ugly. Do it right, then make it fast. Glad to see some mails from you, Levente! frank |
Free forum by Nabble | Edit this page |