getting arraylist elements with same value (not trivial. you have to read!)

  • Thread starter Thread starter The Crow
  • Start date Start date
T

The Crow

i have a arraylist. say it contains integer values. i want to be able to
inform user, which indexes in the array contain same values. but there can
be N different values, and M different indexes having the same value.
actually i will do this with javascript array to inform user which input's
have same value. but i think its not a matter.
 
i have a arraylist. say it contains integer values. i want to be able to
inform user, which indexes in the array contain same values. but there can
be N different values, and M different indexes having the same value.
actually i will do this with javascript array to inform user which input's
have same value. but i think its not a matter.
Click to expand...

what exactly is your problem? to find all duplicates at all, to write
effective code or to inform the user of duplicates?

Wiktor Zychla
 
three of them. find all duplicates doing this most effective way, and inform
user which textbox'es conflict with each other. ive done my job. some parts
are turkish (in alert message) but i think, it would be easly unserstood.
here are my codes. all advices (espessialy about performanse greatly
appreciated.)

<html>
<head>
<title></title>
<script type="text/javascript">
var caseSensitive = false;


function getAllTextInputs(beginningId)
{
aryResult = new Array();
var allTextInputElements = document.getElementsByTagName('input');
var count = 0;
for(var i = 0; i < allTextInputElements.length; i++)
{
var currentElement = allTextInputElements;
if(currentElement.type == "text" &&
currentElement.id.indexOf(beginningId) == 0)
{
aryResult[count++] = allTextInputElements;
}
}
return aryResult;
}

function getUniqueInputs(aryTextInputs)
{
var aryUniqueInputs = new Array();

for(var i = 0; i < aryTextInputs.length; i++)
{
var tempUniqueArray = null;
for(var j = i + 1; j < aryTextInputs.length; j++)
{
var xValue = caseSensitive ? aryTextInputs.value :
aryTextInputs.value.toLowerCase();
var yValue = caseSensitive ? aryTextInputs[j].value :
aryTextInputs[j].value.toLowerCase();
if(xValue == yValue)
{
if(tempUniqueArray == null)
{
tempUniqueArray = new Array();
tempUniqueArray.push(aryTextInputs);
}
tempUniqueArray.push(aryTextInputs[j]);
aryTextInputs.splice(j, 1);
j--;
}
}
if(tempUniqueArray != null)
{
aryUniqueInputs.push(tempUniqueArray);
}
}
return aryUniqueInputs;
}

function getAlertMessage(aryUniqueInputs)
{
var alertMessage = 'Aþþaðýdaki giriþler ayný deðeri içermekte :';
for(var i = 0; i < aryUniqueInputs.length; i++)
{
alertMessage += "\r\n";
for(var j = 0; j < aryUniqueInputs.length; j++)
{
alertMessage += aryUniqueInputs[j].friendlyName != null ?
aryUniqueInputs[j].friendlyName : aryUniqueInputs[j].id;
if(j != aryUniqueInputs.length -1)
alertMessage += ", ";
}
}
return alertMessage;
}

function validate_Form()
{
debugger;
var aryTextInputs = getAllTextInputs('kod');

var aryUniqueInputs = getUniqueInputs(aryTextInputs);

if(aryUniqueInputs.length != 0)
{
var alertMessage = getAlertMessage(aryUniqueInputs);
alert(alertMessage);
return false;
}
else
return true;
}
</script>
</head>
<body>
<form onsubmit="return validate_Form();">
Alan 1<input type="text" id="kod00" friendlyName="Alan 1"><br>
Alan 2<input type="text" id="kod01" friendlyName="Alan 2"><br>
Alan 3<input type="text" id="kod02" friendlyName="Alan 3"><br>
Alan 4<input type="text" id="kod03" friendlyName="Alan 4"><br>
Alan 5<input type="text" id="kod04" friendlyName="Alan 5"><br>
Alan 6<input type="text" id="kod05" friendlyName="Alan 6"><br>
Alan 7<input type="text" id="kod06" friendlyName="Alan 7"><br>
Alan 8<input type="text" id="kod07" friendlyName="Alan 8"><br>
<input type="submit">
</form>
</body>
</html>
 
