Согласование сгенерированной строки случайных букв на вход

Я сделал программу на Python и хотел, чтобы она была быстрее, поэтому я написал ее на C #, потому что она скомпилирована. К моему удивлению, программа Python работает намного быстрее. Я думаю, что что-то не так с моим кодом на C #, но это довольно просто и просто, поэтому я не знаю. Они структурированы примерно таким же образом.

C #

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Diagnostics;

//This program generates a string of random lowercase letters and matches it to the user's input
//It does this until it gets a match
//It also displays the closest guess so far and the time it took to guess

namespace Monkey
{
    class Program
    {
        static string userinput()
        {
            //Takes user input, makes sure it is all lowercase letters, returns string
            string input;

            while(true)
            {
                input = Console.ReadLine();

                if (Regex.IsMatch(input, @"^[a-z]+$"))
                {
                    return input;
                }
            }
        }

        static string generate(int len)
        {
            //generates string of random letters, returns the random string
            Random rnd = new Random();
            string alpha = "abcdefghijklmnopqrstuvwxyz";
            int letterInt;
            StringBuilder sb = new StringBuilder();


            for (int i = 0; i < len; i++)
            {
                letterInt = rnd.Next(26);
                sb.Append(alpha[letterInt]);
            }

            return sb.ToString();
        }

        static int count(int len, string s, string g)
        {
            //returns number of letters that match user input
            int same = 0;

            for (int i = 0; i < len; i++)
            {
                if(g[i] == s[i])
                {
                    same++;
                }
            }

            return same;
        }

        static void Main(string[] args)
        {
            Console.WriteLine("They say if you lock a monkey in a room with a typewriter and enough time,");
            Console.WriteLine("the monkey would eventually type a work of Shakespeare.");
            Console.WriteLine("Let's see how well C# does...");
            Console.WriteLine("Enter a word");
            Console.WriteLine("(3 letters or less is recommended)");
            string solution = userinput();

            int size = solution.Length;
            bool success = false;
            string guess = null;
            int correct;
            int best = 0;
            Stopwatch watch = Stopwatch.StartNew();

            while (!success)
            {
                guess = generate(size);
                correct = count(size, solution, guess);

                if (correct == size)
                {
                    success = true;
                }

                else if (correct > best)
                {
                    Console.Write("The best guess so far is: ");
                    Console.WriteLine(guess);
                    best = correct;
                }
            }

            watch.Stop();
            TimeSpan ts = watch.Elapsed;
            Console.WriteLine("Success!");
            Console.Write("It took " + ts.TotalSeconds + " seconds for the sharp C to type ");
            Console.WriteLine("\"" + guess + "\"");

            Console.ReadLine();
        }
    }
}

Python:

import random
import time
#This program generates a string of random letters and matches it with the user's string
#It does this until it's guess is the same as the user's string
#It also displays closest guess so far and time it took to guess


def generate():
    # generate random letter for each char of string
    for c in range(size):
        guess[c] = random.choice(alpha)


def count():
    # count how many letters match
    same = 0
    for c in range(size):
        if guess[c] == solution[c]:
            same += 1
    return same


print("They say if you lock a monkey in a room with a typewriter and enough time,")
print("the monkey would eventually type a poem by Shakespeare")
print("Let's see how well a python does...'")

user = ""
badinput = True
while badinput:
    # Make sure user only inputs letters
    user = input("Enter a word\n(5 letters or less is recommended)\n")
    if user.isalpha():
        badinput = False

solution = list(user.lower())
size = len(solution)
guess = [""] * size
alpha = list("abcdefghijklmnopqrstuvwxyz")
random.seed()
success = False
best = 0    # largest number of correct letters so far
start = time.time()    # start timer

while not success:
    # if number of correct letters = length of word
    generate()
    correct = count()
    if correct == size:
        success = True
    elif correct > best:
        print("The best guess so far is: ", end="")
        print("".join(guess))
        best = correct

finish = time.time()    # stop timer
speed = finish - start

print("Success!")
print("It took " + str(speed) + " seconds for the python to type ", end="")
print("\"" + "".join(guess) + "\"")
input()
27 голосов | спросил bobpal 25 FebruaryEurope/MoscowbTue, 25 Feb 2014 22:08:47 +0400000000pmTue, 25 Feb 2014 22:08:47 +040014 2014, 22:08:47

6 ответов


20

Я не знаю , поэтому я 'сосредоточимся на .

  • Ваша программа закодирована с ног на голову. Можно было бы ожидать void Main вверху, с более специализированным кодом ниже.
  • Предполагается, что имена методов в C # последовательно следуют за соглашением PascalCasing . Только этот метод Main делает это, и если вы должны принять соглашение camelCasing , userinput будет лучше вызываться userInput.
  • Не кажется правильным, что метод Count не выводит число итераций из длины строки (ов), которую он задал, и не делает ничего, чтобы проверить, index является законным, что на первый взгляд похоже на запрос IndexOutOfRangeException.

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

Использование StringBuilder было хорошим вызовом.

