Преодоление временной сложности словаря Python

ProgramBox

Преодоление временной сложности словаря Python

Post author:admin
Запись опубликована:7 января, 2022
Post category:Вопросы по программированию

#c #python-3.x #dictionary #hash #hashtable

Вопрос:

У меня есть словарь Python, ключи которого представляют собой строки, состоящие из строчных букв английского алфавита, а значения-int. Более того, существует ровно 5e6 уникальных ключей, все они представляют собой строки длиной ровно 10. Удивительно, но поиск не занимает много времени. Я ожидал, что выполнение займет около 4 или более секунд, но оно не превышает 2,5 с.

Я преобразовал код Python в C , по аналогии со словарем a map . Я попробовал с map , unordered_map и gp_hash_table , в то время как все они занимали более 2 секунд в C .

Вот генератор, который я использовал для генерации уникальных строк.

 from sys import stdout

def increment(l):
    n = len(l)
    i = n - 1
    while i >= 0 and l[i] == 'z':
        l[i] = 'a'
        i -= 1
    l[i] = chr(ord(l[i])   1)

print(5 * 10**6)

string = ['a' for i in range(10)]


for i in range(5 * 10**6):
    stdout.write(''.join(string)   'n')
    increment(string)

string = ['a' for i in range(10)]

print(10**6)
for i in range(5 * 10**6):
    stdout.write(''.join(string)   'n')
    increment(string)

Выходные данные этой программы сохраняются в файле, названном Strings.txt с помощью команды python3 Test.py > Strings.txt ., после чего файл Strings.txt будет выглядеть следующим образом.

 5000000
aaaaaaaaaa
aaaaaaaaab
aaaaaaaaac
aaaaaaaaad
aaaaaaaaae
aaaaaaaaaf
...
...
...
aaaaakymlr
1000000
aaaaaaaaaa
aaaaaaaaab
aaaaaaaaac
...
...
...
aaaaakymlq
aaaaakymlr

Ниже приведен код CPP, на который я ссылался в приведенном выше контексте.

 #include <bits/stdc  .h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N = 0;
    cin >> N;
    map<string, int> freq;
    // unordered_map<string, int> freq;
    // gp_hash_table<string, int> freq;
    for(int i = 0; i < N; i  ) {
        string s;
        cin >> s;
        freq[s]  ;
    }
    int Q = 0;
    cin >> Q;
    for(int i = 0; i < Q; i  ) {
        string s;
        cin >> s;
        cout << freq[s] << 'n';
    }
    return 0;
}

And the following is the Python3 Code I used.

 from collections import defaultdict
from sys import stdin, stdout

input = stdin.readline

freq = defaultdict(int)
for i in range(int(input())):
    freq[input()]  = 1

for i in range(int(input())):
    stdout.write(str(freq[input()])   'n')

Here are the results when the above codes are executed.

 suman@Skynet:~/Documents/String_Pairs$ python3 Test.py > Strings.txt

suman@Skynet:~/Documents/String_Pairs$ time python3 Dict.py < Strings.txt > P_out.txt

real    0m3.145s
user    0m2.662s
sys     0m0.164s
suman@Skynet:~/Documents/String_Pairs$ time python3 Dict.py < Strings.txt > P_out.txt

real    0m2.772s
user    0m2.568s
sys     0m0.204s


suman@Skynet:~/Documents/String_Pairs$ g   -o exe Map.cpp -O2 -std=c  17
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.346s
user    0m2.265s
sys     0m0.080s
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.513s
user    0m2.417s
sys     0m0.096s


suman@Skynet:~/Documents/String_Pairs$ g   -o exe Unordered_Map.cpp -O2 -std=c  17
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.769s
user    0m2.660s
sys     0m0.108s
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.806s
user    0m2.690s
sys     0m0.116s


suman@Skynet:~/Documents/String_Pairs$ g   -o exe gp_hash_table.cpp -O2 -std=c  17
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.099s
user    0m1.686s
sys     0m0.412s
suman@Skynet:~/Documents/String_Pairs$ time ./exe < Strings.txt > Cpp_out.txt

real    0m2.009s
user    0m1.605s
sys     0m0.404s
suman@Skynet:~/Documents/String_Pairs$

Now, the only thing I am concerned about is the fact that Python3 is 5x slower than CPP but still, it’s Competing with CPP when working with hash tables.

Is there any way I can beat the time complexity of the Python hash table?

Any help is greatly appreciated.

