Re: Removing (or picking) items from list 1 via list 2?
Re: Removing (or picking) items from list 1 via list 2?
- Subject: Re: Removing (or picking) items from list 1 via list 2?
- From: email@hidden (Michael Sullivan)
- Date: Tue, 23 Apr 2002 18:58:34 -0400
- Organization: Society for the Incurably Pompous
>
At 1:01 pm -0700 23/4/02, Michael wrote:
>
> (re trying to pick randomly from list1 but not using stuff from list2
>
>
> Here are your biggest speed issues:
>
>
>
> 1. Using a reference (e.g. "my list1")
>
do you mean "a reference to .."?
You can do that, but for some reason just calling it "my list1" instead
of "list1" does the trick.
>
> 2. Random number. This is an osax call and therefore quite slow within
>
> repeats. There are two possibilities. You can use the "some item"
>
> feature, to get a random item from list1, or you can download my
>
> pseudoRand applemod, which will generate random integers from 1 to n
>
> about 40 times as fast as the osax call.
>
Will it work in OSX? (I'll go have a look.)... hmm, OK. There'll certainly
>
be lots of it.
I haven't tested it, but it should work -- it's totally vanilla except
for one use of standard additions.
>
> If your list1 will stay
>
> shorter than 500 items, then some item should be roughly as fast. it's
>
> order n on the length of list, however, and pseudoRand is not, so if
>
> list1 could be very long (more than 2-3,000 items), you should probably
>
> use pseudoRand. BTW, if you use "some item", then using "some item of
>
> my list1" is much faster than "some item of list1"
>
Same as above - do you mean "a reference to"?
I mean exactly what I said -- the "my" is crucial.
BTW, since I sent that, I speed tested this. Some item takes about the
same amount of time as pseudoRand if you use a reference to the list in
question, no matter how big the list is (up to 10K items, anyway).
So, I'd use some item since it's neater.
>
Good point. It does sound like the first method is better, rather than
>
creating a "clean" list.
>
> It might be good to know the context. It's possible there's some major
>
> optimization to be had there as well.
>
My guess is that it's actually a two-stage thing - there's quite an easy
>
process at first (you have a large list1, and not much in list2) but then
>
it becomes increasingly hard to find things in list1 that aren't already in
>
list2. I've gone for two separate methods in the same program, depending
>
how far through the choosing process one is.
Ah! this is useful. I think we can do something much better, create
the whole randomly ordered list at once.
This handler is simple and should be okay as long as you're list doesn't
go too high.
-- begin script:
on randomizeList(aList)
script o
property p : aList
property newP : {}
end script
set found to false
repeat with i from 1 to count of aList
repeat until found
set k to some item of o's p
if k is not in o's newP then
set end of o's newP to k
set found to true
end if
end repeat
set found to false
end repeat
return o's newP
end randomizeList
-- end script
This randomized a 1000 item list in 40 seconds. Which is a bit long.
A 100 item list took less than 1 second.
If I think about this a bit, I can almost certainly do much better (this
has n^2 behavior, and we should be able to approach n * log(n). Alas, I
have somewhere to be. Let me give it a shot this evening, and come back
in the AM.
Michael
--
Michael Sullivan
Business Card Express of CT Thermographers to the Trade
Cheshire, CT email@hidden
_______________________________________________
applescript-users mailing list | email@hidden
Help/Unsubscribe/Archives:
http://www.lists.apple.com/mailman/listinfo/applescript-users
Do not post admin requests to the list. They will be ignored.