Computing mode of a array

[nunos]

Hi all.

I have been having some difficulty trying to compute the mode (the value that appear most often) of an array of bytes, given its length.

I have tried more than one approach, but, besides the fact that it doesnt work 100%, I believe there's a simpler way to go about it.

So, consider, for example, the array

Code Select Expand


.data

buff BYTE 1, 2, 3, 1, 2, 2, 1, 2, 3, 4, 1, 2, 3
tam DWORD $-buff

CALC_MODE proto arr: byte ptr, len: DWORD


In this case, CALC_MODE should return 2.

Any suggestion is appreciated.

Thanks.

[dedndave]

create a second array filled with 0's - let's call it result
it's length has to be the highest value in the first array +1  (length = 5 for the example shown)
then, scan the first array
each time a 1 occurs in the first array, increment result[1]
each time a 2 occurs in the first array, increment result[2]
and so on

        mov     si,arr
        mov     cx,len
        mov     bh,0

loop00: mov     bl,[si]
        inc     si
        inc byte ptr result[bx]
        loop    loop00

when you are done, you have to find the largest value in the result array and convert that to the index value

[Tight_Coder_Ex]

Another possibility is sort the array and then scan it keeping track of the base address of each change and the number of occurences

eg:  1,1,1,1,2,2,2,2,2,3,3,3,4  lets say buff is @ 403000 and you have a local arry on the stack

whenever the value changes you push the address of ESI on the stack

12FFCC = 403000
12FFC8 = 403004
12FFC4 = 403009
12FFC0 = 40300C

As you go along use EAX as an index pointer of which has the most elements which can be calculated in the loop.

This way your array is never any bigger than the individual values in the array.  If this is as clear as mud I'll be happy to provide an example

[nunos]

create a second array filled with 0's - let's call it result
it's length has to be the highest value in the first array +1  (length = 5 for the example shown)
then, scan the first array
each time a 1 occurs in the first array, increment result[1]
each time a 2 occurs in the first array, increment result[2]
and so on

        mov     si,arr
        mov     cx,len
        mov     bh,0

loop00: mov     bl,[si]
        inc     si
        inc byte ptr result[bx]
        loop    loop00

when you are done, you have to find the largest value in the result array and convert that to the index value

The algorithm you mentioned is exactly what I have thought before.

My problem is, since I am not that experienced in assembly, I can't (yet) think very well in terms of "assembly programming" so I get stuck very often.

As I mentioned I tried to imlpement that algo, but got lost in the middle. Would you be kind enough to post the code? It would be greatly appreciated.

Thanks.

[Tight_Coder_Ex]

I'm not sure whom you want to replay as it seems you want me to respond but your quoting Dave.  Anyway I'll post mine. My code has one problem in that if the value with the greatest number has a duplicate then the first one encountered will be in EDX

You can do your own modification for either word or dword values, but we start with a byte  array that's already sorted and upon completion
DH = the value that has the highest number of occurences and DL = How many

Code Select Expand

.686P
.model flat, stdcall
option casemap :none

.data

  Buff db 3,3,3,3,3,3,3,3,10,10,10,10,10,10,10,10,45,45,45,45,45,45,45,45,45,45,45,60,60,60,60,60,60,60
  db 71,71,71,71,71,71,71,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,100,208,208
  db 208,208,208,208,208,208,208,208,208,208,208,208,221,221,221,221,221,230,230,230,230,230,0
 
  .code

  start:
push esi
mov esi, offset Buff
xor eax, eax
mov ecx, eax
mov edx, ecx

@@: lodsb

.if al != 0

.if ah != al

.if cl > dl
mov dl, cl
mov dh,ah
.endif
mov cl,0
mov ah, al
.endif

inc ecx
jmp @B
.endif

pop esi
ret

end start

[jj2007]

My version.

Code Select Expand

include \masm32\include\masm32rt.inc

.data
Source db 3,3,3,3,3,3,3,3,10,10,10,10,10,10,10,10,45,45,45,45,45,45,45,45,45,45,45
db 60,60,60,60,60,60,60,71,71,71,71,71,71,71
db 101,101,101,100,100,100,100,100,100,100,100,100,100,100,100,100,100
db 208,208,208,208,208,208,208,208,208,208,208,208,208,208
db 221,221,221,221,221,230,230,230,230,230
SourceEnd db 0

.data? ; non-initialised variables
CtBuffer dd 256 dup(?)

.code
start:
mov esi, offset Source
mov edi, offset CtBuffer
mov ecx, SourceEnd-Source ; 82 values in this example
.Repeat
movzx eax, byte ptr [esi+ecx]
inc dword ptr [edi+4*eax]
dec ecx
.Until Zero?
xor edx, edx ; max value count
xor esi, esi ; max value position
mov ecx, 256 ; the whole byte range
.Repeat
mov eax, [edi+4*ecx] ; get the count
.if eax>=edx ; we check downwards
mov esi, ecx ; use "eax>edx" for assigning the mod to
xchg eax, edx ; the higher position in case of equal counts
.endif
dec ecx
.Until Zero?
inkey str$(esi), " is the most frequent value"
invoke ExitProcess, 0
end start


[dedndave]

hiyas Jochen, my friend

what - no times ??    :(