ответил Mathieu Guindon 25 FebruaryEurope/MoscowbTue, 25 Feb 2014 22:41:56 +0400000000pmTue, 25 Feb 2014 22:41:56 +040014 2014, 22:41:56
51

Если вы хотите производительность, не создавайте объекты во внутреннем цикле:

    static string generate(int len)
    {
        Random rnd = new Random();                    // creating a new object
        string alpha = "abcdefghijklmnopqrstuvwxyz";
        int letterInt;
        StringBuilder sb = new StringBuilder();      // creating a new object
        ....

    }

создайте их один раз и повторно используйте их

ответил vals 25 FebruaryEurope/MoscowbTue, 25 Feb 2014 22:47:12 +0400000000pmTue, 25 Feb 2014 22:47:12 +040014 2014, 22:47:12
20

Чтобы ответить на вопрос, почему ваш код c # настолько медленный.

Это линия. Согласно профилировщику ~ 90% времени выполнения используется воссозданием объекта Random. Вы заметите, что ваш код на Python использует только случайное, а не воссоздает его.

Random rnd = new Random();

, если вы измените метод генерации на:

    static Random rnd = new Random();

    static string generate(int len)
    {
        //generates string of random letters, returns the random string
        string alpha = "abcdefghijklmnopqrstuvwxyz";
        int letterInt;
        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < len; i++)
        {
            letterInt = rnd.Next(26);
            sb.Append(alpha[letterInt]);
        }

        return sb.ToString();
    }

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

ответил Graeme Bradbury 26 FebruaryEurope/MoscowbWed, 26 Feb 2014 15:31:56 +0400000000pmWed, 26 Feb 2014 15:31:56 +040014 2014, 15:31:56
10

В вашем коде python вы используете массив символов как ваш guess. В коде C # вы создаете StringBuffer. Вместо этого попробуйте использовать char[].

Поскольку вы находитесь в обзоре кода - я также расскажу о вашем коде:

Соглашения об именах . Именование имен C # - это PascalCase, и имя функции python в snake_case, поэтому - UserInput() и user_input(): соответственно.

Значимые имена - generate и count не отображают смысл кода в них GenerateRandomString и CountSimilarLetters лучше. То же самое касается alpha, len, g, s и т. Д.

ответил Uri Agassi 25 FebruaryEurope/MoscowbTue, 25 Feb 2014 22:36:22 +0400000000pmTue, 25 Feb 2014 22:36:22 +040014 2014, 22:36:22
8

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

старый код:

    static string userinput()
    {
        //Takes user input, makes sure it is all lowercase letters, returns string
        string input;

        while(true)
        {
            input = Console.ReadLine();

            if (Regex.IsMatch(input, @"^[a-z]+$"))
            {
                return input;
            }
        }
    }

    private static string generate(int len)
    {
        // generates string of random letters, returns the random string
        Random rnd = new Random();
        string alpha = "abcdefghijklmnopqrstuvwxyz";
        StringBuilder sb = new StringBuilder();
        int letterInt;

        for (int i = 0; i < len; i++)
        {
            letterInt = rnd.Next(26);
            sb.Append(alpha[letterInt]);
        }

        return sb.ToString();
    }

новый код:

    private static readonly Regex regex = new Regex(@"^[a-z]+$", RegexOptions.Compiled);
    private static readonly Random rnd = new Random();

    static string userinput()
    {
        //Takes user input, makes sure it is all lowercase letters, returns string
        string input;

        while(true)
        {
            input = Console.ReadLine();

            if (regex.IsMatch(input))
            {
                return input;
            }
        }
    }

    private static string generate(int len)
    {
        // generates string of random letters, returns the random string
        const string alpha = "abcdefghijklmnopqrstuvwxyz";
        StringBuilder sb = new StringBuilder();
        int letterInt;

        for (int i = 0; i < len; i++)
        {
            letterInt = rnd.Next(26);
            sb.Append(alpha[letterInt]);
        }

        return sb.ToString();
    }
ответил Jesse C. Slicer 26 FebruaryEurope/MoscowbWed, 26 Feb 2014 03:39:32 +0400000000amWed, 26 Feb 2014 03:39:32 +040014 2014, 03:39:32
3

Вот поздний комментарий к вашей программе Python.


Я не знаю C #. Честно говоря, я действительно удивлен тем, что C # не быстрее, потому что написанное вами not , как реализовать быстрый вариант в Python.

В Python вы захотите использовать Numpy, если все будет медленным. На самом деле вам нужно что-то вроде:

"""
This program generates a string of random letters and matches it with the user's string.
It does this until its guess is the same as the user's string.
It also displays closest guess so far and time it took to guess.
"""

import numpy
import time
from string import ascii_lowercase

# Everything is ASCII, which is what the "c" means.
letters = numpy.array(list(ascii_lowercase), dtype="c")

