에이다 : 정수 오버플로

그래서 해시 오전 정의한 이러한 유형/기능 :에이다 : 정수 오버플로

subtype string2 is String(1..2); 
function cString2 is new Ada.Unchecked_Conversion(string2, long_integer); 
function cChar is new Ada.Unchecked_Conversion(character, long_integer);

이 해시 함수를 사용해야합니다

HA = (((cString2(s1) + cString2(s2)) * 256) + cChar(char)) mod 128

(함수가 목적에 나쁜,하지만 이를 구현해야 함) 문제는 오버 플로우에 대해 두 개의 long 정수를 더한 256을 곱하거나 더하려고 시도 할 때 발생합니다. 어떻게 든 문자열을 POSITIVE 정수 값으로 취급해야하고 함수 오버플로가 발생하지 않아야합니다. 감사!!!

출처

2017-04-16 Numnumberry

보통 사람이 만드는 해시 테이블 크기 소수 : 단어 미만의 절반 최악의 경우 두 개의 서로 다른 해시 값에 대한 스물 충돌 각각에 대해 고유 한 해시를 갖는 결과를 생성합니다. – user3344003

숙제 당신은 차선책 인 해시 함수가 붙어 있기 때문에 가정합니다. –

Long_Integer가 부호있는 정수 유형 및 범위 –2**31+1 .. +2**31–1 (존재하는 경우) 커버 보장 유형 :

LRM 3.5.4 (22)

Long_Integer가 사전 정의되면 그 범위는 –2**31+1 .. +2**31–1 범위를 포함해야한다.

선언을 사용하면 변환 된 값에 최소 2 바이트의 임의의 정크를 포함 할 수 있지만 크기가 일치하지 않으므로 결과가 구현 정의되며 유효하지 않거나 비정상 일 수 있습니다.

'Pos 속성과 LRM에있는 Ada.Unchecked_Conversion 속성을 읽어 보시기 바랍니다.

출처

2017-04-16 07:03:34

나는 내 문제를 해결했고 더 큰 숫자를 수용 할 수있는 모듈 형을 만들었습니다. – Numnumberry

하지만 올바른 답을주는 것입니까? –

내 원하는 해시 값을 얻는 중입니다. 내 모듈 형은 2^64 양의 정수를 가질 수있게되어 더 이상 오버플로가되지 않습니다. – Numnumberry

Hash 함수의 품질은 here이라는 접근 방식을 사용하여 사전 단어의 해시 테이블에서 충돌을 비교할 수 있습니다. 그 결과로 Counts은 Ada.Containers.Ordered_Maps의 인스턴스에 저장됩니다. 반면

Word count: 235886 
Table size: 393241 
Load factor: 59.99% 
0: 215725 (0.00%) 
1: 129710 (54.99%) 
2: 38727 (32.84%) 
3: 7768 (9.88%) 
4: 1153 (1.96%) 
5: 143 (0.30%) 
6: 14 (0.04%) 
7: 1 (0.00%)

: 구체적인 예를 들어

, 라이브러리 Hash 기능

function Hash is new Ada.Strings.Bounded.Hash(ASB);

고유 단어의 절반 이상에 대한 해시 및 최악의 경우 단지 일곱 충돌을 갖는 결과를 생성 , Hash 기능

function Hash(Key : ASB.Bounded_String) return Ada.Containers.Hash_Type is 
    S : String := ASB.To_String(Key); 
    H : Ada.Containers.Hash_Type := 0; 
begin 
    for C of S loop 
    H := H * 3 + Character'Pos(C); 
    end loop; 
    return H; 
end;

더 고른 분포를 보장하기 위해

Word count: 235886 
Table size: 393241 
Load factor: 59.99% 
0: 236804 (0.00%) 
1: 107721 (45.67%) 
2: 32247 (27.34%) 
3: 9763 (12.42%) 
4: 3427 (5.81%) 
5: 1431 (3.03%) 
6: 813 (2.07%) 
7: 441 (1.31%) 
8: 250 (0.85%) 
9: 150 (0.57%) 
10: 88 (0.37%) 
11: 41 (0.19%) 
12: 27 (0.14%) 
13: 14 (0.08%) 
14: 11 (0.07%) 
15: 7 (0.04%) 
16: 2 (0.01%) 
17: 1 (0.01%) 
19: 1 (0.01%) 
20: 2 (0.02%)

출처

2017-04-20 10:42:26 trashgod

에이다 : 정수 오버플로

답변

관련 문제