468,244 Members | 2,060 Online

# Array manipulation question

say, we have the following:

// declare an array
myArray = []; // short hand? same as myArray = new Array ?

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

// now problem to solve
// fact: the above array has 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 understand Array has a bunch of methods, but not sure which one is a
good one to solve the above problem.

Thanks.
Jun 27 '08 #1
15 1503
DL schreef:
say, we have the following:

// declare an array
myArray = []; // short hand? same as myArray = new Array ?

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

// now problem to solve
// fact: the above array has 4 sets of data, namely 3 zeros and 1 of
value one.
Hi,

Well, they do not contain a 'set' but just a plain value.
// 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 understand Array has a bunch of methods, but not sure which one is a
good one to solve the above problem.
No offense, but this is so basic I advise you to buy a book on
JavaScript (any will do, but O'Reilly's Definitive Guide is good).

Here follows an example to get you going.
(It can be written in many different ways, and shorter, but I hope this
version is clear to you.)

<script type="text/javascript">
var myArray = [];
// populate it
myArray[0] = 0;
myArray[1] = 1;
myArray[2] = 0;
myArray[3] = 0;

var arrLength = myArray.length;
var firstVal = myArray[0];

for(var i=0;i<arrLength;i++){
if (myArray[i] != firstVal){
break;
}
}
</script>
>
Thanks.
You're welcome.

Regards,
Erwin Moller
Jun 27 '08 #2
On May 30, 2:24 pm, Erwin Moller wrote:
<snip>
var firstVal = myArray[0];

for(var i=0;i<arrLength;i++){
if (myArray[i] != firstVal){
break;
}}
<snip>

You may as well start the loop counter at 1 as you already know that -
firstVal - will be equal to - myArray[i] - when - i - is zero as you
just set it to that value. (Or was that a deliberate mistake as a
learning exercise?)
Jun 27 '08 #3
Henry schreef:
On May 30, 2:24 pm, Erwin Moller wrote:
<snip>
>var firstVal = myArray[0];

for(var i=0;i<arrLength;i++){
if (myArray[i] != firstVal){
break;
}}
<snip>

You may as well start the loop counter at 1 as you already know that -
firstVal - will be equal to - myArray[i] - when - i - is zero as you
just set it to that value. (Or was that a deliberate mistake as a
learning exercise?)
Totally true Henry. A few wasted CPU cycles.

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.).

I just wanted the guy to have some material to work with, and didn't
give the code too much thought. ;-)

Regards,
Erwin Moller
Jun 27 '08 #4
On May 30, 9:24*am, Erwin Moller
Hi,

Well, they do not contain a 'set' but just a plain value.
// 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 understand Array has a bunch of methods, but not sure which one is a
good one to solve the above problem.

No offense, but this is so basic I advise you to buy a book on
JavaScript (any will do, but O'Reilly's Definitive Guide is good).

Here follows an example to get you going.
(It can be written in many different ways, and shorter, but I hope this
version is clear to you.)

<script type="text/javascript">
var myArray = [];
// populate it
myArray[0] = 0;
myArray[1] = 1;
myArray[2] = 0;
myArray[3] = 0;

var arrLength = myArray.length;
var firstVal = myArray[0];

for(var i=0;i<arrLength;i++){
* * * * if (myArray[i] != firstVal){
* * * * * * * * alert ("Black sheep found.");
* * * * * * * * break;
* * * * }}

</script>
Thanks.

You're welcome.

Regards,
Erwin Moller
No offense at all, I know it's embrassing and thanks for the book
recommendation.
Jun 27 '08 #5
On May 30, 6:03 am, DL <tatata9...@gmail.comwrote:
say, we have the following:

// declare an array
myArray = []; // short hand? same as myArray = new Array ?

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

// now problem to solve
// fact: the above array has 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 understand Array has a bunch of methods, but not sure which one is a
good one to solve the above problem.

Thanks.
Here's an interesting way. It occurred to me that the JavaScript
"some" method could be used with a bit of work...

function monoArray(arr) {
function isEqToFirst(element,index,array) {
return (element!==array[0]);
}
if (arr && arr.length>0) {
return !(arr.some(isEqToFirst));
}
}

var passed = monoArray([2,5,8,1,4]);
passed = monoArray([12, 12, 12, 12, 12]);
passed=monoArray([5]);
passed=monoArray([]);
passed=monoArray();
passed=monoArray(5);