UPDATE:
Here’s an update, that excludes time taken for reading strings.

 #include <bits/stdc  .h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N = 0;
    cin >> N;

    vector<string> words(N);

    for(int i = 0; i < N; i  ) {
        cin >> words[i];
    }

    // map<string, int> freq;
    // unordered_map<string, int> freq;
    gp_hash_table<string, int> freq;

    auto start = high_resolution_clock::now();
    for(string word : words) {
        freq[word]  ;
    }

    auto end = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(end - start);
    cout << duration.count() / 1e6 << 'n';



    int Q = 0;
    cin >> Q;
    vector<string> queries(Q);
    for(int i = 0; i < Q; i  ) {
        cin >> queries[i];
    }

    vector<int> results(Q);
    start = high_resolution_clock::now();
    for(int i = 0; i < Q; i  ) {
        results[i] = freq[queries[i]];
    }
    end = high_resolution_clock::now();
    duration = duration_cast<microseconds>(end - start);
    cout << duration.count() / 1e6 << 'n';

    for(int i = 0; i < Q; i  ) {
        cout << results[i] << 'n';
    }

    return 0;
}

The Python Code

 from collections import defaultdict
from time import time
from sys import stdin, stdout

input = stdin.readline

freq = defaultdict(int)

strings = []

for i in range(int(input())):
    strings.append(input())

start = time()
for string in strings:
    freq[string]  = 1
end = time()
print("%.4f" %(end - start))

queries = []
output = []

for i in range(int(input())):
    queries.append(input())

start = time()

for query in queries:
    output.append(freq[query])

end = time()

print("%.4f" %(end - start))

stdout.write('n'.join(map(str, output)))

Even now, Python is running faster than CPP.
The results:

Cpp_out.txt (the time taken for map , unordered_map and gp_hash_table — all are greater than 2s).

 2.28297
0.109844
1
1
...
...
...

P_out.txt

 1.7818
0.1977
1
1
...
...

UPDATE 2: I have modified the code so that I don’t include time taken for reading or writing as well as using references everywhere. Now it is kinda acceptable that CPP beats Python3 in hashing. Here are the benchmarks.

 // CPP Code
#include <bits/stdc  .h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
using namespace chrono;

struct djb2 {
    unsigned long operator()(const stringamp; str) const {
        unsigned long hash = 5381;
        for (auto c : str)
            hash = ((hash << 5)   hash)   c;
        return hash;
    }
};


int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N = 0;
    cin >> N;

    vector<string> words(N);

    for(int i = 0; i < N; i  ) {
        cin >> words[i];
    }

    // map<string, int> freq;
    // unordered_map<string, int> freq;
    gp_hash_table<string, int> freq;

    auto start = high_resolution_clock::now();
    for(const string amp;word : words) {
        freq[word]  ;
    }

    auto end = high_resolution_clock::now();
    auto duration = duration_cast<microseconds>(end - start);
    cout << duration.count() / 1e6 << 'n';



    int Q = 0;
    cin >> Q;
    vector<string> queries(Q);
    for(int i = 0; i < Q; i  ) {
        cin >> queries[i];
    }

    vector<int> results(Q);
    start = high_resolution_clock::now();
    for(int i = 0; i < Q; i  ) {
        results[i] = freq[queries[i]];
    }
    end = high_resolution_clock::now();
    duration = duration_cast<microseconds>(end - start);
    cout << duration.count() / 1e6 << 'n';

    for(int i = 0; i < Q; i  ) {
        cout << results[i] << 'n';
    }

    return 0;
}

 # Python3 Code
from collections import defaultdict
from time import time
from sys import stdin, stdout

input = stdin.readline

freq = defaultdict(int)

strings = []

for i in range(int(input())):
    strings.append(input())

start = time()
for string in strings:
    freq[string]  = 1
end = time()
print("%.4f" %(end - start))

queries = []
output = []

for i in range(int(input())):
    queries.append(input())

start = time()

for query in queries:
    output.append(freq[query])

end = time()

print("%.4f" %(end - start))

stdout.write('n'.join(map(str, output)))

Cpp_out.txt

 1.60026
0.071471

P_out.txt

 1.7849
0.1987

Итак, понятно, что CPP's gp_hash_table превосходит Python3's хэш-таблицу.

Я прошел через реализацию хэш-таблицы Python3. Они используют что-то под названием СИФАШ. Я хочу генерировать строки таким образом, чтобы количество столкновений при хэшировании строк было максимальным. Это что-то вроде атаки на столкновение, но я хочу, чтобы по крайней мере уникальные строки стоимостью 5000 долларов США создавали один и тот же хэш.

