Последовательная генерация ключей

Question

Сейчас я работаю над проектом, который требует последовательной генерации текстовых ключей.Мне нужно заполнить генератор ключей целым числом, соответствующим определенному ключу, который конструктор преобразует в ключ.

Мой генератор ключей перегружает операторы приращения, так что строка увеличивается напрямую, а не то, что у меня былоранее делал это, увеличивая значение индекса, затем преобразовывая индекс в ключ для каждого ключа, который я хотел сгенерировать.

Моя проблема в том, что у меня есть ограниченный набор символов, который я хочу использовать при генерации ключей,Мне нужно найти символ в ключе, который я хочу увеличить, выяснить, где он находится в моем наборе символов, найти следующий символ в наборе, а затем заменить символ в ключе следующим символом в наборе.

Вот мой код:

// Not the full charset
std::string charset = "abcdefghijklmnopqrstuvwxyz0123456789"; 
std::string key;

key.push_back(charset[0]);

for(unsigned int place = 0; place < key.length(); place++)
{
    if(key[place] == charset[charset.length() - 1])
    {
        // Overflow, reset char at place
        key[place] = charset[0];

        if((key.length() - 1) < (place + 1))
        {
            // Carry, no space, insert char
            key.insert(key.begin(), charset[0]);
            break;
        }
        else
        {
            // Space available, increment next char
            continue;
        }
    }
    else
    {
        // Increment char at place
        key[place] = charset[charset.find(key[place]) + 1];
        break;
    }
}

В профилировании я обнаружил, что операция поиска действительно замедляет работу.Есть ли более быстрый способ сделать это?Я думал о создании связанного списка из набора символов, но прежде чем я сделаю это, я хотел бы получить некоторую информацию об этом.

Answer 1

Вместо того, чтобы делать поиск, почему у вас нет массива обратного перевода? Индексом массива будет символ, а значением в массиве будет его числовое значение (или индекс в другом массиве).

key[place] = charset[reverse_charset[key[place]] + 1];

Answer 2

Это еще одна версия обобщенной задачи преобразования баз, с n = 36.

То, что вы хотите сделать, - это просмотреть ключ как целое число без знака и просмотреть «строку», которую вы раздаете, как представление этого ключа в базовом 36 (a-z + 0-9).

После выдачи ключа происходит преобразование значения «следующего ключа» в строку base36, а затем увеличение значения следующего ключа.

Для преобразования сделайте то же самое, что и для преобразования любого целого числа в шестнадцатеричное представление, но поменяйте местами 36 вместо 16 в модуле математики. Я оставлю это как упражнение для читателя. :)

Answer 3

Я не уверен, что точно понял, что вы хотели сделать, но вот небольшая консольная программа, которая печатает последовательность из 36 * 36 * 36 3-значных клавиш в базе 36, используя вашу кодировку в качестве цифр. Таким образом, он начинается в ААА и заканчивается в 999.

#include <stdio.h>
typedef int Number;
const size_t N = 3;
size_t B = 36;
Number key[N] = {0};
bool carry = false;
char A[] = "abcdefghifjlmnopqrstuvwxyz0123456789";

void incr(size_t i)
{
    if(!carry)
    {
        return;
    }
    ++key[i];
    if(key[i] == B)
    {
        key[i] = 0;
    }
    else
    {
        carry = false;
    }
}

void Incr()
{
    carry = true;
    size_t i = 0;
    while(carry)
    {
        incr(i++);
    }
}

void Print()
{
    for(int i = N - 1; i >= 0; --i)
    {
        printf("%c", A[key[i]]);
    }
    printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
    for(int i = 0; i < B * B * B; ++i)
    {
        Print();
        Incr();

    }
    return 0;
}

Answer 4

Вы можете хранить вектор такой же длины, что и ваш ключ, где каждый элемент в векторе является индексом в кодировке соответствующего символа в ключе.

Например, если key[0] было 'c', то thisVector[0] было бы 2, так как 'c' является третьим символом в наборе символов.

Тогда все операции будут выполняться с этим целочисленным вектором, что устраняет необходимость операции find со строкой.

Answer 5

Возможно, вам было бы лучше поработать с индексами в кодировке, а затем при необходимости преобразовать их в реальные символы?

Это избавило бы вас от необходимости поиска символов в кодировке. И преобразование индекса набора символов в символ будет работать в режиме постоянного времени, в отличие от обратного.

Сохраните ваш ключ как вектор целых чисел 0 ~ N-1, где N - длина вашей кодировки. Преобразуйте эти целые числа в действительные символы только при необходимости, то есть после приращения.