标签: cs50

作为哈佛大学CS50课程的一项任务,学生的任务是创建一个拼写检查程序.任务的主要目标是速度 - 纯粹的速度 - 我已经达到了我打败员工实施的程度,但我觉得我可以做得更好,并且正在寻找正确方向的推动力.

这是我的伪代码:

// read the dictionary word list
Read entire dictionary in one fread into memory
rawmemchr through and pick out the words
send each word through the hash function
create chain links for any index where collisions occur

// accept the incoming test words
Run the test word through the hash function
compare to the existing table / linked list
return the result of the comparison

使用150K字的字典,输入文本高达6MB,我能够准确地拼写检查大约半秒钟.

但是,当我查看来自输入文本的单词时,很明显这些单词的大部分是常见的(如"the","and","for"),以及大多数拼写错误的单词也会多次检查.

我的直觉说我应该能够"缓存""好点击"和"糟糕点击",这样我就不会一遍又一遍地为表格查找扫描相同的单词.即使当前结果非常接近O(1),我觉得我应该能够通过重新评估我的方法来减少几微秒的时间.

例如,在我加载字典后,文本输入可能只有8MB,但是:"误导".因此,我不想反复哈希/检查相同的单词(以计算费用),我想了解是否有一种方法可以编程方式丢弃已经被散列和拒绝的单词,但是以一种比哈希/检查本身.(我正在使用MurmurHash3,fwiw).

我意识到理论性能改进将局限于输入文本很长的情况,并且存在大量重复拼写错误.基于我评估的一些输入文本,以下是一些结果:

Unique Misspellings: 6960
Total …

这是一些提供的（CS50）代码的片段，这些代码在嵌套循环中一遍又一遍地声明相同的STRUCT“三元组”。为什么这样可以呢？在我看来，将STRUCT“三元组”声明为嵌套循环的范围上方并在每次迭代中更改值会更有效。

typedef struct
{
    BYTE rgbtBlue;
    BYTE rgbtGreen;
    BYTE rgbtRed;
} __attribute__((__packed__))
RGBTRIPLE;

。

 for (int i = 0, biHeight = abs(bi.biHeight); i < biHeight; i++)
{
    // iterate over pixels in scanline
    for (int j = 0; j < bi.biWidth; j++)
    {
        // temporary storage
        RGBTRIPLE triple;

        // read RGB triple from infile
        fread(&triple, sizeof(RGBTRIPLE), 1, inptr);

        // write RGB triple to outfile
        fwrite(&triple, sizeof(RGBTRIPLE), 1, outptr);
    }

我正在尝试用 C 语言实现 Luhn 算法来检查信用卡有效性，对于那些不知道的人......就是这样：

\n

• 从数字\xe2\x80\x99s\n倒数第二个数字开始，每隔一个数字乘以 2，然后将这些乘积\xe2\x80\x99 数字相加。

  \n
\n

• 将总和添加到 \xe2\x80\x99t 乘以 2 的数字之和。

  \n
\n

• 如果总计 \xe2\x80\x99s 最后一位数字为 0（或者，更正式地说，如果总计
  \n模 10 与 0 全等），则该数字有效！

  \n
\n

为了实现这一点，我循环遍历整个数字，如果我所在的数字位置的模 2 等于 0，那么我将乘以 2 并添加到一个名为totalEven。

如果不是这种情况，我会将我所在的号码添加到totalOdd而不进行乘法。

然后我会将这个位置加 1，并检查其他数字，直到达到 16（卡片的最大数字）。

我稍后会将这两个变量相加，并检查总模数 10 是否等于 0。如果这意味着信用卡号是正确的，否则就是错误的。

这是代码：

#include <stdio.h>\n#include <cs50.h>\n\n//list of variables\n\n   //is the card valid\n   bool isValid = true;\n   // the creditcard number\n   long input;\n   //mod stands for modules, and …

我已经完成拼写并通过了所有检查。但我仍然对性能感到困扰。我尽了最大努力进行研究和运行测试，但与员工的相比，我的实施速度慢了 10-20%。我该如何改进我的代码？

    // Implements a dictionary\'s functionality\n\n#include <ctype.h>\n#include <stdbool.h>\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n#include <strings.h>\n#include "dictionary.h"\n\n// Represents a node in a hash table\ntypedef struct node\n{\n    char word[LENGTH + 1];\n    struct node *next;\n}\nnode;\n//Prototypes\nunsigned int hash(const char *word);\n\n// TODO: Choose number of buckets in hash table\nconst unsigned int N = 187751; //odd prime number bigger than word count, because math\n\n// Hash table\nnode *table[N]; //may need to use calloc\n\n//word count\nint word_count = 0;\n\n// Returns true if word is in dictionary, else false\nbool check(const char …

我正在尝试将C库用于哈佛大学的开放课程.可以在此处找到教师有关设置外部库的说明.

我正在按照ubuntu特有的说明进行操作,因为我试图在我的ubuntu盒子上使用这个库.我按照页面上的说明进行设置,但是当我helloWorld.c使用cs50库函数运行一个简单的程序时,gcc不想播放.

例:

helloWorld.c

#include <stdio.h>
#include <cs50.h>

int
main(void){
        printf("What do you want to say to the world?\n");
        string message = GetString();
        printf("%s!\n\n", message);
}

$ gcc helloWorld.c

/tmp/ccYilBgA.o: In function `main':
helloWorld.c:(.text+0x16): undefined reference to `GetString'
collect2: ld returned 1 exit status

我按照指示中的说明按照说明进行了操作,但它们对我不起作用.我正在运行ubuntu 12.04.如果我能进一步澄清我的问题,请告诉我.

我的问题与CS50,pset5的任务有关.对于那些不了解的人,我会试着解释一下.没什么特别的.我只需要创建将输入字典文件的函数(之前写过,该文件中的所有单词都是大写的),其中包含超过20K的单词,并以某种方式对它们进行排序.我已经制作了简单而天真的算法,构建了哈希表,根据他们的第一个字母对单词进行排序.我已经通过CS50的所有检查,所以我的程序运行良好.但与课程相比 - 它太慢了.执行人员的时间是0.1秒,但对于我的 - 5.0s - 7.0s.我可以在此代码中改进哪些内容以加快速度？或者我应该彻底改变一切吗？我没有优化经验,因为刚开始学习.从你们任何人那里学习会很棒=)在此先感谢!

