The problem that I will attempt to solve is something that was mentioned at the end of class on Friday, October the 26th. Heap mentioned before class ended a problem of finding how close 2 people's list of favourite songs were. The application that was mentioned was recommending music to other people when they are shopping on itunes for example. What I'm going to be looking for is a algorithm to find how close the 2 lists of songs and by scoring the pair with a generic scoring system.
So the data presented presumably is a list of songs ranked from most favoured to least favoured (so in decreasing order). I will assume for simplicity sake at this point that the list of the second person I am comparing to is of the same size and no repetitions are included.
Here is some scratch work I did to get an idea of the problem and see if I can make a conjecture as to the complexity of the problem.
Suppose the sample list is of length 4 comprising of artists A, B, C and D in order of most favoured to least favoured. Now say the list of the second person is the reverse order D, C, B, A
The method I found useful for comparing how close the 2 lists were in terms of order was by determining the number of switches/swaps needed in the second list to get to the same order as the first list. In this case it's exactly 2 swaps required; swap D and A and then swap C and B. The reason these pairs were swapped was because D being at index 0 didn't match with A at index 0 in the first list and so the list was searched to find A and then swapped with D. Then similarly C in list 1 didn't match the item at index 1 in the first list, B, and so the second list was searched for B and then swapped with C.
Let me try a larger list of length 6 to see more swaps and see how it can compare with the above list.
Let L1 = [A, B, C, D, E, F] and L2 = [F, E, D, C, B, A] and notice how I'm simulating the worst case scenario where the lists are total opposites.
So just like before start at index 0, L1[0] is A in this case and compare it to L2[0] right bellow, they are not the same so compare it to L2[1], L2[2],.. and so on till a match is found. A match is found at the end so F and A (in red) are swapped.
Now move the next song by increasing the index by 1, so L1[1] in this case is B and repeat the same
method as above. So at the end E and B are swapped.
Now move the next song by increasing the index by 1, so L1[1] in this case is B and repeat the same
method as above. So at the end E and B are swapped.
Repeat above again for L1[2] which is C. After the swap is done, moving to the next index L1[3] which is a D and comparing L1[3] to L2[3] they are the same! If this is the case then we are done and now the lists are the same.
Now going back and counting the number of swaps there was exactly 3 swaps and the score for how similar these 2 music preferences were could be calculated by [(number of songs)-3]/(number of songs) as a generic way, it's not too important how we calculate the score. Repeating this for a list of length 10 can quickly draw a connection to the number of swaps that much be preformed for the WORST CASE scenario since best case is 0 swaps (happens when the lists are exactly the same). Thinking about it conceptually exactly half (in case of odd (n-1)/2, ie value to the left of the middle) of the elements will need to be swapped since if the swap happens it will be swapping with another element which will take its place and both will be in order. So if it's an even length is this would be n/2 swaps happening. An odd length list will behave similarly except the number of will be floor(n/2) since the middle element will be untouched. So in either case we have floor(n/2) swaps as the worst case.
However what is important is trying to figure out the complexity of such an algorithm (number of comparisons) . First must decide how the 2nd list is going to be searched. A really naive way of searching for a matching value from L1 is by scanning all the values in L2, which means we are looking at elements that are already 'sorted' according to L1. This is right off the bat a O(n^2) algorithm since we are comparing every value in L1 (n values) with every value in L2 'n' amount of times.
A better way I can think of is starting the search to the right of the array of the current index, so if I was comparing the value at index 2 in L1 then I would start the search at L2[2] and search towards the right instead of starting at the beginning of the list in L2. This means I would be making in total n + n-1 + n-2 +... comparisons since the left side of the list (which we ignore since it's sorted) will grow by 1 each iteration of picking the next value in L1 meaning the right side will shrink by 1.
Adding the sum of this series find that it's n(n+1)/2 comparisons which is really 1/2(n^2 + n) so this is another O(n^2) algorithm. Although it will run faster since n^2 > 1/2(n^2 + n), it's still not satisfying for me since we usually like to look for nlogn or logn or linear run-time complexities.
But here's a graph generated by wolfram alpha of the 2 functions for large values from [0, 100000] and clearly the first method is much slower, almost takes twice as long as the second method! So there is a significant difference over large lists.
Now this is too much work for one session, I must revisit this to try to find a better solution that can run faster and possibly consider the cases of lists being different lengths (L1 contains elements that are not in L2 and vise versa). But so far the progression is looking good, I found a solution to solving the problem by finding a scoring system to match the two people's song preferences and looked into the complexity of 2 different versions. I will revisit this Wednesday night!
No comments:
Post a Comment