StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
20507729
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
0
CommunityOwnedDate
CreationDate
2013-12-10T23:42:48.583
FavoriteCount
0
LastActivityDate
2013-12-11T00:46:20.157
LastEditDate
2013-12-11T00:46:20.157
LastEditorUserId
800524
OwnerUserId
800524
ParentId
15470757
PostTypeId
2
Score
0
ViewCount
0
LastEditorDisplayName
text
Body
There are a few things that need to be specified: <ul> <li>Do the input lists contain duplicates?</li> <li>Must the result be ordered?</li> </ul> I'll assume that, using <code>std::list</code>, you can cheaply insert at the head or at the tail. Let's say List 1 has N elements and List 2 has M elements. <hr> <h2>Algorithm 1</h2> It iterates over every item of List 1 searching for it in List 2. Assuming that there may be duplicates and that the result must be ordered, the worse case time for the search is that no element in List 1 exists in List 2, hence it's at least: <ul> <li>O(N × M).</li> </ul> To insert the item of List 1 in the right place, you need to iterate List 2 again until the point of insertion. The worse case will be when every item in List 1 is smaller (if List 2 is searched from the beginning) or greater (if List 2 is searched from the end). Since the previous items of List 1 have been inserted in List 2, there would be M iterations for the first item, M + 1 for the second, M + 2 for the third, etc. and M + N - 1 iterations for the last item, for an average of M + (N - 1) / 2 per item. Something like: <ul> <li>N × (M + (N - 1) / 2)</li> </ul> For big-O notation, constant factors don't matter, so: <ul> <li>N × (M + (N - 1))</li> </ul> For big-O notation, non-variable additions don't matter, so: <ul> <li>O(N × (M + N))</li> </ul> Adding to the original O(N × M): <ul> <li>O(N × M) + O(N × (M + N))</li> <li>O(N × M) + O(N × M + N2)</li> </ul> The second equation is just to make the constant factor elimination evident, e.g. 2 × (N × M), thus: <ul> <li>O(N × (M + N))</li> <li>O(N2 + N × M)</li> </ul> These two are equivalent, which ever you like the most. Possible optimizations: <ul> <li>If the result doesn't have to be ordered, insertion can be O(1), hence the worse time case is: <ul> <li>O(N × M) </li> </ul></li> <li>Don't just test each List 1 item in List 2 by equality, test if each item by e.g. greater than, so that you can stop searching in List 2 when List 1's item is greater than List 2's item; this wouldn't reduce the worse case, but it would reduce the average case</li> <li>Keep the List 2 iterator that points to where List 1's item was found to be greater than List 2's item, to make the sorted insertion O(1); on insertion make sure to keep an iterator that starts at the inserted item, because although List 1 is ordered, it might contain duplicates; with these two, the worse time case becomes: <ul> <li>O(N × M) </li> </ul></li> <li>For the next iterations, search for List 1's item in the rest of List 2 with the iterator we kept; this reduces the worse case, because if you reach the end of List 2, you'll be just "removing" duplicates from List 1; with these three, the worse time case becomes: <ul> <li>O(N + M)</li> </ul></li> </ul> By this point, the only difference between this algorithm and Algorithm 2 is that List 2 is changed to contain the result, instead of creating a new list. <hr> <h2>Algorithm 2</h2> This is the merging of the merge sort. You'll be walking every element of List 1 and every element of List 2 once, and insertion is always made at the head or tail of the list, hence the worse case time is: <ul> <li>O(N + M)</li> </ul> If there are duplicates, they're simply discarded. The result is more easily made ordered than not. <hr> <h2>Final Notes</h2> If there are no duplicates, insertion can be optimized in both cases. For instance, with doubly-linked lists, we can easily check if the last element in List 1 is greater than the first element in List 2 or vice-versa, and simply concatenate the lists. This can be further generalized for any tail of List 1 and List 2. For instance, in Algorithm 1, if a List 1's item is not found in List 2, we can concatenate List 2 and the tail of List 1. In Algorithm 2, this is done in the last step. The worse case, when List 1's items and List 2's items are interleaved, is not reduced, but again the average case is reduced, and in many cases by a big factor that makes a big difference In Real Life™. I ignored: <ul> <li>Allocation times</li> <li>Worse space differences in the algorithms</li> <li>Binary search, because you mentioned lists, not arrays or trees</li> </ul> I hope I didn't make any blatant mistake.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POmost efficient algorithm to get union of 2 ordered lists
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. USacelent
UserOwnerUserId
1. USacelent
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. This table or related slice is empty.
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. This table or related slice is empty.
CommentsPostId
1. This table or related slice is empty.

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.