def brute_force(solution):
    """
    BRRUUUUTTTEEE FFOOORRRCCCEEEE!!!!

    Repeatedly guess at a solution until it matches.
    """

    # Convert to char array
    solution = numpy.array(list(solution.casefold()), dtype="c")

    best = 0
    while True:
        # Do loads of guesses (100000) at once
        guesses = numpy.random.choice(letters, (100000, len(solution)))

        # Check all of the characters for equality, and count the number
        # of correct for each row
        corrects = (guesses == solution).sum(axis=1)

        # Gets the highest-so-far at each point
        maximums = numpy.maximum.accumulate(corrects)

        # Gets how much the maximum increased
        changes = numpy.diff(maximums)

        # Indexes of the increases
        # numpy.where returns a tuple of one element, so unpack it
        [when_increased] = numpy.where(changes > 0)
        # Need to increase by one, because these are indexes into
        # the differences whilst we want indexes into the final array
        # for the *increased* (not increasing) elements
        when_increased += 1

        for index in when_increased:
            guess = guesses[index]
            correct = corrects[index]

            if correct > best:
                yield str(guess, encoding="ascii")
                best = correct

            if correct == len(solution):
                return


print("They say if you lock a monkey in a room with a typewriter and enough time,")
print("the monkey would eventually type a poem by Shakespeare")
print("Let's see how well a python does...'")

while True:
    print("Enter a word")
    print("(5 letters or less is recommended)")
    user_input = input()

    # Make sure user only inputs letters
    if user_input.isalpha():
        break

start = time.time()

for solution in brute_force(user_input):
    print("The best guess so far is: ", solution)

elapsed_time = time.time() - start

print("Success!")
print("It took ", elapsed_time, " seconds for the python to type ", repr(solution))

Это может выглядеть более устрашающе, но есть только ~ 30 строк логики, большинство из которых тривиальны.

Основная идея состоит в том, чтобы делать массовые беспорядочные выборки:

guesses = numpy.random.choice(letters, (100000, len(solution)))

, что быстро. Это делает матрицу 100000xN, например. для N = 3:

h s l
w t x
a m e
i x t
  ⋮

Затем вы можете подсчитать число, соответствующее каждой строке, сравнивая каждую строку с решением (guesses == solution), предоставляя массив bool, и вы можете суммировать каждый row (.sum(axis=1)), чтобы получить правильный номер.

Дополнительные части оттуда (numpy.diff) служат pretend , мы сделали это последовательно, хотя мы этого не сделали. Это не актуально в большинстве реальных ситуаций, где можно просто распечатать лучший ответ из этой группы.

В целом это намного быстрее, чем оригинал (> 10x), и большую часть времени тратится на numpy.random.choice, подразумевая, что невозможно значительно увеличить скорость без замены высококачественные случайные числа, которые генерирует Numpy.

Так что не думайте, чтоPython медленный, потому что он интерпретируется и динамичен. Вполне возможно, чтобы с такими программами выполнялась высококачественная реализация.


Так как это Code Review, я также укажу на некоторые вещи, которые вы должны улучшить:

  • Docstrings , а не комментарии .

    Запись

    """
    This program generates a string of random letters and matches it with the user's string.
    It does this until its guess is the same as the user's string.
    It also displays closest guess so far and time it took to guess.
    """
    

    вместо

    # This program generates a string of random letters and matches it with the user's string.
    # It does this until its guess is the same as the user's string.
    # It also displays closest guess so far and time it took to guess.
    

    Это может звучать бессмысленно суетливо, но это помогает самоанализу.

  • Уменьшите использование глобалов. Функции должны (почти) никогда делиться состоянием; он должен проходить между ними. Поверь мне. Это означает, что вы можете повторно использовать их и перемещать их, не беспокоясь о зависимостях, для одного. Он также позволяет локальным изменениям оставаться локальными.

  • Попробуйте и скомпонуйте IO в одном месте. Если вы посмотрите на мой вариант, вся печать будет локализована и логика будет разделена. Это модулирует программу, поэтому вы можете перемещать вещи и общаться с логикой, не имея «вещей» на вашем пути все время.

  • random.seed() без значения здесь бессмысленно. Его следует использовать только после random.seed(some_value) в удалить семя.

  • Этот код:

    done = False
    while not done:
        if ...:
            done = True
    

    гораздо лучше написано

    while True:
        if ...:
            break
    

    Некоторые люди не согласны. Они ошибаются.

  • Такие вещи, как

    for c in range(size):
        guess[c] = random.choice(alpha)
    

    , где вы посещаете каждый элемент по очереди, лучше написаны без индексов, например:

    guess[:] = [random.choice(alpha) for _ in range(size)]
    

    хотя это действительно должно быть

    def generate(size):
        """Generate random letter for each character of string."""
        return [random.choice(alpha) for _ in range(size)]
    

    , если вы используете мои предыдущие советы.

    То же самое относится к count, который может быть

    sum(g==s for g, s in zip(guess, solution))
    
  • Не бессмысленно выделять значения, например guess = [""] * size. Он просто скрывает ошибки.

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

ответил Veedrac 26 Maypm14 2014, 20:03:59

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132