Solved

Javascript equivalent of php's array_intersect?

Posted on 2006-07-19
5
1,798 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
  • 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

What Should I Do With This Threat Intelligence?

Are you wondering if you actually need threat intelligence? The answer is yes. We explain the basics for creating useful threat intelligence.

Join & Write a Comment

The task A number given should be formatted for easy reading by separating digits into triads. Format must be made inline via JavaScript, i.e., frameworks / functions are not welcome. So let’s take a number like this “12345678.91¿ and format i…
Nothing in an HTTP request can be trusted, including HTTP headers and form data.  A form token is a tool that can be used to guard against request forgeries (CSRF).  This article shows an improved approach to form tokens, making it more difficult to…
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…

707 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

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now