Efficient way to remove elements from array Topic is solved

Get help with using AutoHotkey and its commands and hotkeys
pneumatic
Posts: 286
Joined: 05 Dec 2016, 01:51

Efficient way to remove elements from array

28 Mar 2019, 18:38

Hello

Code: Select all

Array := [1,0,1,1,0,1,0,0,0,1,0]
What is the most efficient way to remove all the 0's from this array, leaving no "blank" elements?

Thanks
wolf_II
Posts: 2688
Joined: 08 Feb 2015, 20:55

Re: Efficient way to remove elements from array

28 Mar 2019, 19:00

Try this:

Code: Select all

Array := [1,0,2,3,0,4,0,0,0,5,0]
ArrRemoveZero(Array)



;-------------------------------------------------------------------------------
ArrRemoveZero(ByRef arr) { ; return a array without zeroes
;-------------------------------------------------------------------------------
    loop, % Len := arr.Length()
        if (arr[i := Len - A_Index + 1] = 0)
            arr.RemoveAt(i)
}
I hope that helps.
User avatar
jeeswg
Posts: 6904
Joined: 19 Dec 2016, 01:58
Location: UK

Re: Efficient way to remove elements from array

28 Mar 2019, 19:06

Here are 2 attempts:

Code: Select all

q:: ;remove empty keys
Array := [1,0,1,1,0,1,0,0,0,1,0]
Loop, % vNum := Array.Length()
{
	if !Array[vNum]
		Array.RemoveAt(vNum)
	vNum--
}
MsgBox, % JEE_ObjList(Array)
return

w:: ;remove empty keys (shorter but less readable)
Array := [1,0,1,1,0,1,0,0,0,1,0]
Loop, % vNum := Array.Length()
	if !Array[vNum--]
		Array.RemoveAt(vNum+1)
MsgBox, % JEE_ObjList(Array)
return
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
User avatar
lvalkov
Posts: 37
Joined: 08 Mar 2019, 16:39

Re: Efficient way to remove elements from array  Topic is solved

28 Mar 2019, 19:27

The most efficient way would be to pluck the elements you would like to remain and place them in their own new array, optionally overwriting the original one.

Code: Select all

Array := [1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0]
Ones := []
Ones.SetCapacity(Array.GetCapacity())

for k, v in Array
	if v
		Ones.Push(v)

Array := Ones
Ones := ""
pneumatic
Posts: 286
Joined: 05 Dec 2016, 01:51

Re: Efficient way to remove elements from array

28 Mar 2019, 20:45

lvalkov wrote:
28 Mar 2019, 19:27
The most efficient way would be to pluck the elements you would like to remain and place them in their own new array
But I didn't want to change the name of the array, I just wanted to remove elements from the already existing array.
Restoring the original name seems to require a lot of extra processing.
Last edited by pneumatic on 28 Mar 2019, 20:55, edited 3 times in total.
User avatar
jeeswg
Posts: 6904
Joined: 19 Dec 2016, 01:58
Location: UK

Re: Efficient way to remove elements from array

28 Mar 2019, 20:50

- If you do RemoveAt, the array has to be shuffled, which is costly.
- So, lvalkov's approach could be the most efficient.
- If you do Array := Ones, Ones := "", that's not costly, because you're not duplicating the data, you're just creating a 2nd reference to an object, and then removing a reference to an object. (When you duplicate strings, you duplicate data, that is costly.)
- You could do benchmark tests: try both approaches (e.g. 100 times each) and measure the time taken.
homepage | tutorials | wish list | fun threads | donate
WARNING: copy your posts/messages before hitting Submit as you may lose them due to CAPTCHA
Klarion
Posts: 176
Joined: 26 Mar 2019, 10:02

Re: Efficient way to remove elements from array

28 Mar 2019, 21:53

@jeeswg
Yes you are right

I have confirmed
The latter was faster 17% (Looped 10 million times, 30 sec vs 25 sec)

