Поддерживайте отсортированный массив, который может поддерживать отдельная итеративная функция.

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 функций).

Моя идея сократить время выполнения - создать массив 2d (в отдельной функции), где каждый столбец является отсортированным столбцом функций. Затем, пока я сохраняю вектор номеров строк примеров обучения в Left [] и Right [] для каждого рекурсивного вызова, я могу просто вызвать эту отдельную функцию, захватить строки, которые я хочу, в предварительно отсортированном вектор-функции, и сэкономить затраты на 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; 
       } 
     } 
} 

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

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

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: Я не могу включить - в URL-адрес StackOverflow. Таким образом, ссылки на Red-black tree немного неактивны и не могут быть нажаты. Если кто-то может отредактировать мой пост, чтобы исправить это, тогда я был бы признателен.