Duplicated values removal in array of floats

[HSE]

Or am I missing something here?

What is n?

[NoCforMe]

What is n?

The number of items in the list (or array if you prefer).

[HSE]

The number of items in the list (or array if you prefer).

  When?

[NoCforMe]

As you add items (you start off with zero, of course:

1, 2, 3, ... n

This is all obvious, right? What are you getting at here?

[HSE]

What are you getting at here?

Apparently you are thinking that all pixels are differents. Anyway that is worst case. But you don't know.

n is the number of pixels. Testing at the end you have n*(n-1) comparisons (in worst case) more something to exclude autocomparison or use later, or you have to rearrange the array when pixel value is a duplicate.

[NoCforMe]

Yes, that's the worst-case assumption.

So it depends on how many duplicates there actually are (which of course you have no idea when you're running). If there are few duplicates, then your suggestion (removing duplicates as you go rather than at the end) would probably be better.

It's a race between doing (potentially) n(n-1) comparisons (worst case) at the end, vs. potentially many more comparisons (1+2+3+4+ ... +n) if you do it your way, as you go.

I don't know. It seems like it would take more time your way, but now I'm not sure. (No expert in combinatorial math here.)

[NoCforMe]

OK, let's try this: I'm not a mathematician, but I'm going to play one on TV for just a minute.

To formalize this, I believe (correct me if I'm wrong) that the potential total number of operations (O₁) to do things your way--eliminating duplicates as they're added to the array--is this:
You cannot view this attachment.

while the total number of operations (O₂) if you wait until the end to remove duplicates is
You cannot view this attachment.
Seems like the first number would be greater.

Now I'm going to sit back and wait for others who know more to shoot holes in my theory ...

[HSE]

At the end probability always is worst:

O2 > O1

n (m-1) > n (m+1) /2

Where
n >= m
n: number of values
m: number of unique values

[NoCforMe]

OK, I'll have to take your word for that.

BTW, I may have screwed up O₁, which I guess is just

  n
{sigma} n
  0

(using a linear search to see if the value being added is already there)

[guga]

Tks a lot guys. I´ll take a look, I´m just finishing the adjustments of the DbScan filter i described here https://masm32.com/board/index.php?topic=11919.30  and later i´ll give a test on the removal duplications problem.