Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>There's not much of a difference. If I've done my math right your's is on average N/16 slower than the authors but pleanty of cases exist where your implementation will be faster.</p> <p><strong>Edit:</strong></p> <p>I'll call your implementation Y and the author's A</p> <p>Both proposed solutions has O(N^2) as worst case and they both have a best case of O(N) when all elements are the same value.</p> <p><strong>EDIT:</strong> This is a complete rewrite. Inspired by the debat in the comments I tried to find the average case for random N random numbers. That is a sequence with a random size and a random distribution. What would the average case be. </p> <p>Y will always run U times where U is the number of unique numbers. For each iteration it will do N-X comparisons where X is the number of elements removed prior to the iteration (+1). The first time no element will have been removed and on average on the second iteration N/U will have been removed.</p> <p>That is on average ½N will been left to iterate. We can express the average cost as U*½N. The average U can be expressed based on N as well 0 <p>Expressing A becomes more difficult. Let's say we use I iterations before we've encountered all unique values. After that will run between 1 and U comparisons (on average that's U/") and will do that N-I times.</p> <p>I*c+U/2(N-I)</p> <p>but whats the average number of comparisons (c) we run for the first I iterations. on average we need to compare against half of the elements already visited and on average we've visited I/2 elements, Ie. c=I/4</p> <p>I/4+U/2(N-I).</p> <p>I can be expressed in terms of N. On average we'll need to visited half on N to find the unique values so I=N/2 yielding an average of</p> <p>(I^2)/4+U/2(N-I) which can be reduced to (3*N^2)/16.</p> <p>That is of course if my estimation of the averages are correct. That is on average for any potential sequence A has N/16 fewer comparisons than Y but pleanty of cases exists where Y is faster than A. So I'd say they are equal when compared to the number of comparisons</p>
    singulars
    1. This table or related slice is empty.
    1. POInterview question: remove duplicates from an unsorted linked list
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USRune FS
    1. USRune FS
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COYou'll have hard time proving this claim. Not to mention, both solutions have asymptotical complexity O(n^2), so 'significantly' isn't applicable here.
      singulars
      1. PO
      1. USNikita Rybak
    2. CO@Rune, aside from Nikita's comment, I'd have to respond that: 1. The suggested solution does not exit when a duplicate is found, and 2. The suggested solution has to iterate from the beginning of the list to the current node. The suggested solution only exits when the current node has reached the end of the list (i.e. every time we move the current node, the runner has to run from the beginning of the list all the way to the current node, which seems to be the mirror action of what I'm doing).
      singulars
      1. PO
      1. USKiril
    3. CO@Lirik your post says it only looks for _ome_ duplicate because from the head to the node there can only be one. Why then continue?
      singulars
      1. PO
      1. USRune FS
 

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.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload