Оптимизация олимпиадной задачи
Есть задача:
Изначально я написал код на питоне, получилось так:
from array import array
def string_xor(a: str, b: str):
"""
Проверка на схожесть строк
3 - одинаковые
2 - 1 различие
1 - больше 2 отличий
"""
k = len(a)
if k == len(b):
a1 = array('u', a)
b1 = array('u', b)
errors = 0
for i in range(k):
if a1[i] != b1[i]:
errors += 1
if errors > 1:
return 1
elif errors == 1:
return 2
elif errors == 0:
return 3
return 1
n, m = map(int, input().split())
words = sorted(input() for _ in range(n))
for _ in range(m):
word = input()
one_diff = [] # Список слов, которые расходятся ровно на одну букву
for cur in words:
ans = string_xor(word, cur)
if ans == 3:
print(cur)
break
elif ans == 2:
one_diff.append(cur)
else:
if one_diff:
print(min(one_diff))
else:
print('?')
Но он валится на одном из тестов по времени. Дальше я переписал его на плюсы, думая, что это поможет.
#include<iostream>
#include "vector"
#include "algorithm"
using namespace std;
int check(string a, string b) {
int k = a.size();
if (k == b.size()) {
int errors(0);
for (int i = 0; i < k; i++)
errors += a[i] != b[i];
if (errors == 0)
return 0;
else if (errors == 1)
return 1;
return 2;
}
return 2;
}
int main() {
ios::sync_with_stdio(false);
int n, m;
cin >> n >> m;
string word;
vector <string> words(n), one_diff;
for (string &el : words)
cin >> el;
sort(words.begin(), words.end());
for (int i = 0; i < m; i++) {
cin >> word;
bool is_break(false);
for (const string &cur : words) {
int d = check(cur, word);
if (d == 0) {
cout << cur << "\n";
is_break = true;
break;
}
else if (d == 1)
one_diff.push_back(cur);
}
if (!is_break) {
if (!one_diff.empty()) {
sort(one_diff.begin(), one_diff.end());
cout << one_diff[0] << "\n";
one_diff.clear();
}
else
cout << "?" << "\n";
}
}
}
Но это не помогло, валится на том же тесте. Подскажите, что тут надо изменить, чтобы программа укладывалась по времени.
Сделал словарь с длинами строк, было время 1.033, стало 1.09 код:
from array import array
def string_xor(a: str, b: str):
k = len(a)
if k == len(b):
errors = 0
for a1, b1 in zip(a, b):
errors += a1 != b1
if errors > 1:
return 1
elif errors == 1:
return 2
elif errors == 0:
return 3
return 1
n, m = map(int, input().split())
d = {}
for _ in range(n):
word = input()
z = len(word)
d[z] = d.get(z, [word]) + [word]
for i in d.keys():
d[i].sort()
for _ in range(m):
word = input()
one_diff = set()
try:
for cur in d[len(word)]:
ans = string_xor(word, cur)
if ans == 3:
print(cur)
break
elif ans == 2:
one_diff.add(cur)
else:
if one_diff:
print(min(one_diff))
else:
print('?')
except KeyError:
print('?')
PS Код валится именно по времени...
PPS Сорян, ссылку на задачу дать не могу.
Ответы (4 шт):
Попробуйте так:
from jellyfish import levenshtein_distance
def orthography(word, vocabulary):
if word in vocabulary:
return word
for v_word in sorted(vocabulary):
if levenshtein_distance(word, v_word) == 1:
return v_word
return '?'
for word in words:
print(orthography(word, vocabulary))
тогда для таких данных:
vocabulary = ['a', 'love', 'contexts', 'math']
words = ['i', 'love', 'programming', 'contests']
выведет следующее:
a
love
?
contexts
а для второго тест-кейса:
vocabulary = ['ac', 'ab']
words = ['aa']
ответом будет:
ab
Это задача на особое хеширование. Нужно всего-лишь сосчитать хеш для пар букв.
X_X_X_X (0-a)
_X_X_X_ (0-b)
XX__XX__XX__XX (1-a)
__XX__XX__XX__ (1-b)
XXXX____XXXX____ (2-a)
____XXXX____XXXX (2-b)
То-есть есть слова
vector<string> words;
И их хеши
array<array<unordered_map<size_t, vector<string*>>, 2>, 5> hashes;
И для проверки есть ли в словаре:
string* word_get(string s)
{
for(size_t i = 0; i < hashes.size(); i++)
{
size_t ha = word_hasher(s, i);
if (hashes[i][0].find(ha) == hashes[i][0].end() &&
hashes[i][1].find(ha) == hashes[i][1].end())
return nullptr;
}
// word final tests
return nullptr;
}
Алгоритм
Для каждого слова длины k вычисляется k + 1 хешей. Один для всего слова, остальные для всех вариантов слова без одной буквы. Буквы не вычеркиваются, (виртуально) заменяются на символ вне алфавита. Так меньше коллизий.
Индексы слов помещаются в рукописную хеш-таблицу. Размер таблицы равен общему числу хешей для всех слов словаря. Другими словами в таблице нет свободных ячеек.
Word words[n] // слова словаря
uint32_t index[ht_size + 1] // метки в следующей таблице
uint32_t table[ht_size] // индексы слов
// этот код перебирает все слова в словаре с хешем `h`
for (uint32_t i = index[h]; i < index[h + 1]; ++i) {
words[table[i]];
}
После создания таблицы, для каждого проверяемого слова вычисляется k + 1 хеш. Все слова соответствующие хешам проверяются на возможное равенство или равенство без одного символа.
Память для словаря
Словарь в котором все слова по 20 символов. Размер файла не превосходит 2MB. Число слов тогда n < 100000. Структура для хранения слова требует 21 байт на слово. Число хешей 2100000 = (1 + 20) * 100000.
words[ 100000] // 2100000B (2.1MB)
index[2100001] // 8400004B (8.4MB)
table[2100000] // 8400000B (8.4MB)
Всего 19MB.
Самое большое число слов, которое можно поместить в в файл размером 2MB - это 1 + 26 + 26**2 + 26**3 + 404953 = 423232. Все различные слова длиной ноль, один, два и три и остаток слова длины четыре. Такой словарь займёт в памяти 423232 * 21 = 8887872 байт. Не более 9MB. Максимальное потребное число хешей не более 423232 + 2 * 1024 * 1024 = 2520384. Суммарная память не более 9MB + 10MB + 10MB = 29MB.
Производительность
Для всех протестированных словарей время работы не более одной секунды на неоптимизированной сборке GCC. Возможно что-то упущенно. Были испробованы словари на 230000 слов до четырех символов и на 50000 слов по двадцать символов. Скорость зависит от качества хеширования, которое в свою очередь должно быть быстрым. Хеш функция была подсмотрена в Boost.
Подбором слов в словаре можно пытаться замедлить программу. Слов до 20 символов около 2 * 10^28, ясно что из них для любой хеш таблицы, которая помещается в 64MB, можно подобрать такие слова что все они окажутся в одной корзине.
Код
// g++ -std=c++11 -pedantic -Wall -Wextra -Werror proofreading.cpp
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
const int max_size = 20;
void fail() {
std::fprintf(stderr, "ERROR\n");
std::exit(EXIT_FAILURE);
}
void skip_line() {
for (; ; ) {
int c = std::getc(stdin);
if (c == EOF) {
fail();
}
if (c == '\n') {
break;
}
}
}
class Word {
public:
void scan() {
if (std::fgets(data, max_size + 1, stdin) == nullptr) {
fail();
}
const size_t len = std::strlen(data);
if (len == 0) {
fail();
}
if (data[len - 1] == '\n') {
data[len - 1] = '\0';
} else {
skip_line();
}
}
void print() const {
std::fputs(data, stdout);
}
size_t length() const {
return std::strlen(data);
}
uint32_t hash() const {
uint32_t seed = 0;
hash(seed, data);
return seed;
}
uint32_t hash(size_t skip) const {
uint32_t seed = 0;
hash(seed, skip, data);
hash(seed, static_cast<char>(skip));
hash(seed, data + (skip + 1));
return seed;
}
bool eq(const Word &w) const {
return std::strcmp(data, w.data) == 0;
}
bool eq(const Word &w, size_t skip) const {
return
length() == w.length() &&
std::memcmp(data , w.data , skip) == 0 &&
std::strcmp(data + (skip + 1), w.data + (skip + 1) ) == 0
;
}
bool lt(const Word &w) const {
return std::strcmp(data, w.data) < 0;
}
private:
char data[max_size + 1];
static void hash(uint32_t &seed, char c) {
seed ^= static_cast<unsigned char>(c) + (seed << 6) + (seed >> 2);
}
static void hash(uint32_t &seed, size_t n, const char data[/* n */]) {
for (size_t i = 0; i < n; ++i) {
hash(seed, data[i]);
}
}
static void hash(uint32_t &seed, const char data[]) {
for (const char *p = data; *p != '\0'; ++p) {
hash(seed, *p);
}
}
};
int main() {
int n, m;
if (std::scanf("%d %d", &n, &m) != 2) {
fail();
}
skip_line();
std::vector<Word> words(n);
size_t ht_size = 0;
for (int i = 0; i < n; ++i) {
words[i].scan();
ht_size += 1 + words[i].length();
}
std::vector<uint32_t> index(ht_size + 1, 0);
for (const Word &w : words) {
++index[w.hash() % ht_size];
const size_t length = w.length();
for (size_t i = 0; i < length; ++i) {
++index[w.hash(i) % ht_size];
}
}
{
uint32_t acc = 0;
for (uint32_t &i : index) {
acc += i;
i = acc;
}
}
for (int i = ht_size; i > 0; --i) {
index[i] = index[i - 1];
}
index[0] = 0;
std::vector<uint32_t> table(ht_size);
for (int i = 0; i < n; ++i) {
const Word &w = words[i];
uint32_t &j = index[w.hash() % ht_size];
table[j++] = i;
const size_t length = w.length();
for (size_t k = 0; k < length; ++k) {
uint32_t &j = index[w.hash(k) % ht_size];
table[j++] = i;
}
}
for (int i = ht_size; i > 0; --i) {
index[i] = index[i - 1];
}
index[0] = 0;
for (int j = 0; j < m; ++j) {
Word w;
w.scan();
{
const uint32_t h = w.hash() % ht_size;
const uint32_t i1 = index[h];
const uint32_t i2 = index[h + 1];
uint32_t i;
for (i = i1; i < i2; ++i) {
if (w.eq(words[table[i]])) {
break;
}
}
if (i < i2) {
w.print();
std::puts("");
continue;
}
}
{
const Word *best_match = nullptr;
const size_t length = w.length();
for (size_t k = 0; k < length; ++k) {
const uint32_t h = w.hash(k) % ht_size;
const uint32_t i1 = index[h];
const uint32_t i2 = index[h + 1];
for (uint32_t i = i1; i < i2; ++i) {
const Word &ww = words[table[i]];
if (w.eq(ww, k)) {
if (best_match == nullptr || ww.lt(*best_match)) {
best_match = &ww;
}
}
}
}
if (best_match != nullptr) {
best_match->print();
std::puts("");
} else {
std::puts("?");
}
}
}
}
Сделал свой вариант:
#include <iostream>
using namespace std;
string* vocab;
string* text;
int quantityOfWordsInVocab, quantityOfWordsInText;
void diff(int index)
{
int howMany{ 0 };
int k = 0;
int sizeOfTextWord = text[index].size();
for (int j = 0; j < quantityOfWordsInVocab; j++)
{
if (sizeOfTextWord != vocab[j].size()) { continue; }
while (k != vocab[j].size())
{
if (text[index][k] != vocab[j][k])
{
howMany++;
}
k++;
}
if (!(howMany >= 2))
{
cout << vocab[j] << '\n';
return;
}
howMany = 0;
}
cout << "?\n";
}
int main()
{
ios::sync_with_stdio(false);
cin >> quantityOfWordsInVocab >> quantityOfWordsInText;
vocab = new string[quantityOfWordsInVocab];
text = new string[quantityOfWordsInText];
for (size_t i = 0; i < quantityOfWordsInVocab; i++)
{
cin >> vocab[i];
}
for (size_t i = 0; i < quantityOfWordsInText; i++)
{
cin >> text[i];
}
cout << endl;
////////////////////////////////////////////////////////////
bool ok = false;
for (size_t i = 0; i < quantityOfWordsInText; i++)
{
for (size_t j = 0; j < quantityOfWordsInVocab; j++)
{
if (text[i] == vocab[j])
{
cout << text[i] << '\n';
ok = true;
break;
}
}
if (!ok)
{
diff(i);
}
ok = false;
}
return 0;
}
Работает достаточно быстро