Mailing List Archive: 49091 messages
  • Home
  • Script library
  • AltME Archive
  • Mailing list
  • Articles Index
  • Site search
 

Finding a value in a series?

 [1/14] from: charliew::drte::com at: 21-May-2001 11:51


How do you do a find on the first element in a series of blocks?
>> probe blk
[ [1 a b] [2 c d] [3 e f] ] I want to search for the value 2 and assign the remainder to a variable. I then want to delete the record in the series? Thanks, Charlie

 [2/14] from: joel:neely:fedex at: 21-May-2001 11:31


Hi, Charles, Charles Wardell wrote:
> How do you do a find on the first element in a series of blocks? > >> probe blk
<<quoted lines omitted: 5>>
> I want to search for the value 2 and assign the remainder to a > variable. I then want to delete the record in the series?
My first suggestion is that you not do all of the above at once. I'd address the first issue first (finding a sub-block on a second- level key), then separately munge the result. Since you are wanting to mutate the searched block, you will have to get back a repositioned version of the block. This can be done as follows: locate: func [b [block!] n [integer!]] [ forall b [ if b/1/1 = n [return b] ] ] which behaves as follows:
>> blk
== [ [1 a b] [2 c d] [3 e f] ]
>> locate blk 17
== [ ]
>> locate blk 2
== [ [2 c d] [3 e f] ] In other words, the result of LOCATE is empty if the target key was not found. Otherwise it is positioned so that the sub-block with the target key is in front. A separate function takes the result, copies out the related data and removes the sub-block. extract-data: func [b [block!] n [integer!] /local s d] [ either empty? s: locate b n [ copy [] ][ d: copy next first s remove s d ] ] which behaves as follows:
>> extract-data blk 17
== []
>> extract-data blk 2
== [c d] Just to prove that the 2 entry is gone...
>> blk
== [[1 a b] [3 e f]]
>>
The reason I'd separate out those two functions is the assumption that there would be other situations in which locating a sub-block by the numeric key might be desired. By returning the outer block positioned to the sub-block (or at end, if not found) you can do any of the following: - Change the content in the sub-block - Replace the entire sub-block with a different block - Insert something just in front of the sub-block - Access the content of the sub-block - Remove the sub-block\ Hope this helps! -jn-

 [3/14] from: charliew:drte at: 21-May-2001 12:46


I really appreciate your helpp. Do you believe that this would perform as well as the native Select?

 [4/14] from: arolls:bigpond:au at: 22-May-2001 2:47


Try this: blk: [[1 a b][2 c d][3 e f]] idx: 1 while [not (first blk/:idx) = 2][idx: idx + 1] var: remove copy blk/:idx remove at blk idx

 [5/14] from: gjones05:mail:orion at: 21-May-2001 12:03


From: "Charles Wardell"
> How do you do a find on the first element in a series of blocks? > >> probe blk
<<quoted lines omitted: 4>>
> ] > I want to search for the value 2 and assign the remainder to a
variable. I
> then want to delete the record in the series?
Hi, Charles, As usual, Joel makes great points about what a person "wants" to do versus really "should" do. ;-) But if you are looking for a down and dirty "one liner"-type script in order to understand how nested blocks work, then consider: a-blk: [ [1 a b] [2 c d] [3 e f] ] forskip a-blk 1 [if find a-blk/1 2 [e: a-blk/1/2 f: a-blk/1/3 remove a-blk]] a-blk: head a-blk ;forskip leaves block index at tail, need to reset probe a-blk print [e f] Basically, 'find does not (currently) work "deep", meaning on nested blocks without some form of iterating through the primary block. --Scott Jones

 [6/14] from: pa:russo:perd at: 21-May-2001 21:08


>How do you do a find on the first element in a series of blocks? >>> probe blk
<<quoted lines omitted: 5>>
>I want to search for the value 2 and assign the remainder to a variable. I >then want to delete the record in the series?
This is a solution for your specific example:
>> a: [ [1 a b] [2 c d] [3 e f] ] >> forall a [if (first first a) = 2 [remove a]]
== [ ]
>> a: head a
== [ [1 a b] [3 e f] ] You can achieve the same result using the line: forall a [if found? find first a 2 [remove a]] HTH -- Paolo Russo [pa--russo--perd--com] _________________ PERD s.r.l. Virtual Technologies for Real Solutions http://www.perd.com

 [7/14] from: joel:neely:fedex at: 21-May-2001 18:04


Hi, Scott, GS Jones wrote:
> As usual, Joel ... >
Oh, no! I'm becoming predictable! Time to change personality. ;-)
> ... points about what a person "wants" to do > versus really "should" do. > ;-) >
Of course, I would *NEVER* have an opinion on what a programmer should do (or not). Just "how" it might be done with more generality... ("Unaccustomed as I am to public speaking..." HA!) -jn-

 [8/14] from: joel:neely:fedex at: 22-May-2001 14:50


