Программирование на С++
Введение
В эпоху продвинутых языковых моделей, таких как ChatGPT от OpenAI и Bard от Google, становится все более интригующим исследовать альтернативные методы генерации текста. Одним из таких методов, заслуживающих внимания, является увлекательная концепция, известная как теорема о бесконечных обезьянах. В этой статье мы попытаемся углубиться в эту теорему и воспроизвести ее сущность с помощью мощного языка программирования C++.
Теорема о бесконечных обезьянах
Теорема о бесконечных обезьянах — это мысленный эксперимент, который всегда восхищал меня. Это предполагает, что если обезьяна будет беспорядочно нажимать клавиши на пишущей машинке в течение бесконечного времени, она в конечном итоге напечатает любой заданный текст.
Хотя это практически невозможно воспроизвести, можно смоделировать генерацию случайных строк до тех пор, пока не будет достигнута целевая строка, подобно обезьяне, печатающей текст.
Реализация на С++
Стремясь улучшить свои навыки в C++, я выбрал его в качестве языка для этого эксперимента, у него также есть преимущество в том, что он быстр, особенно для выполнения циклов for по сравнению с Python (исходный код).
Чтобы имитировать печатающую обезьяну, мы можем структурировать наш код с помощью нескольких функций, одна из которых называется «генерировать», которая генерирует случайную строку при вызове, а другая называется «оценка», которая выводит оценку от 0 до 1 для того, насколько близка сгенерированная строка к целевая строка. На основе этих двух функций могут быть созданы другие служебные функции, такие как «testUntilAchieve», которая продолжает генерировать случайные строки до тех пор, пока не будет создана целевая строка, и «repeatTest», которая повторяет «testUntilAchieve» заданное количество раз для усреднения результатов эксперимента.
«генерировать»: Генерация случайных строк
Чтобы создать случайные строки, мы можем создать алфавит, содержащий буквы, затем случайным образом выбрать индекс и, следовательно, букву, используя возможности C++ rand(); затем мы можем добавлять эту букву к сгенерированной строке до тех пор, пока не будет достигнута желаемая длина, как в реализации ниже.
#include <iostream>
#include <string>
#include <cstdlib>
using namespace std;
string generate(const string &targetString) {
char alphabet[26] = { 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z'};
string generatedString = "";
for (int i = 0; i < targetString.length(); i++) {
int randomIndex = rand() % 26;
char generatedChar = alphabet[randomIndex];
generatedString.push_back(generatedChar);
}
return generatedString;
}
int main() {
srand((unsigned)time(NULL));
string targetString = "hello";
cout << generate(targetString) << "\n";
}
Важно отметить, что для правильной работы rand(), то есть для генерации новой строки при каждом вызове, мы должны установить случайное начальное число с помощью srand() , обычно время выбирается, как в этой реализации.
«score»: оценка сгенерированных строк
Чтобы оценить конкретную строку в соответствии с ее целью, мы можем перебрать длину строки и посмотреть, соответствует ли каждый символ своей цели; тогда высший балл будет получен при проверке идентичной строки, что означает, что она имеет точно такие же буквы в точно таком же порядке. Это реализовано ниже.
#include <iostream>
#include <string>
using namespace std;
double score(const string &targetString, const string &testString) {
int correctCount = 0;
for (int i = 0; i < targetString.length(); i++) {
if (targetString[i] == testString[i]) {
correctCount++;
}
}
return (double) correctCount / targetString.length();
}
int main() {
string targetString = "hello";
string testString = "hillo";
cout << score(targetString, testString) << "\n";
}
Важно отметить, что для работы функции «оценка» строки должны быть одинаковой длины.
«testUntilAcheive»: Генерация случайных строк до тех пор, пока не будет сгенерирована целевая строка.
Логика testUntilAchieve состоит в том, чтобы использовать generate и score для продолжения генерации строк до тех пор, пока оценка не станет идеальной (т.е. 1.0). Это можно сделать с помощью цикла while, как показано ниже. Это также включает в себя печать результатов на данный момент, а также ожидаемое количество итераций, которое представляет собой просто количество элементов в алфавите в степени длины строки.
#include <iostream>
#include <string>
#include <cmath>
#include <cstdlib>
using namespace std;
void testUntilAchieve(const string &targetString) {
double currentScore = 0.0;
int count = 0;
while (currentScore < 1.0) {
string generatedString = generate(targetString);
double currentScore = score(targetString, generatedString);
count++;
cout << "Target String: '" << targetString << "' -> Generated String: '" << generatedString << "' -> Score: " << currentScore * 100 << "% -> Count: " << count << "\n";
if (currentScore == 1.0) {
break;
}
}
cout << "----- PROGRAM OUTCOME -----\n";
cout << "It took " << count << " tries to obtain the target string.\n";
int expectedTries = pow(26, targetString.length());
cout << "The expected amount of tries was " << expectedTries << "\n";
}
int main() {
srand((unsigned)time(NULL));
string targetString = "hi";
testUntilAchieve(targetString);
}
Обратите внимание, что эта функция ничего не возвращает, даже количество различных попыток, которые она должна была сделать, прежде чем достичь целевой строки, по этой причине я сделал еще одну очень похожую функцию, которая ничего не печатала, а просто возвращала это количество для использования в repeatTest .
«repeatTest»: несколько запусков моделирования
Эта функция предназначена для использования testUntilAcheive и запускает ее заданное количество раз, а затем возвращает среднее количество необходимых попыток. Это может быть полезно хотя бы в целях тестирования, поскольку возвращаемое среднее значение можно использовать для проверки правильности определения функций, а именно: возвращаемое среднее значение должно быть близко к ожидаемому количеству попыток, как указано выше, оно равно число элементов в алфавите в степени длины строки. Это можно реализовать, как показано ниже (обратите внимание на использование countTestUntilAchieve):
#include <iostream>
#include <string>
#include <cmath>
#include <cstdlib>
using namespace std;
double repeatTest(int testRepeats, const string &targetString) {
int count = countTestUntilAchieve(targetString);
int countSum = 0;
for (int i = 0; i < testRepeats; i++) {
int count = countTestUntilAchieve(targetString);
countSum += count;
}
return (double)countSum / testRepeats;
}
int main() {
srand((unsigned)time(NULL));
string targetString = "hi";
int testRepeats = 1000000;
cout << repeatTest(testRepeats, targetString);
}
Полный код доступен в моем репозитории GitHub здесь
Будущая работа
Будущая работа может быть выполнена для улучшения читаемости кода C++, а также для увеличения скорости вычислений, которые увеличиваются экспоненциально из-за скорости увеличения числа возможностей, умножающихся на 26 для каждого символа в строке. Я подозреваю, что можно было бы распараллелить функцию repeatTest, чтобы прогоны можно было разделить между разными потоками.
Еще одной интересной областью для улучшения может быть использование алгоритмов, которые сохраняют правильные буквы при прогнозировании будущего, что может значительно сократить объем необходимых вычислений.
Ограничения
Следует отметить, что это не более чем мысленный эксперимент, а не реально возможный способ генерации текста как такового, потому что мы генерируем случайные строки до тех пор, пока не будет достигнута введенная нами строка, это означает, что мы на самом деле не создаем новые струны. Интересной возможностью может быть сохранение этого базового метода создания случайных строк и использования нейронной сети или обучения с подкреплением для создания модели, которая самосовершенствуется для генерации текста, имеющего смысл.
Твой ход
Вам слово, подумайте, как вы можете улучшить код; например, сделайте некоторую обработку ошибок, чтобы функция score не могла оценивать строки разной длины.
Если вам понравилась эта статья, пожалуйста, поставьте лайк и подпишитесь, чтобы узнать больше, это действительно помогает. Хорошего дня!
