Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #32657 > unrolled thread

Update only if not already in array

Back to article view | Back to comp.lang.javascript

Contents

  Update only if not already in array jonas.thornvall@gmail.com - 2017-03-01 05:36 -0800
    Re: Update only if not already in array Julio Di Egidio <julio@diegidio.name> - 2017-03-01 05:53 -0800
      Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-01 07:29 -0800
        Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-01 12:04 -0800
          Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 02:27 -0800
            Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-03 13:02 +0100
              Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 09:07 -0800
                Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 09:13 -0800
                Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-03 18:20 +0100
                  Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 14:30 -0800
                    Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-03 23:41 +0100
                      Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 14:48 -0800
                      Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 14:52 -0800
                        Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-04 00:07 +0100
                          Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-03 16:00 -0800
                            Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-04 12:35 +0100
                              Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-04 06:00 -0800
                                Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-04 15:24 +0100
                            Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-04 07:02 -0800
                              Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-04 15:51 +0000
                                Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-04 09:57 -0800
                                  Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-04 20:56 +0000
                                    Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-04 15:30 -0800
                                      Re: Update only if not already in array jonas.thornvall@gmail.com - 2017-03-04 15:37 -0800
                                        Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-05 00:41 +0000
                                      Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-05 00:29 +0000
                                        Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-05 06:26 -0800
                                          Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-05 15:00 +0000
                                            Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-06 07:50 -0800
                                              Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 00:50 +0000
                                                Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 06:46 +0100
                                                  Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 11:23 +0000
                                                    Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 15:34 +0100
                                                      Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 16:47 +0000
                                                        Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 17:55 +0100
                                                          Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-07 17:28 +0000
                                                            Re: Update only if not already in array Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2017-03-07 21:07 +0100
                                                              Re: Update only if not already in array Flippie Flink <flip@flink.not> - 2017-03-07 22:29 +0100
                                                Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-11 18:24 -0800
                                                  Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-15 17:32 +0000
                                                    Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-15 10:59 -0700
                                                      Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-16 03:49 +0000
                                                        Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-18 11:46 -0700
                                                          Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-18 20:12 +0000
                                                            Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-18 20:45 +0000
                                                            Re: Update only if not already in array "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2017-03-26 11:54 -0700
                                                              Re: Update only if not already in array Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-03-27 22:48 +0100
    Re: Update only if not already in array "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2017-03-01 15:32 +0100

Page 3 of 3 — ← Prev page 1 2 [3]

#32775

Ben Bacarisse wrote:

> I was saying you can't say anything about a single value of f from
> knowing only the order.  If we know if is O(n^2) f(1000) could be 1, 99,
> 1x10^103 or -45.  Also f(2000) could be 17, 1,000,000 or 0.  You gave a
> single value and said that it could be lower but not higher (because O
> is an upper bound).  But f can take any values at all at any of a
> finite set of points and still be O(n^2).

If you meant at a point less than n0, I agree per the definition.

> > I wasn't sure of the answer to this, so I reviewed one of my
> > Algorithms texts [1] and surprisingly on page 45 it has a graph and
> > description which reflects this very issue.
> >
> > What we both overlooked (or forgot) is that O(f(n)) is defined with a
> > minimum constraint as part of the definition that would exclude those
> > lower values. So in the above function it would still be considered
> > O(x^2). From p. 47 of the text:
> >
> > O(g(n)) = {f(n): there exist positive constants c and n0 such that 
> >            0 <= f(n) <= c*g(n) for all n >= n0 }
> >
> > In other words, the larger portion is chopped off.
> 
> I don't think I forgot or overlooked that.  It was the crux of what I
> was trying to say.

If you meant below n0, then that wasn't clear to me at the time.

[toc] | [prev] | [next] | [standalone]

#32777

"Michael Haufe (TNO)" <tno@thenewobjective.com> writes:

> Ben Bacarisse wrote:
>
>> I was saying you can't say anything about a single value of f from
>> knowing only the order.  If we know if is O(n^2) f(1000) could be 1, 99,
>> 1x10^103 or -45.  Also f(2000) could be 17, 1,000,000 or 0.  You gave a
>> single value and said that it could be lower but not higher (because O
>> is an upper bound).  But f can take any values at all at any of a
>> finite set of points and still be O(n^2).
>
> If you meant at a point less than n0, I agree per the definition.

No, even at a point above n0 because there is also c to consider.  Take,
for example, n0 = 0 -- i.e. there is some c such that f(n) < c*n^2 for
all n >= 0.  Any finite set of values for f(n) can *still* be
accommodated.

