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

Groups > comp.lang.javascript > #39672 > unrolled thread

Faster procedure then shift to remove first element of list or array?

Back to article view | Back to comp.lang.javascript

Contents

  Faster procedure then shift to remove first element of list or array? Jonas Thörnvall <jonas.thornvall@gmail.com> - 2021-03-16 22:51 -0700
    Re: Faster procedure then shift to remove first element of list or array? "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2021-03-17 06:09 -0700
      Re: Faster procedure then shift to remove first element of list or array? Jonas Thörnvall <jonas.thornvall@gmail.com> - 2021-03-17 06:45 -0700
      Re: Faster procedure then shift to remove first element of list or array? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2021-03-18 12:26 +0100
        Re: Faster procedure then shift to remove first element of list or array? "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2021-03-18 06:30 -0700
          Re: Faster procedure then shift to remove first element of list or array? Thomas 'PointedEars' Lahn <PointedEars@web.de> - 2021-03-19 02:59 +0100
          Re: Faster procedure then shift to remove first element of list or array? Jonas Thörnvall <jonas.thornvall@gmail.com> - 2021-03-19 12:39 -0700
            Re: Faster procedure then shift to remove first element of list or array? "Michael Haufe (TNO)" <tno@thenewobjective.com> - 2021-03-19 13:55 -0700
            Re: Faster procedure then shift to remove first element of list or array? "sc...@sauyet.com" <scott@sauyet.com> - 2021-03-19 14:42 -0700

#39672 — Faster procedure then shift to remove first element of list or array?

is there a faster way to remove first element of array/list then shift?

[toc] | [next] | [standalone]

#39676

On Wednesday, March 17, 2021 at 12:51:36 AM UTC-5, jonas.t...@gmail.com wrote:
> is there a faster way to remove first element of array/list then shift?

Shift is probably fast enough. Have you tried profiling your code?

[toc] | [prev] | [next] | [standalone]

#39678

onsdag 17 mars 2021 kl. 14:09:27 UTC+1 skrev Michael Haufe (TNO):
> On Wednesday, March 17, 2021 at 12:51:36 AM UTC-5, jonas.t...@gmail.com wrote: 
> > is there a faster way to remove first element of array/list then shift?
> Shift is probably fast enough. Have you tried profiling your code?
The shift was not necessary, so it probably faster just add up counter, it probably does not matter though, the problem is setTimeout, which keep addup latency for every call.

function STARTPLAY(){
	if (keepGoing) {
		stopRec=setTimeout(STARTPLAY,copyEv[q]);
		if (q<copyEv.length) {
			midEvent++;
			if (mode=="play"){pianoKeypressOut();}
			outportarr[outportindex].send(noteMessage[q]);
			q++;
		}
	}
}

[toc] | [prev] | [next] | [standalone]

#39689

Michael Haufe (TNO) wrote:

> On Wednesday, March 17, 2021 at 12:51:36 AM UTC-5, jonas.t...@gmail.com
> wrote:
>> is there a faster way to remove first element of array/list then shift?
> 
> Shift is probably fast enough. Have you tried profiling your code?

The algorithm of Array.prototype.shift() is of order 𝓞(n). The fastest way 
to delete the first element of a zero-indexed iterable is

  delete a[0]

which is of order 𝓞(1), whereas “a” refers to the iterable.  However, 
whether the afterwards non-existing first element (unless it is prevented by 
some mechanism) shows up not at all, or as “undefined” instead, depends on 
how the iterable is accessed, and the accessors and access hooks that may be 
defined.

And it does not change the "length" of the iterable, unless a corresponding 
“delete” hook has been defined (with Proxy).

However:

Array.prototype.shift() usually is not available for non-Array instances; so 
in order to use .shift(), it may be necessary to convert the non-Array to 
Array, or treat it as such (by Function.prototype.call()/.apply()), which 
can be expensive.

A direct, relatively efficient way corresponding to .shift() exists for 
NodeList implementations with nodeList.removeChild(nodeList.firstChild).

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | <http://PointedEars.de/es-matrix>
<https://github.com/PointedEars> | <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | Please do not cc me./Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#39690

On Thursday, March 18, 2021 at 6:26:14 AM UTC-5, Thomas 'PointedEars' Lahn wrote:

> Array.prototype.shift() usually is not available for non-Array instances; so 
> in order to use .shift(), it may be necessary to convert the non-Array to 
> Array, or treat it as such (by Function.prototype.call()/.apply()), which 
> can be expensive. 

