Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 5.00/3: Рейтинг темы: голосов - 3, средняя оценка - 5.00
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
1

Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)

11.05.2017, 16:53. Показов 543. Ответов 11
Метки нет (Все метки)

Вот код, для наглядности (cyberforum.ru - не сохраняет оригинал кода! может не компилироваться)
комментарии не удалял...
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
#include <map>
#include <bitset>
#include <string>
#include <iomanip> // clock()
#include <iostream>
#include <unordered_map>
 
using namespace std;
 
unsigned long long LyRs(string s) // [url]http://vak.ru/doku.php/proj/hash/sources[/url]
{
    unsigned long Ly = 0;
    unsigned long Rs = 0;
    unsigned long magic = 63689;
 
    for (string::iterator i(s.begin()); i != s.end(); ++i)
    {
        Ly = (Ly * 1664525) + (unsigned char)(*i) + 1013904223;
        Rs = Rs * magic + (unsigned char)(*i);
        magic *= 378551;
    }
 
    return ((unsigned long long)Ly << 32) + Rs;
}
 
unsigned long Ly(const string &s)
{
    unsigned long Ly = 0;
    for (string::const_iterator i(s.begin()); i != s.end(); ++i)
        Ly = Ly * 1664525 + (unsigned char)(*i) + 1013904223;
    return Ly;
}
 
unsigned long Rs(const string &s)
{
    unsigned long Rs = 0;
    unsigned long magic = 63689;
    for (string::const_iterator i(s.begin()); i != s.end(); ++i)
        Rs = Rs * magic + (unsigned char)(*i), magic *= 378551;
    return Rs;
}
 
unsigned long(*F[])(const string &)={Ly, Rs};
string I[]={"Ly - proposed by Leonid Yuriev (congruential generator)", 
            "Rs - simple hash function from Robert Sedgwicks book"};
char N = sizeof(F)/sizeof(F[0]); // Кол-во функций до 127 вкл-но
 
bool ffffffff(false); // 0xffffffff
bitset<ULONG_MAX> *BoolHash = new bitset<ULONG_MAX>();
 
void TestBitHash()
{
    string Bit(64,'0');
    string Backspace(72,'');
    string Space(79,' ');
    string S[] = {"\r  Set<", "\rReset<", "\rCheck<"};
    cout << "TestBitHash v0.2 pre-Alpha (May 9th, 2017)\n\n";
    cout << "Hash<UINT_MAX+1> = {0x00000000 , ... , 0xffffffff} і Hash[i] = "true" or "false"";
    cout << "  Bit<64> = {Bit[0] , ... , Bit[63]}   і   Bit[0]   Hash[0x00000000-0x03ffffff]\n";
    cout << "MapBit=[  Bit[0]-Bit[15] | Bit[16]-Bit[31] | Bit[32]-Bit[47] | Bit[48]-Bit[63] ]";
    cout << "MapBit=[00000000-3fffffff|40000000-7fffffff|80000000-bfffffff|c0000000-ffffffff]";
    cout << "\nBit[0]= 0 -     Set<0%>     (all Hash[0x00000000-0x03ffffff] = 0)\n";
    cout << "\tъ - Set<(" << (char) 26 << "0)-12.5%>\n";
    cout << "\t° - Set<12.5-37.5%>\n";
    cout << "\t± - Set<37.5-62.5%>\n";
    cout << "\tІ - Set<62.5-87.5%>\n";
    cout << "\tю - Set<87.5-" << (char) 26 << "100%>\n";
    cout << "\t1 -    Set<100%>    (all Hash[0x00000000-0x03ffffff] = 1)\n\n";
 
    for(char i(-1); ++i != 3; cout << ((i==2)?(S[2] + "100%>[" + Bit.substr(0,16) + '|' + Bit.substr(16,16) + '|' + Bit.substr(32,16) + '|' + Bit.substr(48) + "]"):("\r" + Space)) )
        for(unsigned int b(UINT_MAX); ++b != UINT_MAX;)
            if((i == 1)?(!(*BoolHash)[b]):((*BoolHash)[b])) cout << "\nError\n";
            else 
            {
                if(i != 2)
                {
                    (i)?((*BoolHash).reset(b)):((*BoolHash).set(b));
                    switch(b&0x03ffffff)
                    {
                        case 0x00000000: (i)?(Bit[b>>26] = 'ю'):(Bit[b>>26] = 'ъ');   break;
                        case 0x00800000: (i)?(Bit[b>>26] = 'І'):(Bit[b>>26] = '°');   break; 
                        case 0x01800000: Bit[b>>26] = '±';                         break;
                        case 0x02800000: (i)?(Bit[b>>26] = '°'):(Bit[b>>26] = 'І');   break;
                        case 0x03800000: (i)?(Bit[b>>26] = 'ъ'):(Bit[b>>26] = 'ю');   break;
                            // 0x03fffffe ~ 0x03ffffff
                        case 0x03fffffe: (i)?(Bit[b>>26] = '0'):(Bit[b>>26] = '1'); break;
                    }
                }
                else if(!(b&0x007fffff)) Bit[b>>26] = ((Bit[b>>26] == '0')?' ':'0');
                if(!(b&0x007fffff)) cout << S[i] << (unsigned long long) 100*b/UINT_MAX << "%>[" + Bit.substr(0,16) + '|' + Bit.substr(16,16) + '|' + Bit.substr(32,16) + '|' + Bit.substr(48) + "]" << Backspace;
            }
 
    cout << "Time = " << clock()/1000 << "\n\nPress ENTER to continue...";
    for(clock_t i(clock()+100); i > clock(); cin.get());
}
 