// Some constant values, which are declared before the function
#define LENGTH  46
#define ALPHALENGTH  26
/* Definition of node struct. Nothing special, in fact =) */
typedef struct node {
    char word[LENGTH +1];
    struct node *next;
} node;

node *hashTable[ALPHALENGTH];

bool load(const char *dictionary) { 
    FILE *f = fopen(dictionary, "r");

    if (f == NULL) {
        return false;
    }

    char word[LENGTH + 1];    
    int hash = 0;

    for (int i = 0; i …

#include <cs50.h>
#include <stdio.h>
#include <string.h>

int main(void)
{
    //ask user for input
    string s = get_string();

    //make sure get_string() returned a string
    if(s != NULL)
    {
        //iterate over the characters one at a time
        for(int i = 0, int n = strlen(s); i < n; i++)
        {
            //print i'th character in s
            printf("%c\n", s[i]);
        }
    }
    else
    {
        //tell the user that their input is not a string
        printf("Sorry, no good\n");
    }

}

编译器抱怨这一行:

for(int i = 0, int …

我正在哈佛大学攻读 MOOC课程CS50.我的最后一个讲座是关于内存分配和指针(两个对我来说绝对新的概念).

所教的是malloc(10*sizeof(char))在堆上分配足够的字节来存储10个字符并返回指向第一个字节的指针,该指针可以保存在另一个变量中,如下所示char *x = malloc(10*sizeof(char)).为了释放内存,人们会使用free(x).

但还有另一种方法可以让计算机保留足够的内存来存储10个字符,即char c[10].

1. 在上面的代码片段中c也是一个类型的指针char*？
2. 是否char c[10]还保留内存堆中的malloc呢？
3. 分配内存的方法是否相同？
4. char c[3] = "aaa";free(c);返回运行时错误; 所以我似乎无法释放我分配的内存char c[3].这是为什么？

我真的很感激为那些刚学过指针的人量身定做的答案.

这是我用 Python 编写的第一个程序之一，所以我可能会遗漏一些明显的东西。

在我发布的代码的第一部分中，我想确保用户传递命令行参数。如果没有，我想显示错误并返回 1。当我在没有命令行参数的情况下运行代码时，程序具有预期的行为，因为打印错误并退出程序。

但是，当我对此运行检查器时，出现错误：

处理缺少 argv[1]。预期退出代码 1，而不是 0。

关于我可能缺少什么的任何想法？

import sys
import cs50
from cs50 import get_string


def main(argv):
    # Check for command line argument
    if (len(sys.argv) != 2):
        print("Error: Please input numeric key in command line.")
        return 1

if __name__ == "__main__":
    main(sys.argv)

所以让我们说：

int n = 50;
int *p = &n;

为什么我们在 C 中使用*而不是&？*和之间的主要区别是&什么？