"The shift function is intentionally generic; it does not require that its this value be an Array object. Therefore it can be transferred to other kinds of objects for use as a method."
<https://tc39.es/ecma262/#sec-array.prototype.shift>

How expensive is call/apply really? If it's less than O(n) then the entirety is still O(n) from that standpoint. Practically we could measure these two head to head to know the actual difference,
but who cares? We know we could do better with a data structure different from an array such as a Finger Tree which provides O(1) access to the head and tail and logarithmic concatenation and logarithmic random access.

[toc] | [prev] | [next] | [standalone]

#39704

Michael Haufe (TNO) wrote:

> On Thursday, March 18, 2021 at 6:26:14 AM UTC-5, Thomas 'PointedEars' Lahn
> wrote:
>> Array.prototype.shift() usually is not available for non-Array instances;
>> so in order to use .shift(), it may be necessary to convert the non-Array
>> to Array, or treat it as such (by Function.prototype.call()/.apply()),
>> which can be expensive.
> 
> "The shift function is intentionally generic; it does not require that its
> this value be an Array object. Therefore it can be transferred to other
> kinds of objects for use as a method."
> <https://tc39.es/ecma262/#sec-array.prototype.shift>

That is precisely what I said.
 
> How expensive is call/apply really? […]

Calling .call()/.apply() is one aspect, but I was also considering the cost 
of accessing the data and moving it around.  Think about the example of 
.slice() vs. direct access that we discussed earlier.

-- 
PointedEars
FAQ: <http://PointedEars.de/faq> | <http://PointedEars.de/es-matrix>
<https://github.com/PointedEars> | <http://PointedEars.de/wsvn/>
Twitter: @PointedEars2 | Please do not cc me./Bitte keine Kopien per E-Mail.

[toc] | [prev] | [next] | [standalone]

#39709

torsdag 18 mars 2021 kl. 14:30:07 UTC+1 skrev Michael Haufe (TNO):
> On Thursday, March 18, 2021 at 6:26:14 AM UTC-5, Thomas 'PointedEars' Lahn wrote: 
> 
> > Array.prototype.shift() usually is not available for non-Array instances; so 
> > in order to use .shift(), it may be necessary to convert the non-Array to 
> > Array, or treat it as such (by Function.prototype.call()/.apply()), which 
> > can be expensive.
> "The shift function is intentionally generic; it does not require that its this value be an Array object. Therefore it can be transferred to other kinds of objects for use as a method." 
> <https://tc39.es/ecma262/#sec-array.prototype.shift> 
> 
> How expensive is call/apply really? If it's less than O(n) then the entirety is still O(n) from that standpoint. Practically we could measure these two head to head to know the actual difference, 
> but who cares? We know we could do better with a data structure different from an array such as a Finger Tree which provides O(1) access to the head and tail and logarithmic concatenation and logarithmic random access.
What is a finger tree could you provide a link? I know about pointers and such but never heard the term finger tree?

[toc] | [prev] | [next] | [standalone]

#39711

On Friday, March 19, 2021 at 2:39:19 PM UTC-5, jonas.t...@gmail.com wrote:

> What is a finger tree could you provide a link? I know about pointers and such but never heard the term finger tree?

<https://en.wikipedia.org/wiki/Finger_tree>
<https://andrew.gibiansky.com/blog/haskell/finger-trees/>
<https://www.staff.city.ac.uk/~ross/papers/FingerTree.pdf>

[toc] | [prev] | [next] | [standalone]

#39712

Jonas wrote:
> Michael Haufe (TNO) wrote: 

>> but who cares? We know we could do better with a data structure different
>> from an array such as a Finger Tree which provides O(1) access to the head 
>> and tail and logarithmic concatenation and logarithmic random access.

> What is a finger tree could you provide a link? I know about pointers and 
> such but never heard the term finger tree?

Are you really that lazy?  The Wikipedia article Michael Haufe mentioned is
the first (non-ad) webpage result in a Google search [1], a DuckDuckGo search
[2], or a Bing search [3].

It's fine not to know, or to ask for further clarifications if you've actually
done some research.  But please, do that first.


  [1] https://www.google.com/search?q=finger+tree
  [2] https://duckduckgo.com/?q=finger+tree
  [3] https://www.bing.com/search?q=finger+tree

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.javascript

csiph-web