void main()
{
//  for(char i(-128); ++i != 127;)
//      cout << "123" << i << "456\n";
 
//  TestBitHash();
    unsigned long h;
    string S("1234"); // 4-х символьная строка
    cout.setf(ios_base::fixed);
    cout.precision(3);
    cout << "            Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)            \n";
 
    for(char i(-1); ++i != N; (*BoolHash).reset(), ffffffff = false)
    {
        clock_t t;
        clock_t T(0);
 
        string BitS(64,'0');
        unsigned long BitL[64] = {};
        map<unsigned long, unsigned short> count;
 
        cout << "Function[" << I[i] << "]:\n";
        
        for(unsigned long l(ULONG_MAX); ++l != ULONG_MAX;)
        {
            for(char c(-1); ++c != S._Mysize; S[c] = (unsigned char) (l >> (24 - c*8)) );
            t = clock();
            h = F[i](S); // Надеюсь три присваивания и вызов функции из массива - не много занимают времени)
            T += clock() - t;
            if(h == 0xffffffff) 
                if(ffffffff) ++count[0xffffffff];
                else {ffffffff = true; ++BitL[63];}
            else
                if( (*BoolHash)[h] ) ++count[h];
                else (*BoolHash).set(h), ++BitL[h >> 26];
            if(!(short)l)
            {
                for(char j(-1); ++j != 64;)
                    if(BitL[j] != 0)
                        switch(BitL[j]&0xff800000)
                        {
                            case 0:         BitS[j] = 'ъ';     break;
                            case 1: case 2: BitS[j] = '°';     break; 
                            case 3: case 4: BitS[j] = '±';     break;
                            case 5: case 6: BitS[j] = 'І';     break;
                            case 7: BitS[j] = ((BitL[j] == 0x03ffffff)?'1':'ю');   break;
                            default:        cout<<"\nError\n";  break;
                        }
//              cin.get(); // Не придумал как сохранять результат
                cout << "\r<" << 100.0*l/ULONG_MAX << "%> [" + BitS.substr(0,16) + '|' + BitS.substr(16,16) + '|' + BitS.substr(32,16) + '|' + BitS.substr(48) + "]";
            }
        }
 
        unsigned char tab(0);
        unsigned long amt(0);
        cout << "\r<100%> [" + BitS.substr(0,16) + '|' + BitS.substr(16,16) + '|' + BitS.substr(32,16) + '|' + BitS.substr(48) + "]\t[HEX] = count collisions\n";
        for(map<unsigned long, unsigned short>::iterator it(count.begin()); it!=count.end(); amt+=(*it).second+1, ++it)
            cout << "[" << hex << (*it).first << "]=" << dec << (*it).second+1 << (((++tab)&0x03)?'\t':'\n');
        cout << "\nTotal[" << count.size() << "] = " << amt << "\nTime = " << T/1000.0 << " sec.\n\n" << endl;
    }
 
//  cout << "S = s[0] + s[1] + s[2] + s[3];\n";
 
//  std::hash<std::string> hash_fn;
//    size_t str_hash = hash_fn(s);
 
    /*
    for(short o(-1); ++o != 256;)
    {
        unsigned int t(clock()/1000);
        cout << "s[0] = '" << (s[0] = (unsigned char) o) << "':\n";
 
        for(int i(-1); ++i != 16777216;) // 256^3
        {
            for(int j(0); ++j != 4; s[j] = (unsigned char) (i >> ((3 - j)*8)));
            h = LyRs(s);
            if(hash.find(h) == hash.end()) hash.insert(h);
            else cout << "\n!!!" << " set<" << hash.size() << "> " << s << "\n";
            if(!(i%USHRT_MAX)) cout << "\r" << 100.0*(16777216*o + i)/UINT_MAX << "% -  "" << s << ""[" << hash.size() << "] = " << hex << h << dec << "   ";
        }
 
        cout << "\r" << 1677721600.0*(o+1)/UINT_MAX << " %  vector<" << hash.size() << "> = " << hex << h << dec << "; Time = " << clock()/1000 - t << "cek\n";
        hash.clear();
    }
    */
 
    cout << "Total time = " << clock()/1000.0 << " sec.\nTHE END";
    for(clock_t i(clock()+100); i > clock(); cin.get());
}
Собственно хочу услышать:
1) насколько нужная программа и нужно ли дальше её допиливать, если да то
2) что реализовать или переписать в коде
3) обработку каких хэш-функции включить ещё
4) предложения по ускорению программы
5) и прилагайте свои скрины, если у вас машина мощная что бы быстро все енто обработать)
6) думаю ещё сделать функцию сохранения результата