(Actually even that's a rather limited description since the notation
applies to functions in real analysis.  In fact, even an infinite set of
arbitrary values for f can be accommodated provided they occur over a
bonded region of the domain.)

>> > I wasn't sure of the answer to this, so I reviewed one of my
>> > Algorithms texts [1] and surprisingly on page 45 it has a graph and
>> > description which reflects this very issue.
>> >
>> > What we both overlooked (or forgot) is that O(f(n)) is defined with a
>> > minimum constraint as part of the definition that would exclude those
>> > lower values. So in the above function it would still be considered
>> > O(x^2). From p. 47 of the text:
>> >
>> > O(g(n)) = {f(n): there exist positive constants c and n0 such that 
>> >            0 <= f(n) <= c*g(n) for all n >= n0 }
>> >
>> > In other words, the larger portion is chopped off.
>> 
>> I don't think I forgot or overlooked that.  It was the crux of what I
>> was trying to say.
>
> If you meant below n0, then that wasn't clear to me at the time.

No, I meant above or below n0.  You simply can't say anything about any
finite set of values of f(n), knowing only that f is O(n^2).

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#32806

Ben Bacarisse wrote:

> No, I meant above or below n0.  You simply can't say anything about any
> finite set of values of f(n), knowing only that f is O(n^2).

While you could have a constant multiple at a given point, or some multiple of the lower orders, I'm not convinced that it could be some arbitrary value. If f was declared to be O(n^2), f(5) isn't going to be n^3 with f(6) being at n^50. That would be a different rate.

[toc] | [prev] | [next] | [standalone]

#32807

"Michael Haufe (TNO)" <tno@thenewobjective.com> writes:

> Ben Bacarisse wrote:
>
>> No, I meant above or below n0.  You simply can't say anything about any
>> finite set of values of f(n), knowing only that f is O(n^2).
>
> While you could have a constant multiple at a given point, or some
> multiple of the lower orders, I'm not convinced that it could be some
> arbitrary value. If f was declared to be O(n^2), f(5) isn't going to
> be n^3 with f(6) being at n^50. That would be a different rate.

Give me a few values for f(n) (just list them: f(0) = ?, f(6) = ? and so
on) for which you can be *certain* than f is not O(n^2).

You seem to be saying that f(5) = 125, f(6) =
808281277464764060643139600456536293376 means that f can't be O(n^2) but
that's not so.  You can no idea what happens for n > 6.  f might even be
O(1).

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#32809

Ben Bacarisse <ben.usenet@bsb.me.uk> writes:

> "Michael Haufe (TNO)" <tno@thenewobjective.com> writes:
>
>> Ben Bacarisse wrote:
>>
>>> No, I meant above or below n0.  You simply can't say anything about any
>>> finite set of values of f(n), knowing only that f is O(n^2).
>>
>> While you could have a constant multiple at a given point, or some
>> multiple of the lower orders, I'm not convinced that it could be some
>> arbitrary value. If f was declared to be O(n^2), f(5) isn't going to
>> be n^3 with f(6) being at n^50. That would be a different rate.
>
> Give me a few values for f(n) (just list them: f(0) = ?, f(6) = ? and so
> on) for which you can be *certain* than f is not O(n^2).
>
> You seem to be saying that f(5) = 125, f(6) =
> 808281277464764060643139600456536293376 means that f can't be O(n^2) but
> that's not so.  You can no idea what happens for n > 6.  f might even
> be O(1).
"...you can have no idea..."

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#32849

Ben Bacarisse wrote:

> Give me a few values for f(n) (just list them: f(0) = ?, f(6) = ? and so
> on) for which you can be *certain* than f is not O(n^2).
> 
> You seem to be saying that f(5) = 125, f(6) =
> 808281277464764060643139600456536293376 means that f can't be O(n^2) but
> that's not so.  You can no idea what happens for n > 6.  f might even be
> O(1).

Difference across machines and the same machine of course can occur, but that doesn't prevent one from comparing the quality of an algorithm against another nor against itself when modified. 

If I called f(5) over and over it wouldn't be guaranteed to take the same amount of time/memory to return an answer.

f(5) ran 5 times could be {10ms, 15ms, 12ms, 14ms, 1hour}
f(6) could be {15ms, 17ms, 12ms, 18ms, 16ms}
f(100):       {107ms, 125ms, 120ms, 150ms, 135ms} 

