search in a sorted list

By ARTRAG

Enlighted (6923)

ARTRAG's picture

08-03-2014, 19:15

I need to speed up a search in a list.
Now I do a trivial cpir, the code looks like this:

n_block_up: equ	12 
block_up: 
	db	42 
	db	55 
	db	126 
	db	127 
	db	128 
	db	129 
	db	136 
	db	145 
	db	146 
	db	156 
	db	157 
	db	161 
; in E the byte to search
search:
	ld	hl,block_up
	ld	bc,n_block_up
	ld	a,e
	cpir
	ret	nz ; not found
found:
       etc...

But.... as the list is sorted there could be a faster way to search the byte in E
The fact is that my list is always short, no more that 10 - 12 bytes, so implementing binary search seems a bit too much to me... Any solution off the shell ?

Login or register to post comments

By turbor

Hero (519)

turbor's picture

08-03-2014, 20:16

Artrag, one way to speed it up if you have sufficient memory is to make a pointers towards the entry. If you can align the list to a 256-byte-boundary +1 address then you can speed things up like this:

org #c001
block_up: 
        db	42 
        db	55 
        db	126 
 	db	127 
        db	128 
        db	129 
        db	136 
        db     145 
        db	146 
        db	156 
        db	157 
        db	161 
; in l the byte to search
search:
       ld    h,pointerlist/256
       ld    a,(hl)
       or    a
       ret   z ; not found
       ld h,#c0
       ld l,a
found:
       ; now hl is the adress in the list of the found value
       .....

      ; now have a pointer list aligned to a 256 byte address
      org #d000
pointerlist:
      ds 41,0 ; 41 bytes, all zero
      db 1      ; byte 42 points to index 1
      ds 13,0 ; bytes 43 up to and including 54 are zero again
      db 2      ; byte 55 points to index 2
      ds 70,0  ; bytes 56 up to and including 125 are zero again
      db 3,4,5,6 ; pointers to the value 126,...,129
      ds 6,0    ; bytes for 'not found' again
      db 7
      etc...
 

Of course, if you simply want to check for a value and do not need the index in the list, you can just as well drop the list.
And a possible drawback here is that you can not have double entries in your original list...

If you adapt the list at runtime then you will need some extra code to keep the pointerlist up to date

By wouter_

Champion (508)

wouter_'s picture

08-03-2014, 20:34

It's very hard to give a good answer to this question. It really depends on the exact situation. So I'll just give some general ideas.

Is the requirement really to check whether a byte is present in a (sorted) table? Do you need to know the position in the table or just whether it's present or not?

Or can the table be encoded in some other way? E.g. an array of 256 bytes containing 0/1 for present/not-present). Alternatively you could pack 256 bits in 32 bytes. Or use a single bit in a 256-byte table and pack 8 tables in that space.

Does it need to be a table at all or can it be a dedicated routine per set of values? In that case you could do a hard-coded binary search. I mean the values are hard-coded as the operands of 'cp' instructions. One compare instruction tells you whether a value is smaller, equal or bigger, so take advantage of that (a bit like a ternary instead of a binary search tree).

You could also take advantage of dense regions in the table (126-129 in your example). You don't need to compare every value in such a region, just the lower and upper bound.

If it really needs to be a small table of (sorted) values, you could still do binary search. But have specific routines for each table size (if there are only a small number of different table sizes). That way you can greatly simplify the table-indexing logic.

If some values are more likely than others, you could sort on likelihood instead of numerical value and do a linear search.

By ARTRAG

Enlighted (6923)

ARTRAG's picture

09-03-2014, 00:40

I need only to know if my byte is present or not in my list. The list is static and built at compile time.

I see that using 256 bytes aligned at 0x100 leads to the fastest solution, even if it seems a bit drastic

Actually I was thinking in a solution using cpi, where I stop the comparison when the current value of (HL) is larger than A, but I cannot find a correct (and efficient) way to test flags

By PingPong

Prophet (4093)

PingPong's picture

09-03-2014, 02:54

ARTRAG wrote:

I need to speed up a search in a list.
Now I do a trivial cpir, the code looks like this:

n_block_up: equ	12 
block_up: 
	db	42 
	db	55 
	db	126 
	db	127 
	db	128 
	db	129 
	db	136 
	db	145 
	db	146 
	db	156 
	db	157 
	db	161 
; in E the byte to search
search:
	ld	hl,block_up
	ld	bc,n_block_up
	ld	a,e
	cpir
	ret	nz ; not found
found:
       etc...

But.... as the list is sorted there could be a faster way to search the byte in E
The fact is that my list is always short, no more that 10 - 12 bytes, so implementing binary search seems a bit too much to me... Any solution off the shell ?

Umh, actually you have an average of 6 checks per find operation (assuming 12 values and a brute force sequential search). If the size is 12 switching to a binary search can cut down the number of checks to log2(12) in the average, so about 4 checks. Is the gain relevant for you ?

By ARTRAG

Enlighted (6923)

ARTRAG's picture

09-03-2014, 13:58

Not really.
Actually I have on average 12 checks as the probability I find the byte I look for in the list is very low.
For this reason by simply stopping the search when I find a value bigger than the one I look for would give a gain leading to an average of 6 checks. This is in theory, as testing the result of cpi for condition A&gtCryingHL) seems to add a lot of overhead making vain the whole thing.
On the other head having a 256 byte table is very space consuming, as I need to do more than cone search in short lists.
The idea of packing 8 list search in a byte in the table using different bits is interesting, even if I could need to pack
2+12+4 = 18 searches ... quite a lot...
maybe a more complex approach could allow me to use 2 bits for obstacles plus 2 bits for each destructible item...
anyway I need to study a bit, thanks for the suggestions for now

By hit9918

Prophet (2927)

hit9918's picture

09-03-2014, 19:40

With compile time data, could have a binary search encoded in the code

	cp 129
	jr c,136_to_161
	;is between 42_and_129
	cp ...
	jr c,...

Very fast and takes less than 256 bytes.
12 entries maybe make 24 codes? Then it's about 100 bytes.

By hit9918

Prophet (2927)

hit9918's picture

09-03-2014, 19:44

It is for tile tests?
One time 256 bytes lookuptable and the entries got info bits like isobstacle, isdestructible,...