Forums: » Register « |  Free Tools |  User CP |  Games |  Calendar |  Members |  FAQs |  Sitemap |  Support |

New Free Tools on Dev Shed!

#1
March 31st, 2003, 12:27 PM
 lunatic
Contributing User

Join Date: Mar 2003
Posts: 161
Time spent in forums: 7 h 49 m 45 sec
Reputation Power: 11
Top 3 Spot algorithm

Hello,

I'm trying to figure out the top 3 spot of pictures sent. so far i have this.

two incoming data to work with:
1. the pictures location sent in by form
2. the file that keeps the location and rank. (ie images/fun/002.jpg,132)

@rank holds the picture's rank
@pic holds the location of the pictures.

PHP Code:
``` .....#FIND THE TOP 3 PICTURES \$max_rank = 0; \$max_pic_path = undef; \$max_array_location = 0; \$mid_rank = 0; \$mid_pic_path = undef; \$mid_array_location = 0; \$low_rank = 0; \$low_pic_path = undef; \$low_array_location = 0; for (\$n=0;\$n < \$#rank + 1 ;\$n++) {     #true if new #1 rank > old #1 rank     if (@rank[\$n] > \$max_rank) {         #set #3 to #2         \$low_rank = \$mid_rank;         \$low_pic_path = \$mid_pic_path;         \$low_array_location = \$mid_array_location;         #set #2 to #1         \$mid_rank = \$max_rank;         \$mid_pic_path = \$max_pic_path;         \$mid_array_location = \$max_array_location;         #set #1 to highest         \$max_rank = @rank[\$n];         \$max_pic_path = @pic[\$n];         \$max_array_location = \$n;     }     #true if new #2 rank > old #2 rank but < #1 rank     elsif (@rank[\$n] > \$mid_rank && @rank[\$n] <= \$max_rank) {         #set #3 to #2         \$low_rank = \$mid_rank;         \$low_pic_path = \$mid_pic_path;         \$low_array_location = \$mid_array_location;         #set #2 to #1         \$mid_rank = @rank[\$n];         \$mid_pic_path = @pic[\$n];         \$mid_array_location = \$n;     }     #true if new #1 rank > old #1 rank but < #2 rank     elsif(@rank[\$n] > \$low_rank && @rank[\$n] <= \$mid_rank) {         #set #3 rank         \$low_rank = @rank[\$n];         \$low_pic_path = @pic[\$n];         \$low_array_location = \$n;     } }.....  ```

This works well already except lets says we have this in the rank file

images/fun/002.jpg,100
images/fun/034.jpg,104
images/fun/142.jpg,104
images/fun/749.jpg,105
images/fun/673.jpg,104

well 105 will be displayed for #1.
as for #2 and #3 is will grab as in first come first serve manner. so only pictures 034 and 142 will be displayed every time.

I want it to be random if it has the same rank....

Can anyone help.??

Thanks

#2
April 1st, 2003, 12:29 PM
 epl
Contributing User

Join Date: Mar 2001
Location: Dublin
Posts: 413
Time spent in forums: 2 h 18 m 18 sec
Reputation Power: 13
where the item being consider is equal in rank to that currently in the given rank, you should add in a 50/50 random decision to choose between keeping the current item with the given rank and replacing with the item under consideration.

