Array manipulation question

On May 30, 6:51 pm, DL <tatata9... (AT) gmail (DOT) com> wrote:

On May 30, 9:04 pm, timothytoe <timothy... (AT) gmail (DOT) com> wrote:



On May 30, 6:03 am, DL <tatata9... (AT) gmail (DOT) com> wrote:

say, we have the following:

// declare anarray
myArray = []; // short hand? same as myArray = newArray ?

// populate it
myArray[0] = 0;
myArray[1] = 0;
myArray[2] = 1;
myArray[3] = 0;

// now problem to solve
// fact: the abovearrayhas 4 sets of data, namely 3 zeros and 1 of
value one.
// say, the business rule is, if all set of data are of same value ( 0
|| 1), then do nothing
else alert ('hey dark sheep found').

I understandArrayhas a bunch of methods, but not sure which one is a
good one to solve the above problem.

Thanks.

By the way, if the only possibilities for the data are 0 and 1 (as in
your example), you could useArray.reduce to find the sum of all the
elements in thearray. If the sum is zero of the length of thearray,
you pass. Else you fail.- Hide quoted text -

- Show quoted text -

Wow, the code of your most recent post is elegant. The data is one of
three: 0,1,2. But it looks like one-dimensional array is not good
enough to solve the problem. Too bad my local Barnes and Noble does
not carry the recommended book, can't wait.

A few more solutions.

First, use Array.min() and Array.max() to find the minimum and maximum
values in the array, then compare them.

Array.max = function( array ){
return Math.max.apply( Math, array );
};

Array.min = function( array ){
return Math.min.apply( Math, array );
};

One more solution is interesting to me. Sort the array and then see if
the initial value is the same as the final value. It's a pretty
compact solution, but it could be slow if your array has a lot of
items in it. Without knowing the possibilities for your data, it's
hard to know what the best solution is.

Since you only have three possible values, it might be useful to have
a count(arr,value) function that counts how many times a given value
shows up in the array. Then you could use count() to solve your
problem.

In comp.lang.javascript message <6cc6b834-acfb-4496-ac61-d4d663bf04c0@i1
8g2000prn.googlegroups.com>, Sat, 31 May 2008 07:56:46, timothytoe
<timothytoe (AT) gmail (DOT) com> posted:

On May 30, 6:51 pm, DL <tatata9... (AT) gmail (DOT) com> wrote:
On May 30, 6:03 am, DL <tatata9... (AT) gmail (DOT) com> wrote:

myArray = []; // short hand? same as myArray = newArray ?

myArray[0] = 0;
myArray[1] = 0;
myArray[2] = 1;
myArray[3] = 0;

// now problem to solve
// fact: the abovearrayhas 4 sets of data, namely 3 zeros and 1 of
value one.
// say, the business rule is, if all set of data are of same value ( 0
|| 1), then do nothing
else alert ('hey dark sheep found').

Wow, the code of your most recent post is elegant. The data is one of
three: 0,1,2. But it looks like one-dimensional array is not good
enough to solve the problem. Too bad my local Barnes and Noble does
not carry the recommended book, can't wait.

One more solution is interesting to me. Sort the array and then see if
the initial value is the same as the final value. It's a pretty
compact solution, but it could be slow if your array has a lot of
items in it. Without knowing the possibilities for your data, it's
hard to know what the best solution is.

Unless the array is usually all the same (plausible) and the .sort
method is peculiarly fast for the special case of all the data being the
same (unlikely?), using .sort should be, for large data, much slower
than needed.

Any solution requiring more than a single pass of the array is likely to
be sub-optimum.

OP : Consider the possibilities (for numeric data) of

myArray = [0,0,0,1,1,0,0]
L = myArray.length
A = []
while (--L) A[myArray[L]] = 1
X = A.join("").length

If there were only two possible values, for each of which .toString()
gives a single character, then one could use, I think,
X = /^(.)\1*$/.test(myArray.join(""))
but it destroys its input.

It's a good idea to read the newsgroup c.l.j and its FAQ. See below.

--
(c) John Stockton, nr London UK. ?@merlyn.demon.co.uk IE7 FF2 Op9 Sf3
news:comp.lang.javascript FAQ <URL:http://www.jibbering.com/faq/index.html>.
<URL:http://www.merlyn.demon.co.uk/js-index.htm> jscr maths, dates, sources.
<URL:http://www.merlyn.demon.co.uk/> TP/BP/Delphi/jscr/&c, FAQ items, links.

timothytoe wrote:

On May 30, 6:51 pm, DL <tatata9... (AT) gmail (DOT) com> wrote:
On May 30, 9:04 pm, timothytoe <timothy... (AT) gmail (DOT) com> wrote:
On May 30, 6:03 am, DL <tatata9... (AT) gmail (DOT) com> wrote:
say, we have the following:
...
// now problem to solve
// fact: the abovearrayhas 4 sets of data, namely 3 zeros and 1 of
value one.
// say, the business rule is, if all set of data are of same value ( 0
|| 1), then do nothing
else alert ('hey dark sheep found').
I understandArrayhas a bunch of methods, but not sure which one is a
good one to solve the above problem.

By the way, if the only possibilities for the data are 0 and 1 (as in
your example), you could useArray.reduce to find the sum of all the
elements in thearray. If the sum is zero of the length of thearray,
^^ or

you pass. Else you fail.

This approach has the same time complexity as the obvious one
(comparing every element against the first) - it's O(N). In some
languages it might even have a smaller coefficient, because addition
can be cheaper than testing and branching on modern processors. No
Javascript interpreter is going to reduce the expression to
sufficiently low-level operations for that effect to appear, though.

(An APL compiler might, since this sort of thing is a common APL idiom.)

Wow, the code of your most recent post is elegant. The data is one of
three: 0,1,2.

Then the summation method won't work - but the simple scan-and-compare
approach remains valid.

If we really want to overcomplicate things, here's an alternative that
works for three values: Treat the array as an N-digit trinary number.
(The code's a bit simpler if you treat it as little-endian, so
anarray[0] is the least-significant digit.) Convert that number to a
native integer, by multipling anarray[0] by 3, anarray[1] by 9, etc.
If the result is 0, you have an array of all zeros. If the result is
3**N - 1, you have an array of all twos (just as binary 1111 is 2**4 -
1). If the result is (3**N-1)/2, you have an array of all ones
(because eg trinary 1111 is trinary 2222 divided by 2). Any other
value, and you have a dark sheep.

The code for this can be written relatively elegantly. Unfortunately
it's pointless, since it's just more work for the same answer.

Obviously this can be extended to higher number bases, though
computing some of the allowed results is less convenient.

But it looks like one-dimensional array is not good
enough to solve the problem.

Why not?

You can use a data structure that gives you a constant-time solution
for this problem: an array that also tracks the minimum and maximum
values during insertion, any structure that gives you constant-time
access to the minimum and maximum values, etc. So a simple array does
not give you a time-optimal solution.

However, it seems unlikely a Javascript program will be asked to
perform this operation on an array so large that it makes any
discernible different.

A few more solutions.

First, use Array.min() and Array.max() to find the minimum and maximum
values in the array, then compare them.

Another O(N) solution, but now with a larger constant, since we're
probably looking at two passes through the array. (Array could find
both the minimum and maximum on the first pass and cache the values
for subsequent min() and max() calls; or it could track min and max
during insertion, using extra space to amortize those operations and
making this an O(1) solution. But I doubt any implementations do that.)

One more solution is interesting to me. Sort the array and then see if
the initial value is the same as the final value. It's a pretty
compact solution, but it could be slow if your array has a lot of
items in it. Without knowing the possibilities for your data, it's
hard to know what the best solution is.

Well, that's at best an O(N lg N) solution, so it's hard to see when
it ever wins.

But we can pessimize this further. Compute all rotations of the array
and see if their initial elements match: O(N**2). Do the same with all
permutations: O(N!).

But my favorite is to record the value of the first element, then
choose an element at random and see if they match. If not, return the
"dark sheep" result. If so, repeat with another random element.

Continue until you have reached a preset confidence level. (Computing
the probability of missing a dark sheep, given N elements, M trials, K
dark sheep, and an unbiased PRNG is left as an exercise for the reader.)

This probabilistic approach lets you decide just how much time you
want to waste over using the obvious approach, and how correct you
want to be. It maximizes flexibility, which we all know is always a
Good Thing.

--
Michael Wojcik
Micro Focus
Rhetoric & Writing, Michigan State University

On May 30, 3:38*pm, Erwin Moller
<Since_humans_read_this_I_am_spammed_too_m... (AT) spamyourself (DOT) com> wrote:

A better routine would also check for the number of array elements and
stuff like that (eg refuse if only 1 element, or refuse if 0.).

The way you wrote it, it refuses already :

var i, firstVal= myArray[0];

for (i= 1; i< myArray.length; i++) {
if (myArray[i] !== firstVal) {
alert ("Hey black sheep found.");
break;
}
}

--Jorge.

On Jun 1, 10:56 am, Michael Wojcik <mwoj... (AT) newsguy (DOT) com> wrote:

timothytoe wrote:
On May 30, 6:51 pm, DL <tatata9... (AT) gmail (DOT) com> wrote:
On May 30, 9:04 pm, timothytoe <timothy... (AT) gmail (DOT) com> wrote:
On May 30, 6:03 am, DL <tatata9... (AT) gmail (DOT) com> wrote:
say, we have the following:
...
// now problem to solve
// fact: the abovearrayhas 4 sets of data, namely 3 zeros and 1 of
value one.
// say, the business rule is, if all set of data are of same value ( 0
|| 1), then do nothing
else alert ('hey dark sheep found').
I understandArrayhas a bunch of methods, but not sure which one is a
good one to solve the above problem.

By the way, if the only possibilities for the data are 0 and 1 (as in
your example), you could useArray.reduce to find the sum of all the
elements in thearray. If the sum is zero of the length of thearray,

^^ or

you pass. Else you fail.

This approach has the same time complexity as the obvious one
(comparing every element against the first) - it's O(N). In some
languages it might even have a smaller coefficient, because addition
can be cheaper than testing and branching on modern processors. No
Javascript interpreter is going to reduce the expression to
sufficiently low-level operations for that effect to appear, though.

(An APL compiler might, since this sort of thing is a common APL idiom.)

Wow, the code of your most recent post is elegant. The data is one of
three: 0,1,2.

Then the summation method won't work - but the simple scan-and-compare
approach remains valid.

If we really want to overcomplicate things, here's an alternative that
works for three values: Treat the array as an N-digit trinary number.
(The code's a bit simpler if you treat it as little-endian, so
anarray[0] is the least-significant digit.) Convert that number to a
native integer, by multipling anarray[0] by 3, anarray[1] by 9, etc.
If the result is 0, you have an array of all zeros. If the result is
3**N - 1, you have an array of all twos (just as binary 1111 is 2**4 -
1). If the result is (3**N-1)/2, you have an array of all ones
(because eg trinary 1111 is trinary 2222 divided by 2). Any other
value, and you have a dark sheep.

The code for this can be written relatively elegantly. Unfortunately
it's pointless, since it's just more work for the same answer.

Obviously this can be extended to higher number bases, though
computing some of the allowed results is less convenient.

But it looks like one-dimensional array is not good

enough to solve the problem.

Why not?

You can use a data structure that gives you a constant-time solution
for this problem: an array that also tracks the minimum and maximum
values during insertion, any structure that gives you constant-time
access to the minimum and maximum values, etc. So a simple array does
not give you a time-optimal solution.

However, it seems unlikely a Javascript program will be asked to
perform this operation on an array so large that it makes any
discernible different.

A few more solutions.

First, use Array.min() and Array.max() to find the minimum and maximum
values in the array, then compare them.

Another O(N) solution, but now with a larger constant, since we're
probably looking at two passes through the array. (Array could find
both the minimum and maximum on the first pass and cache the values
for subsequent min() and max() calls; or it could track min and max
during insertion, using extra space to amortize those operations and
making this an O(1) solution. But I doubt any implementations do that.)

One more solution is interesting to me. Sort the array and then see if
the initial value is the same as the final value. It's a pretty
compact solution, but it could be slow if your array has a lot of
items in it. Without knowing the possibilities for your data, it's
hard to know what the best solution is.

Well, that's at best an O(N lg N) solution, so it's hard to see when
it ever wins.

But we can pessimize this further. Compute all rotations of the array
and see if their initial elements match: O(N**2). Do the same with all
permutations: O(N!).

But my favorite is to record the value of the first element, then
choose an element at random and see if they match. If not, return the
"dark sheep" result. If so, repeat with another random element.

Continue until you have reached a preset confidence level. (Computing
the probability of missing a dark sheep, given N elements, M trials, K
dark sheep, and an unbiased PRNG is left as an exercise for the reader.)

This probabilistic approach lets you decide just how much time you
want to waste over using the obvious approach, and how correct you
want to be. It maximizes flexibility, which we all know is always a
Good Thing.

--
Michael Wojcik
Micro Focus
Rhetoric & Writing, Michigan State University

The best solution depends on whether you're optimizing for size or
speed. I was a videogame programmer for about a decade, so a lot of
time I had to optimize for speed. But sometimes we had to optimize for
size. Especially for ROM cartridge machines, or when the game machine
had a small amount of working RAM.

If the user can notice the difference in speed, optimize for that.
Else, optimize for size. If neither matters much, write your code
clearly so it's easy to understand and maintain.

timothytoe wrote:

The best solution depends on whether you're optimizing for size or
speed.

The "best" solution depends on many things, and optimization for size
or speed is often well down the list.

Sometimes it's best to optimize for understanding. Or for insight. Or
for humor - which is just insight in fancy dress.

--
Michael Wojcik
Micro Focus
Rhetoric & Writing, Michigan State University