i have a arraylist. say it contains integer values. i want to be able to
inform user, which indexes in the array contain same values. but there can
be N different values, and M different indexes having the same value.
actually i will do this with javascript array to inform user which input's
have same value. but i think its not a matter.
Click to expand...

Given that you're not actually using C#, I *strongly* suggest you ask
on a JavaScript newsgroup instead. Answers here are less likely to be
from JS experts, and so could easily be wrong or less than optimal.
 
the algorithm was more important for me. it doesnt matter c# or js.
Click to expand...

But which algorithm you use may well depend on the platform - different
platforms have different functionality available.
 
the functionality available will not different. come on, this is just adding
and removing values from/to array and maybe creating another array. it may
be a matter if you use C array but not for a modern language...
the reason why i posted this message to this group is, i think jscript
programmers does not code alghorithms most of their time.
 
the functionality available will not different. come on, this is just adding
and removing values from/to array and maybe creating another array. it may
be a matter if you use C array but not for a modern language...
the reason why i posted this message to this group is, i think jscript
programmers does not code alghorithms most of their time.
Click to expand...

No, the functionality available may well be different. For instance,
JavaScript may or may not have a "Set" implementation (like Java does)
but .NET certainly doesn't - you generally use a Hashtable and either a
fixed value or use the key as the value.

Similarly, JS may or may not have the equivalent of .NET's
Array.IndexOf(Array, object, int).

In general terms, you could go through each element of the array (or
ArrayList - you seem to be using the two terms as if they're
interchangable), and either find the index of the first array element
*after* that source element which is equal to it, *or* you could build
up a Set/Hashtable of "elements seen so far".
 
see my code above, can you see a hash table or "set" implementation.. dont
tell me doing so is more effective. because inserting to hashtable is costly
operration regarding to simply adding to array (btw i know array is not
arraylist.). and i wont do concurrent reads that will give me back lost cpu
cycles.. so hashtable is not efficient.
 
see my code above, can you see a hash table or "set" implementation.. dont
tell me doing so is more effective. because inserting to hashtable is costly
operration regarding to simply adding to array (btw i know array is not
arraylist.).
Click to expand...

That entirely depends on how the array is implemented. Guess what? That
depends on the platform. You can't add to an array in .NET - they're a
fixed size. So, if you're actually after a JavaScript solution then
once again, I'll suggest you ask in the JS newsgroup.
and i wont do concurrent reads that will give me back lost cpu
cycles.. so hashtable is not efficient.
Click to expand...

Have you benchmarked this to find out whether it's actually an issue?
Just how big is your array in real life anyway? It's not worth worrying
about efficiency if the simplest code works fast enough. (Not that I
believe your code is the simplest anyway, but anyway...)

Note that if you have a large array (which is the only time it would
actually matter), especially with a significant number of duplicates,
that would be more efficient - finding a match in a hashtable is faster
than having to loop through the array. Your solution is always O(n^2) -
a hashtable version would be O(n) I believe - according to MSDN, both
inserting into a hashtable and retrieving from it are O(1) operations.

If you're absolutely determined to use the O(n^2) solution, you could
at least call toLowerCase on aryTextInputs *outside* the "j" loop -
you're currently lower-casing the same string every time. (In fact, you
might want to consider creating a separate array and lower-casing all
the values *once*, to avoid doing it within the loop at all.)


Anyway, it seems you've already decided that your solution is the best
one and you're unwilling to listen to my comments, so we might as well
call a halt here.
 
lots of thanks for all your comments. and i dont think my solution is the
best. but even msdn says O(1) and my solution seems to be O(n^2), i think
inserting to hashtable is costly operation then mine because it will do a
lot of decisions and searching.. i agree rest of your comments.
 
lots of thanks for all your comments. and i dont think my solution is the
best. but even msdn says O(1) and my solution seems to be O(n^2), i think
inserting to hashtable is costly operation then mine because it will do a
lot of decisions and searching.. i agree rest of your comments.
Click to expand...

Your solution may well be faster for small arrays, but will degrade
nastily when you have to search over larger ones. My solution will be
slower for small arrays, but won't degrade nearly as badly.

If the arrays are small though, do you really care about performance?
It's going to be blazingly quick whichever version you choose - just
how often are you expecting to do this, anyway?
 
Back
Top