Hi, Charles, Charles Wardell wrote:
> I really appreciate your help. Do you believe that this would > perform as well as the native Select? >
The obvious off-the-top-of-the-head answers are: 1) Of course (if "as well" means "as correctly"), and 2) Of course not (if "as well" means "as quickly"). However, to avoid sounding like a smart-alec, I decided to run some real benchmarks and quantify the answer. In the course of doing so, I ran into some real surprises! I tried to think of several obvious implementation variations on the first quick-and-dirty LOCATE -- still returning a position within a block for the reasons described earlier. I came up with these: locatepath: func [b [block!] t [integer!]] [ forall b [ if t = b/1/1 [return b] ] ] locatepick: func [b [block!] t [integer!]] [ forall b [ if t = pick pick b 1 1 [return b] ] ] locatefirst: func [b [block!] t [integer!]] [ forall b [ if t = first first b [return b] ] ] pickat: func [b [block!] t [integer!]] [ repeat i length? b [ if t = pick pick b i 1 [return at b i] ] tail b ] All of these would use the block-in-a-block scheme from the original question: blk2: [[1 a b] [2 c d] [3 e f]] Based on your second "perform as well?" question, they would need to be compared with the simplistic find/skip block1 t 2 which uses a flattened data structure that would look like this: blk1: [1 [a b] 2 [c d] 3 [e f]] I built a pair of such data blocks with the same content, with a thousand logical records each, with the test code searching for the last key in the block via all of the above methods. I ran several tests of 10,000 searches, averaging times and recycling memory every 1,000 searches. One mild surprise was that there was significant variation between the averages from different tests. I can only assume from those variations (and from observing the system behavior otherwise) that there were intermittent activities (e.g., garbage collection?) that would happen "every now and then" and perturb the measurements. It's no surprise that the FIND/SKIP approach is by far the fastest alternative (but, of course, it doesn't use your desired data structure). The first major surprise is that the PICKAT beats all other options for performance against your desired two-level block structure. It takes about 17 to 20 times as long as the FIND/SKIP code. Given that PICKAT uses as much or more high-level REBOL code per inner cycle as any other option, I expected it to be one of the slower ones. Not so! The next major surprise is that LOCATEFIRST, LOCATEPICK, and LOCATEPATH consistenly rank in a different order on W2K and Linux. On W2K, LOCATEPATH takes about 2 1/3 times as long as PICKAT, LOCATEFIRST takes a little under 2 1/2 times as long, and LOCATEPICK takes a little over 2 1/2 times as long. However, on Linux, LOCATEPATH is the slowest, running about 10% longer than LOCATEFIRST. Again, one might speculate about the affects of different memory managment schemes, but I really have no explanation for the W2k-vs-Linux performance diffs. However, the punchline is clear. Shorter-looking code is *NOT* necessarily shorter-running. Among these contenders, PICKAT is the winner. -jn-

 [9/14] from: agem:crosswinds at: 22-May-2001 22:55


Source repeat == native source forall == meazine so pickat has a big bonus there.. w2k vs linux - small differences. Different compilers i think. Volker
>>>>>>>>>>>>>>>>>> Ursprüngliche Nachricht <<<<<<<<<<<<<<<<<<
Am 22.05.01, 20:50:22, schrieb Joel Neely <[joel--neely--fedex--com]> zum Thema [REBOL] Re: Finding a value in a series?:

 [10/14] from: gjones05:mail:orion at: 22-May-2001 18:16


From "Joel Neely": <huge snip>
> > It's no surprise that the FIND/SKIP approach is by far the > > fastest alternative (but, of course, it doesn't use your > > desired data structure).
<huge snip> Hi, Joel, If you still have the test set-up, will you compare select against find/skip? My own down-n-dirty suggests select is slightly faster than find/skip. Just curious how your test-jig compares. Thanks! --Scott Jones

 [11/14] from: joel:neely:fedex at: 23-May-2001 0:41


GS Jones wrote:
> If you still have the test set-up, will you compare select against > find/skip? My own down-n-dirty suggests select is slightly faster than > find/skip. Just curious how your test-jig compares. Thanks! >
I already tried it. As I recall, they were within a percent or two; given the statistical noise in the samples, that's not a significant difference. -jn- -- ------------------------------------------------------------ Programming languages: compact, powerful, simple ... Pick any two! joel'dot'neely'at'fedex'dot'com

 [12/14] from: gjones05:mail:orion at: 23-May-2001 5:19


From: "Joel Neely"
> GS Jones wrote: > > > > If you still have the test set-up, will you compare select against > > find/skip? My own down-n-dirty suggests select is slightly faster
than
> > find/skip. Just curious how your test-jig compares. Thanks! > > > > I already tried it. As I recall, they were within a percent > or two; given the statistical noise in the samples, that's > not a significant difference. > > -jn-
Thanks, Joel. As a side note, when I hear/read the expression statistical noise , I always think footprints of a nonlinear dynamic being driven toward chaos. Cognitive filters can be sooo distracting. Thanks again. --Scott Jones

 [13/14] from: joel:neely:fedex at: 23-May-2001 7:15


GS Jones wrote:
> ... As a side note, when I hear/read the expression > "statistical noise", I always think footprints of a > nonlinear dynamic being driven toward chaos. >
Sounds like a pretty good description of memory management under W2K to me! ;-) -jn- -- ------------------------------------------------------------ Programming languages: compact, powerful, simple ... Pick any two! joel'dot'neely'at'fedex'dot'com

 [14/14] from: gjones05:mail:orion at: 23-May-2001 7:43


From: "Joel Neely"
> GS Jones wrote: > >
<<quoted lines omitted: 4>>
> Sounds like a pretty good description of memory management > under W2K to me! ;-)
I laughed out loud on that one! --Scott Jones

Notes
  • Quoted lines have been omitted from some messages.
    View the message alone to see the lines that have been omitted