and so on. Given sufficient runs and sufficient inputs you *COULD* derive the trend of the function and assign it a categorization. But you don't have to as this analytical framework exists to eliminate such a dependency on a machine and on limited inputs.

Determining the category of a function is accomplished by evaluating it's components. For instance:

"primitive" operations are considered O(1); In other words 1-step
These include: assignment, calls, arithmetic, index lookups, reference lookups, and a few others. So if I had a function "arrayMax" I could determine it's categorization as follows:

var intList = [8,6,7,15,5,3,0,9]

var arrayMax = (xs, n) => 
  n == 1 ? xs[0] : 
           Math.max(arrayMax(xs, n - 1),xs[n - 1]);

arrayMax(intList, intList.length)

///////////

when n == 1 the runtime is 3 // comparison + lookup + return
else it's the runtime of n - 1 for the recursive call + 7 primitives

or for clarity where T(n) is the runtime:

T(n) = 3, if n == 1
T(n) = T(n - 1) + 7, otherwise

in closed form: T(n) = 7(n - 1) + 3 = 7n - 4

So I'm claiming that 7n - 4 is O(n)

How do I prove it? I simply have to be consistent with the definition of O(n). So I'll "fill in the blanks and turn the crank"

Definition:
f(n) is O(g(n)), for f(n) <= c*g(n) where n >= n0

f(n) := arrayMax
g(n) := n

//7n - 4 <= c*n forAll n >= n0, so :
c := 7
n0 := 1

FIN.

instances of the proof:

var f = n => 7 * n - 4
var g = n => n

f(1) <= 7 * g(1) //true
f(2) <= 7 * g(2) //true
f(3) <= 7 * g(3) //true
...
f(4000) <= 7 * g(4000)
...
etc.


The above was only about evaluating time, but a similar approach is applied for space analysis. 

If this doesn't help, then I still don't understand where we missing each other

[toc] | [prev] | [next] | [standalone]

#32856

"Michael Haufe (TNO)" <tno@thenewobjective.com> writes:

> Ben Bacarisse wrote:
>
>> Give me a few values for f(n) (just list them: f(0) = ?, f(6) = ? and so
>> on) for which you can be *certain* than f is not O(n^2).
>> 
>> You seem to be saying that f(5) = 125, f(6) =
>> 808281277464764060643139600456536293376 means that f can't be O(n^2) but
>> that's not so.  You can no idea what happens for n > 6.  f might even be
>> O(1).

It might help if you commented on this part.  You seemed to be saying
that certain values for f (at some finite from the domain) were
incompatible with some big-O behaviours.  Hence I asked for an example:
some finite set of values for f that shows it not to be O(n^2).

> Difference across machines and the same machine of course can occur,
> but that doesn't prevent one from comparing the quality of an
> algorithm against another nor against itself when modified.

I'm talking about mathematical functions and a mathematical notation
that describes how function may or may not behave.

<snip>
> Determining the category of a function is accomplished by evaluating
> it's components. For instance:
> "primitive" operations are considered O(1); In other words 1-step

This is true for algorithms, yes, but the notation is more general than
that.  (I don't think this is the source of any confusion though.)

<snip example>
> If this doesn't help, then I still don't understand where we missing
> each other

I'm not sure how it could help.  If you agree that any finite set of
function values is compatible with that function being, say, O(n^2) then
we are in agreement.  You seemed to be saying otherwise at one point.

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#32659

jonas.thornvall@gmail.com wrote on 01 Mar 2017 in comp.lang.javascript:

>     inarray=arr.indexOf(nextnode);
>     if (inarray==undefined){ 

What nonsense 'undefined', Jonas, don't you ever read the specs?

Mozolla.org shows this:

"The first index of the element in the array; -1 if not found."

function updateVegetablesCollection (veggies, veggie) {
    if (veggies.indexOf(veggie) === -1) {
        veggies.push(veggie);
        console.log('New veggies collection is : ' + veggies);
    } else if (veggies.indexOf(veggie) > -1) {
        console.log(veggie + ' already exists in the veggies collection.');
    }
}

var veggies = ['potato', 'tomato', 'chillies', 'green-pepper'];

updateVegetablesCollection(veggies, 'spinach'); 
// New veggies collection is : potato,tomato,chillies,green-papper,spinach
updateVegetablesCollection(veggies, 'spinach'); 
// spinach already exists in the veggies collection.



-- 
Evertjan.
The Netherlands.
(Please change the x'es to dots in my emailaddress)

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | comp.lang.javascript

csiph-web