for example (i don't know how to generate random numbers in php:
Code:
```.....#FIND THE TOP 3 PICTURES
\$max_rank = 0;
\$max_pic_path = undef;
\$max_array_location = 0;
\$mid_rank = 0;
\$mid_pic_path = undef;
\$mid_array_location = 0;
\$low_rank = 0;
\$low_pic_path = undef;
\$low_array_location = 0;

for (\$n=0;\$n < \$#rank + 1 ;\$n++) {
#true if new #1 rank > old #1 rank
#true half of the time if equal...
if ((@rank[\$n] > \$max_rank)
||(@rank[\$n] = \$max_rank && rnd()<0.5)) {
#set #3 to #2
\$low_rank = \$mid_rank;
\$low_pic_path = \$mid_pic_path;
\$low_array_location = \$mid_array_location;
#set #2 to #1
\$mid_rank = \$max_rank;
\$mid_pic_path = \$max_pic_path;
\$mid_array_location = \$max_array_location;
#set #1 to highest
\$max_rank = @rank[\$n];
\$max_pic_path = @pic[\$n];
\$max_array_location = \$n;
}
#true if new #2 rank > old #2 rank but < #1 rank
#true half of the time if equal...
elsif ((@rank[\$n] > \$mid_rank)
|| (@rank[\$n] = \$mid_rank && rnd()<0.5)) {
#set #3 to #2
\$low_rank = \$mid_rank;
\$low_pic_path = \$mid_pic_path;
\$low_array_location = \$mid_array_location;
#set #2 to #1
\$mid_rank = @rank[\$n];
\$mid_pic_path = @pic[\$n];
\$mid_array_location = \$n;
}
#true if new #1 rank > old #1 rank but < #2 rank
#true half of the time if equal...
elsif ((@rank[\$n] > \$low_rank)
|| (@rank[\$n] = \$low_rank && rnd()<0.5)) {
#set #3 rank
\$low_rank = @rank[\$n];
\$low_pic_path = @pic[\$n];
\$low_array_location = \$n;
}
}.....```

The above needs to be refined to ensure that the three ranks are filled if empty ... without any random testing but your initial values may well do that (i haven't looked too closely)

you may want to think about it a bit / run a few tests to see how uniformly random this is (run with large data set of identical ranks and observe how your ranks turn out etc. )

Last edited by epl : April 1st, 2003 at 12:59 PM.

#3
April 1st, 2003, 12:56 PM
 epl
Contributing User

Join Date: Mar 2001
Location: Dublin
Posts: 413
Time spent in forums: 2 h 18 m 18 sec
Reputation Power: 13
The above will, I think, favour (quite heavily?) items later in the list. I think this idea might be unbiased.

As each item is read in, assign it a random number selected from a uniform distribution over a given range ... rand() or rnd() or rnd(1), i guess, will yield such.

Then, in the case of equality of rank, compare the random numbers to decide which to keep in the given rank.

I'll have a go at implementing this (again with my rnd() function which should be replaced with whatever is the php equivalent)

Code:
```.....#FIND THE TOP 3 PICTURES
\$max_rank = 0;
\$max_rand = 1; # initialise to maximum possible value
\$max_pic_path = undef;
\$max_array_location = 0;

\$mid_rank = 0;
\$mid_rand = 1; # initialise to maximum possible value
\$mid_pic_path = undef;
\$mid_array_location = 0;

\$low_rank = 0;
\$low_rand = 1; # initialise to maximum possible value
\$low_pic_path = undef;
\$low_array_location = 0;

for (\$n=0;\$n < \$#rank + 1 ;\$n++) {
\$rand=rnd();

#true if new #1 rank > old #1 rank
#random decision if equal...
if ((@rank[\$n] > \$max_rank)
||(@rank[\$n] == \$max_rank && \$rand<\$max_rand)) {
#set #3 to #2
\$low_rank = \$mid_rank;
\$low_rand = \$mid_rand;
\$low_pic_path = \$mid_pic_path;
\$low_array_location = \$mid_array_location;
#set #2 to #1
\$mid_rank = \$max_rank;
\$mid_rand = \$max_rand;
\$mid_pic_path = \$max_pic_path;
\$mid_array_location = \$max_array_location;
#set #1 to highest
\$max_rank = @rank[\$n];
\$max_rand = \$rand;
\$max_pic_path = @pic[\$n];
\$max_array_location = \$n;
}
#true if new #2 rank > old #2 rank but < #1 rank
#random decision if equal...
elsif ((@rank[\$n] > \$mid_rank)
|| (@rank[\$n] == \$mid_rank && \$rand<\$mid_rand)) {
#set #3 to #2
\$low_rank = \$mid_rank;
\$low_rand = \$mid_rand;
\$low_pic_path = \$mid_pic_path;
\$low_array_location = \$mid_array_location;
#set #2 to #1
\$mid_rank = @rank[\$n];
\$mid_rand = \$rand;
\$mid_pic_path = @pic[\$n];
\$mid_array_location = \$n;
}
#true if new #1 rank > old #1 rank but < #2 rank
#random decision if equal...
elsif ((@rank[\$n] > \$low_rank)
|| (@rank[\$n] == \$low_rank && \$rand<\$low_rand)) {
#set #3 rank
\$low_rank = @rank[\$n];
\$low_rand = \$rand;
\$low_pic_path = @pic[\$n];
\$low_array_location = \$n;
}
}.....```
(i haven't checked if my brackets are okay ... just for illustration!)

Last edited by epl : April 1st, 2003 at 02:29 PM.

#4
April 1st, 2003, 02:19 PM
 lunatic
Contributing User

Join Date: Mar 2003
Posts: 161
Time spent in forums: 7 h 49 m 45 sec
Reputation Power: 11
This is greatly appreciated. Would it help if I were to say this is not for php but for perl??!?

seems logical.. i will test it out...

#5
April 1st, 2003, 02:28 PM
 epl
Contributing User

Join Date: Mar 2001
Location: Dublin
Posts: 413
Time spent in forums: 2 h 18 m 18 sec
Reputation Power: 13
not really - i'm even less familiar with perl!

#6
April 8th, 2003, 03:16 PM
 revantdx
Junior Member

Join Date: Apr 2003
Location: Blacksburg, VA
Posts: 3
Time spent in forums: < 1 sec
Reputation Power: 0
Top 3

When iterating the list it might be easier to store everything to a hash table. For example, as you iterate the images, create an entry for each where the key is the rank, and the value of the hash is an array of all images of that rank. So it would look something like:

push \$RANKS{\$imgrank}, \$img;

Then when you've gone through all the images, run a descending numeric sort on the keys of the %RANKS hash. Only look at the first 3 (since those will be your top 3 ranked images).

Since you stored the images into an array, you already know the number of qualifying images for each rank with the \$# operator on the hash array element. You can then do a rand with this number and select one of the equally-ranked images in the case of a tie.

There may be some casting involved with making the elements of a hash be arrays, but I've done it before without any major complications.

Hopefully this solves your problem without having to call a rand for every element.

#7
April 8th, 2003, 05:47 PM
 lunatic
Contributing User

Join Date: Mar 2003
Posts: 161
Time spent in forums: 7 h 49 m 45 sec
Reputation Power: 11
you know, that's a good logical, effiecent way to look at it.. seems to me that the problem of ties is solved and also if i decied to have the top # instead of 3, i can easily change that...

sweet ill give it a try and let you know the outcome....

Thanks very much for your help.. most appriecative

 Viewing: Dev Shed Forums > Programming Languages - More > Software Design > Top 3 Spot algorithm