This only works for JavaScript interpreters which have the "some"
method. See "compatibility" here for the code to add if you're afraid
of running into older, less capable ECMAScript implementations.

http://developer.mozilla.org/en/docs...cts:Array:some
Jun 27 '08 #6
On May 30, 5:50 pm, timothytoe <timothy...@gmail.comwrote:
On May 30, 6:03 am, DL <tatata9...@gmail.comwrote:
say, we have the following:
// declare an array
myArray = []; // short hand? same as myArray = new Array ?
// populate it
myArray[0] = 0;
myArray[1] = 0;
myArray[2] = 1;
myArray[3] = 0;
// now problem to solve
// fact: the above array has 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 understand Array has a bunch of methods, but not sure which one is a
good one to solve the above problem.
Thanks.

Here's an interesting way. It occurred to me that the JavaScript
"some" method could be used with a bit of work...

function monoArray(arr) {
function isEqToFirst(element,index,array) {
return (element!==array[0]);
}
if (arr && arr.length>0) {
return !(arr.some(isEqToFirst));
}

}

var passed = monoArray([2,5,8,1,4]);
passed = monoArray([12, 12, 12, 12, 12]);
passed=monoArray([5]);
passed=monoArray([]);
passed=monoArray();
passed=monoArray(5);

This only works for JavaScript interpreters which have the "some"
method. See "compatibility" here for the code to add if you're afraid
of running into older, less capable ECMAScript implementations.

http://developer.mozilla.org/en/docs...5_Reference:Gl...
Sent too early. A more compact version of the same thing:

function monoArray(arr) {
if (arr && arr.length>0) {
return !arr.some(function(element,index,array) {
return element!==array[0];
});
}
}
Jun 27 '08 #7
On May 30, 6:03 am, DL <tatata9...@gmail.comwrote:
say, we have the following:

// declare an array
myArray = []; // short hand? same as myArray = new Array ?

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

// now problem to solve
// fact: the above array has 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 understand Array has 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 use Array.reduce to find the sum of all the
elements in the array. If the sum is zero of the length of the array,
you pass. Else you fail.
Jun 27 '08 #8
On May 30, 9:04*pm, timothytoe <timothy...@gmail.comwrote:
On May 30, 6:03 am, DL <tatata9...@gmail.comwrote:

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.

Jun 27 '08 #9
On May 30, 6:51 pm, DL <tatata9...@gmail.comwrote:
On May 30, 9:04 pm, timothytoe <timothy...@gmail.comwrote:
On May 30, 6:03 am, DL <tatata9...@gmail.comwrote:
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.
I think it may be overkill for the task at hand, but you seemed
interested in learning how to use the Array methods available in
JavaScript, so I thought I'd give it a shot. Look into Array.map and
Array.reduce as well.
Jun 27 '08 #10
On May 30, 6:51 pm, DL <tatata9...@gmail.comwrote:
On May 30, 9:04 pm, timothytoe <timothy...@gmail.comwrote:
On May 30, 6:03 am, DL <tatata9...@gmail.comwrote:
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.
Jun 27 '08 #11
In comp.lang.javascript message <6cc6b834-acfb-4496-ac61-d4d663bf04c0@i1
8g2000prn.googlegroups.com>, Sat, 31 May 2008 07:56:46, timothytoe
<ti********@gmail.composted:
>On May 30, 6:51 pm, DL <tatata9...@gmail.comwrote:
On May 30, 6:03 am, DL <tatata9...@gmail.comwrote:
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.htmjscr maths, dates, sources.
Jun 27 '08 #12
On May 30, 3:38*pm, Erwin Moller
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) {
break;
}
}

--Jorge.
Jun 27 '08 #13
timothytoe wrote:
On May 30, 6:51 pm, DL <tatata9...@gmail.comwrote:
>On May 30, 9:04 pm, timothytoe <timothy...@gmail.comwrote:
>>On May 30, 6:03 am, DL <tatata9...@gmail.comwrote:
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
Jun 27 '08 #14
On Jun 1, 10:56 am, Michael Wojcik <mwoj...@newsguy.comwrote:
timothytoe wrote:
On May 30, 6:51 pm, DL <tatata9...@gmail.comwrote:
On May 30, 9:04 pm, timothytoe <timothy...@gmail.comwrote:
On May 30, 6:03 am, DL <tatata9...@gmail.comwrote:
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.
Jun 27 '08 #15
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
Jun 27 '08 #16

### This discussion thread is closed

Replies have been disabled for this discussion.