# Why don't these 2 algorithms take the same time to detect duplicate lines in a file?

I'm trying to write a small algorithm to detect and delete duplicate lines inside a subset of consecutive lines in a file. I've come up with 2 similar solutions. After some quick tests, I've noticed that one of them is much faster than the other, especially on large files. But I don't understand why.

Here's the quick solution written in pseudocode, first_line and last_line are the first and last lines in the file where the algorithm looks for duplicate lines (I don't know exactly how to write pseudocode sorry):

i = last_line
while i > first_line
j = i-1
while j >= first_line
if line i = line j
delete line i
break
endif
j = j-1
endwhile
i = i-1
endwhile


And here's the slow solution:

i = last_line
while i > first_line
j = i-1
while j >= first_line
if line i = line j
delete line j
endif
j = j-1
endwhile
i = i-1
endwhile


In the first solution, when 2 duplicate lines are detected and whose addresses are i and j, line i is deleted, and the inner loop exits. In the 2nd solution, line j is deleted, and the inner loop goes on without being broken.

At first, intuitively, I thought that choosing to delete i or j didn't matter. But after some tests, it seems deleting i results in a much quicker process than deleting j. I don't understand the asymmetry. I suspect it's because the purpose of the outer loop is to test the uniqueness of the line whose address is i, so it would make more sense to delete it as soon as we have an answer and not let the loop goes on. But I still don't understand completely.

Deleting line i and exiting earlier in the inner loop of the first solution save comparison operations. But by deleting line j in the 2nd solution, I also save comparison operations, since this j line won't be processed by the outer loop later.

Why is the first saving of operations much more important than the 2nd one?

I'm sorry if the question is too simple for this site, but I don't know much about algorithms, and I'm looking for a reasoning which I can understand and would prove that in the general case, deleting i reduce the number of operations.

In case it matters, here's the real code I'm using, it's written in vimscript:

com! -range=% DelDup call s:del_dup(<line1>,<line2>)

fu! s:del_dup(line1, line2) abort
let view = winsaveview()
let p    = a:line2
while p > a:line1
let q = a:line1
while q < p
if getline(p) ==# getline(q)
exe p . 'd_' | break
endif
let q += 1
endwhile
let p -= 1
endwhile
call winrestview(view)
endfu


Edit:

I've compared the 2 algorithms with this simple file:

apple
banana
grape
kiwi
orange
tangerine


Then, duplicate each line 256 times:

for i in range(1, 8) | sil %t\$ | endfor


Which gives a file with 1536 lines.

Then, I've measured the time it takes for the :DelDup command to delete duplicate lines with the fast algorithm which I wrote earlier:

:Time DelDup


On my machine, the time reported is around 0.1s.

But if I replace the lines:

if getline(p) ==# getline(q)
exe p . 'd_' | break
endif


With these lines:

if getline(p) ==# getline(q)
exe q . 'd_'
endif


Then :Time DelDup reports that the command took more than 8s on average.

In case it matters, here's how the :Time command is defined:

com! -count=1 -nargs=+ -complete=command Time call s:time(<q-args>, <count>)

fu! s:time(cmd, cnt)
let time = reltime()
try
if a:cnt > 1
let i = 0
while i < a:cnt
exe a:cmd
let i += 1
endwhile
else
exe a:cmd
endif
finally
redraw
echomsg matchstr(reltimestr(reltime(time)), '\v.*\..{,3}') . ' seconds to run :' . a:cmd
endtry
endfu

• I suspect that the answer depends on how the list of lines is implemented. Do you have any details on that? – Yuval Filmus Jul 1 '17 at 13:00
• @YuvalFilmus Thank you very much for your answer, I've updated the question with the information I had. – user852573 Jul 1 '17 at 13:25
• When you delete line j, you need to decrement i = i - 1. I think, that's the problem. – rus9384 Jul 1 '17 at 15:45
• @rus9384 I think you are right, I saw a big decrease in time once I added your line. But there are still some duplicate lines which remain, not many though, just a few. I'll try to find how to get rid of them later. If you post your comment as an answer I'll accept it. Thank you very much for your help. – user852573 Jul 1 '17 at 16:01

## 1 Answer

When you delete line j, each line which was after that line will be moved by one line upwards. That means, that your line i, which is below, also will be moved. So, since it was moved, it has changed it's number. And it means that you need to decrease i : i = i - 1.

As an example see this:

Given file:    Lines 2 and 3 are equal    Remove line 2:
1 00                                      1 00
2 01
3 10                                      2 10
4 01                                      3 01


And your second algorithm didn't see that their positions have changed. However, if it wouldn't be file, but an array/list/etc, you'd got an error.