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

Groups > comp.lang.javascript > #21339

Re: Strawmans prime sieve/filter

Show all headers | View raw

Ben Bacarisse wrote:

> Thomas 'PointedEars' Lahn <PointedEars@web.de> writes:
>> Stefan Weiss wrote:
> <snip>
>>> Maybe some memory could be reclaimed by periodically rewriting 'comp' to
>>> remove the parts of the sieve that are no longer needed? Just wondering,
>>> I didn't try it out.
>>
>> Maybe.  For reference, it was
>>
>> ,-
<news:0.f56f47af16523795dd40.20130911144711BST.87fvtb31y8.fsf@bsb.me.uk>
>> | 
>> | function sieve(max) {
>> |     var comp = [], primes = [], cur_prime = 2;
>> |     var upperLimit = Math.sqrt(max);
>> |     while (cur_prime < upperLimit) {
>> |         primes.push(cur_prime);
>> |         for (var mult = cur_prime * cur_prime; mult < max;
>> | mult += cur_prime)
>> |             comp[mult] = true;
>> |         while (comp[++cur_prime]);
>> |     }
>> |     for (; cur_prime < max; cur_prime++)
>> |         if (!comp[cur_prime])
>> |             primes.push(cur_prime);
>> |     return primes;
>> | }
>> | 
>> `----
>>
>> This can be optimized as follows:
>>
>>   function getPrimes (max)
>>   {
>>     var not_prime = Object.create(null);
>>     var prime = Object.create(null);
>>     var i = 2;
>>     var upperLimit = Math.sqrt(max);
>>
>>     while (i < upperLimit)
>>     {
>>       prime[i] = true;
>>
>>       for (var mult = i * i; mult < max; mult += i)
>>       {
>>         not_prime[mult] = true;
>>       }
>>
>>       while (not_prime[++i])
>>       {
>>         delete not_prime[i];
>>       }
>>     }
>>
>>     for (; i < max; ++i)
>>     {
>>       if (!not_prime[i])
>>       {
>>         prime[i] = true;
>>       }
>>
>>       delete not_prime[i];
>>     }
>>
>>     return prime;
>>   }
>>
>> The algorithm differs in that properties of the object referred to by
>> “not_prime” (formerly: “comp”) are removed as they are no longer needed.
>> This *might* decrease the memory footprint (thus increase the memory-
>> efficiency), but it adds another step (thus decreases the runtime-
>> efficiency).
> 
> You say above that this code is an optimised version of mine, but then
> you say it *might* decrease memory footprint,

I said the *deletion* might decrease the memory footprint.

> but that all the deleting decreases the runtime-efficiency.  In what sense
> has it been optimised?

- it can store primes up to 2⁵³−1 (an Array instance can only hold 2³²−1
  elements)
- reduced memory usage (Object instead of Array)
- potentially faster (no extra Array.prototype.push() calls)
- post-increment replaced with pre-increment (maybe faster)
 
> On two test engines (rhino and nodejs) the deleting has a huge impact on
> the run time (a factor of four in rhino and way more in nodejs -- so
> much so I killed it before getting a time).

Thanks.
 
> Setting comp = Object.create(null) is not much help in rhino (a small
> win with optimisation on but it slows things down without)
           ^^^^^^^^^^^^        ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Which JavaScript version, and what do you mean by that?

> but in the better engine (nodejs) it takes 1/4 off the run time.  It's a
> really neat thing to remember -- thanks.

You're welcome.  Which nodeJS and V8 versions?
 
>> The return value differs in that a reference to an Object instance is
>> returned, whose property *names* are the prime numbers in range.  In
>> order to get an Array of up to 2³²−1 prime numbers in range, you can
>> write:
>>
>>   var primes = Object.keys(getPrimes(x));
> 
> That just adds to the time, of course, but you need it to compare like
> with like.

Yes, you have to consider that this approach is more capable and flexible, 
at the cost of increased runtime towards the end when you really need (only) 
an Array or will never have more than 2³²−1 primes (upper bounds at or below 
ca. 10¹¹).

[Observing a need for arrays that can index up to 2⁵³ elements prior to 
Harmony, I am adding jsx.array.BigArray to JSX:array.js.  You will find it 
at <http://PointedEars.de/wsvn/JSX/trunk/array.js>.]
 
>> Note that the elements of the Array referred to by “primes” will be
>> string values (as all property names are strings, even the numeric ones). 
>> Mass conversion is possible:
>>
>>   var primes = Object.keys(getPrimes(x))
>>     /* convert to Number */
>>     .map(function (e) { return +e; })
> 
> I was surprised how fast this was in nodejs.  It's really slow in rhino.

You can skip this step if you are content with strings in the array because 
…
 
>>     /* sort numerically ascending */
>>     .sort(function (a, b) { return a - b; });

… this implicitly converts the elements to Number for sorting.  However, 
skipping the first step might be even slower in Rhino if conversion to 
Number is the cause.
 
> This had little cost in both engines.

Very good.

-- 
PointedEars

Twitter: @PointedEars2
Please do not Cc: me. / Bitte keine Kopien per E-Mail.

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

Thread

Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 19:09 -0700
  Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 05:57 +0200
    Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 21:22 -0700
    Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 21:50 -0700
      Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 13:45 +0200
        Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 06:33 -0700
        Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 06:41 -0700
          Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 18:37 +0200
          Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 19:54 +0200
            Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 12:46 -0700
              Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-09 23:25 +0200
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-09 14:58 -0700
        Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-11 10:39 +0200
          Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-11 02:54 -0700
          Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-11 12:59 +0200
          Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-12 20:17 +0100
            Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 02:27 +0200
              Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-13 04:03 +0200
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-12 19:30 -0700
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 05:15 +0200
                Re: Strawmans prime sieve/filter Stefan Weiss <krewecherl@gmail.com> - 2013-09-13 05:27 +0200
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 08:26 -0700
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 08:15 -0700
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-13 19:13 +0200
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-13 17:15 -0700
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 01:55 +0100
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 04:20 +0200
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 06:16 +0100
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 12:10 +0200
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 12:49 +0100
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-14 15:23 +0200
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-14 21:51 +0100
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-15 03:32 +0200
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-15 04:07 +0100
                Re: Strawmans prime sieve/filter Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2013-09-15 18:57 +0200
                Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-15 19:24 +0100
                Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-14 20:37 -0700
                Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-14 19:38 +0100
    Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 22:26 -0700
      Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-10 22:48 +0100
        Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-11 00:36 -0700
          Re: Strawmans prime sieve/filter Ben Bacarisse <ben.usenet@bsb.me.uk> - 2013-09-11 14:47 +0100
    Re: Strawmans prime sieve/filter jonas.thornvall@gmail.com - 2013-09-08 22:33 -0700
      Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2013-09-09 21:08 -0700
        Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2013-09-10 08:52 -0700
  Re: Strawmans prime sieve/filter Dr J R Stockton <reply1300@merlyn.demon.co.uk.invalid> - 2013-09-10 19:08 +0100
  Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-04-10 22:02 -0700
    Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-05-02 15:39 -0700
      Re: Strawmans prime sieve/filter "Chris M. Thomasson" <no@spam.invalid> - 2014-05-02 15:54 -0700

csiph-web