Solved

Javascript equivalent of php's array_intersect?

Posted on 2006-07-19
5
2,003 Views
Last Modified: 2010-10-05
Hi,

Let start of by having comma-separated strings with [a-z] words (no other characters):
var string1 = "apple,pear,banana,grape,strawberry";
var string2 = "strawberrry,raspberry,blueberry";

What is the most efficent way to determine which words are in both arrays. (assuming the strings are split on comma's)

regular expressions and split/join are fine ofcourse, but I rather avoid nested loops.

Any thoughs?

-r-
0
Comment
Question by:Roonaan
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 2
  • 2
5 Comments
 
LVL 12

Expert Comment

by:enachemc
ID: 17138253
say

var string_1 = "," + string1 + ";";
for (<each item in string2>) if(string_1.indexOf("," + item + ",") != -1) <common item>;
0
 
LVL 19

Accepted Solution

by:
dakyd earned 500 total points
ID: 17140080
I'm not sure, but doing an indexOf() on either of the strings seems like it would be roughly equivalent (performance-wise) to doing a full search of the split array.  I can't back it up, but that's just what gut instinct tells me.

Assuming string1 has m elements and string2 has n elements, my idea was to make an algorithm with O(m+n) rather than O(m*n).  So, split the strings, sort the resulting arrays, then do a linear search through the two arrays.  Since they're sorted, you never have to back-track, and each element in arr1 is compared to an element in arr2 once and only once.  Of course, if indexOf() is fast enough, it may not matter at all.  Regardless, hope that helps.

<script type="text/javascript">
var string1 = "apple,pear,banana,grape,strawberry";
var string2 = "strawberry,raspberry,blueberry";

var arr1 = string1.split(",").sort();
var arr2 = string2.split(",").sort();

var common = new Array();
for (var i = 0, n = arr1.length, j = 0, k = arr2.length; (i < n) && (j < k); i ++)
{
  if (arr1[i] == arr2[j])
  {
    common[common.length] = arr1[i];
    j ++;
  }
  else if (arr1[i] > arr2[j])
  {
    j ++;
    i --;
  }
}

alert(common.toString());
</script>
0
 
LVL 12

Expert Comment

by:enachemc
ID: 17140111
Your algorithm is faster, but not O(m+n) (because of sorting). Sorting is at best O(m) + O(n).
0
 
LVL 49

Author Comment

by:Roonaan
ID: 17140128
I think I'll go with your code dakyd, with minor adjustment of using common.push(arra1[i]);

Thanks a lot

-r-
0
 
LVL 19

Expert Comment

by:dakyd
ID: 17140312
Oops, you're right, I hadn't thought about the sorting ... regardless, glad it helped.
0

Featured Post

Want Experts Exchange at your fingertips?

With Experts Exchange’s latest app release, you can now experience our most recent features, updates, and the same community interface while on-the-go. Download our latest app release at the Android or Apple stores today!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: DanRollins
This article describes a JavaScript program that creates a maze made of hexagonal cells.  In Part 2 (http://www.experts-exchange.com/Programming/Languages/Scripting/JavaScript/A_7850-Hex-Maze-Part-2.html), we'll extend the program by adding a depth-…
Today, the web development industry is booming, and many people consider it to be their vocation. The question you may be asking yourself is – how do I become a web developer?
The viewer will learn the basics of jQuery, including how to invoke it on a web page. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery.: (CODE)
The viewer will learn the basics of jQuery including how to code hide show and toggles. Reference your jQuery libraries: (CODE) Include your new external js/jQuery file: (CODE) Write your first lines of code to setup your site for jQuery…
Suggested Courses

632 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question