Скриншоты программы + ZIP(CPP + EXE):
Миниатюры
Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)   Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)   Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)  

Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)  
Вложения
Тип файла: zip hash.zip (36.9 Кб, 2 просмотров)
__________________
Помощь в написании контрольных, курсовых и дипломных работ здесь
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
11.05.2017, 16:53
Ответы с готовыми решениями:

Pre-alpha Season Unreal Tournament
Качаю последнюю версию, которая уже в разработке, потому что 3 для меня не актуальна - накувыркался...

PERFECT HASH FUNCTION
Вопрос таков, подскажите хэш функцию: формат AcccAA- где A-заглавные буквы,c-цифры. всего 1500...

Вставка тега <pre></pre> в файлы директории
Здравствуйте, форумчане! Не подскажете как можно средствами php вставить тег &lt;pre&gt;&lt;/pre&gt; во все...

Вывести ответ сервера в <pre></pre>
Добрый день! Подскажите, пожалуйста, как мне в примере ниже сделать так, чтобы значение data...

11
Форумчанин
Эксперт CЭксперт С++
8171 / 5021 / 1436
Регистрация: 29.11.2010
Сообщений: 13,453
11.05.2017, 17:14 2
Замените
C++
1
S._Mysize
на
C++
1
S.size()
и
C++
1
void main()
на
C++
1
int main()
чтобы это хотя бы компилировалось.

Добавлено через 2 минуты
После ~12% выдаёт кучу Error

Добавлено через 5 минут
Процесс выжрал всю имеющуюся память и упал в експешн на 34.219%
1
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
11.05.2017, 17:19  [ТС] 3
Цитата Сообщение от MrGluck Посмотреть сообщение
чтобы это хотя бы компилировалось.
интересно а каким макаром, тогда у меня все компилировалось?
0
Форумчанин
Эксперт CЭксперт С++
8171 / 5021 / 1436
Регистрация: 29.11.2010
Сообщений: 13,453
11.05.2017, 17:30 4
Цитата Сообщение от eXPonent Посмотреть сообщение
интересно а каким макаром, тогда у меня все компилировалось?
Написали специфичный для какого-то конкретного компилятора код. Ни в mingw ни в Visual Studio 2015 это не компилируется.

