[Closed] Last bit?

Hah, that’s a good one, I’ll go with

fn lastBit bA =
(
	bAA = bA as Array
	return bAA[bAA.count]
)

Works fast (<5ms) even with cases like this:

bA = #{1..10000}
bA.count = 500000

fn lastBit3 ba step:1000 = (

	bb = copy ba
	sub = #{1..10}
	
	do (		
		
		bc = copy bb
		bc -= sub
		
		if (ba * bc).numberset == 0 do exit
			
		bb = bc
		sub = #{1..(sub.count + step)}
		
	) while true

	local b  = bb as array
	b[b.count]
	
)

another try

fn lastBit4 ba step:5000 = (
	
	startIndex = amax (ba.count - step) 1
	sub = #{ startIndex..ba.count }
	bb
	
	while (bb = sub * ba).numberset == 0 do (
		
		if startIndex == 1 do exit
		oldStartIndex = startIndex
		startIndex = amax (startIndex - step) 1
		sub = #{ startIndex..oldStartIndex }
		
	)
	
	local b = bb as array
	if b.count > 0 then b[ b.count ] else undefined
	
)

and the pre last one

fn lastBit5 ba = (

	z = substituteString (ba as string) ".." ","
	z = substituteString z "{" "("
	z = substituteString z "}" ")"
	bb = execute z
	if bb.count > 0 then bb[ bb.count ] else undefined
	
)

and the last

fn lastBit6 ba range: = (
	
	local lastBit
	
	if range == unsupplied then range = [ 1 , ba.count ]
		
	half = int((range.x + range.y)/2)
				
	
	if not (bb = ba * #{half..range.y}).isEmpty then (
		
		if bb.numberset == 1 do return (bb as array)[1]
		lastBit = lastBit6 ba range:[ half, range.y ]
		
	) 
	else if not (bb = ba * #{range.x..half}).isEmpty then (
			
		if bb.numberset == 1 do return (bb as array)[1]
		lastBit = lastBit6 ba range:[ range.x, half ]
		
	) else lastBit = undefined
	
	lastBit
	
)

ok…

there are only four methods that makes sense to discuss as you can see:

fn lastbit0 bits = 
(
	n 
	for k in bits do n = k
	n
)
fn lastbit1 bits = 
(
	arr = bits as array
	arr[arr.count]
)
fn lastbit2 bits = 
(
	str = bits as string
	ss = filterstring str ".,}"
	ss[ss.count] as integer
)
fn lastbit3 bits = 
(
	b
	n = bits.numberset
	for k=1 to bits.count while n > -1 where bits[k] do 
	(
		b = k
		n -= 1
	)
	b
)

‘for each’, ‘convert to array’, ‘convert to string’, and ‘brute-force’…

now check the numbers for the bitarray:

a = #{1..1000000}

(
	t = timestamp()
	h = heapfree

v = lastbit0 a
--v = lastbit1 a
--v = lastbit2 a
--v = lastbit3 a

	format "% >> time:% heap:%
" v (timestamp() - t) (h - heapfree)
)
1000000 >> time:389 heap:55984048L
1000000 >> time:144 heap:55994688L
1000000 >> time:2 heap:624L
1000000 >> time:1259 heap:111938704L

now we are changing the rule. the bitarray is:

a = #{}
for k=1 to 1000000 by 2 do append a k

here is the numbers:

(
	t = timestamp()
	h = heapfree

--v = lastbit0 a
--v = lastbit1 a
--v = lastbit2 a
v = lastbit3 a

	format "% >> time:% heap:%
" v (timestamp() - t) (h - heapfree)
)

999999 >> time:207 heap:27987800L
999999 >> time:79 heap:27997448L
999999 >> time:4011 heap:32000496L
999999 >> time:922 heap:55982096L

the situation has changed …

Just wanted to point out the same thing about non-continuous bitarrays, you’re too fast

(
fn lastbit0 bits = 
(
	n 
	for k in bits do n = k
	n
)
fn lastbit1 bits = 
(
	arr = bits as array
	arr[arr.count]
)
fn lastbit2 bits = 
(
	str = bits as string
	ss = filterstring str ".,}"
	ss[ss.count] as integer
)
fn lastbit3 bits = 
(
	b
	n = bits.numberset
	for k=1 to bits.count while n > -1 where bits[k] do 
	(
		b = k
		n -= 1
	)
	b
)

fn lastBit6 ba range: = (
	
	if ba.isEmpty do return undefined
		
	local lastBit
	
	if range == unsupplied then range = [ 1 , ba.count ]
		
	half = int((range.x + range.y)/2)
				
	
	if not (bb = ba * #{half..range.y}).isEmpty then (

		lastBit = if bb.numberset == 1 then (bb as array)[1] else lastBit6 ba range:[ half, range.y ]
		
	) 
	else if not (bb = ba * #{range.x..half}).isEmpty then (

		lastBit = if bb.numberset == 1 then (bb as array)[1] else lastBit6 ba range:[ range.x, half ]
		
	) else lastBit = undefined
	
	lastBit
	
)


a = #{}
for k=1 to 1000000 by 2 do append a k
	

gc()
t1=timestamp()
hf = heapfree

	i = lastbit0 a

format "lastbit0 Time: %sec. Mem: % lastBit: %
" ((timestamp()-t1)/1000 as float) (hf-heapfree) i

gc()
t1=timestamp()
hf = heapfree

	i = lastbit1 a

format "lastbit1 Time: %sec. Mem: % lastBit: %
" ((timestamp()-t1)/1000 as float) (hf-heapfree) i

gc()
t1=timestamp()
hf = heapfree

	i = lastbit2 a

format "lastbit2 Time: %sec. Mem: % lastBit: %
" ((timestamp()-t1)/1000 as float) (hf-heapfree) i

gc()
t1=timestamp()
hf = heapfree

	i = lastbit3 a

format "lastbit3 Time: %sec. Mem: % lastBit: %
" ((timestamp()-t1)/1000 as float) (hf-heapfree) i


gc()
t1=timestamp()
hf = heapfree

	i = lastbit6 a

format "lastbit6 Time: %sec. Mem: % lastBit: %
" ((timestamp()-t1)/1000 as float) (hf-heapfree) i
)

lastbit0 Time: 0.443sec. Mem: 28023904L lastBit: 999999
lastbit1 Time: 0.162sec. Mem: 28024016L lastBit: 999999
lastbit2 Time: 9.489sec. Mem: 32006928L lastBit: 999999
lastbit3 Time: 2.117sec. Mem: 55992967L lastBit: 999999
lastbit6 Time: 0.012sec. Mem: 2752L lastBit: 999999

The binary search one is pretty good, other ones will beat it in cases like

a = #{1}
a.count = 1000000

but for a general case and big array it’s a winner.

the using of binary chop is definitely the good idea… but it might be optimized. the .numberset method is very slow. there is a way to avoid its using