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

Question

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

Answer 1

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.