Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.javascript > #24504

Re: Difference between two arrays

X-Received by 10.58.119.100 with SMTP id kt4mr9101505veb.42.1401536128207; Sat, 31 May 2014 04:35:28 -0700 (PDT)
MIME-Version 1.0
Path csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!news.glorb.com!j5no70242qaq.1!news-out.google.com!s2ni265qap.0!nntp.google.com!Xl.tags.giganews.com!border1.nntp.dca.giganews.com!nntp.giganews.com!local2.nntp.dca.giganews.com!nntp.inch.com!news.inch.com.POSTED!not-for-mail
NNTP-Posting-Date Sat, 31 May 2014 06:35:28 -0500
Newsgroups comp.lang.javascript
From Spamless <Spamless@Nil.nil>
Subject Re: Difference between two arrays
References <z_ydnZKbtslwbR7OnZ2dnUVZ_rGdnZ2d@westnet.com.au> <85360d2c-679b-4d2f-b2f6-4ef9b4c83bd5@googlegroups.com>
User-Agent slrn/1.0.1 (FreeBSD)
Message-ID <iuCdnTK18O0dIxTOnZ2dnUVZ_sudnZ2d@inch.com> (permalink)
Date Sat, 31 May 2014 06:35:28 -0500
Lines 23
X-Usenet-Provider http://www.giganews.com
NNTP-Posting-Host 216.223.198.30
X-Trace sv3-Fq1nSGxNh5e2HPo4EYtq9xysnwh2SJJU9aAfu/Ar4WjNdgSWe8evMDstYYIjsp9goOuErulZZXQjYmK!/iG2RzOaNJ+nR4nIa6KZsNfiGO6qsptVpYwrF5g5FxvHJXrVjVBP9vGWrlIFXab2GjvGgzONuPSS!ZgDCuw==
X-Abuse-and-DMCA-Info Please be sure to forward a copy of ALL headers
X-Abuse-and-DMCA-Info Otherwise we will be unable to process your complaint properly
X-Postfilter 1.3.40
X-Original-Bytes 2253
Xref csiph.com comp.lang.javascript:24504

Show key headers only | View raw

On 2014-05-27, John C <rescattered@gmail.com> wrote:
>
> If your code is doing this often and the arrays have more than just a few 
> elements then you might run into performance issues. I think that .indexOf
> just implements a linear search hence the code you show is O(mn) where m, n are 
> the lengths of the arrays (so roughly 1,000,000 comparisons if m = n = 1000). 
> It might be better to first sort the arrays and then replace .indexOf with a
> binary search function (giving you something like O((m+n)(log(m) + log(n))). 
> For things like m = n = 1000 this would be an order of magnitude quicker. On 
> the other hand, for small m and n the time spent sorting might be hard to 
> justify.

A sort (say alphanumeric) and then a binary search might be quicker.

In perl I have often seen scripts which simply set an unordered list
to be searched as the keys of a hash (associative array) and then check
if the key exists since, in creating a hash, perl is rather efficient
in creating a structure (heap?) enabling efficient searching.

There are so many interpreters/JIT engines for Javascript that I don't
know if creating an associative array with keys being the elements of
an array (then checking for assoc_array[key])) would drastically
improve the search process.

Back to comp.lang.javascript | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Difference between two arrays Andrew Poulos <ap_prog@hotmail.com> - 2014-05-27 11:55 +1000
  Re: Difference between two arrays Denis McMahon <denismfmcmahon@gmail.com> - 2014-05-27 05:58 +0000
  Re: Difference between two arrays John C <rescattered@gmail.com> - 2014-05-27 03:34 -0700
    Re: Difference between two arrays Spamless <Spamless@Nil.nil> - 2014-05-31 06:35 -0500
      Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-31 14:57 +0200
        Re: Difference between two arrays Spamless <Spamless@Nil.nil> - 2014-06-01 03:43 -0500
          Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-06-01 14:01 +0200
            Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-06-01 16:53 +0200
  Re: Difference between two arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-05-27 13:41 +0100
    Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-27 17:41 +0200
    Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-27 17:49 +0200
      Re: Difference between two arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-05-27 17:34 +0100
        Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-27 19:33 +0200
          Re: Difference between two arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-05-27 20:03 +0100
    Re: Difference between two arrays Ben Bacarisse <ben.usenet@bsb.me.uk> - 2014-05-27 17:16 +0100
      Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-27 19:29 +0200
  Re: Difference between two arrays Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2014-05-27 17:21 +0200
  Re: Difference between two arrays Dr J R Stockton <reply1400@merlyn.demon.co.uk.invalid> - 2014-05-28 18:22 +0100
    Re: Difference between two arrays Dr J R Stockton <reply1400@merlyn.demon.co.uk.invalid> - 2014-05-30 22:23 +0100
    Re: Difference between two arrays "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2014-05-31 14:59 -0700
      Re: Difference between two arrays "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2014-06-01 00:50 +0200
        Re: Difference between two arrays "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2014-05-31 16:17 -0700
          Re: Difference between two arrays "Evertjan." <exxjxw.hannivoort@inter.nl.net> - 2014-06-01 10:49 +0200
            Re: Difference between two arrays "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2014-06-01 13:37 -0700
      Re: Difference between two arrays Dr J R Stockton <reply1400@merlyn.demon.co.uk.invalid> - 2014-06-01 18:56 +0100

csiph-web