c - 维护一个单独的迭代函数可以继续访问的排序数组

Question

我正在用 C 语言编写决策树代码。现在它给了我正确的结果(0% 训练误差，低测试误差)，但需要很长时间才能运行。

问题在于我运行 qsort 的频率。我的基本算法是这样的:

    for every feature
        sort that feature column using qsort
        remove duplicate feature values in that column
        for every unique feature value
          split
          determine entropy given that split
    save the best feature to split + split value
    for every training_example
      if training_example's value for best feature < best split value, store in Left[]
      else store in Right[]
    recursively call this function, using only the Left[] training examples
    recursively call this function, using only the Right[] training examples

因为最后两行是迭代调用，并且树可以扩展到数十个分支，所以对 qsort 的调用数量很大(特别是对于我的数据集具有超过 1000 个特征)。

我减少运行时间的想法是创建一个二维数组(在单独的函数中)，其中每一列都是排序的特征列。然后，只要我在每次递归调用的 Left[] 和 Right[] 中维护训练示例的行号 vector ，我就可以调用这个单独的函数，在预排序的特征向量中获取我想要的行，并节省每次都要进行qsort的成本。

我对 C 相当陌生，所以我不知道如何编写这个代码。在 MatLab 中，我可以拥有一个任何函数都可以更改或访问的全局数组，在 C 中寻找类似的东西。

Answer 1

C 中的全局数组是完全可能的。实际上有两种方法可以做到这一点。在第一种情况下，应用程序的数组尺寸是固定的:

#define NROWS   100
#define NCOLS   100
int array[NROWS][NCOLS];

int main(void)
{
        int     i, j;

        for (i = 0; i < NROWS; i++)
        for (j = 0; j < NCOLS; j++)
        {
                array[i][j] = i+j;
        }
        return 0;
}

在第二个示例中，尺寸可能取决于输入的值。

#include <stdlib.h>
int **array;

int main(void)
{
        int     nrows = 100;
        int     ncols = 100;
        int     i, j;

        array = malloc(nrows*sizeof(*array));
        for (i = 0; i < nrows; i++)
        {
                array[i] = malloc(ncols*sizeof(*(array[i])));
                for (j = 0; j < ncols; j++)
                {
                        array[i][j] = i+j;
                }
        }
}

尽管两个示例中对数组的访问看起来非常相似，但数组的实现却截然不同。在第一个示例中，数组位于一 block 内存中，访问行的步幅是整行。在第二个示例中，每个行访问都是指向一行的指针，该行是一 block 内存。然而，各个行可以位于存储器的不同区域中。在第二个示例中，行也可能具有不同的长度。在这种情况下，您还需要将每行的长度存储在某处。

我不完全理解你想要实现的目标，因为我不熟悉决策树、特征的术语和标准训练方法套。但您可能还想查看其他数据结构来维护排序数据:

1. http://en.wikipedia.org/wiki/Red –black_tree 维护一个或多或少平衡和排序的树。
2. AVL tree稍微慢一点但更平衡和排序的树。
3. Trie元素列表上的排序树。
4. Hash function轻松地将复杂元素映射到可用于对元素进行排序的整数值。适合查找精确的元素，但元素本身没有真正的顺序。

P.S1:来自 Matlab 的您可能需要考虑迁移到 C 之外的其他语言。 C++有标准库来支持上述数据结构。 Java、Python 都会浮现在你的脑海中，如果你够大胆的话，甚至可以想到 Haskell。 C 中的指针处理可能非常乏味且容易出错。

P.S2:我无法在 StackOverflow 上的 URL 中包含 -。所以红黑树链接有点偏，无法点击。如果有人可以编辑我的帖子来修复它，那么我将不胜感激。