Добавлено через 8 минут
Хоть расскажите, что программа должна делать, а то складывается впечатление, что она вызывает дьявола
2
282 / 230 / 114
Регистрация: 07.09.2016
Сообщений: 584
11.05.2017, 17:48 5
хеши какие-то хитрые считает, но запускать ее опасно, ибо жрет она тьму памяти, начинаются свопы и прочие прелести.
вся движуха в других постах похоже ради этого кода и затевалась.

по поводу чего не хватает:
почему строки? хочу например бинарные данные. нет поддержки. а еще хочу считать хеши здоровенных файлов.
скажем на террабайт, которые не влезут в память. как сделать с текущей реализацией, не прогружая их в память?
никак. такие штуки делаются в духе стримов или чего-то такого. методу последовательно блоки данных передаются,
а он высчитвает хеш с учутом предыдущих вызовов. ну и в конце, когда данные файла по кускам зачитаны и пропущены
через такой классик - получается хеш файла.
1
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
11.05.2017, 20:43  [ТС] 6
Цитата Сообщение от MrGluck Посмотреть сообщение
После ~12% выдаёт кучу Error
замените 136 строчку: switch(BitL[j]&0xff800000)
на
C++
1
switch(BitL[j]>>23)
Я накосячил, согласен(

Цитата Сообщение от MrGluck Посмотреть сообщение
Написали специфичный для какого-то конкретного компилятора код. Ни в mingw ни в Visual Studio 2015 это не компилируется.
VS 2010 у меня

Цитата Сообщение от DU3 Посмотреть сообщение
если функции
unsigned long Ly(const string &s) { ... }
unsigned long Rs(const string &s) { ... }
про коллизии ничего не знаю. если по мере выполения цикла возвращают уникальные значения из всего диаппазона от 0 до ULONG_MAX - в целом процессу на хранение этого добра потребуется много памяти. как себя при этом программа поведет - я хз. почему бы системе постепенно не отбирать ту память, которая была выделена стеку и в конце концов не напороться на то, что памяти для стека уже не хватает. и стековерфлоу - это по вашему не крах?
Цитата Сообщение от MrGluck Посмотреть сообщение
Процесс выжрал всю имеющуюся память и упал в експешн на 34.219%
видимо функции не такие уж и идеальные как я думал...
первая на 34,6% вылетела, а вторая и того хуже на 23,5%
(скрины прилагаются ниже)

Цитата Сообщение от DU3 Посмотреть сообщение
но запускать ее опасно, ибо жрет она тьму памяти
можно придумать алгоритм распознавания сжирания памяти, а точнее когда размер карты равен ~1 Гб завершать сканирование, таким образом прога будет жрать от 515 Мб до 1,5 Гб памяти.

Цитата Сообщение от DU3 Посмотреть сообщение
бинарные данные. нет поддержки. а еще хочу считать хеши здоровенных файлов.
бинарные данные имеете ввиду бинарный файл?
файл можно разбить на блоки строк, например по 256 Мб и посчитать хэш

Цитата Сообщение от DU3 Посмотреть сообщение
методу последовательно блоки данных передаются,
а он высчитвает хеш с учутом предыдущих вызовов. ну и в конце, когда данные файла по кускам зачитаны и пропущены
через такой классик - получается хеш файла.
мне кажется подобным образом считает и MD5 и иные хэши
0
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
11.05.2017, 21:09  [ТС] 7
Цитата Сообщение от eXPonent Посмотреть сообщение
видимо функции не такие уж и идеальные как я думал...
первая на 34,6% вылетела, а вторая и того хуже на 23,5%
Этапы выполнения программ:
1) первые 23 минуты работы, все норм (стандартно жрется 515Мб из-за bitset)
2) после 30 минут Ly стал жрать память(
3) 35 минута Rs начал жрать память (скрин удалил случайно, на замену ему скрин на 41 минуте)
4) 51 минута MAP в функции Rs весит ~1,5Гб
5) 70 минута MAP в функции Ly весит ~1,5Гб
Миниатюры
Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)   Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)   Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)  

Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)   Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)  
0
Форумчанин
Эксперт CЭксперт С++
8171 / 5021 / 1436
Регистрация: 29.11.2010
Сообщений: 13,453
11.05.2017, 21:27 8
Цитата Сообщение от eXPonent Посмотреть сообщение
VS 2010 у меня
Ну так я вам и пытаюсь подсказать как сделать чтобы код хотя бы компилировался на других платформах.
0
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
11.05.2017, 21:44  [ТС] 9
Цитата Сообщение от MrGluck Посмотреть сообщение
Хоть расскажите, что программа должна делать, а то складывается впечатление, что она вызывает дьявола
Вся инфа в кратком виде располагается в функции:
C++
1
//  TestBitHash();
Но я поясню каждую строчку:
Hash<UINT_MAX+1> = {0x00000000 , ... , 0xffffffff} - собственно сами хэши
Hash[i] = "true" or "false" - булевское значение i-го хэша
"false" - если ни разу не встречался
"true" - встретился один раз
Bit<64> = {Bit[0] , ... , Bit[63]} - содержит в себе 64 группы хэшей, в каждой по (UINT_MAX+1)/64 хэша
Например Bit[0] содержит в себе хэши: Hash[0x00000000-0x03ffffff]
MapBit=[ Bit[0]-Bit[15] | Bit[16]-Bit[31] | Bit[32]-Bit[47] | Bit[48]-Bit[63] ]
MapBit=[00000000-3fffffff|40000000-7fffffff|80000000-bfffffff|c0000000-ffffffff]
- полная карта хэшей в картинка, каждая картинка из которой показывает степень заполненности...
Миниатюры
Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)  
0
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
11.05.2017, 22:55  [ТС] 10
Что же делает функция TestBitHash() ?
1) У меня жрет 515Мб памяти (инициализация bitset)

