0

多くの配列アクセス (静的配列、実行時に変更なし) を使用してワード プロセッシング コードをコーディングしています。文字列をハッシュしてから、配列にあるかどうかを確認します（ルックアップ）。しかし、それの良い実装は何ですか? 私は簡単な方法でやっています。ハッシュ入力と一致するかどうか、値ごとに値をチェックしています。それを最速にするためのアイデア？

私は現在チェックしています：

ループのアンローリングを使用すると、これは非常に異なったものになります。順序付けられていない配列を使用すると、並べ替えられた配列よりもはるかに遅くなります。この場合、ベクトル化がうまくいくかどうかを確認します。

おすすめは何ですか？または、このアルゴリズムをどのように実装しますか?

現在のルーチンはEAX次のとおりです (一致しない場合は、配列内のハッシュのインデックスまたは負の値に戻ります)。

Index_of:
push edx
push ecx
push ebx
mov ecx,123456          ;hash example. in the real code,it's set by a routine.
xor ebx,ebx
mov eax,array
.LOOP1:
        cmp [eax],ecx           ;match hash?
        je .FOUND
        cmp byte [eax],0
        je .NOTFOUND
        add ebx,1
        add eax,4
        jmp .LOOP1
.NOTFOUND:
        neg eax
        jmp .DONE
.FOUND:
        mov eax,ebx
.DONE:
pop ebx
pop ecx
pop edx
ret

配列は次のとおりです。

; hashs for examples
array:
dd 33389990
dd 1234567
dd 81919191
dd 938383737
0
4

1 に答える 1

1

ハッシュ テーブルの考え方は、ループせずにハッシュ キーの関数として値を取得することです。

決して返されない値を 1 つ持つことができる場合は、次のようにすることができます。

; first fill the hash table with values, and with invalid values for the rest.
; for an example, I assume here hash table of 0x1000000h = 16777216d bytes.
; 0xFFFFFFFFF marks no match and 0xFFFFFFFE marks hash collision. 

; first fill the hash table with "no match" values.

    mov ecx,(16777216/4)
    mov eax,0xFFFFFFFF
    mov edi,hash_array
    rep stosd

; here set the values you want to return into the hash table.
; for hash collisions write 0xFFFFFFFE, and handle hash collision in the
; hash collision handling code.

; here we have some hash function that outputs 123456d with some input string.

編集:ハッシュ配列の開始アドレスは に入力できるeaxため、ハードコーディングされていません。

    mov eax,hash_array               ; the start address of the hash array
    mov ecx,123456                   ; example hash
    call @get_value_from_hash_table  ; call to get the value from hash table

    ...

編集: ecxハッシュ値が dwords の場合、4 でスケーリングする必要があります。

@get_value_from_hash_table:
    mov eax,[eax+4*ecx] 
    cmp eax,0xFFFFFFE
    ja  @no_match ; 0xFFFFFFFF ; no match
    je  @hash_collision        ; hash collision

    ; match, no hash collisions, no jumps needed.

    ...

@hash_collision:
    ; handle hash collision here, the best way depends on your data.

    ...

@no_match:
    ; handle no match here.

    ...
于 2013-02-18T22:00:05.507 に答える