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: Wed, 24 Apr 2002 14:30:52 -0400
- Organization: Society for the Incurably Pompous
Charles Arthur writes:
>
On Tue, 23 Apr 2002 23:37:53 +0200, Emmanuel <email@hidden>
>
wrote:
>
>
>At 7:06 PM +0200 23/4/02, Charles Arthur wrote:
>
>>Here's the problem, speed freaks.
>
>>I have a list - list1 - which could get quite large - say, 400-500 items,
>
>>all OS aliases.
>
>>Meanwhile I also have list2 which will also have lots of aliases. Might
>
>>easily be bigger than list1.
>
>>I want to pick things randomly from list1 that aren't in list2, to create
>
>>mywanteditem.
>
>Not saying that the solutions proposed were not optimal, but personally I
>
>would check the following proposition: build / update list3 as you build /
>
>change list1. Ideally, new items would be inserted into list3 at a random
>
>rank, so when "playing" list1 you would just pick list3's first item. There
>
>is no need to empty list1, only list3 (set list3 to rest of list3). For the
>
>purposes here, list1 is useless.
>
The problem though is that list1 is what I get presented with. It's
>
iTunes's playlist (a list of aliases).
>
OK, I'll really explain it. I'm making random playlists in iTunes
>
for MP3 players.
Here you go -- this is a shuffle algorithm which works well. (If I
understand Emmanuel right, it's doing pretty much what he suggested,
although I began this before I read his post).
Since I couldn't figure out how to do get the correct information out of
some item, I included a minimal implementation of pseudoRand to speed up
the random number generation.
What this will do is take a list, and generate a new list of the same
items in random order. The algorithm is to create a temporary list that
is twice the size, then take each item in list1 and place it in a random
position in the temp list. If there's already something there, a new
random position is chosen. This keeps up until a space is open, and
then the item is put in that position. Since the temp list is twice as
big, this should rarely require more than 4 or 5 tries, even when most
of list1 is already placed, since 50% of the spaces will still be open.
The we repeat through the temp list, and put everything that isn't
missing value in newList. I used script object encapsulation to make
the list handling faster, and the whole thing ends up being roughly
O(n). Took 38 ticks to do a 1000 item list which was all integers. A
5000 item list took 207 ticks.
BTW, this shuffle list handler is probably going in the next edition of
pseudoRand -- too late for 1.1.1 though. or maybe I'll do a separate
mod since psRand is starting to get too big for my tastes.
-- begin:
(**************************************************************
* ShuffleList v. 1.0 (4/24/02)
* by Michael Sullivan
*
* uses:
* minimal pseudoRand v. 1.0 (4/2/02) included in this distribution
* by Michael Sullivan
*
* Takes any list, and returns a new list with the items of the
* first list in random order. (Well, pseudo-random, but close enough)
* Will shuffle top level items only. Items in sub lists will be
* left in their original order in the sublist.
*
* API:
* shuffleList(anyList)
*
* c. 2002 Michael E. Sullivan
* email@hidden
*
* freeware use and abuse with credit via applemods general license.
*
***********************************************************)
-- test code begins:
set k to {}
repeat with i from 1 to 1000
set end of my k to i
end repeat
set t0 to the ticks
repeat 1 times
set newList to shuffleList(k)
end repeat
set t1 to the ticks
{t1 - t0}
--> 38
-- test code ends.
-- begin handlers:
on shuffleList(aList)
script o
property p : aList
property temp : {}
property newP : {}
end script
set rng to initPseudoRand()
set theCount to count o's p
repeat with i from 1 to theCount * 2
set end of o's temp to missing value
end repeat
set spotFound to false
repeat with i from 1 to theCount
repeat until spotFound
set k to rng's Random(1, theCount * 2)
if item k of o's temp is missing value then
set item k of o's temp to item i of o's p
set spotFound to true
end if
end repeat
set spotFound to false
end repeat
repeat with i from 1 to theCount * 2
if item i of o's temp is not missing value then
set end of o's newP to item i of o's temp
end if
end repeat
return o's newP
end shuffleList
on initPseudoRand()
script pseudoRand
property kBigPrime : 2.147483647E+9 -- 2^31 - 1
property kA : 524287 -- also prime
property kLast : (the ticks) mod kBigPrime
on RandomInt()
set kLast to (kLast * kA) mod kBigPrime
end RandomInt
on Random(a, b)
if a = 0 and b = 0 then
return random01()
end if
if b - a < 0 then
set {a, b} to {b, a}
end if
return RandomInt() mod (b - a + 1) + a
end Random
end script
return pseudoRand
end initPseudoRand
-- end
>
Take a big playlist - say the "library" playlist in iTunes. This is list1.
>
Take a smaller list - say of genres of music that you want to include (or
>
exclude; it's just a comparison you'll make).
>
My method is to take list1, randomly choose an item, and compare its
>
properties (eg size, genre) against the smaller "genrelist", and if it's OK
>
to use then add it to the new playlist you're making. That's fine for your
>
first item.
>
So now you want to "remove" that item from list1 (*curses* that
>
there's no such command in vanilla AS... is there? If there was then most
>
of these questions would disappear. Remember, no OSAX allowed!! Because
>
this is for distribution.)
There's a ListDelete handler discussed in the Script Debugger
documentation. Only problem is that it's O(n), so using repeatedly like
you descript is going to produce an O(n^2) script. Bad news for big
lists. It's possible that if you use AS's linked list implementation
that you can do ListDelete in constant time. It *should* be possible,
but I haven't tested it.
>
There also comes a stage though when you're approaching the limit of the
>
size of playlist you want to build, and so there aren't many tracks which
>
are small enough to choose. (Can't add a 20Mb track to 2Mb remaining
>
space.)
Here's the deal -- once you've got a shuffled list, it's O(n) to repeat
through it and tally the total MB value, then toss anything that doesn't
fit in the remaining space until you reach the end of the list.
If you want to be *really* smart, you could keep track of tossed items
and maybe replaced large tracks when you could get twoor three in and
leave less space at the end.
>
At this point, it becomes really slow to hope that you'll randomly
>
pick tracks which are small enough from list1; you have to create a
>
"chosen" list of small-enough tracks. (Anyone care to guess when it's
>
efficient to make that shift? I've guessed when the number of small-enough
>
tracks is one-tenth of the whole playlist's contents. Perhaps instead a
>
comparison with the size of list2?)
No need when you do it the way I've proposed.
>
So to return to Emmanuel's answer, list1 is very much not useless. It's the
>
source of the information. And I don't follow how I would create list3 and
>
add items "at a random rank" to it. And I wonder whether it's really the
>
best answer, and what the best (=quickest) algorithm is here.
Well, I just showed you. The key is to make the list3 bigger than list1
by enough so that there will be few crashes, then compact it when you're
done.
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.