2) Выполняет последовательно функции (проверяет работоспособность каждого бита)
Set (что на картинке выше) - устанавливает значение ''true" если Hash[i] = "false" иначе "Error"
Reset (что на картинке ниже) - устанавливает значение ''false" если Hash[i] = "true" иначе "Error"
Check (что на картинке ниже) - проверяет что все значения Hash[i] = "false" иначе "Error"
теоретически если функция отработала нормально, то с блоком памяти выделенным под bitset все норм, работает хорошо)

3) Под конец функции TestBitHash() выводится в консоль затраченное время и ожидает команды начать выполнения основной программы "Press ENTER to continue..."

Цитата Сообщение от MrGluck Посмотреть сообщение
Ну так я вам и пытаюсь подсказать как сделать чтобы код хотя бы компилировался на других платформах.
спасибо, я учел рекомендации, только я до сих пор не понимаю почему нужно писать:
Цитата Сообщение от MrGluck Посмотреть сообщение
int main()
это связано с ошибками компиляции или с Stack overflow?

Цитата Сообщение от MrGluck Посмотреть сообщение
Хоть расскажите, что программа должна делать, а то складывается впечатление, что она вызывает дьявола
Цитата Сообщение от DU3 Посмотреть сообщение
хеши какие-то хитрые считает, но запускать ее опасно, ибо жрет она тьму памяти, начинаются свопы и прочие прелести.
вся движуха в других постах похоже ради этого кода и затевалась.
Теперь подробнее разберем, что же такого страшного делает программа и почему вылетает ошибка Stack overflow:
1) Перебирает все функции
C++
1
109 for(char i(-1); ++i != N; (*BoolHash).reset(), ffffffff = false)
2) Перебор всех возможный 4-х символьных строк, почему 4-х символьных? 256^4 = ULONG_MAX+1
C++
1
2
120 for(unsigned long l(ULONG_MAX); ++l != ULONG_MAX;)
122 for(char c(-1); ++c != S.size(); S[c] = (unsigned char) (l >> (24 - c*8)) );
кстати, только вот сейчас понял что не всех 4-х символьных строк...

3) Замер времени и выполнение подсчета хэша
C++
1
2
3
123 t = clock();
124 h = F[i](S);
125 T += clock() - t;
4) 126-131: строчка в bitset<№ хэша> устанавливаем "true" если там "false"
иначе создаем значение (если оно не создано) ++count[h] и увеличиваем его на 1 // Вот отсюда прога и начинает жрать память
++BitL[h >> 26] - подсчитывает кол-во хэшей в одной из 64 групп хэшей, для отображения картинки)
C++
1
2
3
4
5
6
if(h == 0xffffffff) 
    if(ffffffff) ++count[0xffffffff];
    else {ffffffff = true; ++BitL[63];}