Может ли кто-нибудь предоставить для этого какой-либо ресурс (обратите внимание, что мне нужны уникальные строки стоимостью не менее 5000 долларов США, которые создают один и тот же хэш).

1. Что же Unordered_Map.cpp в нем содержится?

2. @kiner_shah Содержит точно такой же скрипт Map.cpp , с той лишь разницей unordered_map<string, int> , что он используется вместо двух других (они прокомментированы).

3. Вы включаете время на чтение и запись > 50 мегабайт. Результаты по существу не имеют ничего общего с производительностью хэш-таблицы.

4. @ChitturiSaiSuman Ваш обновленный код повторяет string элементы по значению, что означает, что он должен выполнять динамическое распределение и копировать все содержимое. Вы должны делать for (const string amp;word : words) (или const auto amp;word )

5. Вы должны возглавить свою карту C , то есть это .

Ответ №1:

reserve Вызов, указанный в комментарии, является наиболее важным для unordered_map . Кроме того, вы должны использовать правильную реализацию unordered_map (не стандартную для g , с 2019 года все в порядке) и учитывать используемую вами архитектуру.

С помощью инструментов Microsoft (Python37_64 и VS 2019) на моем компьютере — с использованием x86, за исключением последних строк:

Python 1.697 0.202
Оригинальная карта C : 1.361 0.138
Оригинальная C неупорядоченная карта: 1.035 0.067
строка constamp;: 1.013 0.067
резерв: 0,675 0,056
На x64 вместо этого: 0,686 0,060 (так что почти то же самое)

Использование robin_hood (как предлагает @thc ) не быстрее на x86, прежде чем вы добавите резерв — и даже в этом случае разница не столь существенна для неупорядоченной карты gcc:

robin_hood неупорядоченная карта x86: 1.107 0.100
строка const и x86: 1.059 0.101
резервный код: 0,477 0,108

Однако robin_hood также быстрее в построении, но не в поиске, если вы работаете на x64 (и резерв все еще важен).:

Оригинал ПРОТИВ C unordered_map x64: 1.130 0.065
строка const и x64: 1,119 0,063
резервный код: 0,671 0,065
robin_hood неупорядоченная карта x64: 0,611 0,069
строка const и x64: 0,577 0,072
резервный код: 0,384 0,069
Оригинальный g C unordered_map x64: 1.639 0.135
строка const и x64: 1.611 0.135
резервная копия: 0,946 0,128

Фрагмент кода (обратите внимание, что важно, чтобы резерв был внутри времени для справедливости):

 auto start = high_resolution_clock::now();
unordered_map<string, int> freq;
freq.reserve(Q);
for(const stringamp; word : words) {
    freq[word]  ;
}
auto end = high_resolution_clock::now();

Добавлено: Существует также стоимость отмены распределения для «freq» (и robin_hood там кажется быстрее). Всего лишь часть построения карты, но все еще значительная.

Ответ №2:

Я сам нашел ответ на этот пост. Python использует рандомизированные алгоритмы хеширования, которые сделают практически невозможным создание двух строк (состоящих из полностью строчных или полностью прописных символов), которые генерируют одинаковые значения хэша.

Теперь, переходя к проблемам производительности C по сравнению с Python3, я также учитывал время, затрачиваемое на чтение и запись, из-за чего C показывался медленнее, чем Python3.

Когда я исправил коды и убедился, что при чтении/записи или назначении нет дополнительных накладных расходов (в случае C я использовал const stringamp; ссылки на записи карты), я обнаружил, что C работает быстрее, чем Python3, когда gp_hash_table используется.

Спасибо всем, кто потратил время/усилия, работая над моим вопросом.

Ответ №3:

Возможно, это конструкция копирования в этом цикле for:

 for(string word : words) {
    freq[word]  ;
}

«Строковое слово» копирует новую строку каждую итерацию. Рассмотрите возможность перехода на доступ по ссылке, как это:

 for(const stringamp; word : words) {
    freq[word]  ;
}

Метки: Преодоление временной сложности словаря Python

Вопрос:

Комментарии:

Ответ №1:

Ответ №2:

Ответ №3:

Вам также может понравиться

Код сборки PIC не работает, PICKit2, ультразвуковой датчик

Не удается найти глобально установленный пакет NPM

Liferay 7 — получение комментариев к ресурсам из ADT