我想制作一个算法来过滤一些数字,例如 101010101010101。其中有一些模式的数字。但它们非常大,我需要 4 或 5 秒才能达到 100.000.000。大约有 99,500,000 个数字被过滤掉。问题是,我怎样才能达到 1.000.000.000.000.000 而无需等待几个月。我希望代码在 0.4 秒或更短时间内达到 100.000.000。我希望有人能帮助我。这是我的代码:
#include <stdio.h>
#include <stdbool.h>
#include <string.h>
#include <windows.h>
#define NUM_THREADS 8
#define MAX_NUM 100000ULL
typedef struct {
unsigned long long int start;
unsigned long long int end;
unsigned long long int count;
} ThreadData;
// Funktion zur Überprüfung auf aufeinanderfolgende Ziffern
bool has_consecutive_digits(const char* password, int length) {
int len = strlen(password);
for (int i = 0; i <= len - length; i++) {
bool increasing = true, decreasing = true;
for (int j = 0; j < length; j++) {
if (password[i+j] != password[i] + j) increasing = false;
if (password[i+j] != password[i] - j) decreasing = false;
}
if (increasing || decreasing) return true;
}
return false;
}
// Funktion zur Überprüfung auf zu viele Wiederholungen der gleichen Ziffer
bool has_repeated_digits(const char* password, int max_repeats) {
int counts[10] = {0};
int len = strlen(password);
for (int i = 0; i < len; i++) {
counts[password[i] - '0']++;
if (counts[password[i] - '0'] > max_repeats) return true;
}
return false;
}
// Funktion zur Überprüfung auf palindromische Muster
bool has_palindromic_pattern(const char* password, int length) {
int len = strlen(password);
for (int i = 0; i <= len - length; i++) {
bool is_palindrome = true;
for (int j = 0; j < length / 2; j++) {
if (password[i+j] != password[i+length-1-j]) {
is_palindrome = false;
break;
}
}
if (is_palindrome) return true;
}
return false;
}
// Funktion zur Überprüfung, ob das Passwort ein bekanntes Muster enthält
bool is_substring_of_common_patterns(const char* password) {
const char* common_patterns[] = {
"123456", "654321", "111111", "222222", "333333",
"012345", "543210", "987654", "000000", "999999"
};
for (int i = 0; i < 10; i++) {
if (strstr(password, common_patterns[i])) return true;
}
return false;
}
// Funktion zur Überprüfung auf abwechselnde Ziffern
bool has_alternating_digits(const char* password, int length) {
int len = strlen(password);
for (int i = 0; i <= len - length; i++) {
bool valid = true;
for (int j = 0; j < length; j++) {
if ((j % 2 == 0 && password[i+j] != password[i]) ||
(j % 2 == 1 && password[i+j] == password[i])) {
valid = false;
break;
}
}
if (valid) return true;
}
return false;
}
// Funktion zur Überprüfung auf aufeinanderfolgende Blöcke von steigenden oder fallenden Ziffern
bool has_increasing_or_decreasing_blocks(const char* password, int block_size) {
int len = strlen(password);
for (int i = 0; i <= len - block_size; i += block_size) {
if (has_consecutive_digits(password + i, block_size)) return true;
}
return false;
}
// Funktion zur Überprüfung auf spiegelbildliche Blöcke
bool has_mirrored_blocks(const char* password, int block_size) {
int len = strlen(password);
for (int i = 0; i <= len - 2 * block_size; i += block_size) {
bool mirrored = true;
for (int j = 0; j < block_size; j++) {
if (password[i + j] != password[i + block_size * 2 - 1 - j]) {
mirrored = false;
break;
}
}
if (mirrored) return true;
}
return false;
}
// Funktion zur Überprüfung, ob das Passwort ein zu einfaches Muster hat
bool is_pattern_too_simple(const char* password) {
return has_consecutive_digits(password, 3) ||
has_repeated_digits(password, 1) ||
has_palindromic_pattern(password, 4) ||
is_substring_of_common_patterns(password) ||
has_alternating_digits(password, 4) ||
has_increasing_or_decreasing_blocks(password, 2) ||
has_mirrored_blocks(password, 4); // 3,1,3, ,4,2,4
}
// Funktion zur Überprüfung der Passwortgültigkeit
bool is_valid_password(const char* password) {
return !is_pattern_too_simple(password);
}
DWORD WINAPI check_passwords(LPVOID arg) {
ThreadData* data = (ThreadData*)arg;
char password[7]; // Für Zahlen bis 999999 (6 Ziffern + Nullzeichen)
data->count = 0;
for (unsigned long long int i = data->start; i < data->end; i++) {
sprintf(password, "%06llu", i); // Erzeuge ein 6-stelliges Passwort
if (is_valid_password(password)) {
data->count++;
}
}
return 0;
}
int main() {
HANDLE threads[NUM_THREADS];
ThreadData thread_data[NUM_THREADS];
unsigned long long int range = MAX_NUM / NUM_THREADS;
unsigned long long total_count = 0;
// Starte die Threads
for (int i = 0; i < NUM_THREADS; i++) {
thread_data[i].start = i * range;
thread_data[i].end = (i + 1) * range;
threads[i] = CreateThread(NULL, 0, check_passwords, &thread_data[i], 0, NULL);
if (threads[i] == NULL) {
fprintf(stderr, "Error creating thread %d\n", i);
return 1;
}
}
// Warte auf Threads und sammle Ergebnisse
for (int i = 0; i < NUM_THREADS; i++) {
WaitForSingleObject(threads[i], INFINITE);
DWORD exit_code;
if (GetExitCodeThread(threads[i], &exit_code)) {
total_count += thread_data[i].count;
} else {
fprintf(stderr, "Error getting thread exit code %d\n", i);
}
CloseHandle(threads[i]);
}
// Zeige die Gesamtanzahl der gültigen Passwörter an
printf("Anzahl der gültigen Zahlen: %llu\n", total_count);
return 0;
}
我尝试使用多线程,我的代码速度提高了大约 10 倍,并且从 int 切换到 unsigned long long int,这使我的代码速度更快了一些。我需要比这个至少快 10 倍的代码。我也尝试过标志。我不需要用 c 语言编写这段代码,如果有更快的语言请告诉我。
对于您的某些单独检查,如果密码前缀未通过检查,则完整密码也将无法通过检查。
例如,所有以“11”开头的密码都无效,因为
has_repeated_digits
。因此,您可以跳过整个 110000-119999 范围,而不是单独检查所有这些。
这将大大减少需要考虑的密码数量 - 随着密码变得更长,
has_repeated_digits
就可以将其中的大多数排除在考虑范围之外。