else
    if( (*BoolHash)[h] ) ++count[h];
    else (*BoolHash).set(h), ++BitL[h >> 26];
5) 132 - 147 строчка: Программа выводит результат каждый if(!(short)l) раз т.е. раз в USHRT_MAX итераций раз всего USHRT_MAX выводов, т.к. 2*(USHRT_MAX+1)=(ULONG_MAX+1)
что выводит, уже описано выше)

6) 150 - 155 и 183 строчки: выводит окончательный результат <100%> а так же КАРТУ хэшей
Время работы каждой функции и программы в целом (в том случае если программа не завершилась из-за Stack overflow)

7) Ждёт нажатия ENTER
C++
1
184 for(clock_t i(clock()+100); i > clock(); cin.get());
сам придумал, подробнее тут
Миниатюры
Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)   Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)  
0
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
12.05.2017, 16:16  [ТС] 11
Вдохновлялся я написанием проги этой статьёй
В русскоязычном источнике написано:
Общее количество после слияния — 326797 уникальных слов. При идеально равномерном распределении 32-битного хэша для достижения 50%-ной вероятности коллизии требуется 77163 слова. Так что коллизии должны иметь место.
В англоязычном этой части текста нет
Что они имели ввиду?

Если знаете программу которая работает подобным образом, ткните меня носом в неё)
спасибо. А так же благодарю MrGluck и DU3 за тестирование кода)


Добавлено через 32 минуты
А если учитывать эти данные:
Цитата Сообщение от eXPonent Посмотреть сообщение
2) после 30 минут Ly стал жрать память(
3) 35 минута Rs начал жрать память (скрин удалил случайно, на замену ему скрин на 41 минуте)
то у меня получается прошло примерно: 730 144 440
и 858 993 459 различных хэшей для алгоритма Ly и Rs соответственно
и только после этих цифр начались коллизии (т.е. совпадение хэшей)
но они даже и близко не стоят с цифрой 77163!
000 077 163 = 0x00012D6B
730 144 440 = 0x2B851EB8 (77163*9462)
858 993 459 = 0x33333333 (77163*11132)
т.е. цифры различаются в 10 000 раз!
помогите разобраться...
0
99 / 52 / 27
Регистрация: 21.05.2012
Сообщений: 1,170
13.05.2017, 22:04  [ТС] 12
Вызов итераторов настолько затруднен для компилятора?

Воть функция:
C++
1
2
3
4
5
6
7
unsigned long s4(const string &s)
{
    unsigned long s4(0);
    for (string::const_iterator i(s.begin()); i != s.end(); ++i)
        s4 += ( (unsigned char)(*i) << ((i-s.begin())%4*8) );
    return s4;
}
работает долго...
НО так как очень часто поступают строки состоящие из 4 символов можно его заменить эквивалентным:
C++
1
2
3
4
5
6
7
8
9
10
11
12
unsigned long s4(const string &s)
{
    if(s.size() == 4)
        return (unsigned char) s[0] + ((unsigned char) s[1] << 8) + ((unsigned char) s[2] << 16) + ((unsigned char) s[3] << 24);
    else
    {
        unsigned long s4(0);
        for (string::const_iterator i(s.begin()); i != s.end(); ++i)
            s4 += ( (unsigned char)(*i) << ((i-s.begin())%4*8) );
        return s4;
    }   
}

работает в 7 раз быстрее!
Как так то?


Добавлено через 1 час 46 минут
Цитата Сообщение от eXPonent Посмотреть сообщение
77163
может они имели ввиду тип unsigned SHORT?
так как UINT_MAX = USHRT_MAX на некоторых платформах, кстати где такое наблюдается?
но у него же (USHRT_MAX = 65535) <> 77163
Миниатюры
Hash Function Efficiency v0.1 pre-Alpha (May 11th, 2017)  
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.05.2017, 22:04

Продам плату Stream Alpha Plus + Alpha Pro 2.0 + Tele 2.2 б/у
Плата Stream Alpha Plus немного б/у, CD-диск Alpho Pro 2.0, CD-диск TELE 2.2, USB-ключ защиты для...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
12
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2022, CyberForum.ru