Efficient way to remove elements from array Topic is solved

[pneumatic]

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]

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.

[jeeswg]

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

[lvalkov]

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]

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.

[jeeswg]

- 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.

[Klarion]

@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

[lvalkov]

@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.

[sinkfaze]

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,"),","),",")

[nnnik]

@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.

[Klarion]

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

Thanks for good show

[Klarion]

@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

[Klarion]

@sinkfaze
Good Idea
recorded 36 sec for 10 million iteration

[lvalkov]

@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.

[paulpma]

@jeeswg

Code: Select all

MsgBox, % JEE_ObjList(Array)

Would you be willing to share JEE_ObjList.. I have searched forum / web and had no luck. Thank you very much.

[Chunjee]

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?

I find this the most human efficient:

Code: Select all

A := new biga() ; requires https://www.npmjs.com/package/biga.ahk

Array := [1,0,1,1,0,1,0,0,0,1,0]
NewArray := A.compact(Array)
msgbox, % A.print(NewArray)
; => [1, 1, 1, 1, 1]

.compact Creates an array with all falsey values removed. The values false, 0, and "" are falsey.