## News:

Message to All Guests
NB: Posting URL's See here: Posted URL Change

## Duplicated values removal in array of floats

Started by guga, June 02, 2024, 07:21:09 AM

#### HSE

Quote from: NoCforMe on June 04, 2024, 08:31:13 AMOr am I missing something here?

What is n?
Equations in Assembly: SmplMath

#### NoCforMe

Quote from: HSE on June 04, 2024, 08:48:16 AMWhat is n?
The number of items in the list (or array if you prefer).
Assembly language programming should be fun. That's why I do it.

#### HSE

Quote from: NoCforMe on June 04, 2024, 09:00:45 AMThe number of items in the list (or array if you prefer).

When?
Equations in Assembly: SmplMath

#### 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?
Assembly language programming should be fun. That's why I do it.

#### HSE

Quote from: NoCforMe on June 04, 2024, 09:22:41 AMWhat 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.

Equations in Assembly: SmplMath

#### 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.)
Assembly language programming should be fun. That's why I do it.

#### 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 (O1) 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 (O2) 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 ...
Assembly language programming should be fun. That's why I do it.

#### 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

Equations in Assembly: SmplMath

#### NoCforMe

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

BTW, I may have screwed up O1, which I guess is just
`  n{sigma} n  0`

(using a linear search to see if the value being added is already there)
Assembly language programming should be fun. That's why I do it.

#### 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.
Coding in Assembly requires a mix of:
80% of brain, passion, intuition, creativity
10% of programming skills
10% of alcoholic levels in your blood.

My Code Sites:
http://rosasm.freeforums.org
http://winasm.tripod.com