But, I prefer to your code
Because
It is more efficient - easy to write, easy to read, easy to follow, easy to understand, easy to fix and easy to remember
Speed does not matter, except you have to iterate 100 million times (in that case you'd better use C language)
The matter is to write and to maintenance. That is the real problem in my previous experiences.

Regards
User avatar
lvalkov
Posts: 37
Joined: 08 Mar 2019, 16:39

Re: Efficient way to remove elements from array

29 Mar 2019, 13:09

@pneumatic
I don't quite understand what you meant by "extra processing". Performance-wise the impact of reassigning arrays is minimal, as @jeeswg has pointed out. The only "extra" thing required is allocating enough space for the temp array. That is the trade-off. If you find typing it out unwieldly, define a function. Example:

Code: Select all

Array := [1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0]
Array := remove_zeros(Array)

remove_zeros(Array) {
	if !IsObject(Array)
		throw "Invalid argument. Not an object."
	
	Ones := []
	Ones.SetCapacity(Array.GetCapacity())

	for k, v in Array
		if v
			Ones.Push(v)

	return Ones
}


@Klarion
Mind revealing your testing methodology? These numbers seem bogus.
Disclaimer: I haven't looked into the exact implementation. The following is based off of common sense assumptions about the likely implementation. If anyone deeply familiar with it happens to spot any errors in my analysis, feel free to correct them.
Traversing an array requires O(n). Appending an element to an array, without resizing - O(1). Deleting an element from an array at index - O(1). Shifting the rest of the elements that follow to close the gap after deleting - O(n).
Therefore, the .Push() method should be achievable in O(n) time, whereas .RemoveAt() requires O(n^2). Having tested the performance of both methods empirically myself, I have become even more doubtful of the validity of your results.

Code: Select all

#NoEnv
#KeyHistory 0
SetBatchLines -1
ListLines Off

tick() {
	DllCall("QueryPerformanceCounter", "Int64*", tick)
	return tick
}

rand(a, b) {
	Random r, a, b
	return r
}

make_arrays(size, ByRef Mixed, ByRef MixedClone, ByRef Ones) {
	if !IsObject(Mixed)
		Mixed := []

	Mixed.SetCapacity(size)
	Loop % size - Mixed.Count()
		Mixed.Push(rand(0, 1))

	MixedClone := Mixed.Clone()
		
	Ones := []
	Ones.SetCapacity(size)
}

tick_removeat(Array) {
	start := tick()

	Loop, % vNum := Array.Length()
		if !Array[vNum--]
			Array.RemoveAt(vNum+1)

	return tick() - start
}

tick_push(Mixed, Ones) {
	start := tick()

	for k, v in Mixed
		if v
			Ones.Push(v)

	return tick() - start
}

csv := "numElem,.RemoveAt(),.Push()`n"
for k, numElements in [1, 10, 100, 1000, 10000, 100000, 1000000]
{
	make_arrays(numElements, Mixed, MixedClone, Ones)
	csv .= numElements "," tick_removeat(MixedClone) "," tick_push(Mixed, Ones) "`n"
}

MsgBox % Clipboard := csv
The unit of measurement is ticks. The log-log plot, I've attached at the end, also seems to confirm my assumptions.

Code: Select all

numElem | .RemoveAt() | .Push()
-------------------------------
      1 |          38 |      32
     10 |          55 |      34
    100 |         308 |     192
   1000 |        4060 |    1928
  10000 |      213709 |   19687
 100000 |    25565595 |  204756
1000000 |  7728849218 | 2106586
Running the 1M .RemoveAt() benchmark alone took 12m 20s on a 6600K, clocked at 4.5 GHz. A far cry from your 10M / 30s. Frankly, I dared not go for the 10M.
Lastly, a O(n^2) algorithm is still a O(n^2) algorithm. C won't help much.
Attachments
loglog.png
loglog.png (24.75 KiB) Viewed 1214 times
User avatar
sinkfaze
Posts: 613
Joined: 01 Oct 2013, 08:01

Re: Efficient way to remove elements from array

29 Mar 2019, 13:35

Code: Select all

Array := [1, 0, 2, 3, 0, 4, 0, 0, 0, 5, 0]
For i, v in Array
	out .=	v ","
Array :=	StrSplit(Trim(RegExReplace(out,"\b0,"),","),",")
:?:
User avatar
nnnik
Posts: 4317
Joined: 30 Sep 2013, 01:01
Location: Germany

Re: Efficient way to remove elements from array

29 Mar 2019, 17:12

@Ivalkov the array is a binary lookup array.
In v2 array indexing is solved by simple direct array access - however it only works for numbers only.

Regardless the array has changed which is a cost in itself - e.g. you would have lost all binary data in the new array you created.
Recommends AHK Studio
Klarion
Posts: 176
Joined: 26 Mar 2019, 10:02

Re: Efficient way to remove elements from array

29 Mar 2019, 20:20

@lvalkov
Wow
Nice presentation
You are a real professional
I'm loving it

Thanks for good show
Klarion
Posts: 176
Joined: 26 Mar 2019, 10:02

Re: Efficient way to remove elements from array

29 Mar 2019, 20:21

@lvalkov
Here comes my humble codes
Pls do not blame elementary style
That's me

Code: Select all

startTime := A_TickCount	
Loop 10000000		;  Ten_Million
{
	myArray := [1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0]				;  30 sec
	Loop, % myMax := myArray.Length()
		If !myArray[myMax --]
			myArray.RemoveAt(myMax + 1)
}
stopTime1 := RegExReplace(Floor((A_TickCount - startTime)/1000), "(?<=\d)(?=(\d{3})+$)", ",") " sec"	
startTime := A_TickCount	
Loop 10000000	
{
	myArray := [1, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0]				;  25 sec     
	myArray2 := []
	myArray2.SetCapacity(myArray.GetCapacity())
	For Each, x In myArray
		If x
			myArray2.Push(x)							
	myArray := myArray2
	myArray2 := ""
}
stopTime2 := RegExReplace(Floor((A_TickCount - startTime)/1000), "(?<=\d)(?=(\d{3})+$)", ",") " sec"	
MsgBox % stopTime1 "`n" stopTime2
Last edited by Klarion on 29 Mar 2019, 21:05, edited 2 times in total.
Klarion
Posts: 176
Joined: 26 Mar 2019, 10:02

Re: Efficient way to remove elements from array

29 Mar 2019, 20:35

@sinkfaze
Good Idea
recorded 36 sec for 10 million iteration
User avatar
lvalkov
Posts: 37
Joined: 08 Mar 2019, 16:39

Re: Efficient way to remove elements from array

31 Mar 2019, 06:49

@Klarion
I see. You have literally "Looped 10 million times" each function on the same, fixed-size array. Apparently, I was trying to read way too much into your assertion. That was a reading comprehension fail on my part. You are, however, correct in claiming that the difference in the execution speeds of both approaches is negligible. For small enough N array elements, that is.


@nnnik
Would you care to further elaborate on your "binary data" remark? I am not entirely certain what kind of binary data you're referring to. I presume if a given element of the array stored binary data that the data would have to be copied over to the new array. If you're talking about some other kind of binary data, specific to the particular instance of the array (metadata?), then it would be lost, indeed.

Return to “Ask For Help”

Who is online

Users browsing this forum: Bing [Bot] and 207 guests