learn-algorithm / learn-algorithm

拖延症患者学习算法小分队

这是什么?

这是一个专供一小撮人学习算法的仓储，这里记录着每个人的算法成长历程。

为什么需要?

我想，很多程序员都有一本翻了没几页的《算法导论》，坚持下来的原因只有一个，没坚持下来的原因却又千千万个

• 工作忙，没时间
• 太难了，看不懂
• 暂时用不到，以后再说
• ...

就这样，很多人不超过100页就放弃了（包括我:sob:）

有句老话说得好：“一个人走的快:runner:，一群人走得远:two_men_holding_hands:。”

那么！让我们一起来学算法吧，一起相互监督克服懒惰！

Rules!

既然大家都是拖延症患者，那么一定要有一套强有力的措施来治这病。

一条不留情面，强而有力的规矩：

按时间完成每次任务并且提交！如果有两次未完成，踢出学习小组！毫不留情！！！

如果你想要有所学习和进步，那么，坚持下来吧！

How?

作业提交方法：

首先 fork 这个项目，每次任务我会放到章节对应目录下的markdown里，请大家及时查看，同时我会在微信群进行通知和teambition进行通知。

作业目录一般如下：

1-树
	1-二叉树
	2-AVL树
	3-...
2-..
	1-...
	2-...

每个人在每一次任务下创建自己id命名的文件夹（请保持每次id一致），然后在里面完成任务，如：

1-树
	1-二叉树
		daimajia
		kehr
		...
		...
	2-AVL树
		...

书写完成后，发送pull request，检查通过后，即可。

== 坚持就是胜利！ ==

光荣榜：

只要你按时完成一期任务，你就会上光荣榜，领取一枚小星星 ⭐

耻辱柱：

这里记录的是被踢出学习小组的家伙们： 🔫

learn-algorithm's Issues

大家有决心坚持下来吗？

一起坚持:two_men_holding_hands:就是力量:muscle:！

这里是不是有问题？

https://github.com/Learn-Algorithm/Learn-Algorithm/blob/master/1-%E6%A0%91/0-%E4%BA%8C%E5%8F%89%E6%A0%91/Akagi201/binary-tree.c#L32
这里的两个括号是什么意思？

kehr — 测一测小伙伴们的代码

@Dodolong 马超的

很厉害的一位小伙伴。前几次的代码给了不少帮助。这次的 trie 也学习了不少，这里提点个人看完代码和测试后的感想：

1. 原本以为自己看到了一个BUG，测了一下，然后在看，我错了～
2. 觉还有优化的地方，比如单词长度可以用strlen计算，或者直接判断'\0'

@daimajia 的 Trie

void Query(Trie **trees,char* word){

    if (*word == '\0') {
        if ((*trees)->count > 0) {
            printf("存在\n");
        }else{
            printf("不存在\n");
        }
        return;
    }

    Trie **next = (*trees)->next;
    int distance = *word - 97;

    if (next[distance] != NULL) {
        return Query(&next[distance], word+1);
    }else{
        printf("单词不存在\n");
    }
}

返回值是 void, 还出现了 return Query()...这个没问题吗

大家最近都在忙什么？

从开始到现在已经有很长一段时间了。初期大家激情澎湃，接着很默契的沉默了一段时间（至今）。
在这期间我开始了第一段实习生活，新知识的了解和学习让我焦头烂额，目前这在恶补以前留下的坑。
很喜欢这个气氛，虽然时间紧张，但仍愿意每天抽时间和大家一起做题。
ok，我说完了，大家最近在做什么呢？

Cyberoe

怎么没有注释呢

代码规范问题

一直写代码都有点轻微的强迫症，缩进、空格、命名 ……

大家平时写代码是怎么弄的呢？

做了四道题，发现对于代码的健壮性检查和测试用例都没做。对于这两个问题我是这么看的：

1. 健壮性检查。 对于参数检查和内存分配等等异常检查，可以方在算法实现之后，即每一题结束，下一题开始时做。
2. 测试用例。水平有限，我有看大家代码的习惯，发现小伙伴们并没有把自己的测试结果贴出来。比如用 mac 的小伙伴，写 cpp 的时候用头文件 algorithm, 输出语句用的是 printf，貌似是可以正常运行的。我用 Linux 测的时候gcc是不支持的，只能用 stdio.h 才可以。

发起建议：每一题写测试用例，在 README 里贴上测试结果。（也费不了太多时间，copy → paste）。每一题结束后 review 的时候完善代码健壮性。

我想每位小伙伴都希望自己的代码可以是一个规范、简洁、优雅、健壮的小家伙吧 💯

我准备 review 代码了～

同意的举手:raised_hand:

建议不要使用中文路径，我用的cmake不支持中文路径

[讨论]关于多次内存分配占用运行时间过长的问题

在测试hashmap(我实现成hashtable了，对hashmap待了解)的运行时间时，总是发现运行时间总是难以降下，一次偶然发现N次printf造成了占用时间的问题，后来为了进一步减小运行时间进行了删减测试，去掉其他部分只留要测试的子函数，最终觉得应该是内存分配上出了问题。后来我对malloc进行了专门的测试。数据量500KK(即N=500 000 000)：

• for循环中malloc一个结构体(假设大小4char)。
• 直接malloc(4*N)。

结果很明显，前者时间远大于后者。后来在两中操作中添加strncpy操作，目的是将申请到的内存全填满。结果还是前者时间远大于后者。
我在想，对于大量数据的操作中是否如我所测的多次malloc的效率远低于一次malloc。并且，我是否应该选择另外的方式来分配内存，比如自建内存池封装malloc，这样做的话会有一些什么问题，或者说大家是否有更好的方法。（我还没有仔细研读malloc函数的实现） @daimajia @Dodolong